一起学加密(第10期)——公钥加密算法RSA的安全性

RSA的安全性

通过分析RSA的加密算法公钥私钥的生成过程，不难看到攻击者如果要破解获取到私钥，必须通过N进行因数分解得到p和q

N = p x q

而因数分解这个事，除了暴力穷举，没有别的办法，但如果N选的足够大，暴力破解是不可能完成的任务（除非量子计算机问世）。

维基百科说“2020年为止，世界上还没有任何可靠的攻击RSA算法的方式”，实际上到目前2022年，应该也没有什么可靠的算法。

N多大才算安全？

目前大多数的SSH客户端sshkey都会默认用RSA生成3072位key，因为这是最低安全标准，业界的共识一般是推荐使用4096位。

那这里的RSA key的位数是什么意思呢？这个位数实际上指的是N的二进制表示的位数。比如对于我们的前面的演示：

p=421
q=5441
N=p*q=2290661

N转换成二进制是1000101111001111100101，也就是22位，所以最后生成的key就是22位的。

以下内容来自维基百科：

针对RSA最流行的攻击一般是基于大数因数分解。1999年，RSA-155 (512 bits)被成功分解，花了五个月时间（约8000 MIPS年）和224 CPU hours在一台有3.2G中央内存的Cray C916计算机上完成。

RSA-155表示如下：

39505874583265144526419767800614481996020776460304936454139376051579355626529450683609
727842468219535093544305870490251995655335710209799226484977949442955603
=3388495837466721394368393204672181522815830368604993048084925840555281177×
11658823406671259903148376558383270818131012258146392600439520994131344334162924536139

2009年12月12日，编号为RSA-768（768 bits, 232 digits）数也被成功分解。这一事件威胁了现通行的1024-bit密钥的安全性，普遍认为用户应尽快升级到2048-bit或以上。

RSA-768表示如下：

123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413
=3347807169895689878604416984821269081770479498371376856891
2431388982883793878002287614711652531743087737814467999489×
3674604366679959042824463379962795263227915816434308764267
6032283815739666511279233373417143396810270092798736308917

Python大因数分解

暴力的方法进行大因数分解并不难，也有很多现成的Python库可以用，比如sympy就可以。

以上面我们的N为例

p=421
q=5441
N=p*q=2290661

通过N去破解p和q非常简单，这个N只有22位，一秒就可以出结果。

from sympy import factorint
a = factorint(2290661)
print(a)

得到的结果a是

{421:1,5441:1}

也就是421和5441.

最后

当然，针对RSA的攻击方法还有很多，这里就不展开了，感兴趣的同学可以自行查找相关资料。