Hill密码由美国数学家Lester S. Hill于1929年发明，是一种基于线性代数的经典加密方法。其核心原理是利用矩阵乘法在模26的整数环上进行加密变换。

加密公式：C = K · P (mod 26)，其中K是密钥矩阵，P是明文向量，C是密文向量。

解密公式：P = K^-1 · C (mod 26)，需要密钥矩阵K在模26下可逆（即行列式与26互质）。

Hill密码是现代分组密码的雏形，它首次将代数结构引入密码学，对后续密码算法的发展产生了深远影响。

解密需要使用密钥矩阵的模逆矩阵K^-1。矩阵在模26下可逆的充要条件是其行列式与模数26互质（即gcd(det(K), 26) = 1）。

由于26 = 2 × 13，因此行列式mod 26不能是偶数，也不能是13的倍数。符合条件的行列式值包括：1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25（共12个可能值）。

如果行列式与26不互质，则无法找到模逆矩阵，加密后的信息将无法解密，这就是密钥矩阵必须满足的数学约束。

Hill密码对于唯密文攻击具有一定抵抗力，但在已知明文攻击面前非常脆弱。如果攻击者获得了足够数量的明文-密文对（对于n×n矩阵需要n²对），就可以通过解线性方程组来恢复密钥矩阵。

在现代密码学标准下，Hill密码不再被认为是安全的，因为它是一种线性加密方法，无法抵抗统计分析。但它仍然是密码学教学中理解分组加密和线性变换概念的优秀范例。

Hill密码要求明文按矩阵维度分组。对于2×2矩阵，每组2个字母；对于3×3矩阵，每组3个字母。如果明文长度不是维度的倍数，需要进行填充（padding）。

常用的填充方案是使用字母'X'填充不足的位置（因为X在英文中较少出现）。解密后，如果末尾有连续的X，很可能是填充字符。在实际应用中，也可以使用PKCS风格的填充方案。

在模26运算中，一个数a的模逆元a^-1满足：a × a^-1 ≡ 1 (mod 26)。

计算模逆元使用扩展欧几里得算法。由于26较小，也可以通过暴力枚举（1到25逐一验证）。例如9在模26下的逆元是3，因为9×3=27≡1 (mod 26)。

对于2×2密钥矩阵，逆矩阵计算公式为：K^-1 = det^-1 × [[d, -b], [-c, a]] (mod 26)，其中det^-1是行列式的模逆元。