RSA 加密算法原理

RSA 概述展开目录

RSA 加密算法是一种非对称加密算法。在公开密钥加密和电子商业中 RSA 被广泛使用。RSA 是 1977 年由罗纳德・李维斯特（Ron Rivest）、阿迪・萨莫尔（Adi Shamir）和伦纳德・阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的

数论基础展开目录

其实 RSA 加密算法最主要的就是两个公式，在理解这两个公式之前需要学习数论中的四个概念：互质、欧拉函数、欧拉定理、模反元素

互质展开目录

如果两个正整数，除了 1 以外没有其他公因子，则称这两个数互质，比如 6 和 21 的公因子有 3 和 1，所以 6 和 21 就不互质；而 10 和 21 只有一个公因子 1，所以它们互质。不是质数也可以构成互质关系

只要满足以下几点就可构成互质关系：

1. 任意两个质数构成互质关系，比如 13 和 61
2. 1 和任意一个自然数是都是互质关系，比如 1 和 99
3. p 是大于 1 的整数，则 p 和 p-1 构成互质关系，比如 57 和 56
4. p 是大于 1 的奇数，则 p 和 p-2 构成互质关系，比如 17 和 15
5. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如 97 和 10
6. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如 3 和 10

欧拉函数展开目录

请问 10 以内的正整数有哪些与 10 互质呢？

答案是：{1,3,7,9}，10 以内用手就可以算的过来，那 100 呢？1000 呢？数字越大越难手算出来，有公式可以计算，就是欧拉函数

欧拉函数以 $\psi (n)$ 表示。在 1 到 10 之中，与 10 形成互质关系的是 {1,3,7,9}，所以 $\psi (10) = 4$

$\psi (n)$ 的计算方法并不复杂，推到步骤可以在网上找到，这里只要记住最终结论就行

第一种情况

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

---

第二种情况

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

---

第三种情况

如果 n 是质数的某一个次方值，即 $n = p^k$（p 为质数，k 为大于等于 1 的整数），则：

$$ \psi(p^k) = p^k - p^{k-1} $$

例如，$\psi (8) = \psi (2^3) = 2^3 - 2^2 = 4$

这是因为只有当一个数不包含质数 p，才可能与 n 互质，而包含质数 p 的数共有 $p^{k-1}$ 个，即 $p,2p,3p...p^k$，把他们去除，剩下的就是与 n 互质的数

上面的式子还可以写成下面的形式：

$$ \psi(p^k) = p^k - p^{k-1} = p^k(1-\frac{1}{p}) $$

可以看出，上面的第二种情况是 k=1 时的特例

---

第四种情况
如果 n 可以分解成两个互质的整数之积 $n = p_1 * p_2$，则：

$$ \psi(n) = \psi(p_1p_2) = \psi(p_1)\psi(p_2) $$

积的欧拉函数等于各个因子的欧拉函数之积。例如，$\psi (56) = \psi (8*7) = \psi (8)*\psi (7)=4*6=24$

---

第五种情况
因为任意一个大于 1 的正整数，都可以写成一系列质数的积 $n=p^{k_1}_1p^{k_2}_2...p^{k_r}_r$

根据第四条结论，得到：

$$ \psi(n)=\psi(p^{k_1}_1)\psi(p^{k_2}_2)...\psi(p^{k_r}_r) $$

再根据第三条结论，得到：

$$ \psi(n) = p^{k_1}_{1} p^{k_2}_{2} ... p^{k_r}_{r} (1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_r}) $$

也就等于

$$ \psi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_r}) $$

这就是欧拉函数的通用计算公式。比如 1323 的欧拉函数，计算过程如下

$$ \psi(1323) = \psi(3^3 * 7^2) = 1323(1-\frac{1}{3})(1-\frac{1}{7})=756 $$

欧拉定理展开目录

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

$$ a^{\psi(n)} \equiv 1(mod\; n) $$

也就是说，a 的 $\psi (n)$ 次方除以 n 的余数为 1。或者说，a 的 $\psi (n) 次方减 1 可以整除 n$。例如，3 和 7 互质，而 7 的欧拉函数 $\psi (7)=6$，所以 $(3^6 - 1) / 7 = 728 / 7 = 104$

科普：mod 为取模，取模运算与取余运算还是有区别。取余的商靠近 0，而取模的商是靠近负无穷的

欧拉定理可以大大简化某些运算。比如，7 和 10 互质，根据欧拉定理，则 $7^{\psi (10)} \equiv 1 (mod\; 10)$

因此，7 的任意次方的个位数（例如 7 的 222 次方），心算就可以算出来，因为 $7^{222} = (7^4)^{55} * 7^2$，又因为某个整数的个位数，就是这个整数 mod 10，所以 $(7^{\psi (10)})^{55} * 7^2 \equiv 9 (mod\; 10)$

欧拉定理是 RSA 算法的核心，只有理解这个定理，才能理解 RSA

模反元素展开目录

如果两个正整数 a 和 n 互质，那么一定可以找到整数 b，使得 (a*b)-1 整除 n

$$ a * b \equiv 1(mod\; n) $$

这时，b 就叫 a 的 “模反元素”

比如，3 和 11 互质，找到 3 的模反元素 4，使得 (3*4)-1 可以整除 11。显然，模反元素不止一个，4 加减 11 的非零整数倍都是 3 的模反元素 {...,-18,-7,4,15,...}。即如果 b 是 a 的模反元素，则 $b+kn$ 都是 a 的模反元素

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

$$ a^{\psi(n)} = a * a^{\psi(n) - 1} \equiv 1 (mod\; n) $$

可以看到，$a^{\psi (n) - 1}$ 就是 a 的模反元素

RSA 密钥生成过程展开目录

首先假设小红和小明两个人进行通信

因为 RSA 是非对称加密算法，这也就意味着加密和解密使用的是不同的密钥，生成密钥具体分为六步：

（1）随机选择两个不相等的质数 p 和 q

小红随机选择 61 和 53（实际应用中，两个质数越大，就越难破解）

---

（2）计算 p 和 q 的乘积 n

n = 61*53 = 3233

---

（3）计算 n 的欧拉函数
这里利用欧拉函数求解的第四种情况：

如果 n 可以分解成两个互质的整数之积，即 $n = p_1 * p_2$，则 $\psi (n)=\psi (p_1p_2) = \psi (p_1)\psi (p_2)$，所以 $\psi (3233)=\psi (61*53)=\psi (61)*\psi (53)$

又因为 61 和 53 都是质数，于是可以根据欧拉函数求解的第二种情况：

如果 n 是质数，则 $\psi (n)=n-1$，所以 $\psi (65) * \psi (53)=60*52=3120$

所以 $\psi (n)=3120$

---

（4）随机选择一个整数 $e$，条件是 $1 <e < \psi (n)$，且 $e$ 与 $\psi (n)$ 互质

小红在 1 到 3120 之间，随机选择了 17

---

（5）计算 $e$ 对于 $\psi (n)$ 的模反元素 d
所谓模反元素就是指有一个整数 d，可以使得 e*d 除以 $\psi (n)$ 的余数为 1，公式表示为

$e * d = 1(mod \; \psi(n))$

这个公式等价于

$e * d - k * \psi(n) = 1$

将 $e=17,\psi (n)=3120$ 带入得

$17d - 3120k = 1$

令 $d = x,-k = y$，则

$17x + 3120y = 1$

所以我们要求的模反元素 d 就是对上面的二元一次方程求解，根据扩展欧几里得算法（辗转相除法）得
上图我们使用拓展欧几里得求得 d=-367，但通常我们习惯取正整数，利用模反元素的特性

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

所以取 $d = d + k\psi (n) = -367+1*3120=2753$

到现在为止，所有的计算都已结束

---

（6）将 n 和 e 封装成公钥，n 和 d 封装成私钥
首先回归一下一共出现的 6 个数字：

1. $p = 61$ 随机数，与 $q$ 互质
2. $q = 53$ 随机数，与 $p$ 互质
3. $n = p * q = 3233$
4. $\psi(n) = 3120$
5. $e = 17$ 随机数，条件是 $1 <e < \psi (n)$，且 $e$ 与 $\psi (n)$ 互质
6. $d = 2753$ $e$ 对于 $\psi (n)$ 的模反元素 $d$

在这个例子中 n=3233，e=17，d=2753，所以公钥就是 (n,e)=(3233,17)，私钥就是 (n,d)=(3233, 2753)，这样小红就可以将公钥公布出去，自己保存好私钥就可以了

RSA 加解密演示展开目录

加密要用公钥 (n,e)
假设小明先试探性的给小红发一个字母 m = 'A'，由于在通信传输中只能传输 0 和 1，所以我们先将 'A' 转 ASCII 码为 65，所以 m = 65（m 必须是整数，且 m 必须小于 n）

所谓加密，就是使用下面的加密公式算出密文 c

$m^e = c(mod \; n)$

小明得到的公钥是 (n,e) = (3233,17)，m = 65，那么得到下面的等式

$65^{17} = c (mod \; 3233)$

小明通过计算得到 c = 2790，所以他就把 2790 发给小红了

---

（2）揭秘要用私钥 (n,d)
小红拿到小明发过来的密文 c = 2790，就用下面的公式进行解密出明文 m：

$c^d \equiv m (mod \; n)$

而小红的私钥为 (n,d) = (3233,2753)，所以得到下面的等式：

$2790^{2753} \equiv m (mod \; 3233)$

小红通过计算器以算，得 m = 65，然后小红对着 ASCII 码表得出 65 对应的字母为 A

至此，整个加密过程就演示完了，总结一下：

1. 小明获取到小红的公钥 (n,e) = (3233,17)
2. 小明选取发送的消息 m = 'A' = 65，注意 m 要小于 n，如果消息大于 n，必须分段加密！
3. 小明通过加密公式：$m^e \equiv c (mod \; n)$ 算出密文 c = 2790
4. 小红获取到小明的密文 c = 2790
5. 小红使用解密公式：$c^d \equiv m (mod \; n)$ 算法明文 m = 65 = 'A'