最近给学生讲密码学入门讲完凯撒密码和维吉尼亚密码之后我开始琢磨怎么让他们理解“分组加密”这个概念。教材里的AES数学门槛太高学生听完基本只能记住名字。后来我翻出Hill密码——这家伙1929年就被提出来了用的数学工具却简单到只需要一门线性代数而它已经是正经八百的“分组密码”雏形了。这篇文章就是我用C从零实现Hill密码加解密算法的完整记录源码可以直接编译运行你也可以把整个实现当成理解现代分组密码的一块跳板。Hill密码最迷人的地方在于它把加密从“逐字替换”推进到了“整组变换”一组字母组成的向量乘上一个密钥矩阵得到一组新的字母。这个“乘矩阵”的动作放在今天来看就是分组密码里的线性扩散层只不过现代算法把它做得更复杂、更抗攻击罢了。我会从数学原理讲到C实现再把我实际调试中踩过的坑一并列出来最后给出完整的源码和测试用例。1. 为什么在AES时代还要研究Hill密码从线性代数到分组密码的桥梁1.1 分组密码的“活化石”1929年美国数学家Lester S. Hill提出了一种基于矩阵乘法的加密方案这就是Hill密码。它的历史地位很特殊在它之前古典密码大多是单表替换或多表替换本质上是“逐字符”操作Hill密码第一次把明文分成固定大小的组每一组整体参与运算这就是后来DES、AES这些分组密码的基本形态。学密码学的人有个共识直接啃AES的数学原理容易劝退。AES里的S盒、轮密钥、列混合混在一起新手很难分清哪一步是混淆、哪一步是扩散。但Hill密码清清楚楚地把“扩散”这一步摆在你面前——矩阵乘法把一组内各个字母的信息搅在一起任何一个输入字母的变化会影响整组中多个输出字母。这种“牵一发而动全身”的效果就是密码学里说的雪崩效应雏形。搞懂了Hill密码再回头看AES的列混合层你会觉得亲切得多。1.2 学Hill密码到底在学什么从实用角度说Hill密码早就退出了实际加密场景它的密钥空间有限而且线性结构导致它扛不住已知明文攻击。但作为教学工具和C练手项目它有三个不可替代的价值。第一它能让你直观感受“密钥”不是一串神秘数字而是一个有数学结构的对象。密钥矩阵的选择有约束条件不是随便填个数就能用这会让你意识到密码方案和底层数学是深度绑定的。第二实现它需要同时用到线性代数、数论和C工程能力。求行列式、算伴随矩阵、用扩展欧几里得求模逆元、处理负数取模、设计输入过滤逻辑——每个环节都有实实在在的坑练完一遍比刷十道算法题收获都大。第三它是理解“可逆变换”用于解密的核心思想。加密时做一次线性变换解密就是做逆变换。这个思想在后面学RSA模幂运算的可逆性、ElGamal离散对数时都会反复出现。我推荐所有想认真学密码学或者想练C工程能力的读者把这套代码自己实现一遍。2. 数学原理拆解加密是矩阵乘法解密就是找逆矩阵2.1 编码方案为什么必须用0到25Hill密码的第一步是把字母转换成数字。常见两种映射方式A0B1……Z25或者A1B2……Z26。我见过很多初学者用后者理由是“人类习惯从1开始数数”。但用1到26会埋下一个致命隐患加密时是模26运算26对26取模等于0加密出来的字母对应的数字可能是0也可能是26解密时你根本分不清它原本是A还是Z。所以正确做法是A0B1……Z25。这样每个字母和模26的剩余类一一对应没有任何歧义。实现时就是简单的char - A反变换就是char A干净利落。2.2 加密与解密的矩阵表达假设你选了一个n乘n的密钥矩阵K把明文每n个字母分为一组每组看成一个n维列向量P那么加密就是做矩阵乘法C K × P (mod 26)C是密文向量。解密时你需要一个逆矩阵K^(-1)使得K^(-1) × K等于单位矩阵然后P K^(-1) × C (mod 26)这个式子看起来简单但在模26的世界里逆矩阵的存在是有条件的密钥矩阵的行列式det(K)必须和模数26互质也就是gcd(det(K), 26) 1。为什么因为在模26意义下行列式的逆元存在当且仅当det(K)和26互质。如果行列式等于13和26不互质你在模26下找不到任何一个整数x能让det(K) × x ≡ 1 (mod 26)逆矩阵就不复存在密文也就无法正确还原。这正是一个常见的坑很多人随手填一个矩阵就加密没有检查行列式条件加密过程“成功”了解密却得到一堆乱码。后面我会在代码里加上自动检测。2.3 一个完整的手算例子2x2矩阵加解密全过程为了避免“看了公式还是不会”的问题这里手算一个完整例子。密钥矩阵取K [3 3; 2 5]先验证行列式det 3×5 - 3×2 15 - 6 9gcd(9, 26) 1合法。用经典明文HILL来试。H7I8L11L11两个一组第一组 [7, 8]密文第1个 (3×7 3×8) mod 26 (21 24) mod 26 45 mod 26 19对应字母T密文第2个 (2×7 5×8) mod 26 (14 40) mod 26 54 mod 26 2对应字母C第二组 [11, 11]密文第1个 (3×11 3×11) mod 26 66 mod 26 14对应字母O密文第2个 (2×11 5×11) mod 26 77 mod 26 25对应字母Z密文就是TCOZ。现在求逆矩阵来解密。2x2矩阵的伴随矩阵是[d, -b; -c, a]所以K的伴随矩阵是[5, -3; -2, 3]。9在模26下的逆元是3因为3×927≡1 mod 26。于是K^(-1) 3 × [5, -3; -2, 3] [15, -9; -6, 9]全部模26后 [15, 17; 20, 9]用它解第一组密文[19, 2]明文第1个 (15×19 17×2) mod 26 (285 34) mod 26 319 mod 26 7对应H明文第2个 (20×19 9×2) mod 26 (380 18) mod 26 398 mod 26 8对应I第二组[14, 25]明文第1个 (15×14 17×25) mod 26 635 mod 26 11对应L明文第2个 (20×14 9×25) mod 26 505 mod 26 11对应L还原出HILL完美闭环。手算一遍你就会发现实现时的核心难点全在逆矩阵上加密反而只是两个循环的事。3. C实现的三个关键设计决策写代码前先想清楚3.1 矩阵与分组的数据结构选择C里表示矩阵有很多方式二维数组、vector嵌套、一维数组手动索引。我最终选了vectorvectorint理由有三个。第一运行时维度灵活。密钥矩阵是2x2还是3x3得等用户输入才知道静态二维数组必须提前定死最大维度硬编码的味道太重。第二嵌套vector初始化方便vectorvectorint(n, vectorint(n, 0))一行就能生成n乘n的零矩阵。第三内存管理安全不需要手写new和delete避免泄漏。分组向量我用vectorint长度等于矩阵维度。实际编码时要注意encrypt函数里输入字符串会被过滤成大写字母串然后按size大小切成若干块每一块就是一个向量。块数不足时补X字符这一步在后面会细说。3.2 求逆算法选型伴随矩阵法vs高斯消元模26下的逆矩阵最经典的两种求法伴随矩阵法和高斯消元法。我选的是伴随矩阵法因为它对2x2和3x3矩阵特别友好。伴随矩阵法的公式是K^(-1) (1/det(K)) × adj(K)其中adj(K)是伴随矩阵也就是余子式矩阵的转置。对2x2来说这个公式非常工整对3x3来说每个余子式只是一个二阶行列式代码量不大。整个过程是确定性的公式运算不需要考虑行交换、主元选择之类的问题。高斯消元法在n很大的时候更通用但代码要复杂得多——你要在高斯消元每一步都做模运算、处理列主元为零的情况、记录行交换的符号变化。杀鸡用牛刀还会增加调试成本。我写这类教学代码的原则是在覆盖需求的前提下选最容易读、最不容易错的方案。将来如果确实需要扩展到更高维度再考虑换算法不迟。3.3 模运算的负数陷阱与统一处理这是我在调试中踩得最深的一个坑单独拿出来强调。C的%运算符对负数的行为和数学意义上的取模不一致-3 % 26在C里的结果是-3不是23。而伴随矩阵里几乎必然出现负数比如前面例子里的-9、-6如果不做处理算出来的逆矩阵全是错的。我的处理方法是写一个统一的口诀(value % mod mod) % mod。任何需要取模的结果都先对mod取一次余加上mod保证为正再取一次余这样就把C的“余数”行为修正成了数学的“模”行为。这个代码在multiply和inverseKey里都用了一处都不能少。另一个隐蔽的问题是int会不会溢出n3时矩阵元素、向量元素、乘积求和理论最大值是3×25×25×2546875远不到int上限。所以这个项目里int足够不需要long long。但如果你自己扩展成更大的矩阵就要重新评估类型。4. 完整源码与逐段解析从扩展欧几里得到加解密主流程4.1 完整源码下面这段代码就是整个Hill密码加解密程序我把它组织成HillCipher类独立辅助函数的结构。你在任何支持C11的编译器上都能直接编译运行比如Visual Studio、g、Clang。#include iostream #include vector #include string #include cctype using namespace std; // 最大公约数用于判断行列式与26是否互质 int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } // 扩展欧几里得求 a 在模 m 下的乘法逆元 // 前提gcd(a, m) 1 int modInverse(int a, int m) { a (a % m m) % m; int m0 m; int y 0, x 1; if (m 1) return 0; while (a 1) { int q a / m; int t m; m a % m; a t; t y; y x - q * y; x t; } if (x 0) x m0; return x; } class HillCipher { private: vectorvectorint key; // 密钥矩阵 int size; // 矩阵维度 int mod 26; // 模数 // 计算行列式当前支持2x2和3x3 int determinant(const vectorvectorint mat) { if (size 2) { return mat[0][0] * mat[1][1] - mat[0][1] * mat[1][0]; } else if (size 3) { return mat[0][0] * (mat[1][1] * mat[2][2] - mat[1][2] * mat[2][1]) - mat[0][1] * (mat[1][0] * mat[2][2] - mat[1][2] * mat[2][0]) mat[0][2] * (mat[1][0] * mat[2][1] - mat[1][1] * mat[2][0]); } return 0; } // 余子式矩阵 vectorvectorint cofactor(const vectorvectorint mat) { vectorvectorint cof(size, vectorint(size, 0)); if (size 2) { cof[0][0] mat[1][1]; cof[0][1] -mat[1][0]; cof[1][0] -mat[0][1]; cof[1][1] mat[0][0]; } else if (size 3) { for (int i 0; i 3; i) { for (int j 0; j 3; j) { vectorvectorint sub(2, vectorint(2)); int r 0, c 0; for (int p 0; p 3; p) { if (p i) continue; c 0; for (int q 0; q 3; q) { if (q j) continue; sub[r][c] mat[p][q]; c; } r; } int det2 sub[0][0] * sub[1][1] - sub[0][1] * sub[1][0]; cof[i][j] ((i j) % 2 0) ? det2 : -det2; } } } return cof; } // 伴随矩阵 余子式矩阵的转置 vectorvectorint adjugate(const vectorvectorint mat) { vectorvectorint cof cofactor(mat); vectorvectorint adj(size, vectorint(size, 0)); for (int i 0; i size; i) for (int j 0; j size; j) adj[i][j] cof[j][i]; return adj; } // 矩阵与向量乘法结果逐项模26 vectorint multiply(const vectorvectorint mat, const vectorint vec) { vectorint res(size, 0); for (int i 0; i size; i) { int sum 0; for (int j 0; j size; j) { sum mat[i][j] * vec[j]; } res[i] (sum % mod mod) % mod; } return res; } public: HillCipher(const vectorvectorint k) : key(k) { size (int)k.size(); } // 检查密钥矩阵是否可用于Hill密码 bool isKeyValid() { int det (determinant(key) % mod mod) % mod; return gcd(det, mod) 1; } // 模26意义下的逆矩阵 vectorvectorint inverseKey() { int det (determinant(key) % mod mod) % mod; int invDet modInverse(det, mod); vectorvectorint adj adjugate(key); vectorvectorint inv(size, vectorint(size, 0)); for (int i 0; i size; i) for (int j 0; j size; j) inv[i][j] (adj[i][j] * invDet % mod mod) % mod; return inv; } // 加密输入任意字符串只处理英文字母输出大写密文 string encrypt(const string plaintext) { string text; for (char c : plaintext) { if (isalpha(c)) text toupper(c); } while (text.size() % size ! 0) text X; string cipher; for (int i 0; i (int)text.size(); i size) { vectorint vec(size); for (int j 0; j size; j) vec[j] text[i j] - A; vectorint res multiply(key, vec); for (int j 0; j size; j) cipher char(res[j] A); } return cipher; } // 解密输入密文输出大写明文 string decrypt(const string ciphertext) { string text; for (char c : ciphertext) { if (isalpha(c)) text toupper(c); } while (text.size() % size ! 0) text X; vectorvectorint inv inverseKey(); string plain; for (int i 0; i (int)text.size(); i size) { vectorint vec(size); for (int j 0; j size; j) vec[j] text[i j] - A; vectorint res multiply(inv, vec); for (int j 0; j size; j) plain char(res[j] A); } return plain; } }; int main() { cout Hill 密码加解密 endl; cout 请输入密钥矩阵维度 n2 或 3; int n; cin n; if (n ! 2 n ! 3) { cout 目前仅支持 2x2 或 3x3 密钥矩阵。 endl; return 1; } vectorvectorint key(n, vectorint(n)); cout 请输入 n x n 密钥矩阵每行 n 个整数空格分隔 endl; for (int i 0; i n; i) for (int j 0; j n; j) cin key[i][j]; HillCipher cipher(key); if (!cipher.isKeyValid()) { cout 密钥矩阵不可用行列式必须与26互质否则无法解密。 endl; return 1; } cout 请选择1-加密 2-解密; int choice; cin choice; cin.ignore(); if (choice 1) { cout 请输入明文; string plain; getline(cin, plain); cout 密文 cipher.encrypt(plain) endl; } else if (choice 2) { cout 请输入密文; string cipherText; getline(cin, cipherText); cout 明文 cipher.decrypt(cipherText) endl; } else { cout 无效选择。 endl; } return 0; }4.2 核心函数逐段解析扩展欧几里得、逆矩阵、加解密整个程序最关键的函数是modInverse。它用扩展欧几里得算法求模逆元我在迭代过程中用x和y记录贝祖等式的系数。算法的原理一句话概括gcd(a, m) ax my当gcd为1时x就是a在模m下的逆元。代码里那个while (a 1)循环就是欧几里得辗转相除的迭代版最终返回值归一化到[0, m)区间。inverseKey函数把逆矩阵的组装分成了三步和数学公式一一对应第一计算行列式的模逆元invDet第二通过cofactor和adjugate得到伴随矩阵第三伴随矩阵每个元素乘以invDet模26后填入结果矩阵。只要isKeyValid已经确认行列式和26互质modInverse一定能求得有效结果不需要再处理异常分支。encrypt和decrypt的结构几乎对称。区别只在乘的矩阵不同一个是密钥矩阵一个是逆矩阵。我特意把输入过滤逻辑写成一样因为加解密时都可能混入空格、标点和数字——用户传进来的一段话往往不是纯净的大写字母串。过滤加填充之后两个函数各自按size分组逐组乘矩阵、取模、映射回字母。这种对称性是密码学里的一个优点加解密算法可以共用大量代码只在密钥选择上分叉。4.3 main函数交互设计从一次运行说起main函数的流程我设计成四个阶段读维度、读密钥、验证密钥合法性、选择加解密。我的建议是先验证再干活而不是等解密时静默出错。程序会在密钥行列式与26不互质时立刻拒绝运行并且给出清晰的中文提示这在教学演示时很有用——学生能当场看到某种矩阵为什么不能当密钥。输入上有个细节选择操作后必须用cin.ignore()吃掉缓冲区里的换行符否则后面的getline会直接读到一个空行。这个坑几乎每个C初学者都会碰到我在代码里特意写上了。如果你要把这个程序扩展成一个带命令行参数的版本还可以考虑用-e和-d两个flag指定模式后期版本迭代时会更方便。5. 实测演示与边界情况这些坑不处理一定会翻车5.1 正常测试用例2x2与3x3的加解密结果按上面源码编译后我做了两组实测。第一组用2x2密钥矩阵[3 3; 2 5]输入明文HILL程序输出密文TCOZ解密后回到HILL。和手算结果完全一致。第二组测试3x3场景密钥矩阵取[3 0 0; 0 5 0; 0 0 7]。这是一个对角阵行列式是3×5×7105gcd(105, 26)1合法。明文HILL因为明文长度4不能被3整除自动补一个X实际加密的是HILLX。输出的密文和解密结果都正常但你会在解密明文末尾看到多出来的X。这正好引出下一节要讲的填充字符问题。5.2 不可逆密钥不加防护的后果如果你去掉程序里的isKeyValid检查直接用一个行列式和26不互质的矩阵跑解密比如密钥矩阵[2 0; 0 2]行列式4gcd(4, 26)2。加密得到的密文还像模像样但解密时modInverse(4, 26)会进入循环后退出返回的值根本没有意义最终解密结果是一堆乱码。更糟的是某些行列式值会让modInverse里的循环行为异常甚至可能让程序长时间空转。我调试时就把一个行列式为13的矩阵输入结果解密出来的东西完全看不出原文的痕迹。所以我的建议是在加密开始前就验证密钥把错误掐死在源头。源码里保留isKeyValid正是为了这一点。5.3 填充字符的结果陷阱Hill密码要求明文长度必须是密钥维度的整数倍不足时补字符。我在代码里用X代表25做填充。这个方案有一个天然缺陷解密结果里你无法区分哪些X是填充的、哪些是明文本身自带的。比如用户明文就是HELLO3x3矩阵加密时会补成HELLOX解密回来就变成了HELLOX。如果用户不记得自己输入了什么可能误以为解密有误。我在教学演示时会告诉学生这个算法本身不携带原始长度信息。工程上如果要解决可以在加密前记录原始明文长度或者采用可逆的填充方案比如PKCS#7那种按填充字节数填充的规则但那样的填充值范围是1到size和字母表映射又要重新设计。作为教学版本我选择X是为了直观简单这个取舍需要自己心里有数。5.4 输入过滤与空字符串问题用户输入的字符串几乎不可能是标准的全大写字母串——可能有空格、逗号、数字、甚至全角字符。我的encrypt和decrypt里统一做了过滤只保留isalpha判定的英文字母其余全部丢弃。这样Hello, World!经过滤后是HELLOWORLD输出密文时也更干净。但要注意如果用户输入的全是非字母字符过滤后得到空字符串程序会直接返回空密文。我在教学中遇到过学生输了个全角标点串程序一点动静都没有一脸懵。代码里对空串做一次防御性判断会更友好不过在没有消息长度字段的协议里空串本身也算一个合法输入所以源码中我保留了原样留给读者按需扩展。6. 安全性评估与扩展方向教学价值之外的思考6.1 为什么它不能用于真实加密Hill密码有一个致命弱点完全线性。给定一对明密文就能列出线性方程收集足够多的明密文对密钥矩阵就能被直接解出来。这就是所谓的已知明文攻击攻击难度极低。此外它还有两个明显的问题第一密钥空间非常有限2x2矩阵加26字母的密钥数量大约只有三十多万种可能暴力穷举完全可行第二明文的统计特征会被泄露。矩阵乘法是线性变换字母频率的分布形态虽然在具体数值上变了但并没有做S盒那样的非线性混淆攻击者结合频率分析仍有很大的破解空间。所以我的结论很明确Hill密码只能当教学和练习用的模型绝不能用在实际加密通信中。如果有人拿着一个当年学过的Hill密码实现跟你说“用这个传密码吧”一定要拒绝。6.2 从Hill密码到现代分组密码的扩展思路Hill密码的价值在于让你看清分组密码的骨架。如果你想在这个基础上继续深入我建议做几个方向上的扩展。第一个方向是加混淆层。仿照AES的S盒在矩阵乘法前后加入非线性替换表。这样即使攻击者拿到线性变换的规律也无法直接建立明文到密文的线性方程组。第二个方向是增大密钥矩阵维度但伴随矩阵法的代码就不再适用了你可以切换到高斯消元法顺带练一下模运算下的消元实现。第三个方向是引入轮结构一轮Hill加密后对结果做一次移位或异或再进入下一轮把单元密文和整体密文搅在一起。这不就是简化版的分组密码原型么。如果要做成完整的教学项目你还可以给它加上文件读写功能、统计字母频率的工具、已知明文攻击的破解脚本这一套做下来对密码学基础的理解会扎实很多。最后分享一个我个人的实践体会给这段代码写文档的时候我把每个函数和数学公式的对应关系都标注了一遍虽然工作量大了点但以后再翻出来复习时五分钟就能回忆起全部思路。你要是也在学密码学建议别偷懒自己在源码里把cofactor和伴随矩阵的关系补上注释——这个“翻译”的过程本身就是最好的学习方式。
