今天午睡的时候，可能是想到了之前对开源openssl做定制化算法生成的时看到自己生成的公钥和私钥，突然想起来好像自己从来没从原理的角度去解释一下，什么是rsa算法中的公钥和私钥，为什么他能做到公钥加密但不能解密，而公钥加密的私钥却能解密的原因。
开始学习后，才知道如果想要了解RSA算法的原理，必须要从欧拉定理入手，通过欧拉定理的变形和模反才能得到RSA算法的雏形。由于学下来发现篇幅太大，我懒得写了，所以下面的内容都是我和AI问答之后，我给的AI整体框架，让AI基于我们的对话生成的，当然其中也有我自己的一些补充，由于文笔粗劣，夹杂在AI流畅的文本中会很显眼，大家阅读的时候发现写的不好的地方，那大概率是我加的~😄。
内容有点多，我分了三篇wiki来讲。
非对称加密的数学原理（一）
欧拉定理的数学基础
引言
在广阔的数学领域中，某些原理如同万能钥匙，能解锁深层的结构性真理，并催生强大的现实世界应用。欧拉定理便是其中之一，作为数论的基石，它为我们理解整数的周期性本质提供了深刻的洞见。本文将作为系列文章的第一部分，系统梳理欧拉定理的数学基础，为后续引出RSA公钥加密算法做好理论铺垫。
一、基本概念回顾
`` 在正式阐述欧拉定理之前，我们需要先厘清几个数论中的基础概念，它们是理解后续内容的基石。
1.1 余数与同余
给定一个正整数 $n$，如果两个整数 a 和 b，能满足 n % a == n % b (百分号是计算机内取余的说法，我习惯这么写了)，那么就称 $a$ 与 $b$ 对模 $n$ 同余。同余还有另一个数学算法，即如果两个整数 $a$ 和 $b$ 满足 $a - b$ 能够被 $n$ 整除，即 $n \mid (a - b)$，记作：
$$a \equiv b \pmod{n}$$ 为什么二者等价呢？推理如下：
- 假设 $a$ 除以 $n$ 的商是 $q_1$，余数是 $r_1$；$b$ 除以 $n$ 的商是 $q_2$，余数是 $r_2$。即 $a = q_1 n + r_1$，$b = q_2 n + r_2$。
- 那么它们的差 $a - b = (q_1 - q_2)n + (r_1 - r_2)$。
- 如果 $a$ 和 $b$ 的余数相同（即 $r_1 = r_2$），那么 $r_1 - r_2 = 0$，此时 $a - b = (q_1 - q_2)n$，显然能被 $n$ 整除。
- 反过来，如果 $a - b$ 能被 $n$ 整除，因为 $a - b = (q_1 - q_2)n + (r_1 - r_2)$，这意味着 $(r_1 - r_2)$ 也必须能被 $n$ 整除。但由于余数 $r_1, r_2$ 都小于 $n$，它们之间的差也必定小于 $n$。一个绝对值小于 $n$ 的数要想被 $n$ 整除，只能是 0。所以 $r_1 - r_2 = 0$，即余数相同。
同余是整数的一个重要等价关系，它将无限的整数划分成有限的等价类。欧拉定理本质上就是一个关于同余的定理。
1.2 互质
若两个正整数 $a$ 和 $b$ 的最大公约数为 1，即 $\gcd(a, b) = 1$，则称 $a$ 与 $b$ 互质。需要注意的是，互质的两个数并不要求各自都是质数——例如 $(15, 8) = 1$，两个合数同样可以互质。
1.3 质数
质数（也称素数）是指只能被 1 和其自身整除的正整数，如 2, 3, 5, 7, 11, 13 等。质数是数论中最基本的构建单元，算术基本定理告诉我们，任何一个大于 1 的正整数都可以唯一地分解为质数的乘积。
二、欧拉函数 $\varphi(n)$
2.1 定义
对于任意正整数 $n$，欧拉函数 $\varphi(n)$ 定义为小于或等于 $n$ 的正整数中与 $n$ 互质的数的个数。
举例来说：
- 当 $n = 8$ 时，与 8 互质的数有 ${1, 3, 5, 7}$，共 4 个，因此 $\varphi(8) = 4$。
- 当 $n = 10$ 时，与 10 互质的数有 ${1, 3, 7, 9}$，共 4 个，因此 $\varphi(10) = 4$。
2.2 计算方法
欧拉函数的计算依赖于 $n$ 的质因数分解。设 $n$ 的质因数分解为：
$$n = p_1^{k_1} \cdot p_2^{k_2} \cdots p_m^{k_m}$$
则欧拉函数可通过下式计算：
$$\varphi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_m}\right)$$
在实际计算中，我们常常遇到以下几种特殊情况：
| 情形 | 条件 | 公式 | 示例 |
|---|---|---|---|
| 情形1 | $n = 1$ | $\varphi(1) = 1$ | $\varphi(1) = 1$ |
| 情形2 | $n$ 为质数 $p$ | $\varphi(p) = p - 1$ | $\varphi(7) = 6$ |
| 情形3 | $n = p^k$ | $\varphi(p^k) = (p-1) \cdot p^{k-1}$ | $\varphi(8) = \varphi(2^3) = 1 \cdot 2^2 = 4$ |
| 情形4 | $n = pq$（$p, q$ 为不同质数） | $\varphi(pq) = (p-1)(q-1)$ | $\varphi(15) = \varphi(3 \times 5) = 2 \times 4 = 8$ |
其中，情形4，也就是 $\varphi(pq) = (p-1)(q-1)$ 在后续 RSA 算法中扮演着至关重要的角色，我们稍后会详细讨论。
2.3 情形4的简单证明
由于 $p, q$ 是不同的质数，在区间 $[1, pq)$ 上，与 $pq$ 不互质的数只有两类：
- $p$ 的整数倍：$p, 2p, 3p, \ldots, (q-1)p$，共 $q - 1$ 个；
- $q$ 的整数倍：$q, 2q, 3q, \ldots, (p-1)q$，共 $p - 1$ 个。
因此，与 $pq$ 互质的正整数个数为：
$$\varphi(pq) = (pq - 1) - (q - 1) - (p - 1) = pq - p - q + 1 = (p - 1)(q - 1)$$
证毕。
三、欧拉定理
3.1 定理表述
欧拉定理（Euler’s Theorem）：若 $a$ 和 $n$ 为正整数，且 $\gcd(a, n) = 1$（即 $a$ 与 $n$ 互质），则：
$$a^{\varphi(n)} \equiv 1 \pmod{n}$$
其中 $\varphi(n)$ 是欧拉函数。
3.2 直观理解：指数的周期性
欧拉定理的核心思想在于指数的周期性。在模 $n$ 运算中，不断地用一个数 $a$ 去乘以自己（即 $a, a^2, a^3, \ldots$），结果会呈现出周期性循环。欧拉定理告诉我们：只要 $a$ 和 $n$ 互质，那么 $a$ 的 $\varphi(n)$ 次方模 $n$ 的结果必然是 1。
换一种说法：在模 $n$ 的世界里，$a^{\varphi(n)}$ 就像是”走完了一整圈”，回到了起点 1。
3.3 一个具体例子
令 $a = 3$，$n = 10$。首先验证两者互质：$\gcd(3, 10) = 1$。
计算欧拉函数：
- 与 10 互质的数有 ${1, 3, 7, 9}$，故 $\varphi(10) = 4$。
验证欧拉定理：
$$3^{\varphi(10)} = 3^4 = 81 = 80 + 1 \equiv 1 \pmod{10} \quad \checkmark$$
与定理结论完全相符。
3.4 与费马小定理的关系
欧拉定理实际上是费马小定理的推广。当 $n$ 为质数 $p$ 时，$\varphi(p) = p - 1$，代入欧拉定理即得：
$$a^{p-1} \equiv 1 \pmod{p}$$
这就是费马小定理。因此，费马小定理可以视为欧拉定理在模数为质数时的特殊情形。
四、欧拉定理的证明
以下是一个基于剩余系置换的经典证明思路。
4.1 构造缩系
设 $b_1, b_2, \ldots, b_{\varphi(n)}$ 为小于 $n$ 且与 $n$ 互质的全部正整数，即缩系（reduced residue system）。
考虑如下 $\varphi(n)$ 个数：
$$m_i = a \cdot b_i \pmod{n}, \quad i = 1, 2, \ldots, \varphi(n)$$
4.2 证明这 $\varphi(n)$ 个数互不相同
假设存在 $i \neq j$ 使得 $a \cdot b_i \equiv a \cdot b_j \pmod{n}$。
由于 $\gcd(a, n) = 1$，$a$ 在模 $n$ 下存在乘法逆元，可以两边消去 $a$(乘法逆元可以看七、补充中的内容)，得到：
$$b_i \equiv b_j \pmod{n}$$
但 $b_i, b_j$ 都小于 $n$ 且互不相同，矛盾。因此 $m_1, m_2, \ldots, m_{\varphi(n)}$ 互不相同。
4.3 证明这些数都与 $n$ 互质
因为 $\gcd(a, n) = 1$ 且 $\gcd(b_i, n) = 1$，所以 $\gcd(a \cdot b_i, n) = 1$，进而 $\gcd(m_i, n) = \gcd(a \cdot b_i \bmod n, n) = 1$。
4.4 得出结论
由于 $m_1, m_2, \ldots, m_{\varphi(n)}$ 是 $\varphi(n)$ 个互不相同且都与 $n$ 互质的数，它们必然恰好是 $b_1, b_2, \ldots, b_{\varphi(n)}$ 的一个排列。因此：
$$\prod_{i=1}^{\varphi(n)} m_i \equiv \prod_{i=1}^{\varphi(n)} b_i \pmod{n}$$
即：
$$a^{\varphi(n)} \cdot \prod_{i=1}^{\varphi(n)} b_i \equiv \prod_{i=1}^{\varphi(n)} b_i \pmod{n}$$
由于 $\prod b_i$ 与 $n$ 互质，可以在两边消去，得到：
$$a^{\varphi(n)} \equiv 1 \pmod{n}$$
证毕。 $\blacksquare$
五、欧拉定理的一个重要推论
对欧拉定理稍作变形，可以得到一个在后续 RSA 算法中至关重要的推论。
将 $a^{\varphi(n)} \equiv 1 \pmod{n}$ 两边同时取 $k$ 次方，再乘以 $a$，得到：
$$a^{k \cdot \varphi(n) + 1} \equiv a \pmod{n}$$
其中 $k$ 为任意正整数。
这个推论的深刻含义在于：如果一个数的指数可以写成 $k \cdot \varphi(n) + 1$ 的形式，那么对该数进行这个指数次方运算后模 $n$，结果会还原为原数本身。
这正是后续 RSA 加解密能够成功还原明文的数学根基所在——通过精心设计公钥指数 $e$ 和私钥指数 $d$，使得 $e \cdot d = k \cdot \varphi(n) + 1$，从而利用这一推论实现可逆的加密与解密。
六、欧拉定理的应用：降幂
除了作为密码学的基石，欧拉定理在计算数学中还有一个非常实用的功能——降幂。
当需要计算 $a^b \bmod n$ 而 $b$ 极其巨大时，如果 $\gcd(a, n) = 1$，可以利用欧拉定理将指数降低：
$$a^b \equiv a^{b \bmod \varphi(n)} \pmod{n}$$
示例：计算 $3^{100} \bmod 7$。
- 检查条件：$\gcd(3, 7) = 1$，满足。
- 计算 $\varphi(7) = 6$（因为 7 是质数）。
- 降幂：$100 \bmod 6 = 4$。
- 简化：$3^{100} \equiv 3^4 = 81 \equiv 4 \pmod{7}$。
这种降幂技巧在算法竞赛和密码学工程中极为常用。
七、补充
7.1 乘法逆元的概念
“乘法逆元”是模运算里的一个概念，可以类比成”模意义下的倒数”。
定义
在模 n意义下，如果 gcd(a,n)=1，则存在唯一一个整数 a−1（记作 a−1modn），使得 a⋅a−1≡1(modn) 这个 a−1就叫做 a在模 n下的乘法逆元。
例子
比如模 n=7，a=3：
- 3×5=15≡1(mod7)
- 所以 3−1≡5(mod7)，即 3 的逆元是 5。
再比如模 n=6，a=4：
- gcd(4,6)=2=1，没有逆元（因为 4 乘任何数模 6 都不可能等于 1）。
为什么存在唯一的乘法逆元
假设存在两个不同的整数 x1,x2都是 a的逆元，即： ax1≡1(modn) ax2≡1(modn)
两式相减得： a(x1−x2)≡0(modn)
这意味着 n∣a(x1−x2)。 因为 gcd(a,n)=1，所以 n∣(x1−x2)（这是数论的一个基本性质：若 gcd(a,n)=1且 n∣a⋅k，则 n∣k）。 于是 x1≡x2(modn)，即它们在模 n下相等。所以逆元在模 n意义下唯一。
小结
在本篇中，我们从同余、互质等基本概念出发，系统介绍了欧拉函数 $\varphi(n)$ 的定义与计算，阐述了欧拉定理的内容及其证明，并引出了对 RSA 算法至关重要的推论 $a^{k\varphi(n)+1} \equiv a \pmod{n}$。
欧拉定理揭示了模运算中指数的周期性规律，它”能将看似不可能的巨大指数计算转变为可处理的问题”，并为构建陷门函数提供了理论基础。在下一篇中，我们将以此为基础，探讨欧拉定理的进一步变形，并最终引出 RSA 公钥加密算法的完整构造。
下一篇预告：《从欧拉定理到RSA算法（二）：欧拉定理的变形与模反元素》