理解 RSA 加密算法的基本工作原理

参考资料：

RSA 算法原理（二）

数论基础

质数（素数）

质数（Prime Number），又称素数，指在大于 1 的自然数中，除了 1 和该数自身外，无法被其他自然数整除的数（也可定义为只有 1 和该数本身两个正因数的数）。

大于 1 的自然数若不是质数，则称之为合数（也称为合成数）。

0 和 1 既不是质数，也不是合数。

参考 Wiki 质数

例如 2,3,5,7,11,13... 是质数，因为它们只有 1 和自身两个正因数。

例如 4,6,8,9,10,12,14... 是合数。4 除了 1 和 4 两个正因数外，还有 2 也是其正因数。6 除了 1 和 6 两个正因数外，还有 2 和 3 两个正因数。

算术基本定理

算术基本定理，又称正整数的唯一分解定理。即，每个大于 1 的自然数，要么本身是质数，要么可以写成 2 个或以上的质数的积，而这些质数（质因子）按大小排列以后，写法只有一种形式。

参考 Wiki 算术基本定理

例如 1200 = 2^4 * 3 * 5^2

最大公约数

最大公因数（英语：highest common factor，hcf）也称最大公约数（英语：greatest common divisor，gcd）。指能够整除多个不全为 0 的整数的最大正整数。

参考 Wiki 最大公约数

例如 8 和 12 的最大公约数是 4。

欧几里德算法

欧几里德算法，又称辗转相除法。是求最大公约数的算法。

参考 Wiki 欧几里德算法

扩展欧几里德算法

互质（互素）

互质（Coprime），如果两个或两个以上的整数的最大公约数是 1，则称它们为互质。

参考 Wiki 互质

若两个整数 a 和 b 的最大公约数是 1，则称 a 和 b 互质，记作： a \perp b。

例如 15 和 32 没有除 1 以外的公约数，所以它们为互质关系（不是质数也可以构成互质关系）。

同余

当两个正整数除以同一个正整数，若余数相同，则二整数同余。

参考 Wiki 同余

若两个正整数 a 和 b 除以正整数 m 所得的余数相同，则称 a 和 b 对于模 m 同余，记作：a \equiv b \pmod m，读作：a 同余于 b 模 m，或：a 和 b 关于模 m 同余。

例如 26 和 14 除以 12 所得的余数都是 2，所以：26 \equiv 14 \pmod {12}。

积性函数

定义域为正整数 n 的函数 f，有如下性质：

f(1) = 1，且当 a \perp b 时 f(ab) = f(a) f(b)，则此函数为积性函数；

f(1) = 1，且对于任意两个正整数 a 和 b 而言 f(ab) = f(a) f(b)，则此函数为完全积性函数。

欧拉函数

对于正整数 n，欧拉函数是小于等于 n 的正整数中与 n 互质的数的个数，表示为：\varphi(n)。

参考 Wiki 欧拉函数

例如 n = 8，在 1 到 8 中与 8 互质的数有 1，3，5，7，所以 \varphi(8)=4。

欧拉函数的性质：

1. 若 n = 1，则 \varphi(1) = 1

   因为 1 与任何数（包括自身）互质

2. 若 n 是质数，则 \varphi(n) = n - 1

3. 若 n = p^k（p 为质数，k 为大于等于 1 的整数），则 \varphi(n) = \varphi(p^k) = p^k - p^{k - 1} = p^k (1 - \frac{1}{p})

4. 若 n = p_1 p_2 且 p_1 \perp p_2，则 \varphi(n) = \varphi(p_1 p_2) = \varphi(p_1) \varphi(p_2)（可以看出欧拉函数是积性函数）

   例如 \varphi(56) = \varphi(8 * 7) = \varphi(8) \varphi(7) = 4 * 6 = 24

欧拉函数：

1. 把 n 质因数分解：n = p_1^{k1} p_2^{k2} \cdots p_r^{kr}

2. 根据第 4 条性质得到：\varphi(n) = \varphi(p_1^{k1}) \varphi(p_2^{k2}) \cdots \varphi(p_r^{kr})

3. 根据第 3 条性质得到：\varphi(n) = p_1^{k1} p_2^{k2} \cdots p_r^{kr} (1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \cdots (1 - \frac{1}{p_r})

4. 得到欧拉函数公式：

\varphi(n) = n (1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \cdots (1 - \frac{1}{p_r})

例如：\varphi(1323) = \varphi(3^3 * 7^2) = 1323 (1 - \frac{1}{3}) (1 - \frac{1}{7}) = 756

欧拉定理

若 a 和 n 为正整数，且 a \perp n，

则 a^{\varphi(n)} \equiv 1 \pmod n。

参考 Wiki 欧拉定理

a^{\varphi(n)} \equiv 1 \pmod n

也就是说 a^{\varphi(n)} 被 n 除的余数为 1，或者说 a^{\varphi(n)} - 1 能被 n 整除。例如：

1. 3 \perp 7 （3 和 7 互质）

2. \varphi(7) = 6 （欧拉函数 \varphi(7) 等于 6）

3. 3^{\varphi(7)} = 3^6 = 729 （3 的 \varphi(7) 次方等于 729）

4. 3^{\varphi(7)} = 3^6 = 729 \equiv 1 \pmod{7}（729 减去 1 等于 728，728 / 7 = 104，相当于 729 模 7 等于 1）

欧拉函数的特例

若 n 为质数，则 \varphi(n) = n - 1，则

a^{n - 1} \equiv 1 \pmod n

或

a^n \equiv a \pmod n

模反元素

模反元素，也称模倒数、模逆元。

参考 Wiki 模反元素

假设 a \perp n，那么一定能找到整数 b，使得 ab-1 能被 n 整除，或者说 ab 被 n 除的余数为 1。

ab \equiv 1 \pmod n

这时 b 就叫做 a 的模反元素。

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

欧拉定理可以证明模反元素必然存在：

a^{\varphi(n)} = a * a^{\varphi(n) - 1} \equiv 1 \pmod n

可以看到：a^{\varphi(n) - 1} 就是 a 的模反元素。

RSA 算法

RSA 密钥生成

1. 随机选择两个不相等的质数 p 和 q，例如 61 和 53

   实际应用中，这两个质数越大，就越难破解。

2. 计算 p 和 q 的乘积 n，n = 61 * 53 = 3233

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

3. 计算 n 的欧拉函数 \varphi(n)，\varphi(n) = \varphi(3233) = \varphi(61) \varphi(53) = 60 * 52 = 3120

4. 随机选择一个 e 满足 1 < e < \varphi(n) 且 e \perp \varphi(n)，例如 e = 17

   实际应用中，常常选择 65537。

5. 计算 e 对于 \varphi(n) 的模反元素 d，ed \equiv 1 \pmod {\varphi(n)}，这里求得 d = 2753

6. 公钥：(n,e) 为 (3233,17)

7. 私钥：(n,d) 为 (3233,2753)

根据已知的私钥可以生成公钥（要求已知 p 和 q）：

1. 私钥：(n,d) 为 (3233,2753)，p 为 61，q 为 53

2. ed \equiv 1 \pmod {\varphi(n)}

3. ed - 1 = k \varphi(n) = k (p - 1) (q - 1)

4. e * 2753 - 1 = k * (61 - 1) * (53 - 1)

5. 用扩展欧几里德算法求得当 k = 15 时 e = 17

6. 得到公钥 (n,e) 为 (3233,17)

通过公钥推导私钥：

1. 公钥：(n,e) 为 (3233,17)

2. ed \equiv 1 \pmod {\varphi(n)}

3. 17 * d \equiv 1 \pmod {\varphi(n)}，只有知道了 \varphi(n) 才能算出 d

4. \varphi(n) = (p - 1) (q - 1)，只有知道了 p 和 q 才能算出 \varphi(n)

   只有将 n 质因数分解才能得到 p 和 q

   所以对极大整数做因数分解的难度决定了 RSA 算法的可靠性。

RSA 加解密

RSA 加密

1. 公钥：(n,e) 为 (3233,17)

2. 明文：m = 65

3. 加密：m^e \equiv c \pmod n

4. 密文： c = m^e \mod n = 65^{17} \mod 3233 = 2790

RSA 解密

1. 私钥：(n,d) 为 (3233, 2753)

2. 密文：c = 2790

3. 解密：c^d \equiv m \pmod n

4. 明文：m = c^d \mod n = 2790^{2753} \mod 3233 = 65