RSA算法与其背后的数学原理

知识储备
RSA加密过程
RSA加密原理
RSA算法的可靠性
几个定理的证明
References：

我虽然不是计算机专业的，但 RSA 算法这个东西我真的耳朵都听出茧子了。之前好奇查网页链接的 http 和 https 有啥区别，答案是 RSA；好奇查安全要求高的密码难道不怕暴力破解？答案是没事 RSA 不怕；有事没事老遇见公钥、私钥这俩名词不知道啥意思，一查嚯你好啊 RSA 咱俩又见面了。不行，我已经抑制不住我的好奇心了……

但在讨论 RSA 算法之前，我先去回顾了一下密码学的历史。

密码学的漫长历史可以追溯到两千年前的尤利乌斯 · 恺撒时代。当时，凯撒和他的军官们通过密钥为三的加法替换密码进行通信，这便是著名的凯撒密码。从那之后到二十世纪七十年代这两千年来，所有的加密通信其实都和凯撒密码一样基于一个密钥系统，我们称之为对称密钥系统。也就是说，通信双方在加密和解密时使用同一个密钥，或是使用两个可以简单地相互推算的密钥。这样做的前提是在安全通信建立前需要交换密钥（例如：两个罗马百夫长在澡堂碰头然后约定密码什么的）。

虽然现代社会仍然广泛使用对称加密，不过这种加密模式也是有缺点的。比如说：

进行安全通信前需要以安全方式进行密钥交换。这一步骤在某种情况下是可行的，但在某些情况下会非常困难，甚至无法实现。
密钥分发困难，例如一个网络中有 n 个用户，他们之间彼此都可能进行秘密通信，这时网络中将需要 n(n-1)/2 个密钥（其中，每个用户都需要保存 n-1 个密钥）。这就表明如果有一百万人相互之间要通信的话，每个人几乎要有一百万把不同的密钥，总共得要一万亿把密钥！

所以我们有什么办法可以解决这些问题呢？1976年，两位美国计算机学家 Whitfield Diffie 和 Martin Hellman 论证了一个解决这个问题的算法，现在称为 Diffie-Hellman 密钥交换，这是一个完全不同的，甚至可以说极为优雅的安全通信算法，我们可以称之为非对称加密，或者是公开密钥加密。

为了说明非对称加密的思想，我举一个例子。（现在有请 Alice、Bob、Eve 三大将）假如 Alice 要想向 Bob 通讯，那么 Bob 需要生成一个公钥和一个私钥，我们分别用 $K_{public}$ 和 $K_{private}$ 来表示这两把密钥。注意，这里跟对称密钥体系不同的是，接收方 Bob 担起了加密的全部责任。接下来 Bob 会向全世界所有人公开自己的公钥，但是藏好自己的私钥。Alice 用 Bob 公开的那个公钥和一个周知的、标准化的加密算法加密报文 a 得到密文 x，也就是计算 $K_{public}(a)$ 得到 x。Bob 收到密文后用私钥和一个同样周知的、标准化的解密算法解密密文 x 得到明文 a，也就是计算 $K_{private} (x)$ 得到 a，整个加密通信过程就完成了。对这个过程你也许并没有什么特别的感觉，但实际上这是一个非常奇妙的结果，因为加密和解密时使用的密钥并不一样，但 Bob 计算 $K_{private} (K_{public}(a))$ 却还原出了明文 a！这便是非对称加密不同于对称加密的地方，它的奇妙之处也正在于此。

我们还需要注意另外两个问题，首先，从计算 $K_{private} (K_{public}(a))$ 可以还原出 a 来看，表面上完全无关的公钥和私钥间其实仍隐藏着某种数学上的相关性。但是别忘了，公钥会向所有人公开，这就意味着绝不能让人们可以通过公钥来推出私钥，换句话说，公钥和私钥之间的相关性必须被设法“封装”起来，这对于实现非对称加密是一个挑战，而在后文你会看到 RSA 算法精巧的实现了这一要求。另一个问题是，既然所有人都可以获取到 Bob 的公钥，那么岂不是所有人都可以冒充 Alice 向 Bob 发信？这的确是个问题，不过我们同样有解决办法，简单的说就是利用数字签名把发送方和密文绑定到一起，有兴趣的人可以去了解一下数字签名是个什么东西。

回到前文所讲，Diffie-Hellman 密钥交换的出现启发了其他科学家。人们意识到加密和解密其实可以使用不同的规则，只要这两种规则之间存在某种关系就行了。于是在 1977年，有三位数学家 Rivest、Shamir 和 Adleman 基于非对称加密的思想设计了一种算法。这种算法用他们三人名字的首字母命名，叫做 RSA 算法。显然，RSA 算法既实现了公钥加密的思想，同时也完美解决了我们前面思考的那两个问题。从那时直到现在，RSA算法便一直是应用最为广泛的非对称加密算法。可以说，地球上只要有网络的地方，那就一定会有 RSA！

但是要想真正理解 RSA 算法“优雅”的思想，我们还需要补充一些初等数论知识。

知识储备

注意：为了不影响阅读的流畅性，我把其中欧拉函数，欧拉定理和费马小定理的证明放在了文末，有兴趣的话可以看一下。

一、同余
对于两个整数 a, b，若它们除以正整数 m 所得的余数相等，则称 a，b 对于模 m 同余。
记作：$a \equiv b \pmod n$
读作：a 同余于 b 模 m，或读作 a 与 b 关于模 m 同余。
例如：$26 \equiv 14 \pmod {12}$

我在学习同余时，看过台湾一个很棒的老师 PengTitus 的视频，在视频里我了解到了一个很重要的的观念：

同余最重要的精神，其实是它把自然数加以分类。比如一个自然数除以 7，便是把这个自然数分成整除、余 1、余 2……余 6 这七类，然后我们把每一类里的所有自然数，称为同余。

这里我们需要了解几个关于同余的性质，它们对后面一些定理的证明很有帮助：

整除性：
当 $n \in N$ 且 $a,\enspace b \in Z$
则$a \equiv b \pmod n$ $\iff n \mid a-b$ $\iff a=kn+b$
反身性：
$a \equiv a \pmod n$
对称性：
$a \equiv b \pmod n \iff b \equiv a \pmod n$
传递性：
若 $a \equiv b \pmod n$ 且 $b \equiv c \pmod n$
则 $a \equiv c \pmod n$
加性：
若 $a \equiv b \pmod n$ 且 $c \equiv d \pmod n$
则 $a+c \equiv b+d \pmod n$
乘性：
若 $a \equiv b \pmod n$ 且 $c \equiv d \pmod n$
则 $ac \equiv bd \pmod n$
或者写成 $[(a \mod n) \cdot (c \mod n)] \mod n$
$=(a \cdot c) \mod n$

二、欧拉函数
在数论中，对正整数 n，欧拉函数 $φ(n)$ 是小于或等于 n 的正整数中与 n 互质的数的数目。

文末的证明里我会给出欧拉函数的一般形式，这里先给出当 n 可以分解成两个质因数 p 和 q 相乘时，$φ(n)$ 的简单形式，即：$$φ(n)=(p-1)(q-1)$$记下来，我们一会就会用到这个式子。

三、模逆元
模逆元也称为模倒数，模逆元或者模反元素。一个整数 a 对同余 n 之模逆元是指满足以下公式的整数 b：$$a^{-1} \equiv b \pmod n$$也可以写成以下的式子：$$ab \equiv 1 \pmod n$$同样记住这个式子，一会要用。

四、欧拉定理（数论）
在介绍欧拉定理前我们要知道，欧拉定理是 RSA 加密算法的核心所在。RSA 算法之所以可以用私钥解密密文就是因为欧拉定理的存在。先不用思考为什么，在这里只需记住欧拉定理的形式与概念即可。

在数论中，欧拉定理是一个关于同余的性质。欧拉定理表明，若 n, a 为正整数，且 $gcd(a,n)=1$（即 a, n 互素，又即 a, n 最大公约数等于 1），则有：$$a^{φ(n)} \equiv 1 \pmod n$$即 $a^{φ(n)}$ 与 1 在模 n 下同余，$φ(n) $为欧拉函数，记住上面这个形式。

说到欧拉定理，就不得不提一下号称“业余数学王子”的费马大神推导出的费马小定理。欧拉定理其实就是同为大神的欧拉把费马小定理推广而来的。费马小定理概念及形式如下：

假设正整数 a 与质数 p 互质，又已知 φ(p) 等于 p-1，则有：$$a^{p-1} \equiv 1 \pmod p$$必要的知识储备就是这些。

RSA加密过程

我们首先把加密过程过一遍，在这里先不用管每一步代表是什么意思，也别去想背后的原理，仅仅先从全局上串一遍。

寻找两个非常大的指数，设为 p 和 q。
计算 $n=p \cdot q$。
计算 $φ(n)=(p-1)(q-1)$。
选取一个小于 $φ$ 的且与 $φ(n)$ 互质的数 e，我们把 $(n,e)$ 作为加密用的公钥。
选取一个数 d，使 $ed \equiv 1 \pmod φ$ 成立，我们把 $(n,d)$ 作为解密用的私钥。
假如 Alice 想给 Bob 发一份报文，该报文明文为 m，密文为 c。
加密过程：$m^e \equiv c \pmod n$。
解密过程：$c^d \equiv m \pmod n$。

到这里整个RSA加密解密过程就走完了，其实一般学习 RSA 时应该了解这上面八条应该就可以了，但现在这么一个设计精巧还又分外可靠的密钥系统摆在我面前，我就突然很想扒光它的衣服看看里面究竟是什么原理（意思就是我现在闲的蛋疼）

RSA加密原理

首先，在第一步我们选取了两个非常大的素数，并在第二步计算这两个素数的乘积 n。选择这两个大素数并且相乘到底有什么意义呢？我觉得应该先提前说一下 RSA 算法之所以很难被破解的原因：截至目前为止，大整数的因式分解对我们人类来说都是一个非常非常困难的事请。也就是说让 p 和 q 相乘算出 n 十分简单，但要想从 n 算出 p 和 q 却极端困难。你可能会说 3 乘 7 算出 21 后我很快就能反推出 21 等于 3 乘 7 啊？那好，你试试给我反推一下这个数字：

1230186684530117755130494958
3849627207728535695953347921
9732245215172640050726365751
8745202199786469389956474942
7740638459251925573263034537
3154826850791702612214291346
1670429214311602221240479274
7377940806653514195974598569
02143413

这是一个 768 个二进制位、232 个十进制位的整数。以目前的数学水平，我们还没有一个行之有效的算法来分解像这样大的整数。不过对于上面写的这个数，我们人类还是勉勉强强分解出来了，也就是下面这两个质因数相乘：

33478071698956898786044169848
21269081770479498371376856891
24313889828837938780022876147
11652531743087737814467999489
×
36746043666799590428244633799
62795263227915816434308764267
60322838157396665112792333734
17143396810270092798736308917

不过我们也就这样了，这就是目前为止人类能分解的最大整数。（也许还有“聪明人”或“聪明组织”分解出来更大的但没有公开）。因为见诸报端的最长被破解 RSA 密钥就是 768 位，所以现在普遍使用 1024 位乃至 2048 位的整数作为 n。至于你想说为什么分解了 n 就相当于破解了密钥，别急，最后我们验证可靠性时会详细说明。

接下来是第三步，计算 $φ(n)=(p-1)(q-1)$，也就是前面提到过的欧拉函数。那么这个欧拉函数存在的意义又是什么呢？为啥不能用别的数去作为 $φ$？仔细看看前面的步骤，当 $ed \equiv 1 \pmod φ$ 成立时，分别负责加密与解密的 $m^e \equiv c \pmod n$ 与 $c^d \equiv m \pmod n$ 才能成立。也就是说，我们需要这个 $φ(n)$ 是由 RSA 背后的数学原理所决定的。

第四步，e 的值一般选择 65537。我没有详细了解过RSA实际应用的细节，所以据我的粗略理解这个数字应该是介于安全性和计算机运算效率之间的一个折衷的选择，如果对更详细一点的解释有兴趣，可以去参考一下这篇回答This Cryptography StackExchange answer（我这种英语菜鸡也想找中文解释啊，找不到啊，况且 google 时发现很多解答竟然都是直接贴上这个链接，想必写的很好）。

在第五步，我们要选取一个数 d，使 $ed \equiv 1 \pmod φ$ 成立，而这个 d 便是我在预备知识里提到的整数 a 对同余 n 的模逆元。计算模逆元的计算方法是扩展欧几里得算法，计算过程我就不加说明了，有兴趣可以自行了解。

然后我们就可以利用上面求得的这些量来完成加密和解密了，这里才是真的有好多东西要说。

首先我们要知道，RSA加密之所以如此可靠其实是因为数学家们给它找了两大法宝，第一个法宝我在解释第一、二步时已经说明了，也就是利用了人们在面对大整数因数分解时的无可奈何。而第二个法宝，则是同余！打个比方，传统的对称加密就好像是函数的映射，通信双方都知道这个映射规则，发送方利用规则把明文映射到密文，接收方利用规则把密文映射到明文。同余则完全不同，它就像个单方向的转盘，只能往前转，不能往后转。就拿RSA的加密过程举个例子，我们在前面的第七步里利用了 $m^e \equiv c \pmod n$ 来加密 m 得到密文 c。如果你是一个第三方，那么纵然你知道 e，c 和 n 又如何，这个转盘你根本转不回去。因为在没有私钥的你眼里，所有和 $m^e$ 属于“同一类”的数都有可能是那个 $m^e$。

那么，为什么用私钥 d 运算 $c^d \equiv m \pmod n$ 便把这个转盘转回来了呢？这就是欧拉定理的功劳了。接下来我们就一起来证明，为什么上面的那个运算可以利用欧拉定理还原出明文 m。我们首先把需要证明的加密和解密的式子改变一下形式：

$\because m^e \equiv c \pmod n$
$c^d \equiv m \pmod n$
$\therefore m^{ed} \equiv m \pmod n$

上面的推导利用了同余的乘性与传递性。接下来

$\because ed \equiv 1 \pmod {φ(n)}$
$\therefore ed = kφ(n) + 1$
$\because m^{ed} \equiv m \pmod n$
$\therefore m^{kφ(n) + 1} \equiv m \pmod n$

走到这里，我们发现要想证明私钥 d 可以还原密文 c，只需证明 $m^{kφ(n) + 1} \equiv m \pmod n$ 即可。这时，就要用到前面提了一万遍的欧拉定理和费马小定理了。证明这个式子，需要分两种情况。

第一种情况：

当 $\gcd(m, n) = 1$ （互质）时（满足了欧拉定理的条件）
由欧拉定理，$m^{φ(n)} \equiv 1 \pmod n$
$\therefore m^{kφ(n) } \equiv 1 \pmod n$
$\therefore m^{kφ(n) + 1} \equiv m \pmod n$

证毕。

第二种情况是当 $\gcd(m, n) > 1$ （最大公约数大于 1 ），这时我们需要用到费马小定理与一个事实（我不知道这叫啥定理）来证明。

一个事实：如果 x，y 是质数，且 $a \equiv b \pmod x$ 和 $a \equiv b \pmod y$ 同时成立，可以得出 $a \equiv b \pmod {xy}$。这个事实的证明如下：$\because a \equiv b \pmod x \implies x|a-b$ 且 $a ≡ b \pmod y \implies y|a-b$ $\enspace \therefore xy|a-b \enspace$ $\therefore a \equiv b \pmod {xy}$

另外，当 $\gcd(m, n) > 1$ 时，显然 n 的质因数 p，q 的其中一个一定可以整除 m，所以不妨假设是 $q | m$，即 $m \equiv 0 \pmod q$，则可得：

$0 \equiv m^{kφ(n)+1} \equiv m \pmod q\enspace …\enspace (1)$

其实，证到这里时只要加一句“对 q 同理”，就把当 $\gcd(m, n) = 1$ 时的第一种情况证明了。

因为 $m < n = pq$ 且我们假设 $q | m$，所以 $\gcd(m,p)=1$。利用费马小定理 $m^{p-1} \equiv 1 \pmod p $，我们可得：

$m^{(p-1)(q-1)} ≡ 1^{q-1} \equiv 1 \pmod p$
$\therefore m^{φ(n)} \equiv 1 \pmod p$
$\therefore m^{kφ(n)} \equiv 1^k \equiv 1 \pmod p$
$\therefore m^{kφ(n)+1} \equiv m \pmod p \enspace ……\enspace (2)$

由 (1)(2) 及上面提到的那个“事实”，我们可以得出 $m^{kφ(n)+1} \equiv m \pmod {pq}$，即$m^{kφ(n)+1} \equiv m \pmod n$

至此证毕。私钥 d 的确可以还原这个“转盘”！

RSA算法的可靠性

我们知道，公钥对所有人公开。我们也知道，得益于同余的“单向转盘”特性，没有私钥则绝无可能破解密文。所以如果我是个邪恶的第三方，我必须要得到私钥。那么我们有无可能在知道公钥（n，e）的情况下的情况下推出私钥 d 呢？

只要你有本事因数分解 n ！

前面提到过，我们是通过扩展欧几里得算法计算出一个满足 $ed \equiv 1 \pmod {φ(n)}$ 的 d 来作为私钥。那么我作为不知道私钥的邪恶第三方，我就需要知道 $φ(n)$ 来计算 d，而 $φ(n)=(p-1)(q-1)$，所以我们需要知道 p 与 q，于是 n 是否可以成功的因数分解便成了破解秘钥的关键。而相信你也知道，这并不是个轻松的活儿…所以只要人类一天没搞定大素数因式分解这个坑，RSA 算法就一天牢不可破。

题外话：虽然我这智商活该被数学从小虐到大，但还是得承认数学真是万物之源！几百年前的那些大数学家们整日整夜的研究这些纯粹到极致的数字游戏，没人觉得这些成果有什么实际意义。谁能想到在几百年后的今天，这些数字游戏却撑起整个计算机安全领域的半边天空。

几个定理的证明

先证费马小定理吧。费马小定理的证明在网上的证明又多长篇大论哈欠连篇。最后，我在《数论妙趣》里找到了一个短到令人感动的证法，用书中原文形容就是：

费马小定理有多种证法，但以同余证法最为简短而精致。

话不多数，证明如下，我自认为写的不可能比书中还好，就把原文注释一下直接贴上来吧：

我们任意选取一个素数 13，当然如果选择其他任意素数 p，证法也几乎同样简单。现在考虑从 1 到 12 的一系列整数 1, 2, 3, 4, … , 11, 12，每一个都比13小。若我们对这些数的每一个都乘上一个与 13 互质的整数，譬如 3，我们即可得出 3, 6, 9, 12, … , 33, 36。对模 13 而言，这些数同余于 3, 6, 9, 12, 2, 5, 8, 11, 1, 4, 7, 10 且其中并无重复。实际上它们就是原来的 1, 2, 3, 4, … , 10, 12 只不过是顺序不同而已。

（注：为什么只是改变了一下顺序？我们来稍微分析一下。这是因为对于任两个相异 ka 而言（在这个例子里 k=1, 2, 3, … , 11, 12，a=3），其差不会是 p 的倍数（所以不会有相同余数），且任一个 ka 亦不为 p 的倍数（所以余数不为 0 ）（另外，其实任两个相异 ka 的差形式上还是 ka，不过后面这个 k 范围小了一点）。既没有相同余数且余数又不为零，所以所有 ka 都不同余于 p（p是模，本例中为 13）这就出现了上文说的重新排列的情况。）

现在让我们把原先一系列数统统相乘起来，把其乘积 1 ⋅ 2 ⋅ 3 ⋅ … ⋅ 11 ⋅ 12 记作 12!。如果类似地把 3, 6, 9, 12, … , 33, 36 相乘，可以提出公因子 $3^{12}$, 并把乘积记作 $3^{12} \cdot 12!$。对模 13 而言，这两个积互相同余，因为 3, 6, 9, 12, … , 33, 36 的系列同余于 1, 2, 3, 4, … 11, 12 系列，尽管不是前后都一一对应。因而（由同余的乘性）$3^{12} \cdot 12! \equiv 12! \pmod {13}$，除以 12! 之后，便得出$3^{12} \equiv 1 \pmod {13}$。如果我们用 p 代替 13，用 a 代替 3，我们即能得到 $a^{p-1} \equiv 1 \pmod p$，也就是费马小定理，至此证明完毕。（书中为了简单起见，应该省略了一些使证明“严谨”的细节，有兴趣请移步费马小定理的证明）

现在轮到欧拉函数了，我们会一步一步地讨论不同情况，并在最后得出欧拉函数的一般形式。

首先，考虑当 $n = 1$ 时，显然可得 $φ(1)=1$ 。因为 1 与任何数（包括自身）都构成互质关系。

然后，如果 n 是素数呢，这样会得出什么结果？由于素数已经是不可分割的元素了，所以素数肯定与比自己小的任何数都互素，那么这时我们就有： $φ(p)=p-1$。

那么，如果 n 是合数又如何呢？这个情况有点复杂，我们先从简单的考虑起，也就是 n 是两个素数 p，q 相乘的积。这时 $φ(n)=φ(pq)$，因为我们已经有 $φ(p)=p-1$ 和 $φ(q)=q-1$。所以与 p • q 互质的数肯定是在分别与 p，q 互质的数里选出来再相乘得到的。这样我们可以得出，所有组合出来的数对个数为 $(p-1)(q-1)$ 个，所以在这个情况下 $φ(pq)=(p-1)(q-1)$ $=φ(p)φ(q)$。（这里说的只是一个简略的思路，更严谨的证明又牵扯到了中国剩余定理和剩余系的概念，有时间我再去研究……如果实在如果感兴趣的话请自行搜索关于欧拉函数是积性函数的证明）。

在继续下一步讨论前我们需要引入算数基本定理的概念，放心这个真的非常简单。

算数基本定理又称正整数的唯一分解定理，即：每个大于 1 的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。例如：$6936 = 2^3 + 3 + 17^2$

显然，有了算数基本定理，刚刚说过的那个情况就可以直接推广到任意 k 个不同的素数相乘得出来的合数，即此时欧拉函数的值为：
$φ(n)=(p_1-1)(p_2-1)…(p_n-n)$

接下来考虑这种情况，当合数 n 是由单个素数 p 的 k 次幂组成时，欧拉函数又会怎样？这时情况跟上面不一样了。那么我们思考一下，小于 $p^k$ 且与它不互质的数是什么数？我们知道只有当一个数不包含质数 p 才可能与 n 互质。而包含质数 p 且小于 $p^k$ 的数都有 $1×p$，$2×p$，$3×p$，… ，$(p^k-p)$。最后一个数也可以写成 $(p^{k-1}-1)p$，也就是一共 $p^{k-1}-1$ 个包含质数 p 且小于 $p^k$ 的数。所以显然，去掉这 $p^{k-1}-1$ 个数，那剩下的就是与 n 互质的数。即这时的欧拉函数为：$φ(n)=(p^k-1)-(p^{k-1}-1)$ $= p^k-p^{k-1}$ $=p^k(1-\dfrac{1}{p})$ $=p^{k-1}(p-1)$

这时，回头再看一遍刚才一路讨论过来的五种情况的结论，我们发现，我们似乎已经可以导出欧拉函数~~终极大结局形式~~一般形式了，现在给出 $n = p_1^{k_1}p_2^{k_2} … p_i^{k_i}$，则有：

$φ(n)=φ({p_1}^{k_1})φ({p_2}^{k_2})…φ({p_i}^{k_i})$
$={p_1}^{k_1}{p_2}^{k_2}……{p_i}^{k_i}×$
$(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})…(1-\dfrac{1}{p_i})$
$=n(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})…(1-\dfrac{1}{p_i}) \enspace (1)$
$={p_1}^{a_1-1}(p_1-1){p_2}^{a_2-1}(p_2-1)$
$……{p_n}^{a_n-n}(p_n-n) \enspace (2)$

平常一般使用 (1) 式作为欧拉函数的通用计算公式，而RSA算法中用到的形式 $φ(n)=(p-1)(q-1)$ 则显然是脱胎于 (2) 式。至此欧拉函数证明完毕。

至于欧拉定理的证明……