RSA 密钥生成的步骤

参考：阮一峰

六、密钥生成的步骤

我们通过一个例子，来理解 RSA 算法。假设爱丽丝要与鲍勃进行加密通信，她该怎么生成公钥和私钥呢？

第一步，随机选择两个不相等的质数 p 和 q。

爱丽丝选择了 61 和 53。（实际应用中，这两个质数越大，就越难破解。）

第二步，计算 p 和 q 的乘积 n。

爱丽丝就把 61 和 53 相乘。

n = 61×53 = 3233

n 的长度就是密钥长度。3233 写成二进制是 110010100001，一共有 12 位，所以这个密钥就是 12 位。实际应用中，RSA 密钥一般是 1024 位，重要场合则为 2048 位。

第三步，计算 n 的欧拉函数 φ(n)。

根据公式：

φ(n) = (p-1)(q-1)

爱丽丝算出 φ(3233)等于 60×52，即 3120。

第四步，随机选择一个整数 e，条件是 1< e < φ(n)，且 e 与 φ(n) 互质。

爱丽丝就在 1 到 3120 之间，随机选择了 17。（实际应用中，常常选择 65537。）

第五步，计算 e 对于 φ(n)的模反元素 d。

所谓"模反元素"就是指有一个整数 d，可以使得 ed 被 φ(n)除的余数为 1。

ed ≡ 1 (mod φ(n))

这个式子等价于

ed - 1 = kφ(n)

于是，找到模反元素 d，实质上就是对下面这个二元一次方程求解。

ex + φ(n)y = 1

已知 e=17, φ(n)=3120，

17x + 3120y = 1

这个方程可以用"扩展欧几里得算法"求解，此处省略具体过程。总之，爱丽丝算出一组整数解为 (x,y)=(2753,-15)，即 d=2753。

至此所有计算完成。

第六步，将 n 和 e 封装成公钥，n 和 d 封装成私钥。

在爱丽丝的例子中，n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。

实际应用中，公钥和私钥的数据都采用 ASN.1 格式表达（实例）。

七、RSA 算法的可靠性

回顾上面的密钥生成步骤，一共出现六个数字：

这六个数字之中，公钥用到了两个（n 和 e），其余四个数字都是不公开的。其中最关键的是 d，因为 n 和 d 组成了私钥，一旦 d 泄漏，就等于私钥泄漏。

那么，有无可能在已知 n 和 e 的情况下，推导出 d？

（1）ed≡1 (mod φ(n))。只有知道 e 和 φ(n)，才能算出 d。　　（2）φ(n)=(p-1)(q-1)。只有知道 p 和 q，才能算出 φ(n)。　　（3）n=pq。只有将 n 因数分解，才能算出 p 和 q。

结论：如果 n 可以被因数分解，d 就可以算出，也就意味着私钥被破解。

可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。维基百科这样写道：

“对极大整数做因数分解的难度决定了 RSA 算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。　　假如有人找到一种快速因数分解的算法，那么 RSA 的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的 RSA 密钥才可能被暴力破解。到 2008 年为止，世界上还没有任何可靠的攻击 RSA 算法的方式。　　只要密钥长度足够长，用 RSA 加密的信息实际上是不能被解破的。”

举例来说，你可以对 3233 进行因数分解（61×53），但是你没法对下面这个整数进行因数分解。

它等于这样两个质数的乘积：

事实上，这大概是人类已经分解的最大整数（232 个十进制位，768 个二进制位）。比它更大的因数分解，还没有被报道过，因此目前被破解的最长 RSA 密钥就是 768 位。

八、加密和解密

有了公钥和密钥，就能进行加密和解密了。

（1）加密要用公钥 (n,e)

假设鲍勃要向爱丽丝发送加密信息 m，他就要用爱丽丝的公钥 (n,e) 对 m 进行加密。这里需要注意，m 必须是整数（字符串可以取 ascii 值或 unicode 值），且 m 必须小于 n。

所谓"加密"，就是算出下式的 c：

me ≡ c (mod n)

爱丽丝的公钥是 (3233, 17)，鲍勃的 m 假设是 65，那么可以算出下面的等式：

6517 ≡ 2790 (mod 3233)

于是，c 等于 2790，鲍勃就把 2790 发给了爱丽丝。

（2）解密要用私钥(n,d)

爱丽丝拿到鲍勃发来的 2790 以后，就用自己的私钥(3233, 2753) 进行解密。可以证明，下面的等式一定成立：

cd ≡ m (mod n)

也就是说，c 的 d 次方除以 n 的余数为 m。现在，c 等于 2790，私钥是(3233, 2753)，那么，爱丽丝算出

27902753 ≡ 65 (mod 3233)

因此，爱丽丝知道了鲍勃加密前的原文就是 65。

至此，“加密–解密"的整个过程全部完成。

我们可以看到，如果不知道 d，就没有办法从 c 求出 m。而前面已经说过，要知道 d 就必须分解 n，这是极难做到的，所以 RSA 算法保证了通信安全。

你可能会问，公钥(n,e) 只能加密小于 n 的整数 m，那么如果要加密大于 n 的整数，该怎么办？有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种"对称性加密算法”（比如 DES），用这种算法的密钥加密信息，再用 RSA 公钥加密 DES 密钥。

九、私钥解密的证明

最后，我们来证明，为什么用私钥解密，一定可以正确地得到 m。也就是证明下面这个式子：

cd ≡ m (mod n)

因为，根据加密规则

ｍ e ≡ c (mod n)

于是，c 可以写成下面的形式：

c = me - kn

将 c 代入要我们要证明的那个解密规则：

(me - kn)d ≡ m (mod n)

它等同于求证

med ≡ m (mod n)

由于

ed ≡ 1 (mod φ(n))

所以

ed = hφ(n)+1

将 ed 代入：

mhφ(n)+1 ≡ m (mod n)

接下来，分成两种情况证明上面这个式子。

（1）m 与 n 互质。

根据欧拉定理，此时

mφ(n) ≡ 1 (mod n)

得到

(mφ(n))h × m ≡ m (mod n)

原式得到证明。

（2）m 与 n 不是互质关系。

此时，由于 n 等于质数 p 和 q 的乘积，所以 m 必然等于 kp 或 kq。

以 m = kp 为例，考虑到这时 k 与 q 必然互质，则根据欧拉定理，下面的式子成立：

(kp)q-1 ≡ 1 (mod q)

进一步得到

[(kp)q-1]h(p-1) × kp ≡ kp (mod q)

即

(kp)ed ≡ kp (mod q)

将它改写成下面的等式

(kp)ed = tq + kp

这时 t 必然能被 p 整除，即 t=t’p

(kp)ed = t’pq + kp

因为 m=kp，n=pq，所以

med ≡ m (mod n)

原式得到证明。

（完）