RSA加密算法

RSA加密算法
该算法于1977年由美国麻省理工学院MIT(Massachusetts Institute of Technology)的Ronal Rivest，Adi Shamir和Len Adleman三位年轻教授提出，并以三人的姓氏Rivest，Shamir和Adlernan命名为RSA算法。该算法利用了数论领域的一个事实，那就是虽然把两个大质数相乘生成一个合数是件十分容易的事情，但要把一个合数分解为两个质数却十分困难。合数分解问题目前仍然是数学领域尚未解决的一大难题，至今没有任何高效的分解方法。与Diffie-Hellman算法相比，RSA算法具有明显的优越性，因为它无须收发双方同时参与加密过程，且非常适合于电子函件系统的加密。

RSA算法可以表述如下：

(1) 密钥配制。假设m是想要传送的报文，现任选两个很大的质数p与q，使得：

                                 (12-1)；

选择正整数e，使得e与(p－1)(q－1)互质；这里(p－1)(q－1)表示二者相乘。再利用辗转相除法，求得d，使得：

                          (12-2)；

其中x mod y是整数求余运算，其结果是x整除以y后剩余的余数，如5 mod 3 = 2。

这样得：

(e，n)，是用于加密的公共密钥，可以公开出去；以及

(d，n)，是用于解密的专用钥匙，必须保密。

(2) 加密过程。使用(e，n)对明文m进行加密，算法为：

                               (12-3)；

这里的c即是m加密后的密文。

(3) 解密过程。使用(d，n)对密文c进行解密，算法为：

                              (12-4)；