RSA初探 - Rock's log

加密过程#

甲向乙发送信息“中”。首先，汉字“中”通过 UTF-8 编码为 [e4 b8 ad]，转换为 10 进制为 [228, 184, 173]。

使用乙的公钥 $(n, e) = (4757, 101)$ 进行加密。由于被加密的数字必须小于 $n$ ，我们将“中”字拆分为三个字节 [228, 184, 173]，分别加密。

假设 $a$ 为明文， $b$ 为密文，加密公式如下：

a^e \pmod{n} = b

对 [228, 184, 173] 的加密计算如下：

228^{101} \pmod{4757} = 4296 \\ 184^{101} \pmod{4757} = 2458 \\ 173^{101} \pmod{4757} = 3263

加密后的密文为 [4296, 2458, 3263]。没有私钥，无法从中解密出原始字节。

乙收到密文 [4296, 2458, 3263]，并用自己的私钥 $(n, d) = (4757, 1601)$ 进行解密。

解密公式如下：

b^d \pmod{n} = a

解密计算如下：

4296^{1601} \pmod{4757} = 228 \\ 2458^{1601} \pmod{4757} = 184 \\ 3263^{1601} \pmod{4757} = 173

解密后得到 [228, 184, 173]，再按 UTF-8 解码为汉字“中”，解密完成。

$P$ 和 $Q$ 越大，安全性越高。例如 $P = 67$ ， $Q = 71$ 。计算 $n = P \times Q = 4757$ 。 $n$ 的二进制表示为 1001010010101，共 13 位。实际应用中常使用 1024 位或 2048 位。

$\phi(n)$ 表示小于 $n$ 且与 $n$ 互质的正整数的个数。对于 $n = P \times Q$ （ $P, Q$ 为质数），有：

\phi(n) = (P - 1)(Q - 1)

本例中 $\phi(n) = (67 - 1)(71 - 1) = 66 \times 70 = 4620$ 。记 $m = \phi(n) = 4620$ 。

条件是 $1 < e < m$ ，且 $e$ 与 $m$ 互质（即 $\gcd(e, m) = 1$ ）。随机选择 $e = 101$ 。（注意 $e \ne m - 1 = 4619$ ）。

$d$ 必须满足 $(e \times d) \pmod{m} = 1$ 。这等价于求解二元一次方程：

e \times x - m \times y = 1

代入 $e=101, m=4620$ ：

101x - 4620y = 1

使用扩展欧几里得算法求解，得到 $(x, y) = (1601, 35)$ 。因此 $d = 1601$ 。

至此，密钥对生成完毕。不同的 $e$ 会生成不同的 $d$ ，从而生成不同的密钥对。

RSA 的核心基于以下数学原理：

a^{ed} \equiv a \pmod{\phi(n)}

同时，在密钥选择中需要满足不出现以下情况：

e^2 \equiv 1 \pmod{\phi(n)}