仿射密码求解

[!info] related notes

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

已知加密公式c=mk1+k2(mod26)，明文密文对(m,c)=(5,23)和(3,11)，则k1=(），k2=(）。

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

1. 建立方程组

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

1. 当 $m=5$ 时，$c=23$
2. 当 $m=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 $$

验证通过，结果正确。

---

最终答案

$k_1 = 19$， $k_2 = 6$