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