仿射密码求解

[!info] related notes

• 相关概念: 仿射密码, 密码学, euclidean-algorithm, modular-inverse

已知 $c \equiv pk_1+k_2 \pmod{26}$，两对明密文 $(p,c)=(5,23),(3,11)$，求合法仿射密钥。这里用 $p$ 表示明文字母数值，避免与模数混淆。

这是一道关于**仿射密码（Affine Cipher）**已知明文攻击的求解题目。我们需要根据给定的明文和密文对，求解加密密钥 $k_1$ 和 $k_2$。

1. 建立方程组

根据题目给出的加密公式 $c \equiv pk_1 + k_2 \pmod{26}$ 以及两组明密文对 $(p, c)$：

1. 当 $p=5$ 时，$c=23$
2. 当 $p=3$ 时，$c=11$

我们可以列出以下模运算方程组：

$$ \begin{cases} 5k_1 + k_2 \equiv 23 \pmod{26} \quad \text{------ (1)} \ 3k_1 + k_2 \equiv 11 \pmod{26} \quad \text{------ (2)} \end{cases} $$

2. 求解 $k_1$

用方程 (1) 减去方程 (2) 消去 $k_2$：

$$ (5k_1 + k_2) - (3k_1 + k_2) \equiv 23 - 11 \pmod{26} $$

$$ 2k_1 \equiv 12 \pmod{26} $$

解这个同余方程。因为模数 26 和系数 2 有最大公约数 $\gcd(2, 26) = 2$，我们需要小心处理：

$$ 2k_1 = 12 + 26n \quad (n \text{ 为整数}) $$

两边同时除以 2：

$$ k_1 = 6 + 13n $$

所以在模 26 的范围内，$k_1$ 有两个可能的解：

• 当 $n$ 是偶数时，$k_1 = 6$
• 当 $n$ 是奇数时，$k_1 = 6 + 13 = 19$

关键判断：

在仿射密码中，为了保证加密是一一对应的（即可以唯一解密），乘法密钥 $k_1$ 必须与模数 26 互素（即 $\gcd(k_1, 26) = 1$）。

• 若 $k_1 = 6$，$\gcd(6, 26) = 2 \neq 1$，这会导致无法正常解密，因此舍去。
• 若 $k_1 = 19$，$\gcd(19, 26) = 1$，符合加密要求，保留。

因此，$k_1 = 19$。

3. 求解 $k_2$

将 $k_1 = 19$ 代入方程 (2)（或者方程 1）：

$$ 3(19) + k_2 \equiv 11 \pmod{26} $$

$$ 57 + k_2 \equiv 11 \pmod{26} $$

对 57 取模 26（$57 = 2 \times 26 + 5$）：

$$ 5 + k_2 \equiv 11 \pmod{26} $$

$$ k_2 \equiv 11 - 5 \pmod{26} $$

$$ k_2 = 6 $$

4. 验证

我们将 $k_1=19, k_2=6$ 代入方程 (1) 验证：

$$ 5(19) + 6 = 95 + 6 = 101 $$

$$ 101 \pmod{26} = 101 - (3 \times 26) = 101 - 78 = 23 $$

另一对也满足 $3 \times 19+6=63\equiv11\pmod{26}$；且 $\gcd(19,26)=1$，因此它是本题唯一合法密钥。

---

最终答案

$k_1 = 19$， $k_2 = 6$

通用检查

消元后若得到 $da\equiv r\pmod m$，令 $g=\gcd(d,m)$：

• 若 $g$ 不整除 $r$，没有解。
• 否则先除以 $g$，模数也要变成 $m/g$；回到模 $m$ 后有 $g$ 个候选剩余类。
• 逐个检查 $\gcd(a,m)=1$，再回代求 $b$，最后核对全部已知对应关系。

本题的两个同余解只有一个合法，不代表任何两对明密文都唯一确定仿射密钥。