RSA 算法原理（一）：数学知识

在学习 RSA 算法原理之前，读者应该有一些基本的数学知识，这里介绍下模运算、质因数和欧拉函数。以下情况如无特别说明，假设讨论的数字都是正整数

余数和取模

取模运算是求两个数相除的余数。例如，7÷3 = 2 .... 1，也就是商等于 2，余数为 1。我们也可以称之为 7 对 3 取模，可以写作：7 mod 3 = 1。一般公式：a mod b=c，指的是 a ÷ b 的余数为 c。

由于模运算的英文是 Modular Arithmetic，我们常用 mod 表示取模运算符，也叫求余运算符。在编程语言中，经常使用百分号 % 作为取模运算符。

有时候我们还会见到一个公式：a ≡ b (mod c)，这个公式的意思是说，a 和 b 分别对 c 取模，余数是相同的，也读作 a 与 b 同余，mod 为 c ，“≡”是数论中表示同余的符号。例如：7 ≡ 1（mod 3），指的是 7 和 1 分别对 3 取余，余数是相同的。

由于取模其实就是取余数，因此有这样的规律：

设 x mod y = n，则存在一个整数 k，使得 ky + n = x。

这应该不难理解，x mod y 其实就是 x ÷ y，那么结果就是 k（商），余数为 n，也就是 x ÷ y = k.... n

其实我们生活中就有用到取模的例子。

1. 假设现在是上午 10 点，同事约你说 7 小时后吃饭，也就是 17 点，那么其实也就是下午 5 点（17 mod 12 = 5）。在一些钟表里，只有 1 ~ 12 的数字，可以认为超过 12 的会自动做取模运算
2. 若 12 月 1 号是周一，很容易就知道 12 月 8 号、15 号、22 号、29 号也是周一。

同时，我们可以推导出以下规律：

• 自反性：a≡a（mod m）。
• 对称性：若 a≡b（mod m）, 则 b ≡ a（mod m）。
• 传递性： 若 a≡b（mod m)，b≡c（mod m）, 则 a≡c（mod m）。

此外，模运算的加减乘除，和基本的四则运算类似：

• 加法：(a + b) mod p = (a mod p + b mod p) mod p
• 减法：(a - b) mod p = (a mod p - b mod p ) mod p
• 乘法：(a * b) mod p = (a mod p * b mod p) mod p
• 幂运算：(a^b) mod p = ((a mod p)^b) mod p （这个幂运算的规律后续会经常用到）

另外还有一个公式要了解：（其实就是幂运算的一种情况）

a^xy mod p = （（a^x mod p）^y ）mod p 证明如下：

a^xy mod p =（a^x * a^x .... * a^x）mod p （注：y 个 a^x 相乘等于 a^xy）。

            =  （a<sup>x</sup> mod p   * a<sup>x</sup> mod p....  * a<sup>x</sup>mod p ）mod p（根据乘法规律可得）

            =   ( (a<sup>x</sup> mod p )<sup>y</sup> )  mod p   （ y 个 a<sup>x</sup>mod p 相乘，也就是(a<sup>x</sup> mod p )<sup>y</sup>）

还有一个公式知道即可：若 a ≡ b（mod m），则 （a - b）mod m = 0。这个很好推导：

• 假设 a mod m 的余数是 y，则 a mod m = y； 另外，b mod m 也等于 y
• 假设 a = km + y （k 是正整数），b = zm + y （z 也是整数）
• 那么 a - b = （km + y ）- （zm + y） = （k - z）m，这个数 mod m，余数当然是 0 了。

取模运算的用处

在公钥加密算法中，由于公钥是对所有人公开的信息，我们需要保证数据被“公钥”加密之后，不能够被轻易地反推出来。

那什么样的算法单向计算容易，而逆向反推却非常难呢？答案是模运算（Modular Arithmetic），像计算机中的伪随机数，散列（hash）算法都是它的典型应用。

试想下面这个例子：3³ mod 7 的值是多少？要计算 3 的 3 次方对 7 取余数，很容易；算出来等于 27 mod 7 = 6；

但如果是这个式子：3^x mod 7 = 6。已知余数是 6 的情况下，我们又应当如何去寻找这里的 x 值呢？

由于求余运算并不可逆，我们只能一个数一个数地带进去试：

3⁰ mod 7 = 1

3¹ mod 7 = 3

3² mod 7 = 2

3³ mod 7 = 6

3⁴ mod 7 = 4

3⁵ mod 7 = 5

但如果这里出现的是很大很大的数，例如 3^x mod 935654654654651616516498465178135 = 5，再逐个去尝试就不太现实了。

这也是为什么模运算被称作是单向函数，因为对于大数来说，对模运算求逆是根本不现实的。因此也常用在加密算法里，用来生成密文。

质数、素数、因子

加密算法中经常会用到几种特别的数字：

• 质数：只能被自身和 1 整除的数，就是质数，也叫素数。例如 2,3,5,7,11,13,17,19......

• 合数：比 1 大但不是质数的数字，或者说能被 1 和自身之外的数整除的数字，例如 4 = 2 × 2， 15 = 3 × 5

• 1 和 0 既非质数也非合数。

• 因子：也叫因数，约数。设 a × b =c，（a 和 b 都是整数）则 a 和 b 就是 c 的因子，例如：2× 3 = 6，则 2 和 3 是 6 的因子；1 × 6 = 6，则 1 和 6 也是 6 的因子。因此 6 有两组因子

• 公因子：能同时整除几个整数的整数。例如 4 可以整除 8，也可以整除 12，那么 8 和 12 有一个公因子 4；同理，24 和 12 也有一个公因子 4。公因子可能有多个。例如 8 和 12 的公因子有 1,2,4

• 质因数：如果一个质数是某个数 n 的因子，我们就称这个质数为 n 的质因数

• 分解质因数：把一个合数用质因数相乘的形式表现出来，就是分解质因数。例如：

  30=2×3×5，则 2,3,5 就是 30 的质因数。

  12=2×2×3，则 2 和 3 都是 12 的质因数

  分解质因数只针对合数，每个合数都可以写成几个质数相乘的形式。

大整数分解质因数

分解质因数，是非常非常困难的。分解没有公式，只能暴力破解（也就是一个个穷举），数字小的时候容易，当数字特别大时，只能靠计算机的计算速度了。

举例来说，你可以对 30 做质因数分解，也可以对 3233 进行质因数分解（61×53），但是如果让你对下面这个整数进行质因数分解呢？：

1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

这里直接说答案吧，上面的整数是如下两个质数的乘积：

33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 × 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

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

质因数分解被认为是指数级增长类型的问题（随着数字的增大，难度指数级增长）。所以，在加密算法里，就是依靠这个特点来保证破解密钥是非常困难的，实际应用中，RSA 密钥一般是 1024 个二进制位，重要场合则为 2048 位，基本不可能被分解成功，因此也破解不了。

假如有人找到一种快速因数分解的算法，那么可能目前的加密体系得颠覆了，但找到这样的算法的可能性是非常小的，也不是本文的重点。

互质

互质：如果两个正整数，除了 1 以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15 和 32 没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。

由互质关系能得出以下结论：

• 1 和任意一个自然数是都是互质关系，比如 1 和 99。
• 任意两个质数构成互质关系，比如 7 和 61。
• 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如 3 和 10。
• p 是大于 1 的整数，则 p 和 p-1 构成互质关系，比如 57 和 56。
• p 是大于 1 的奇数，则 p 和 p-2 构成互质关系，比如 17 和 15。

欧拉函数

思考一个问题：任意给定正整数 n，请问在小于等于 n 的正整数之中，有多少个与 n 构成互质关系？（比如，在 1 到 8 之中，有多少个数与 8 构成互质关系？）

有一个计算这个数量的函数，称为欧拉函数。以 φ(n)表示（φ 是希腊字母，读音/fai/）。例如，在 1 到 8 之中，与 8 形成互质关系的是 1、3、5、7，所以 φ(n) = 4。

φ(n) 的计算方法并不复杂，我们分以下情况讨论，最后再得出通用的公式：

1. 如果 n=1，则 φ(1) = 1 。因为 1 与任何数（包括自身）都构成互质关系。

2. 如果 n 是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如 5 与 1、2、3、4 都构成互质关系。

3. 如果 n 是质数的某一个次方，即 n = p^k（p 是质数，k 是大于或等于 1 的整数），则 φ(p^k) = p^k- p^k-1。比如 φ(8) = φ (2³) =2³ - 2² = 8 - 4 = 4。怎么推导的呢？

   首先，p 是质数，而 n 是 p 的某一个次方；那么 1×p、2×p、3×p....p^(k-1)×p，这几个数都和 n 有一个共同的公因子 p， 把它们减去，剩下的就是与 n 互质的数。可以看出，上面的第二种情况是 k=1 时的特例。

   这个公式也可以写成：φ(p^k) = p^k- p^k-1= p^k（1-1/p）

4. 如果 n 可以分解成两个互质的整数之积，n = p1 × p2，则 φ(n) = φ(p1p2) = φ(p1)φ(p2)。即积的欧拉函数等于各个因子的欧拉函数之积。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。原理涉及到中国剩余定理，这里不展开了，毕竟本文是计算机系列，不是数学系列 （主要是因为笔者也看不懂了 🙁）

我们来总结下通用的公式是怎么得出的：

1. 任意一个大于 1 的正整数，都可以写成一系列质数的积（合数可以质因数分解，质数的话则是 1× 本身）：n = p₁​^k1p₂​^k2p₃​^k3......p_r​^kr
2. 根据第 4 种情况，可以得出：φ (n) =φ (p₁​^k1) × φ (p₂​^k) × ...... × φ (p_r​^kr)
3. 根据第 3 种情况，可以得到 φ (n) = p₁​^k1p₂​^k2p₃​^k3......p_r​^kr（1-1/p₁）（1-1/p₂）...（1-1/pr）
4. 也就是等于 φ (n) = n （1-1/p₁）×（1-1/p₂）× ... ×（1-1/pr）。这就是通用公式

我们来测试下这个公式：

1. φ(8) = φ(2³) = 8 × （1 - 1/2） = 4
2. φ(1323) = φ ( 3³ × 7²) = 1323 ×（1-1/3 ）× (1 - 1/7） =756
3. 其他的就不一一计算了

以上规律理解即可，不用死记硬背，知道有这个公式即可。

需要注意的是，即使有了这个公式，也并不是说求欧拉函数是一件很容易的事情，因为本身质因数分解是非常困难的。之前我们假设 n = p₁​^k1p₂​^k2p₃​^k3......p_r​^kr，如果不知道 p₁​^k1，p₂​^k2....p_r​^kr 分别是多少，还是很难计算出来欧拉函数的值的。

欧拉定理

欧拉函数的用处，在于欧拉定理：

如果两个正整数 a 和 n 互质，则 n 的欧拉函数 φ(n) 可以让下面的等式成立：

a^{φ (n)}= 1 （mod n）

也就是说，a 的 φ(n)次方被 n 除的余数为 1。或者说，a 的 φ(n)次方减去 1，可以被 n 整除。比如，3 和 7 互质，而 7 的欧拉函数 φ(7)等于 6，所以 3 的 6 次方（729）减去 1，可以被 7 整除（728/7=104）。

欧拉定理的证明比较复杂，这里就省略了。我们只要记住它的结论就行了。

欧拉定理可以大大简化某些运算。比如，7 和 10 互质，根据欧拉定理，7^{φ (10)}= 1 （mod 10），已知 φ(10)=φ( 2 × 5) = φ( 2 ) × φ(5) = 1 × 4，所以马上得到 7 的 4 倍数次方的个位数肯定是 1。因此，7 的任意次方的个位数，能很快就算出来（不用算出整个数是多少）。

欧拉定理是 RSA 算法的核心。理解了这个定理，就可以理解 RSA。

这里说一个欧拉定理的特例，假设正整数 a 与质数 p 互质，因为质数 p 的 φ(p)等于 p-1，则欧拉定理可以写成 a^p-1= 1 （mod p），这就是著名的费马小定理。

模反元素

最后一个知识点：如果两个正整数 a 和 n 互质，那么一定可以找到整数 b，使得 ab-1 被 n 整除，或者说 ab 被 n 除的余数是 1，公式：ab ≡ 1 （mod n）。这时，b 就叫做 a 的"模反元素"。

比如，3 和 11 互质，那么 3 的模反元素就是 4，因为 ( 3 × 4 ) -1 可以被 11 整除。显然，模反元素不止一个， 4 加减 11 的整数倍都是 3 的模反元素 {...,-18,-7,4,15,26,...}，即如果 b 是 a 的模反元素，则 b+kn 都是 a 的模反元素。

欧拉定理可以用来证明模反元素必然存在：a^{φ (n)}= a × a^{φ (n) -1} ≡ 1（mod n） ，我们设 a^{φ (n) -1}=b，也就是 ab ≡ 1（mod n）

可以看到，b，也就是 a 的 φ(n)-1 次方，就是 a 的模反元素。

课后习题

1. 举一个生活中取模的例子
2. 理解什么是质数、合数和质因数，并尝试质因数分解 28
3. 理解什么是欧拉函数，并计算 28 的欧拉函数值
4. 理解什么是欧拉定理，并计验证 7^{φ (20)}= 1 （mod 20）
5. 理解什么是模反元素

在往下看答案之前，请先自己计算一遍

课后答案

2. 数字 28 = 2 × 14 = 2 × 2 × 7，28 这个数字很小，可以人肉眼看出质因数
3. φ(28) = φ(2) × φ(2) × φ(7) = 1 × 1 × 6 = 6。首先是质因数分解，然后计算乘积即可
4. φ(20) = φ(2) × φ(2) × φ(5) = 1 × 1 × 4 = 4，而 7⁴ = 2401，2401 mod 20 =1. （目前数字都比较小，可以通过电脑自带的计算器运算）