紧急需要 会编者感谢！！！

RSA算法是由Rivest、Shamir与Adleman三人于1978年合作开发的，并以他们的名字命名的公开密钥算法。其加密密钥是公开的，而解密密钥是保密的。它是基于一个非常简单的数论思想：“将两个素数乘起来是很容易的，但是分解该乘积是非常困难的”。

RSA算法的特别为利用素数（也就是质数）的因式不可分解性，选用很大的素数（一般为几百位到几千位），为了使政府部门与军事部门的数据保密，大多采用几千位以上的素数作为加密的密钥。RSA算法的要点与难点有二：①算法主要为求模取余运算，这给此算法的应用增添了实际的应用难度，因为给一个几千位的素数进行求模取余运算是很难的；②判断一个数是否为素数也是数学界几百年来一直讨论与研究证明的难题，虽然费马提出了著名的“费马猜想”，但一直却未得到过完全的证明，基于此要找一个几千位的素数更是难上加难。

（1）RSA算法原理

RSA算法是基于数论中的同余理论。如果用m代表明文，c代表密文，E(m)代表加密运算，D（c）代表解密运算，x=y(mode z)表示x和y模z同余，则加密和解密算法简单表示如下：

加密算法 c=E(m)=me(mod n)

解密算法 m=D(c)=cd(mod n)

其中n和密钥e是公开的，而密钥d是保密的。

下面讨论密钥的求取：

①选取两个随机大素数p和q（保密）；

②设n=p×q；

③欧拉函数φ（n）=（p-1）（q-1）（保密）；

④选取与φ（n）互素的正整数e，即满足gcd(φ(n),e)=1和0<e<φ(n)；

⑤计算d(保密)，使满足e×d=1（mod φ(n)），即d和e相对于模φ(n)互为逆元素。

由RSA算法原理可知，RSA算法的核心是求模取余运算，其安全性是建立在大合数因子分解困难的基础之上的。

（2）模运算的实现

RSA算法的核心操作也是最耗时的操作是模运算，所以开发一种快速指数和取模运算是解决运算速度的关键。通常的模运算都是利用加减法来实现的，因为加减法指