RSA 背后的算法

这篇文章我本来是想写了放到极客时间上 我写的专栏

里面的，但是专栏的内容是需要仔细斟酌的。这篇文章我认为还是偏难，不适合整个专栏的内容和难度的定位，因此我把它稍微加工了一下，放到我这个博客上。

在专栏中的第 36 讲的选修课堂（该讲预计在 12 月初发布）中，我介绍了 Diffie–Hellman 密钥交换这一算法，它可以说是质数在加密技术中的一个应用，并且是通过其中的 “模幂运算” 来实现的。今天，我来介绍质数的另一个应用，RSA 背后的算法。我在互联网上搜索了一下，我发现基本没有能把它背后的实现原理用浅显的中文叙述讲清楚的，但我还是想试一试，看看能不能尽可能避开那些难懂的术语，用尽量形象和易于理解的方式，把 RSA 背后的原理讲清楚。

在专栏的 第 02 讲 ，我们讲了非对称性加密，比如通过公钥加密的数据，能且只能通过私钥来解密，可是这是怎样实现的呢？这就要讲 RSA 加密技术的原理了。现在，假定我们要通过 RSA 来进行安全的通信，于是你要使用我发布的公钥来对数据加密，加密以后发给我，我拿到加密数据以后使用对应的私钥解密，而攻击者截获了这个加密数据并尝试破解。

模幂等式

我们在介绍 Diffie–Hellman 密钥交换的时候讲到了这个模幂等式：

gᵃ mod p = A

从难度上看它具有如下三个特性：

• 特性 ①：已知 g、a 和 p，求 A 容易；
• 特性 ②：已知 g、p 和 A，求 a 困难；
• 特性 ③：已知 a、p 和 A，求 g 也困难。

再看看上面我们介绍的模幂公式关于离散对数求解的三种难易程度不同的情况吧， 我们在 Diffie–Hellman 密钥交换中应用了特性 ① 和特性 ②，而在 RSA 中，我们还要应用特性 ① 和特性 ③ 。

观察特性 ①，我们可以利用它来设计 RSA 加密，即让 g 代表需要被加密的实际值，而 a、p 可以公开。于是你就求出它的 a 次幂，并取 p 模，得到了 “密文” A，把它发给我。这个过程中，如果 A 被截获，那么根据特性 ③，已知 A、p 和 a，攻击者是很难求解出 g 来的。我们已经说过了，这符合 “ 正向计算简单，逆向求解困难 ” 这一特性，这一点很适合用来加密。

但是和前面的 Diffie–Hellman 密钥交换不同的是，我们并不是要让所有人都求解这个 g 困难，因为密文是发给我的，我得很容易求解这个 g 才行啊，要不然就像是用一把没人拥有钥匙的锁来加密，这把锁就失去意义了。

我们再来观察一下这个模幂等式：

gᵃ mod p = A

藉由 Diffie–Hellman 密钥交换带来的灵感，如果我们构造这样一个和上式形式一致，但变量具有一定对称性的等式：

Aᵈ mod p = g

这其实是什么？这不就是将加密的数据 A，经过模幂运算以后，得到了原始的未加密数据 g 了吗？也就是说， 既然 a 是公钥，那么这里的 d 就是所谓的 “私钥” 啊 。

好，我们把后面这个公式的 A 通过前面那个公式来带入，得到：(gᵃ mod p)ᵈ mod p = g，根据我们前面介绍模幂运算时提到的联等公式，它就可以化简为：

gᵃᵈ mod p = g

因此这个式子，就表示出了公钥、私钥，以及被加密数之间的关系。

接下去，我们来思考怎样生成这个私钥 d。

欧拉函数

为了继续进行后面的分析，我们需要一点知识储备，首先是欧拉函数。 欧拉函数 φ(x) 表示，有多少不大于 x 的正整数中，与 x 互质的数目 （即公因数只有 1）。

举例来说，要计算 φ(4)，你看不大于 4 的正整数包括 1、2、3、4，其中：

• 1 和 4 互质；
• 2 不和 4 互质，因为它们有公因数 2；
• 3 和 4 互质；
• 4 不和 4 互质，因为它们有公因数 4。

所以 φ(4) = 2。

欧拉函数 φ(x) 一般很难计算，但是如果 x 是质数，情况就不同了，因为质数和任何比它小的正整数互质，比如 φ(5) = 4，这四个数分别是 1、2、3、4，因此，在 x 是质数的情况下：

φ(x) = x – 1

同时，如果 x 是一个可以因式分解的合数，比如 x = m*n，欧拉函数还具备这样的特性：

φ(m*n) = φ(m) * φ(n) = (m-1) * (n-1)

这个公式我们后面还会用到。

欧拉定理

有了欧拉函数的知识，我们进一步了解欧拉定理。 欧拉定理 指的是，对于正整数且互质的 g 和 x，有如下性质：

gᵠ⁽ᴾ⁾ ≡ 1 (mod p)

其中的三横线不是表示 “恒等”，而是表示 “同余”，上面的意思是，g 的 φ(p) 次幂，除以 p 所得的余数，和 1 除以 p 所得的余数，二者相同。

举例来说，当 g=3，p=5，根据前面学的欧拉函数有 φ(5)=4，那么 gᵠ⁽ᴾ⁾=81，81 除以 5 余 1；1 除以 5 也余 1，同余关系成立。

密钥生成

由于 1ᵏ ≡ 1 (mod p)，我们可以给指数上的欧拉函数赋予正整数系数 k，gᵏᵠ⁽ᴾ⁾ ≡ 1 (mod p)，我们再给两边乘以 g，得到 gᵏᵠ⁽ᴾ⁾⁺¹ ≡ g (mod p)。当 g 小于 p 的时候，g 除以 p 的余数就是 g，因此这个同余式可以写成：

gᵏᵠ⁽ᴾ⁾⁺¹ mod p = g

再联想前面的：

gᵃᵈ mod p = g

你看，这两个式子的形式是一样的，这就意味着，kφ(p)+1 = ad。因此，这个私钥就是：

d = (kφ(p)+1)/a

这意味着什么？这意味着如果能够求得 φ(p) 的值，那么这个私钥就求解出来了。但是，怎样求解 φ(p) 呢？这里，我希望：

• 密钥是我生成的，因此我求解这个 φ(p) 要非常容易，这样我就可以很容易计算出密钥来；
• p 是公开的，攻击者仅仅知道 p，求解 φ(p) 要非常困难才行，那样才能保证加密的安全性。

你看，这是不是又一个需要 “ 正向计算简单，逆向求解困难 ” 特性的问题？

回想一下前面我们学习欧拉函数的时候，我讲到了，如果 m、n 是质数，那么欧拉函数可以这样求得：

φ(m*n) = φ(m) * φ(n) = (m-1) * (n-1)

这正是我需要的！

你想，如果我选取两个非常非常大的质数 m 和 n，选择 p 的时候，就让它等于 m 和 n 的乘积，那么 φ(p) = φ(m*n) = (m-1) * (n-1)，这个正向计算是很简单的，也就是说，因为我知道 m、n，密钥的生成是很容易的一件事情。

可是，攻击者拿不到 m、n，就只能硬生生地尝试去给 p 因式分解才能得到 m、n，而对于一个超大质数的因式分解，这个过程是极其困难的。纵观整个 RSA 的原理，其中涉及到了两个和质数相关的 “正向计算简单，逆向求解困难” 的特性：

• 一个是前面介绍的模幂等式逆向求底数；
• 另一个就是这里介绍的超大质数的因式分解。

这也就是 RSA 安全性的基本原理。

当然，随着科技发展，计算能力越来越强，特别是量子计算的兴起，我们对超大质数的位数要求也越来越高，512 bit 的 RSA 已经被破解，而 1024 bit 也已经摇摇欲坠，现阶段 2048 bit 长度还是安全的，可是未来，谁又知道呢？