RSA加密算法

RSA加密算法由1977年Ron Rivest、Adi Shamir和Leonard Adlemen一起提出的。三人均是在MIT工作的。RSA即为三人姓氏简拼。RSA作为非对称加密算法，需要用私钥对明文进行加密，然后用公钥对明文进行解密，这种分对称的方法保证了加密的安全性。

---

一、RSA算法原理

1. 公钥与私钥的产生

• 模运算

模运算即求余运算。“模”是“Mod”的音译。和模运算紧密相关的一个概念是“同余”。数学上，当两个整数除以同一个正整数，若得相同余数，则二整数同余。
　　两个整数a，b，若它们除以正整数m所得的余数相等，则称a，b对于模m同余，记作: a ≡ b (mod m)；读作：a同余于b模m，或者，a与b关于模m同余。例如：26 ≡ 14 (mod 12)。

假设Alice想要通过一个不可靠的媒体接收Bob的一条私人信息。她可以用一下方式来产生一条公钥和私钥：

1. 随意选择两个大的质数p和q，计算N=pq；
2. 根据欧拉函数，求得 r = (p-1)(q-1)
3. 选择一个小于r的整数e，求得e关于r的模反元素，命名为d
4. 将p和q的记录销毁
   (N,e)是公钥，(N,d)是私钥。Alice将其公钥(N,e)发送给Bob，将私钥(N,d)藏起来

2. 加解密消息

假设Bob想给Alice送一个消息m，他知道Alice产生的N和e。他使用起先与Alice约好的格式将m转换为一个小于N的整数n，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为n。用下面这个公式他可以将n加密为c：

　　n^e ≡ c (mod N)

计算c并不复杂。Bob算出c后就可以将它传递给Alice。
Alice得到Bob的消息c后就可以利用她的密钥d来解码。她可以用以下这个公式来将c转换为n：

　　c^d ≡ n (mod N)

得到n后，她可以将原来的信息m重新复原

3. 消息签名

RSA签名：签名就是在这份资料后面增加一段强而有力的证明，以此证明这段信息的发布者和这段信息的有效性完整性。RSA签名常用的就是将这份信息进行hash，得到一个hash值，再将hash值加密作为签名，后缀在信息的末尾。接收方接到传输的资料后，使用私钥解密这段加密过的hash，得到hash值，然后对信息原文进行hash，对比两次hash是否一致（验签）。签名的过程是不可逆的，因为hash是不可逆的，毕竟那么大的文件被hash成一段字符串还能还原的话那就碉堡了。

消息签名主要用来身份验证，相比于传统的加密，它对于信息不进行加密而是对信息hash后的摘要进行加密。前者使用加密来保证内容无需泄露，后者使用加密用来进行身份验证