仿射密码
使用 E(x) = (ax + b) mod 26 进行编码和解码。输入 a 和 b,工具会检查 a 是否可以被还原、求出它的模逆元,并逐个字母演算;如果您不知道密钥,解码模式会尝试全部 312 个密钥,并按结果看起来有多像英语来排序。
必须与 26 没有公因数——请从下面 12 个值中选择一个。
任何整数;会被对 26 取模。
此密钥的演算过程
编码:E(x) = (5x + 8) mod 26
解码:D(y) = 21(y − 8) mod 26
21 是 5 的逆元,因为 5 × 21 = 105,比 26 的某个倍数多 1。
每个有效的 a 及其逆元
| a | 1 | 3 | 5 | 7 | 9 | 11 | 15 | 17 | 19 | 21 | 23 | 25 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a⁻¹ | 1 | 9 | 21 | 15 | 3 | 19 | 7 | 23 | 11 | 5 | 17 | 25 |
逐个字母演算——前 12 个字母
| 字母 | x | a·x + b | mod 26 | 结果 |
|---|---|---|---|---|
| A | 0 | 8 | 8 | I |
| F | 5 | 33 | 7 | H |
| F | 5 | 33 | 7 | H |
| I | 8 | 48 | 22 | W |
| N | 13 | 73 | 21 | V |
| E | 4 | 28 | 2 | C |
| C | 2 | 18 | 18 | S |
| I | 8 | 48 | 22 | W |
| P | 15 | 83 | 5 | F |
| H | 7 | 43 | 17 | R |
| E | 4 | 28 | 2 | C |
| R | 17 | 93 | 15 | P |
如何使用仿射密码
- 1. 选择模式并输入文本。 编码把明文变成密文;解码则反向还原。
- 2. 设置密钥。 输入 a(乘数)和 b(移位)。a 必须是输入框下方列出的 12 个值之一——点击其中一个即可使用。b 可以是任何整数,它会被对 26 取模。
- 3. 查看演算过程。 结果下方的面板会给出您这个密钥的两个公式、a 的逆元,以及每个字母的算术过程。
- 4. 没有密钥?全部试一遍。 在解码模式下,勾选尝试全部 312 个密钥。结果会按字母计数与英语的接近程度排序,点击使用此密钥即可载入其中任意一个。
仿射密码公式
把字母从零开始编号:A = 0,B = 1 … Z = 25。加密一个字母 x 时,先乘以 a,再加 b,然后取除以 26 后的余数:E(x) = (a·x + b) mod 26。解密一个字母 y 时,按相反顺序撤销这些步骤——先减去 b,再乘以 a⁻¹,即 a 的模逆元:D(y) = a⁻¹·(y − b) mod 26。逆元是这样一个数:它与 a 相乘后余数为 1。对于 a = 5,它是 21,因为 5 × 21 = 105 = 4 × 26 + 1。
为什么只有 12 个 a 的取值可用
乘以 a 绝不能让两个字母落到同一个位置,否则解码就会有两个答案。只要 a 与 26 = 2 × 13 有公因数,就会出现这种情况。例如 a = 2 时,A(0)和 N(13)都会落在 b 上,因为 2 × 13 = 26,即 0 mod 26。所以 a 必须是奇数,而且不能是 13,剩下的就是下面这十二个数——恰好是在模 26 下存在逆元的那些数。b 有 26 种选择,因此一共有 12 × 26 = 312 个密钥,其中一个(a = 1,b = 0)不会改变任何内容。
| a | 1 | 3 | 5 | 7 | 9 | 11 | 15 | 17 | 19 | 21 | 23 | 25 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a⁻¹ | 1 | 9 | 21 | 15 | 3 | 19 | 7 | 23 | 11 | 5 | 17 | 25 |
示例:a = 5,b = 8
当 a = 5、b = 8 时,AFFINE CIPHER 会被加密为 IHHWVC SWFRCP——这就是工具的示例。AFFINE 各个字母的演算过程如下:
| 字母 | x | 5x + 8 | mod 26 | 结果 |
|---|---|---|---|---|
| A | 0 | 8 | 8 | I |
| F | 5 | 33 | 7 | H |
| I | 8 | 48 | 22 | W |
| N | 13 | 73 | 21 | V |
| E | 4 | 28 | 2 | C |
解码时,工具会乘以 a⁻¹ = 21。I(8)变成 21 × (8 − 8) = 0,即 A;H(7)变成 21 × (7 − 8) = −21,即模 26 后的 5,也就是 F。这一步出现负数是正常的——mod 26 的意思只是不断加上或减去 26,直到数落在 0 到 25 之间。
有两种大家熟悉的密码其实是仿射密码的特例。当 a = 1 时,公式就是 x + b,即移位 b 的凯撒移位;当 a = 25 且 b = 25 时,它就是埃特巴什密码,即把字母表倒过来读。
如何破解仿射密码
只有 311 个密钥会真正改变内容,最直接的攻击方式就是把它们全试一遍,暴力破解选项只需不到一秒钟就能完成。难点在于认出正确答案,所以工具会用卡方检验把每个结果的字母计数与典型英语进行比较并排序。对于一句话或更长的文本,正确的密钥会排在最前;对于很短的短语则未必——仅对 IHHWVC SWFRCP 而言,真正的密钥 (5, 8) 排在第四位——所以请往下浏览列表,而不要只相信第一行。
密码分析者可以借助代数做得更好。仿射密码是单表替换——每个字母总是变成同一个字母——因此频率分析能提示哪些密文字母代表 E 和 T,两次这样的猜测就能列出两个方程。在上面的密钥下,E(4)变成 C(2),T(19)变成 Z(25),所以 4a + b ≡ 2 且 19a + b ≡ 25(mod 26)。用第二式减去第一式得 15a ≡ 23;两边乘以 7(15 的逆元),得 a ≡ 161 ≡ 5,然后 b ≡ 2 − 20 ≡ 8。已知明文中的两个字母就能还原整个密钥。
常见问题
- 什么是仿射密码?
- 一种替换密码,它把每个字母的编号 x 变成 (a·x + b) mod 26,也就是每个字母先乘以 a,再移位 b。密钥是数对 (a, b)。由于同一个字母总是变成同一个密文字母,它属于单表密码——是凯撒密码看起来更强的“亲戚”,但并不更难破解。
- 为什么 a 必须与 26 互质?
- 解码时要乘以 a 在模 26 下的逆元,而只有当 a 与 26 没有公因数时,这个逆元才存在。如果两者有公因数,两个不同的字母会被加密成同一个字母,信息就无法确定地还原。这就排除了所有偶数和 13,剩下 1、3、5、7、9、11、15、17、19、21、23 和 25。
- 如何求 a 的模逆元?
- 找出 1 到 25 之间这样一个数:它与 a 相乘后除以 26 余数为 1。对于 a = 7,它是 15,因为 7 × 15 = 105 = 4 × 26 + 1。只有十二种情况,直接从上面的表格里读最快;对于较大的模数,可以用扩展欧几里得算法直接求出逆元。
- 仿射密码有多少个密钥?
- 312 个——a 有十二种选择,乘以 b 的 26 种选择。其中一个(a = 1,b = 0)不会改变文本,所以实际起加密作用的是 311 个。这个数量少到一个下午就能手工试遍每个密钥,用计算机则是一瞬间的事。
- 凯撒密码是一种仿射密码吗?
- 是的。令 a = 1,公式就变成 x + b,即移位 b 的凯撒移位;ROT13 就是 a = 1、b = 13。埃特巴什密码也是仿射密码,即 a = 25、b = 25。这两者都在暴力破解所尝试的 312 个密钥之中。
- 仿射密码安全吗?
- 不安全。它经不起暴力破解和频率分析,而且只要知道两个明文字母就能破解,正如上面的代数推导所示。它是练习模运算的绝佳材料,但凡是重要的内容,都需要使用现代加密技术。