仿射密码 (Affine Cipher)

[!info] related notes

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

1. 简介

仿射密码是一种单表代换密码。它将明文中的每个字母映射为数值，然后通过一个线性方程（仿射函数）计算出对应的密文数值，最后还原为字母。

它的数学形式为：$y = ax + b$，在密码学中通常在模 $m$（字母表长度）下进行。

关系：

• 当 $a = 1$ 时，退化为移位密码。
• 当 $b = 0$ 时，它退化为 乘法密码。

2. 数学模型

假设字母表大小为 $m$（通常英文为 26），将字母 A-Z 对应数字 0-25。

密钥

密钥由两个整数 $(a, b)$ 组成：

1. $a$ (乘数)：必须满足 $gcd(a, m) = 1$，即 $a$ 与 $m$ 互素。
   • 原因：只有 $a$ 与 $m$ 互素时，$a$ 才存在模逆元 $a^{-1}$，才能保证解密的唯一性。
2. $b$ (位移)：任意整数，$0 \le b < m$。

加密过程

$$ C = E(P) = (a \times P + b) \pmod m $$

• $P$: 明文 (Plaintext)
• $C$: 密文 (Ciphertext)

解密过程

$$ P = D(C) = a^{-1} \times (C - b) \pmod m $$

• $a^{-1}$: 是 $a$ 关于模 $m$ 的乘法逆元（即满足 $a \times a^{-1} \equiv 1 \pmod m$）。
• 注意：解密不是简单的除以 $a$，而是乘以 $a$ 的逆元。

3. 计算实例

设定：

• 模数 $m = 26$
• 密钥 $a = 5, b = 8$ (检查：$gcd(5, 26)=1$，满足条件)
• 明文：“HOT”

第一步：加密

1. H (7): $C = (5 \times 7 + 8) \pmod{26} = 43 \pmod{26} = 17 \rightarrow \textbf{R}$
2. O (14): $C = (5 \times 14 + 8) \pmod{26} = 78 \pmod{26} = 0 \rightarrow \textbf{A}$
3. T (19): $C = (5 \times 19 + 8) \pmod{26} = 103 \pmod{26} = 25 \rightarrow \textbf{Z}$

• 密文：“RAZ”

第二步：解密

首先计算 $a=5$ 的逆元 $a^{-1}$： 我们需要找一个数 $x$，使得 $5x \equiv 1 \pmod{26}$。 通过扩展欧几里得算法或试算，可知 $5 \times 21 = 105 = 4 \times 26 + 1$。 所以 $a^{-1} = 21$。

解密公式变为：$P = 21 \times (C - 8) \pmod{26}$

1. R (17): $P = 21 \times (17 - 8) = 21 \times 9 = 189$。 $189 \pmod{26} = 7 \rightarrow \textbf{H}$
2. A (0): $P = 21 \times (0 - 8) = 21 \times (-8) = -168$。 $-168 \pmod{26} = -168 + 7 \times 26 = -168 + 182 = 14 \rightarrow \textbf{O}$ (或者理解为 $0-8 = -8 \equiv 18 \pmod{26}$，然后 $21 \times 18 = 378 \equiv 14$)
3. Z (25): $P = 21 \times (25 - 8) = 21 \times 17 = 357$。 $357 \pmod{26} = 19 \rightarrow \textbf{T}$

• 明文：“HOT”

4. 安全性分析

• 密钥空间：
  • $a$ 的选择：26以内与26互素的数有 $\phi(26) = 12$ 个 (1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25)。
  • $b$ 的选择：26 种 (0-25)。
  • 总密钥空间：$12 \times 26 = 312$。
• 弱点：
  1. 密钥空间极小：计算机瞬间可以穷举破解。
  2. 保留了频率特征：作为单表代换密码，它无法隐藏明文的统计规律（如字母 E 出现的频率），容易被频率分析法破解。
  3. 已知明文攻击：两组对应关系可建立同余方程，但未必唯一确定密钥。相减得到 $(P_1-P_2)a \equiv C_1-C_2 \pmod m$；只有明文差与 $m$ 互素时才能直接乘逆元唯一解出 $a$，否则需枚举同余解并检查密钥合法性，见 affine-cipher-solving。

---

相关链接：

• euclidean-algorithm (用于求逆元)

此密码适合教学，不适合保护实际敏感数据。实现时应明确大小写、空格和标点的处理规则；本例只定义 A–Z 的映射。

学习检查

1. 为什么乘数必须与字母表大小互素？
2. 两对明密文为什么可能仍留下多个合法密钥？