buuoj上做到一道题,一脸懵逼,看来仅仅知道RSA算法的实现方法还是不行的,所以用这篇文章作为学习RSA的笔记
RSA的实现原理
首先原理是肯定要知道的
– 首先选择两个大质数p
和q
– 计算n=p*q
,以及n
的欧拉函数fn=(p-1)*(q-1)
– 选择一个与fn
互素的公钥e
,一般取质数65537(0x10001)
,(e, n)
即为公钥
– 计算私钥d
,使得d*e%fn=1
,(d, n)
即为私钥
– 加密时,对于明文m
求密文c=m^e%n
– 解密时,对于密文c
求明文m=c^d%n
RSA的可靠性在于对大整数做因子分解是极为困难的,一般p
和q
的取值越大,暴力破解的难度越大
如何求模逆
在计算私钥时,要求计算私钥d
使得d
满足d*e%fn=1
,即为求e
模fn
的逆元
求d*e%fn=1
可以转化为求d*e-k*fn=1
,已知e
和fn
的情况下求d
(和k
)
在python3.8
中原生支持求模逆,pow(e, -1, fn)
即可求出e
在模fn
的情况下的逆元
RSA的攻击方式
因为rsa确实是比较安全的加密算法,所以攻击方式是比较确定的,常见的一般只有那几种
暴力破解
在已知公钥(e, n)
的情况下,如果n
不太大,那么就可以采用这种攻击方法,直接暴力破解质数p
和q
,但是当n
足够大时,这种攻击方法就失效了。
RSA爆破的工具如:CADO-NFS,GGNFS,MSIEVE,YAFU等,还有在线破解的网站如cocalc.com,factordb.com