[!info] related notes 算法面试题型 MOC 密码学

辗转相除法 (Euclidean Algorithm)

1. 简介

辗转相除法，又称欧几里得算法 (Euclidean Algorithm)，是求两个正整数最大公约数 (Greatest Common Divisor, GCD) 的一种古老而高效的算法。

在密码学中，它有着至关重要的地位，特别是在 RSA 的密钥生成过程中。

Related: 非对称密码学（Asymmetric-Encryption）

2. 核心原理

两个整数 $a$ 和 $b$（假设 $a > b$）的最大公约数等于 $b$ 和 $a \pmod b$（即 $a$ 除以 $b$ 的余数）的最大公约数。 公式表示为：

$$ gcd(a, b) = gcd(b, a \pmod b) $$

3. 算法流程

1. 用较大数除以较小数，得到商和余数。
2. 若余数为 0，则除数即为最大公约数。
3. 若余数不为 0，则将原来的除数作为新的被除数，原来的余数作为新的除数，重复步骤 1。

口诀：以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数。

4. 扩展欧几里得算法 (Extended Euclidean Algorithm)

这是辗转相除法的扩展版本，不仅能求出 $gcd(a, b)$，还能找到整数 $x$ 和 $y$，满足贝祖等式 (Bézout’s identity)：

$$ ax + by = gcd(a, b) $$

在 RSA 中的应用

在 RSA 中，扩展欧几里得算法主要用于求解模逆元（即计算私钥 $d$）。

• 场景：已知公钥指数 $e$ 和欧拉函数 $\phi(n)$，求 $d$ 使得 $e \times d \equiv 1 \pmod{\phi(n)}$。
• 这等价于求解 $ed - k\phi(n) = 1$ 中的 $d$（即贝祖等式中的系数）。

5. 计算实例 (RSA 场景)

假设 $e = 7$，$\phi(n) = 192$。

第一步：验证互素 (普通辗转相除)

目标：计算 $gcd(192, 7)$

1. $192 \div 7 = 27 \dots 3$ $\Rightarrow 192 = 27 \times 7 + 3$
2. $7 \div 3 = 2 \dots 1$ $\Rightarrow 7 = 2 \times 3 + 1$
3. $3 \div 1 = 3 \dots 0$ $\Rightarrow 3 = 3 \times 1 + 0$ 结果：余数为 0，上一行的余数 1 为 GCD。因为 $gcd=1$，所以互素。

第二步：求私钥 d (扩展辗转相除)

目标：求 $d$ 使得 $7d \equiv 1 \pmod{192}$。 利用第一步的式子进行逆向代入：

1. 由第 2 行得：$1 = 7 - 2 \times 3$

2. 由第 1 行得：$3 = 192 - 27 \times 7$

3. 代入消去 3：

   $$

1 = 7 - 2 \times (192 - 27 \times 7)

$$

$$

1 = 7 - 2 \times 192 + 54 \times 7

$$

$$

1 = 55 \times 7 - 2 \times 192

$$

4. 这意味着 $55 \times 7$ 除以 192 的余数是 1。 结果：私钥 $d = 55$。

---

相关链接：

• RSA
• 非对称密码学（Asymmetric-Encryption）