RSA超级难!
RSA初探
加密过程
两个质数 P 和 Q ,越大越难以破解
n 的欧拉函数 ,记为 m
1
φ(n) = φ(P * Q)= φ(P - 1)φ(Q - 1) = (P - 1)(Q - 1)
随机选择整数 e ,条件为
1 < e < m
,且 e 和 m 互质找一个整数 d ,使
( e * d ) % m = 1
等价于
e * d - 1 = y * m
( y 为整数)找到 d ,实质就是求解
e * x - m * y =1
求出整数解 ,公钥就是
(n,e)
,私钥就是(n,d)
对密文加密过程
假设发送一个中文“中” 以 utf-8 方式编码为 [e4 b8 ad],转为 10 进制为 [228,184,173]。要想使用公钥(n,e) = (4757 , 101)加密,要求被加密的数字必须小于 n,被加密的数字必须是整数,字符串可以取 ascii 值或unicode值,因此将“中”字折为三个字节 [228,184,173],分别对三个字节加密。
假设 a 为明文,b 为密文,则按下列公式计算出 b
1 | a^e % n = b |
计算 [228,184,173]的密文:
228^101 % 4757 = 4296
184^101 % 4757 = 2458
173^101 % 4757 = 3263
即 [228,184,173]加密后得到密文 [4296,2458,3263] ,如果没有私钥 d ,神仙也无法从 [4296,2458,3263]中恢复 [228,184,173]
解密过程
乙收到密文 [4296,2458,3263],并用自己的私钥(n,d) = (4757 ,1601) 解密。解密公式如下:
假设 a 为明文,b 为密文,则按下列公式计算出 a
1 | a^d % n = b |
密文 [4296,2458,3263]的明文如下:
4296^1601% 4757 = 228
2458^1601% 4757 = 184
3263^1601% 4757 = 173
即密文 [4296,2458,3263] 解密后得到 [228,184,173]
将[228,184,173] 再按 utf-8 解码为汉字 “中”,至此解密完毕。
假设破解过程
根据密钥生成过程
需要知道私钥即为知道d
需要知道P和Q,他们的来源是n的因数分解,当对于大整数的因数分解,是很困难的,除了暴力破解
目前已破解最大整数
1 | 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413 |
所以可破解最大密钥为768位,实际应用中 RSA 的密钥长度为 1024 位,重要场合 2048 位,未来半个世纪不可能破解。
参考:一文搞懂 RSA 算法