RSA算法是在1977年由美国的3位教授R.L.Rivest、A.Shamirt和M.Adleman在题为“获得数字签名和公开钥密码系统的一种方法”中提出的，算法的名称取自3位教授的名字。RSA算法是第一个提出的公开密钥算法，是至今为止最为完善的公开密钥算法之一。RSA算法的这3位发明者也因此在2002年获得了计算机领域的最高奖——图灵奖。

RSA算法的安全性基于大数分解的难度，其公钥和私钥是一对大素数的函数。从一个公钥和密文中恢复出明文的难度等价于分解两个大素数的乘积。

下面通过具体的例子说明RSA算法的基本思想。

首先，用户秘密地选择两个大素数，这里为了计算方便，假设这两个素数为p=7，q=17。计算出n=p×q=7×17=119，将n公开。

用户使用欧拉函数计算出n。

Φ(n)=(p-1)×(q-1)=6×16=96。

从1到Φ（n）之间选择一个和Φ（n）互素的数e作为公开的加密密钥（公钥），这里选择5。

计算解密密钥d，使得（d×e）modΦ（n）=1，这里可以得到d为77。

将p=7和q=17丢弃；将n=119和e=5公开，作为公钥；将d=77保密，作为私钥。这样就可以使用公钥对发送的信息进行加密，接收者如果拥有私钥，就可以对信息进行解密了。

例如，要发送的信息为s=19，那么可以通过如下计算得到密文。(www.daowen.com)

c=semod(n)=195mod(119)=66

将密文66发送给接收端，接收者在接收到密文信息后，可以使用私钥恢复出明文。

s=cdmod(n)=6677mod(119)=19

例子中选择的两个素数p和q只是作为示例，并不大，但是可以看到，从p和q计算n的过程非常简单，而从n=119找出；p=7、q=17不太容易。在实际应用中，p和q将是非常大的素数（上百位的十进制数），那样，通过n找出p和q的难度将非常大，甚至接近不可能。所以这种大数分解素数的运算是一种“单向”运算，单向运算的安全性就决定了RSA算法的安全性。

下面可以通过一个小工具RSA-Tool演示上面所说的过程。

如图4-8所示，选择好密钥长度（Keysize）和进制（Number Base），并确定P、Q和公钥E（PublicExponent）的值后，单击按钮，则可算出私钥D的值。

图4-8　RSA-Tool工具

RSA-Tool这个工具的基本功能还包括生成一组RSA密钥对、明文和密文的相互变换、分解一个数等。具体的使用方法可以参考RSA-Tool的帮助文档，这里不再详述。