有人找我解释一下RSA算法。今天我就用我学到的知识来解释一下。首先我们了解RSARSA是一种非对称加密算法。它是由罗纳德·里维斯特（RonaldRivest）于1977年开发的）、阿迪·沙米尔（AdiShamir）和伦纳德·阿德尔曼（LeonardAdleman），因此非对称加密算法RSA算法就是以这三个姓氏的首字母命名的。在理解非对称加密的时候，我们需要理解什么是对称加密。说说徐克导演的电影《智取威虎山》。土匪：天王盖地虎！，有基础！土匪：你见过奶奶吗？杨子荣：他家没有瓦片，不不不！通过他们的对话，我们知道土匪是在试探杨子荣的身份。土匪说天王造虎，不得不说宝塔镇河妖！也就是说，双方都知道这段话是什么意思。翻译成程序员的话，双方都有加密密钥。因此，对称加密也可以说是秘密交易者的密码。但是，对称加密有一个很大的问题，密钥容易泄露。知道了土匪的暗号，杨子荣很容易取得了他们的信任。对于RSA加密，我们需要预习一下返回给数学老师的知识。欧拉函数在数论中，有正整数n，小于n且与n互质的正整数的个数称为n的欧拉函数。记住φ(n)。例如：φ(7)7对应于7、1、2、3、4、5、6互质的小于7的共6个数，所以φ(7)=6；φ(8)8对应有1、3、5、7个小于8的数与8互质，所以φ(8)=4；φ(9)9对应的1与9互质。2、4、5、6、7、8共7，故φ(9)=7。通式（P为数N的质因数）φ(10)=10×(1-1/2)×(1-1/5)=4；φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8；φ(49)=49×(1-1/7)=42。如果mn是互质数：φ(n*m)=φ(n)*φ(m)，如果n是质数则φ(n)=n-1。分解素因子评估：φ(12)=φ(4*3)=φ(2^2*3^1)=(2^2-2^1)*(3^1-3^0)=4。欧拉定理如果两个正整数m和n互质，则m的φ(n)次方在取n的余量时等于1。m^φ(n)%n≡1。费马小定理有素数p，且整数a不是p的倍数，则有a^(p-1)%p≡1。费马小定理是欧拉定理的特例。因为φ(p)=p-1（任何数与质数互质）。模元如果两个正整数e和x互质，则必定存在一个整数d使得ed-1能被x整除，则称d为e对x的模元。e*d%x≡1，则e*d≡k*x+1。由上述定理得到以下公式：m^φ(n)%n≡1m^(k*φ(n))%n≡1两端乘以mm^(k*φ(n)+1)%n≡me*d≡k*x+1m^e*d%n≡m替换第3步k*φ(n)+1和m^e*d%n≡m就是我们需要的对称加密的公式.m为明文，e和d分别对应公钥和私钥。DiffieKalman密钥交换对公式拆分：m^e%n=c加密c^d%n=m解密其中c为e加密的密文，然后d可以解密明文m。因此：公钥：e,n秘钥：d,n明文：m密文：cRSA加密过程取两个质数p1，p2；确定n的值，n=p1*p2，n的值一般很大，长度一般为1024个二进制位；确定φ(n)，φ(n)=(p1-1)*(p2-1)；确定e值，1确定d值，e*d%φ(n)=1；加密c=m^e%n;解密m=c^d%n。实际验证：p1=3，p2=7；n=p1*p2=3*7=21；φ(n)=(p1-1)*(p2-1)=2*6=12；1e*d%φ(n)=5*d%12=1，得d=17；设置明文m=3，则c=m^e%n=3^5%21=12；解密密文m=c^d%n=12^17%21=3。通过上面的解释，我们知道在RSA加密中使用的六个参数p1p2nφ(n)ed中，使用了其中两个公钥（n和e），剩下的四个数字是不公开的。其中最关键的是d，因为n和d组成了私钥，d一旦泄露，就等于私钥泄露了。那么，在知道n和e的情况下是否可以推导出d呢？e*d%φ(n)=1(只有知道e和φ(n)才能计算出d)φ(n)=(p1-1)*(p2-1)(phi(n)可以是只有知道p1和p2才能计算。）n=p1*p2（p和q只有分解n才能计算出来。）结论：如果n可以进行因式分解，就可以计算出d，也就是说私钥有被破解了。然而，大整数的因式分解是一件非常困难的事情。目前除了暴力破解外，还没有找到其他有效的方法。维基百科写道：“对一个非常大的整数进行因式分解的难度决定了RSA算法的可靠性。换句话说，对一个非常大的整数进行因式分解越困难，RSA算法就越可靠。如果有人找到一个快速的因式分解算法，那么RSA的可靠性会大大降低。但是找到这样一种算法的可能性很小。今天只能暴力破解RSA短密钥。截至2008年，世界上还没有可靠的密钥。方式攻击RSA算法，只要密钥长度足够长，用RSA加密的信息实际上是无法被破译的。看到这里可能你不信，我可以写个程序试试看。比如21，你可能很快把它分解成3×7，但是这个数更大，比如这个质数2^57,885,161-1，它有1700万多位数。如果让传统计算机去验证是不是素数，估计就可以永远跑下去了。
