第一次在密码学课里看到“希尔密码”这几个字时我的第一反应是这不就是把矩阵乘法包装成加密吗后来真正动手实现“基于字母表编码的希尔加解密”才发现事情远没有看上去那么轻松——字母映射、矩阵取模、逆矩阵求解、负数模运算每一个环节都有暗坑。这篇文章想把整条链路重新走一遍从字母表编码开始到密钥矩阵的合法性判断再到手写实现和实际踩坑全部用大白话讲清楚让正在学希尔密码、准备做相关课程设计或者只是好奇古典密码原理的人少走点弯路。1. 希尔密码的原理坐标系字母表编码与线性变换如何握手1.1 先把“字母”翻译成“数字”一张编码表就够了所有基于字母表编码的希尔加解密第一步几乎都是同一件事把字母和数字绑定。最常见的做法是把 A 到 Z 按顺序编码成 0 到 25也就是 A0、B1、C2……一直到 Z25。这张表是整个体系的起点加密和解密都必须严格使用同一套映射。举个例子后面要反复用到的几个字母字母编码字母编码A0N13B1O14C2P15D3Q16E4R17F5S18G6T19H7U20I8V21L11W22M12Z25为什么选 0 到 25而不是 1 到 26原因很简单后面所有运算都要取模 26用 0 到 25 的取值范围时取模结果能自动落回同一张编码表里不需要再做一次偏移修正。你当然可以设计出一套 1 到 26 的编码表但那样每次取模后都要额外处理 26 变 0 的问题纯属给自己找麻烦。这个看似微不足道的决定实际影响着后续每一行代码和每一步手算。如果你想把空格、标点也纳入编码范围可以把字母表扩成 0 到 26 甚至更大。但标题既然说的是“基于字母表编码”我们就先锁定最经典的 26 个英文字母。后面我会专门讲扩大字母表会带来什么额外约束。1.2 加密不是替换而是“矩阵乘法 取模”古典密码里凯撒密码是单个字母的移位维吉尼亚密码是 key 驱动的多表替换。它们有一个共同特点每次只处理一个字母字符之间没有数学关联。希尔密码完全换了一种思路它把 n 个字母拼成一个向量再用一个 n×n 的密钥矩阵去乘这个向量从而实现“一组字母一起被打乱”。用数学语言描述就是取密钥矩阵 K它是 n×n 阶矩阵把明文连续拆成若干个长度为 n 的分块每个分块写成列向量 P加密计算C K·P mod 26解密计算P K⁻¹·C mod 26。这里的“mod 26”不是一个可有可无的尾巴而是整个运算的核心。因为矩阵乘法会把数字放大比如 19×15 这种中间结果早就超出字母表范围了必须通过取模把每个结果拉回到 0 到 25 之间才能重新对应到一个英文字母。换句话说希尔密码本质上是在模 26 的整数环上做线性变换。这种“一次处理一个块”的方式和现代分组密码的思路已经非常接近了。只不过现代分组密码在分组之后会引入大量非线性替换和置换而希尔密码把所有变换都限制在线性矩阵运算里。正是这种线性性埋下了它后来被轻易攻破的伏笔。1.3 为什么非要绕进模 26 的算术世界很多人第一次看到 mod 26 时会产生疑问直接在实数域上算矩阵乘法不是更简单吗问题在于只算乘法不取模密文数字会无限膨胀而且解密时你无法保证逆矩阵乘回去的结果能还原成原来的字母。取模让整个体系变成了一个封闭集合输入是 0 到 25输出也一定是 0 到 25。更重要的是取模让“逆矩阵”这个概念发生了微妙变化。在实数域里只要行列式不等于 0矩阵就有逆。但在模 26 的世界里行列式等于 0 当然不行行列式与 26 不互质也不行。比如行列式是 2那么求这个行列式的模逆元时需要找到一个整数 x 使得 2x ≡ 1 mod 26而这是不可能的因为 2 和 26 不互质。这也正是 26 这个数字最“麻烦”的地方26 2 × 13它不是质数所以希尔密码对密钥矩阵的要求非常苛刻。密钥矩阵的行列式必须同时避开 2 的倍数和 13 的倍数。理解了这一点你就理解了希尔密码设计中真正核心的约束条件不是矩阵维度越高越安全而是你的矩阵在被 26 取模之后必须仍然可逆。2. 手动走一遍 2×2 希尔密码的完整加解密流程2.1 选定密钥矩阵并检查是否合法为了完整展示希尔密码的工作过程我选一个经典的小矩阵K [[3, 3], [2, 5]]这是一个 2×2 矩阵所以每轮加密处理两个字母。先算行列式det(K) 3×5 - 3×2 15 - 6 9然后检查 9 和 26 是否互质。gcd(9, 26) 1满足条件。这说明这个矩阵在模 26 下有逆矩阵可以用于解密。这里建议所有第一次接触希尔密码的朋友都老老实实把行列式和最大公约数算一遍。我曾经为了省事直接拿一个 det2 的矩阵跑代码结果加密很顺解密彻底玩完输出一堆乱码。后来才发现根源就是行列式与 26 不互质逆矩阵根本不存在。2.2 加密过程明文分块、逐块变换用明文“HILL”来演示。先把字母转成数字H7, I8, L11, L11因为密钥矩阵是 2×2所以把明文按两个字母一组拆分第一组是 [7, 8]第二组是 [11, 11]。第一组向量 P₁ [7, 8]^T计算C₁ K·P₁ [[3, 3], [2, 5]]·[7, 8]展开得到第一个元素3×7 3×8 21 24 4545 mod 26 19第二个元素2×7 5×8 14 40 5454 mod 26 2。所以 C₁ [19, 2]查表得到 19T2C第一组密文是“TC”。第二组 P₂ [11, 11]^T计算C₂ [[3, 3], [2, 5]]·[11, 11]展开得到第一个元素3×11 3×11 33 33 6666 mod 26 14第二个元素2×11 5×11 22 55 7777 mod 26 25。所以 C₂ [14, 25]14O25Z第二组密文是“OZ”。最终明文“HILL”被加密成“TCOZ”。2.3 解密过程模逆矩阵与回代验算解密必须先求出 K 在模 26 下的逆矩阵。对 2×2 矩阵公式是K⁻¹ det(K)⁻¹ × adj(K)其中 det(K)9det(K)⁻¹ 是 9 在模 26 下的逆元也就是找 x 满足 9x ≡ 1 mod 26。因为 9×327≡1所以 det(K)⁻¹ 3。adj(K) 是伴随矩阵把主对角线交换、副对角线取负adj(K) [[5, -3], [-2, 3]]于是K⁻¹ 3 × [[5, -3], [-2, 3]] mod 26逐项计算3×5153×(-3)-9-9 mod 26 173×(-2)-6-6 mod 26 203×39。所以 K⁻¹ [[15, 17], [20, 9]]。验证一下 K·K⁻¹ 是否等于单位矩阵。第一行第一列3×153×20105105 mod 261第一行第二列3×173×97878 mod 260。第二行第一列2×155×20130130 mod 260第二行第二列2×175×97979 mod 261。结果确实是单位矩阵逆矩阵求对了。现在用逆矩阵解密密文“TCOZ”“TC”对应 [19, 2]“OZ”对应 [14, 25]。对第一组P₁ [[15, 17], [20, 9]]·[19, 2]第一个元素15×1917×228534319319 mod 26 7对应 H第二个元素20×199×238018398398 mod 26 8对应 I。完美恢复出“HI”。对第二组P₂ [[15, 17], [20, 9]]·[14, 25]第一个元素15×1417×25210425635635 mod 26 11对应 L第二个元素20×149×25280225505505 mod 26 11对应 L。恢复出“LL”。整个流程闭合HILL → TCOZ → HILL。手算一遍后希尔密码就不再是抽象公式了你对“为什么需要逆矩阵”“为什么行列式必须与 26 互质”会有非常具体的体感。3. 密钥矩阵的生死线行列式、可逆性与弱密钥3.1 行列式与 26 不互质时会发生什么假设你选了一个行列式为 0 的矩阵比如 K[[2,2],[1,1]]。这个矩阵把两个不同的明文向量 [1,0] 和 [0,1] 都映射到同一个结果加密函数根本不是单射解密时你根本不知道原始明文是哪一个。行列式不为 0 但 gcd 不为 1 的情况更隐蔽。比如 det2gcd(2,26)2矩阵在普通数域里可逆但模 26 下不可逆。原因很简单求逆矩阵需要 det 的逆元而 2 在模 26 下没有逆元因为你找不到整数 x 让 2x 等于 1 mod 26。此时即使你强行算出某个“伪逆矩阵”回代结果也会出现多个候选明文无法唯一还原。从数论角度看262×13所以行列式只要同时不被 2 和 13 整除矩阵就可逆。这也是为什么很多教材建议初学者直接选质数模比如模 29 或 31。如果是质数模只需要行列式不为 0 这一条就够了判断起来简单很多。用 26 的话就得额外多做一步 gcd 检查。3.2 模 n 下的逆矩阵求法2×2 的逆矩阵用手算很方便用伴随矩阵公式就行。3×3 甚至更大的矩阵伴随矩阵展开的运算量会迅速变大而且计算过程中全是负数取模时非常容易出错。我更推荐用高斯-约旦消元法在模 n 下对增广矩阵 [A|I] 做初等行变换把左边变成单位矩阵后右边自然就是 A⁻¹。具体步骤是把 A 和同阶单位矩阵拼成一个 n×2n 的增广矩阵从第 0 列开始找一个当前行及以下不为 0 的主元交换两行使主元落到对角位置用模逆元把主元变成 1用这个主元所在行消去其他所有行的当前列不只是下面行上面行也消直接消成对角单位阵如果某一列从当前行到末尾全部是 0说明矩阵不可逆。这个过程只涉及整数加减乘和模运算完全避免浮点数。我第一次用浮点求逆矩阵时遇到类似 0.9999999 的东西判断是否整除 26 简直是一场灾难。改用纯整数高斯消元后问题彻底消失。3.3 弱密钥、平凡密钥与密钥空间估算并不是所有可逆矩阵都适合当密钥。单位矩阵会把明文原封不动输出显然不合格。还有一些特殊矩阵比如只在对角线上有值、其余位置为 0 的对角矩阵它会让每个字母独立变换退化成一个单表替换完全丢失了希尔密码分组混合的意义。密钥空间方面2×2 模 26 可逆矩阵的总数是 157248 个。这个数字听起来不小但在现代计算机面前根本不值一提枚举一次只需要毫秒级时间。提升矩阵阶数能大幅增加暴力破解难度但希尔密码最致命的问题不是暴力破解而是它的线性结构。只要拿到 n 组线性无关的“明文-密文”对就能列出一个线性方程组直接从明密文对里解出密钥矩阵 K。这在前面的 2×2 例子里特别明显随便找两组不重复的明密文对比如 HILL → TCOZ 中的两组向量列两个方程组K 就被唯一确定了。这种已知明文攻击的效率高得吓人所以现代密码学里几乎不可能允许加密变换是纯线性的。4. 自己动手实现Python 从零写出 Hill 加解密4.1 环境与整体设计我的实现只用 Python 标准库没有引入 numpy。原因有三个numpy 的 linalg.inv 和 det 都是浮点运算对“是否能被 26 整除”这种判断不友好numpy 的整数取模、求逆行为在某些版本里和 Python 原生的 int 不一致容易踩坑手写一遍对理解算法特别有帮助代码量也不大。整体设计分成三层编码表层、模数运算层、矩阵运算层最后用 hill_encrypt 和 hill_decrypt 做入口。这样分层以后后面想换 3×3 矩阵或扩大字母表只需要改少量代码。4.2 模数运算与扩展欧几里得最容易被负数坑的地方求模逆元是希尔密码实现里最要紧的函数。扩展欧几里得算法是标准解法def extended_gcd(a, b): if b 0: return a, 1, 0 g, x1, y1 extended_gcd(b, a % b) x, y y1, x1 - (a // b) * y1 return g, x, y def mod_inverse(a, m): g, x, _ extended_gcd(a, m) if g ! 1: raise ValueError(a 在模 m 下不存在逆元) return x % mPython 的x % m天然返回非负余数比如-3 % 26的结果是 23这正好是我们需要的。但很多其他语言里负数的取模结果也会是负数所以写代码时最好统一风格所有进入取模的表达式要么先转成非负整数要么依赖 Python 的模运算特性别写一半留一半。我以前在这上面栽过跟头手动算伴随矩阵时有 -9直接当负数用了结果后面全乱套。4.3 矩阵乘法与模逆矩阵实现矩阵乘法写成通用的三层循环结果里的每个元素都直接取模def matrix_mult_mod(A, B, mod): m, n, p len(A), len(A[0]), len(B[0]) res [[0] * p for _ in range(m)] for i in range(m): for j in range(p): s 0 for k in range(n): s A[i][k] * B[k][j] res[i][j] s % mod return res求逆矩阵用高斯-约旦消元实现在整数环上完成def matrix_inverse_mod(A, mod): n len(A) aug [A[i][:] [1 if i j else 0 for j in range(n)] for i in range(n)] for col in range(n): pivot None for row in range(col, n): if aug[row][col] % mod ! 0: pivot row break if pivot is None: raise ValueError(矩阵不可逆) aug[col], aug[pivot] aug[pivot], aug[col] inv mod_inverse(aug[col][col], mod) for j in range(2 * n): aug[col][j] (aug[col][j] * inv) % mod for row in range(n): if row col: continue factor aug[row][col] for j in range(2 * n): aug[row][j] (aug[row][j] - factor * aug[col][j]) % mod return [aug[i][n:] for i in range(n)]这段代码的核心逻辑是每一列都找一个非零主元先用模逆元把主元变成 1再用它消掉其他所有行的这一列。最后左半边变成单位阵右半边就是逆矩阵。和伴随矩阵公式相比这个方法对 3×3、4×4 同样适用代码也不用改。4.4 加密、解密函数和完整测试预处理逻辑统一处理大小写、非字母字符和填充import re def prepare_text(text, block_size): text re.sub(r[^A-Za-z], , text).upper() while len(text) % block_size ! 0: text X return text def text_to_indices(text): return [ord(c) - ord(A) for c in text] def indices_to_text(indices): return .join(chr(i ord(A)) for i in indices)主体加密函数和解密函数可以共用一个矩阵乘法逻辑区别只在于加密用密钥矩阵解密用密钥矩阵的逆矩阵def hill_encrypt(plaintext, key_matrix, mod26): n len(key_matrix) text prepare_text(plaintext, n) nums text_to_indices(text) cipher_nums [] for i in range(0, len(nums), n): block [[nums[i j]] for j in range(n)] cipher_block matrix_mult_mod(key_matrix, block, mod) cipher_nums.extend([cipher_block[j][0] for j in range(n)]) return indices_to_text(cipher_nums) def hill_decrypt(ciphertext, key_matrix, mod26): n len(key_matrix) inv_key matrix_inverse_mod(key_matrix, mod) nums text_to_indices(ciphertext) plain_nums [] for i in range(0, len(nums), n): block [[nums[i j]] for j in range(n)] plain_block matrix_mult_mod(inv_key, block, mod) plain_nums.extend([plain_block[j][0] for j in range(n)]) return indices_to_text(plain_nums)用前面手算的例子验证K [[3, 3], [2, 5]] print(hill_encrypt(HILL, K)) # 输出 TCOZ print(hill_decrypt(TCOZ, K)) # 输出 HILL我实际运行的结果完全正确。这里有个小提醒填充字符选 X 是可以的但如果你的明文本身以 X 结尾解密之后你会难以分辨哪个 X 是原文、哪个 X 是填充。严谨的做法是在密文里附带原始明文长度或者在预处理时记录填充数量解密后再剔除。课程设计里这一步经常被忽略但恰恰是它最影响可用性。5. 我在实际测试中踩过的坑和总结的经验5.1 明文字母表与密钥矩阵维度不匹配希尔密码有个容易忽略的硬性限制密钥矩阵的阶数决定了每个分块的长度。你选了 2×2 矩阵明文就要两个字母一组选了 3×3 矩阵明文就要三个字母一组。如果明文长度不是块长度的整数倍必须填充。我第一次做 3×3 测试时密文长度总是对不上排查半天才发现是明文长度除以 3 有余数填充字符被我自己在导入阶段丢掉了。另一个常见问题是密文里出现非法字符。如果你的加密函数把空格、逗号、数字也放进去了那说明编码表没有严格遵守 0 到 25。希尔密码只认识英文字母预处理时必须把所有非字母字符全部过滤掉。比如“HELLO, WORLD!”会先被变成“HELLOWORLD”第二个字母合成分块时是“HE LL OW OR LD”一个字符都不多。5.2 同分组内容重复会导致密文模式泄露因为每个分块独立加密如果一段明文里出现完全相同的两个字母组它们在密文里也会对应相同的结果。这在某些场景下会暴露原文结构。比如一个很长的文本里反复出现“TH”在 2×2 希尔密码下每个位置上的“TH”加密后都完全相同攻击者可以通过观察重复模式猜出部分单词边界。这其实和分组密码里的 ECB 模式弱点如出一辙。每次加密同一个明文块永远得到同一个密文块这种确定性在古典密码学时代还能接受在现代安全模型里是不可接受的。如果你做课程展示可以主动展示这个弱点然后和带有反馈机制的分组模式做对比会显得你对密码系统有更深的理解。5.3 用这个实现搞教学和课设的几条建议我强烈建议初学者不要直接用 numpy 的现成矩阵求逆哪怕只是为了交作业。原因不是 numpy 不好而是你需要在调试中真正理解“模逆元”是怎么回事。用我前面给的纯整数高斯消元法每一行每一步都是可追踪、可打印的出了问题一眼能定位。想增加一点难度和实用感可以尝试把字母表扩到 27 或 29。比如加入空格变成 27 个符号密钥矩阵的行列式与 27 互质的要求又不一样了计算规则也随之变化。如果扩到 95 个可打印 ASCII 字符还能对带标点的句子直接加密但要注意 955×19依然有互质约束。这些扩展本质上都还是“基于字母表编码的希尔加解密”核心套路没变。对中文文本理论上你也可以给每个常用汉字建一张编码表再套同样的矩阵运算。真正上手后你会发现最大的麻烦不是矩阵运算而是汉字数量太多编码表本身就成了额外负担。偶尔做个小 Demo 可以但如果目标是可靠加密用成熟的现代加密方案要稳妥得多。我自己跑通这套流程之后最大的收获不是学会了一个 Python 脚本而是真正理解了加密算法为什么要同时追求“可逆性”和“非线性”。希尔密码把线性代数的美和尴尬同时展现得一清二楚它能让你快速上手加解密也让你记住光靠矩阵乘法的对称世界在上世纪就被密码分析者看穿了。最后分享一个调试小习惯我会故意把密文改错一个字符比如把 TCOZ 改成 TCOY看程序能不能准确报错或输出明显异常这能提前发现一堆边缘问题。希尔密码看着简单真正写到能交出去的水平沉下心来把每一步捋清楚还是能花掉一下午的。