RSA数学运算的魅力

一、RSA缘由

Rivest哥、Shamir哥和Adleman哥发明了RSA。Rivest哥也发明了家喻户晓 RC4对称算法。RSA，一种公钥算法，通信双方使用不对称密钥，解决了如何在不安全的信道传输加密后的信息。

对称密钥是基于比特的移位或者异或XOR。非对称密钥是基于数字的一些特性。对称密钥的趋势是在可接收的计算延迟上增加计算的复杂度。而非对称密钥是利用计算下不擅长做一些数学特性的运算，而不至于陷入跟对称密钥一样的困境。

二、RSA的数学本质

RSA的大数原理：他是基于数字的一个事实，任何一个消息m，只要对m的位数的一些数字运算生成大数，再对这个大数取模（n>m）。就可以得到m本身。一句话概括RSA。就好比一个人在跑道里面跑了n圈。总可以回到起跑起点。用数学公式表示就是（m^e）d%n=m。 RSA协议的精髓就是去找寻这个e，d和n。其中数字d称为私钥。E和n称为公钥。

三、为啥是安全的

RSA安全性是得益于一个数学原理：即使得到了公钥e和n。但是也很难计算出d。要达到一定的破解计算强度，必须要求数字的位数>512（或者1024，2048， 512相当于人脑理解的10154）。

现代计算机基本是32或者64位架构。计算2048位的数字，并且这些2048位记过中间计算，取模之前，可能是百万级的数字，这对内存容量的要求和计算的复杂度。都是有要求。所以RSA在工程计算前需要一些运算技巧。

四、实践

RSA实现本质是对大数加减乘除的实现：相关的代码见：

https://github.com/lumanyu/rsa