希尔密码：密码学中的矩阵加密与线性代数

简介

大多数古典密码每次只处理一个字母。凯撒密码对每个字母独立进行移位。仿射密码对每个字母单独应用线性公式。维吉尼亚密码虽然使用多字符密钥，但仍然每次处理明文中的一个字母——密钥只是决定在每个位置应用哪种移位。

希尔密码打破了这一模式。它由数学家 Lester S. Hill 于 1929 年发明，是第一种将多个字母作为单一代数单元同时加密的实用密码。希尔密码不再用标量运算变换单个字母，而是使用矩阵乘法对字母块进行变换。这是一次概念上的飞跃，将线性代数引入密码学工具箱，并预示了主导现代加密的分组密码设计。

希尔密码按现代标准并不安全——它容易受到已知明文攻击，即使攻击者只获得少量对应的明文和密文，也无法提供有效保护。但其数学优雅性及其作为矩阵加密技术先驱的地位，使其成为最具教学价值的古典密码之一。

使用我们免费的希尔密码工具，在阅读本指南的同时用矩阵密钥加密和解密消息。

Lester S. Hill 与多字母替换加密的起源

这位数学家

Lester Sanders Hill（1891—1961）是一位美国数学家，职业生涯大部分时间在纽约市亨特学院度过。Hill 的学术兴趣横跨代数、数论和组合数学，他以数学家的视角进入了一个长期由语言学家、军官和业余爱好者主导的领域。

20 世纪 20 年代，Hill 开始研究如何构造能够抵抗频率分析的密码——频率分析是一种已有数百年历史的技术，通过分析密文中的字母频率来推断底层明文。Hill 认识到，频率分析之所以有效，是因为大多数密码逐个处理字母，保留了源语言的统计特征。他的解决方案是将字母分组加密，使得单个字母的频率因同一组中多个字母之间的相互作用而被混淆。

1929 年的论文

Hill 于 1929 年在《美国数学月刊》上发表了他的密码，题为《代数字母表中的密码学》。论文提出了一个完整的基于模 26 矩阵乘法的加密系统，包括加密、解密以及密钥矩阵有效所需的数学条件。

该论文以其数学严谨性著称。以往密码发明者以程序性语言描述其系统（"取第一个字母，将其移位……"），而 Hill 则将其密码呈现为环 Z₂₆ 上向量的正式代数运算。这种方法远超时代，预示了密码学代数形式化体系的建立——而这一体系直到二十世纪后半叶才成为标准。

实用化尝试

Hill 尝试通过机器实现将其密码商业化。他设计了一种装置，利用相互连接的齿轮和轮盘机械地执行矩阵乘法。然而，该机器结构复杂、造价昂贵且容易出错，始终未能获得商业成功。希尔密码主要停留在理论层面，直到计算机的出现使矩阵运算变得轻而易举。

密码学中的矩阵乘法基础

在学习希尔密码示例之前，有必要简要回顾所涉及的矩阵运算。

向量与矩阵

向量是一组有序数字。在希尔密码中，n 个字母的明文块被表示为一个 n 维列向量，其中每个整数是字母的数值（A=0，B=1，……，Z=25）。

矩阵是数字的矩形排列。在希尔密码中，加密密钥是一个 n×n 的整数方阵。

矩阵与向量相乘

将 n×n 矩阵乘以 n×1 向量，计算矩阵每行与向量的点积。以 2x2 为例：

| a  b |   | x |   | ax + by |
| c  d | × | y | = | cx + dy |

结果向量的每个元素是矩阵某行与向量对应元素乘积之和。

模运算归约

在希尔密码中，所有运算均在模 26 下进行。计算结果向量的每个元素后，将其对 26 取模，得到 0 到 25 之间的值，再映射回对应字母。

完整的 2x2 加密示例

用 2x2 密钥矩阵加密消息"SHORT"。使用 2x2 矩阵时，每次处理两个字母。

第一步：选择密钥矩阵

设密钥矩阵 K 为：

K = | 3  3 |
    | 2  5 |

使用此矩阵前，必须验证其有效性——密钥约束部分将详细说明。此处先确认：det(K) = 3(5) - 3(2) = 15 - 6 = 9，且 gcd(9, 26) = 1，因此该矩阵在模 26 下可逆。

第二步：将明文转换为数字

S = 18, H = 7, O = 14, R = 17, T = 19

使用 2x2 矩阵，将明文分成两个一组：(S, H)、(O, R)、(T, ?)。最后一组不完整，需用填充字母补齐。以 X（= 23）作为填充：(T, X)。

明文向量为：

P₁ = | 18 |    P₂ = | 14 |    P₃ = | 19 |
     |  7 |         | 17 |         | 23 |

第三步：加密每个块

块 1：(S, H)

| 3  3 |   | 18 |   | 3×18 + 3×7 |   | 54 + 21 |   | 75 |
| 2  5 | × |  7 | = | 2×18 + 5×7 | = | 36 + 35 | = | 71 |

模 26 归约：75 mod 26 = 23，71 mod 26 = 19。

结果：23 = X，19 = T。第一对密文：XT。

块 2：(O, R)

| 3  3 |   | 14 |   | 3×14 + 3×17 |   | 42 + 51 |   | 93 |
| 2  5 | × | 17 | = | 2×14 + 5×17 | = | 28 + 85 | = | 113 |

模 26 归约：93 mod 26 = 15，113 mod 26 = 9。

结果：15 = P，9 = J。第二对密文：PJ。

块 3：(T, X)

| 3  3 |   | 19 |   | 3×19 + 3×23 |   | 57 + 69 |   | 126 |
| 2  5 | × | 23 | = | 2×19 + 5×23 | = | 38 + 115 | = | 153 |

模 26 归约：126 mod 26 = 22，153 mod 26 = 23。

结果：22 = W，23 = X。第三对密文：WX。

最终密文

SHORT 加密结果为 XTPJWX。

注意，明文中两次出现的字母 T（一次在"SHORT"中，一次在填充字母中）并未产生相同的密文字母。这正是多字母替换加密的根本优势：同一字母根据其相邻字母的不同而产生不同的加密结果。

完整的 3x3 加密示例

更大的密钥矩阵能提供更强的加密效果。以下是一个使用 3x3 矩阵的示例。

密钥矩阵

K = | 6  24  1 |
    | 13 16 10 |
    | 20 17 15 |

行列式为：6(16×15 - 10×17) - 24(13×15 - 10×20) + 1(13×17 - 16×20) = 6(240 - 170) - 24(195 - 200) + 1(221 - 320) = 6(70) - 24(-5) + 1(-99) = 420 + 120 - 99 = 441。

441 mod 26 = 441 - 16(26) = 441 - 416 = 25。gcd(25, 26) = 1，因此该矩阵有效。

加密"ACT"

转换为数字：A=0，C=2，T=19。

| 6  24  1 |   | 0 |   | 6×0 + 24×2 + 1×19 |   | 0 + 48 + 19 |   | 67 |
| 13 16 10 | × | 2 | = | 13×0 + 16×2 + 10×19 | = | 0 + 32 + 190 | = | 222 |
| 20 17 15 |   | 19|   | 20×0 + 17×2 + 15×19 | = | 0 + 34 + 285 | = | 319 |

模 26 归约：67 mod 26 = 15，222 mod 26 = 14，319 mod 26 = 7。

结果：15 = P，14 = O，7 = H。密文：POH。

使用 3x3 矩阵时，每个密文字母依赖于三个明文字母，比 2x2 的情况提供了更强的扩散效果。

求逆矩阵用于解密

解密希尔密码消息需要在模运算（模 26）下求密钥矩阵的逆矩阵，这比求标量模逆要复杂得多。

解密公式

解密是加密的逆过程：

P = K⁻¹ × C (mod 26)

其中 K⁻¹ 是密钥矩阵 K 的模逆矩阵。

计算 2x2 矩阵的逆

对于 2x2 矩阵，逆矩阵公式为：

K = | a  b |       K⁻¹ = d⁻¹ × |  d  -b |   (mod 26)
    | c  d |                     | -c   a |

此处 d⁻¹ 指 det(K) mod 26 的模乘逆元（而非矩阵元素 d）。步骤如下：

计算行列式：det(K) = ad - bc
将行列式对 26 取模
求行列式在模 26 下的模乘逆元
构造伴随矩阵（交换对角元素，对角外元素取反）
将伴随矩阵乘以行列式的逆元，并将所有元素对 26 取模

工作示例：求 2x2 密钥的逆矩阵

密钥为 K = [[3, 3], [2, 5]]。

第一步：det(K) = 3(5) - 3(2) = 15 - 6 = 9。

第二步：9 mod 26 = 9。

第三步：求 9⁻¹ mod 26。需找 x 使得 9x ≡ 1 (mod 26)。验算：9×3 = 27 = 1 mod 26。故 9⁻¹ = 3。

第四步：伴随矩阵为：

|  5  -3 |
| -2   3 |

第五步：将每个元素乘以 3（行列式的逆元）并对 26 取模：

| 3×5    3×(-3) |   | 15  -9 |   | 15  17 |
| 3×(-2) 3×3    | = | -6   9 | = | 20   9 |

（负数转换：-9 mod 26 = 17，-6 mod 26 = 20。）

逆矩阵为：

K⁻¹ = | 15  17 |
      | 20   9 |

验证：解密"XT"

通过解密第一个密文块"XT"（X=23，T=19）来验证：

| 15  17 |   | 23 |   | 15×23 + 17×19 |   | 345 + 323 |   | 668 |
| 20   9 | × | 19 | = | 20×23 + 9×19  | = | 460 + 171 | = | 631 |

668 mod 26 = 668 - 25(26) = 668 - 650 = 18 = S。 631 mod 26 = 631 - 24(26) = 631 - 624 = 7 = H。

得到 SH——原始明文"SHORT"的第一对字母。解密验证正确。

密钥约束：为何行列式必须与 26 互质

希尔密码只有当密钥矩阵存在模逆矩阵时才能正常工作，而矩阵在模 26 下存在逆矩阵，当且仅当其行列式与 26 互质。

数学原因

矩阵求逆需要除以行列式。在模运算中，"除法"意味着乘以模乘逆元。整数 d 在模 26 下的模逆存在，当且仅当 gcd(d, 26) = 1。

由于 26 = 2×13，任何能被 2 或 13 整除的行列式都没有模逆元。这意味着以下行列式值无效：0、2、4、6、8、10、12、13、14、16、18、20、22、24（所有偶数加上 13）。

有效的行列式值为：1、3、5、7、9、11、15、17、19、21、23、25——与仿射密码中乘法密钥有效值完全相同的 12 个数。这并非巧合。两者的约束条件源于同一底层要求：在环 Z₂₆ 中的可逆性。

密钥无效时的情况

若行列式与 26 不互质，加密函数就不是双射——多个明文块会映射到同一密文块，导致解密不可能。这是矩阵形式下同一问题的推广，类似于仿射密码中乘法密钥与 26 有公因子时的情况。

统计有效的 2x2 密钥数量

希尔密码有多少个有效的 2x2 密钥矩阵？矩阵的四个元素各可取 0 到 25 中的任意值（各 26 种），共有 26⁴ = 456,976 个矩阵。其中约有 157,248 个矩阵的行列式与 26 互质，是有效的希尔密码密钥。这比仿射密码的 312 个密钥或凯撒密码的 26 个密钥要大得多。

对于 3x3 矩阵，有效密钥空间增长到约 16 亿——这是显著的提升，尽管按现代标准仍微不足道。

破解希尔密码：已知明文攻击

希尔密码最大的弱点是已知明文攻击。如果攻击者知道足够数量的明文及其对应密文，就能通过线性代数完全恢复密钥矩阵。

攻击原理（2x2 情形）

对于 2x2 希尔密码，攻击者需要两对明文-密文块。假设攻击者知道：

明文"TH"加密为"LP"
明文"EX"加密为"FQ"

转换为数字：T=19、H=7 加密为 L=11、P=15；E=4、X=23 加密为 F=5、Q=16。

加密方程为：

K × | 19 | = | 11 |  (mod 26)
    |  7 |   | 15 |

K × |  4 | = |  5 |  (mod 26)
    | 23 |   | 16 |

合并为矩阵形式：

K × | 19  4 | = | 11  5 |  (mod 26)
    |  7 23 |   | 15 16 |

设 P = [[19, 4], [7, 23]]，C = [[11, 5], [15, 16]]。

则 K = C × P⁻¹ (mod 26)。

计算 P⁻¹：det(P) = 19(23) - 4(7) = 437 - 28 = 409。409 mod 26 = 409 - 15(26) = 409 - 390 = 19。且 19⁻¹ mod 26 = 11（因为 19×11 = 209 = 8×26 + 1）。

P 的伴随矩阵为 [[23, -4], [-7, 19]]，模 26 后为 [[23, 22], [19, 19]]。

P⁻¹ = 11 × [[23, 22], [19, 19]] mod 26 = [[253, 242], [209, 209]] mod 26 = [[19, 8], [1, 1]]。

最终：K = C × P⁻¹ = [[11, 5], [15, 16]] × [[19, 8], [1, 1]] mod 26。

K = | 11×19 + 5×1    11×8 + 5×1  |  mod 26
    | 15×19 + 16×1   15×8 + 16×1 |

  = | 209 + 5    88 + 5  |  mod 26
    | 285 + 16   120 + 16|

  = | 214  93  |  mod 26
    | 301  136 |

  = |  6  15 |
    | 15   6 |

攻击者仅凭四个已知明文字母就恢复了完整的密钥矩阵。

安全影响

这种攻击具有毁灭性。实际上，攻击者往往知道或能猜到消息的某些部分——问候语、签名、日期、常用短语。即便只有两个已知单词，也能提供足够的明文-密文对来破解 2x2 希尔密码。对于 3x3 密码，三个块（九个字母）的已知明文就足够了。对于 n×n 密码，需要 n 个块（n² 个字母）。

这一弱点是线性密码的根本缺陷。普莱费尔密码同样加密二元组（字母对），但通过其非线性替换规则避免了这种特定攻击，尽管它有其自身的弱点。

优势与劣势

优势

抵抗单字母频率分析。 由于希尔密码将多个字母一起加密，单个密文字母的频率分布不直接对应明文字母的频率分布。在 2x2 希尔密码中，每个密文字母依赖于两个明文字母，从而遮蔽了单个字母的频率。在 3x3 密码中，遮蔽效果更强。

密钥空间大。 有效密钥矩阵的数量随矩阵尺寸迅速增长。2x2 希尔密码有超过 157,000 个有效密钥，3x3 密码有超过 16 亿个。尽管按现代标准这些数字很小，但相比早期古典密码已是显著进步。

数学优雅性。 希尔密码的代数结构便于形式化分析，并与现代数学密码学自然衔接。它是连接古典密码与现代分组密码的优秀教学桥梁。

劣势

容易受到已知明文攻击。 如上所示，少量已知明文即可完全破解密码。这是希尔密码的致命弱点。

线性性。 加密函数是线性变换，这意味着它保留了加法关系。若明文向量满足 P₁ + P₂ = P₃ (mod 26)，则对应密文向量满足 C₁ + C₂ = C₃ (mod 26)。这种线性性泄露了结构信息，可被老练的攻击者利用。

块结构漏洞。 相同的明文块加密后得到相同的密文块（与现代分组密码中电子密码本模式相同的弱点）。这使攻击者能够检测明文中的重复模式。

块间无扩散。 每个块独立加密，因此更改一个块中的字母只影响该块的密文。现代分组密码使用链接模式（CBC、CTR 等）在块之间建立依赖关系，防止此类模式泄露。

现代语境下的希尔密码

与现代分组密码的联系

希尔密码预示了现代分组密码设计中的几个核心思想：

分组加密。 希尔密码是第一种将固定大小的明文块作为单一单元加密的实用密码。每种现代分组密码（AES、DES、Blowfish 等）都以块为单位运算，只是使用了复杂得多的变换。

依赖密钥的线性变换。 AES 中的 MixColumns 步骤将状态矩阵的每一列在 GF(2⁸) 中与一个固定矩阵相乘，与希尔密码加密直接类比。区别在于 AES 将这一线性步骤与非线性替换（SubBytes 步骤）、密钥混合（AddRoundKey）和置换（ShiftRows）结合，跨越多轮。

可逆性要求。 正如希尔密码需要可逆密钥矩阵，AES 也要求每个组件操作可逆以实现解密。数学约束在细节上有所不同，但原则上完全一致。

与仿射密码的对比

仿射密码可视为 1x1 希尔密码的特例。仿射公式 E(x) = (ax + b) mod 26 等价于用 1x1"矩阵"[a] 乘以 1x1"向量"[x] 并加上 1x1"向量"[b]。希尔密码将其推广到更高维度，但两种密码共享同一数学基础——Z₂₆ 上的线性代数。

与普莱费尔密码的对比

普莱费尔密码同样加密二元组（字母对），但采用了根本不同的方法。希尔密码应用线性矩阵变换，而普莱费尔密码使用带密钥的 5x5 方格中的几何查找规则（同行、同列、矩形）。普莱费尔密码的非线性替换使其能够抵抗破解希尔密码的已知明文攻击，但其有效密钥空间小得多，且容易受到其他形式的分析。

波利比奥斯方阵提供了另一个比较基准：它将字母转换为 5x5 方格中的坐标对，但不做进一步变换。希尔密码的矩阵乘法可以看作是比波利比奥斯方阵的简单坐标表示更为彻底的字母值混淆。

常见问题

希尔密码应该使用什么尺寸的密钥矩阵？

出于教学目的，2x2 矩阵是理想选择，因为运算量手工可以处理。若需稍强的加密效果，3x3 矩阵能提供更好的扩散效果和更大的密钥空间。实际上，即使是大型希尔密码矩阵，由于已知明文漏洞也不具备真正的安全性，因此密钥矩阵尺寸的选择主要取决于教学目的。

在没有任何已知明文的情况下能破解希尔密码吗？

可以，但更困难。针对希尔密码的纯密文攻击通常使用二元组或三元组频率分析（分析字母对或字母三元组的频率，而非单个字母），结合爬山算法或遗传算法优化。对于短密文，这种方法可能不切实际；对于较长的文本，统计规律会变得足够强，足以引导自动求解器。

希尔密码为何使用模 26？

模数 26 对应英语字母表的 26 个字母（A=0 到 Z=25）。所有运算结果均对 26 取模，以确保映射回有效字母。对于不同大小的字母表，将使用不同的模数。某些实现将字母表扩展以包含数字和标点符号，使用更大的模数，如 37 或 95。

希尔密码能与其他技术结合以提高安全性吗？

可以。在希尔密码矩阵乘法之前或之后添加非线性替换步骤，可以通过消除已知明文攻击的可利用性来显著增强安全性。这本质上正是 AES 的做法：将线性混合步骤（类比于希尔密码）与非线性替换、密钥加法和置换相结合。希尔密码与简单替换密码的组合比任何单一密码都更难破解。

Lester Hill 是谁？

Lester Sanders Hill（1891—1961）是一位美国数学家，曾任纽约市亨特学院教授。他于 1929 年在《美国数学月刊》上发表了希尔密码，并花费数年尝试构建实用的机器实现。尽管该密码在其有生之年未被广泛采用，但它已成为密码学教育中的标准课题，如今被公认为线性代数应用于加密领域的开创性成果。

简介