模逆元
模逆元的定义、计算方法和在密码学中的作用。
模逆元
1. 什么是“模逆元”？
通俗类比：倒数（乘法逆元）
在普通的数学（实数域）中，如果我想“抵消”掉一个数字 3，我会乘以它的倒数 $\frac{1}{3}$：
$$ 3 \times \frac{1}{3} = 1 $$
在这个等式中，$\frac{1}{3}$ 就是 3 的逆元（用来让 3 变成 1）。
回到模运算世界
在密码学中，我们使用的是模运算（整数求余数），这里没有分数，也没有小数。一切都是整数。
那么，在模运算中，如何“抵消”掉一个数字呢？
定义： 如果在模 $\phi(n)$ 的世界里，两个整数 $e$ 和 $d$ 相乘，除以 $\phi(n)$ 后的余数是 1，那么 $d$ 就是 $e$ 的模逆元。
$$ e \times d \equiv 1 \pmod{\phi(n)} $$
举个例子：
假设模数是 10，数字是 3。我想找 3 的模逆元 $d$。
我们要找一个 $d$，使得 $3 \times d$ 除以 10 余 1。
- $d=1$: $3 \times 1 = 3$ (余3)
- $d=2$: $3 \times 2 = 6$ (余6)
- $d=3$: $3 \times 3 = 9$ (余9)
- …
- $d=7$: $3 \times 7 = 21$。 $21 \div 10 = 2$ 余 1。
所以，在模 10 的世界里，7 就是 3 的逆元（就像 1/3 是 3 的倒数一样）。
2. 为什么会出现模逆元？（为了“还原”）
在 RSA 中，加密和解密是一对相反的操作。
-
加密：把明文 $M$ 变成密文 $C$。
$$
C = M^e \pmod n
$$
这相当于把 $M$ 做了 $e$ 次乘法。- 解密：我们需要把 $C$ 变回 $M$。 我们不能直接用“开 $e$ 次方根”这种方法，因为模运算是离散的、乱序的，开方非常难算。 巧妙的思路： 我们不想开方，我们想继续乘！我想乘上某个数 $d$，让它“转了一圈”后，刚好回到原点（变回 $M$）。 即：
$$
C^d \equiv (M^e)^d \equiv M^{e \times d} \equiv M^1 \pmod n
$$ 为什么会出现模逆元？
因为我们需要 $M^{e \times d}$ 变回 $M^1$。 这就要求指数部分 $e \times d$ 必须起到“变成 1”的效果。 在欧拉定理的数学框架下（涉及到群论知识），这就要求：
$e \times d$ 在模 $\phi(n)$ 下必须等于 1。
所以，模逆元的出现，是为了在只允许整数乘法的情况下，实现“除法”或“还原”的效果。
3. 为什么私钥要使用模逆元？
这就涉及到了非对称密码学最精妙的设计——单向陷门函数。
A. 只有私钥能解密
- 公钥 ($e, n$) 是公开的。任何人都可以用 $e$ 对数据进行加密（$M^e$）。
- 想要解密，必须消除掉 $e$ 的影响。
- 根据数学原理，唯一能消除 $e$ 的方法，就是乘以它的模逆元 $d$。
- 所以，私钥必须是 $d$。拥有 $d$，你就能把混乱的密文瞬间还原成明文。
B. 为什么别人算不出 d？
既然 $d$ 是 $e$ 的逆元，大家知道 $e$，为什么算不出 $d$ 呢？
回顾公式： $$
e \times d \equiv 1 \pmod{\phi(n)}
$$
- 要计算 $d$，你必须知道模数 $\phi(n)$。
- 根据 PPT 中的公式：$\phi(n) = (p-1)(q-1)$。
- 这意味着，要算出 $\phi(n)$，你必须知道 $p$ 和 $q$。
- 但是，公钥里只有 $n$（$p \times q$ 的结果）。
- 大整数分解难题：从 $n$ 分解出 $p$ 和 $q$ 是极度困难的。
结论：
私钥使用模逆元 $d$，是因为它是解开公钥 $e$ 的唯一数学钥匙。而计算这个逆元的前提是拥有分解因子 $p$ 和 $q$，这正是私钥持有者的特权，也是 RSA 安全性的基石。
Related notes
- 相关概念: 仿射密码(Affine-Cipher)
- 相关概念: RSA
- 相关概念: 3DES