1、信息与计算科学 0902 班任龙杰090701031古典密码学之希尔密码希尔密码（Hill Password）是运用基本矩阵论原理的替换密码，由 Lester S. Hill 在 1929 年发明。每个字母当作 26 进制数字： A=0, B=1, C=2. 一串字母当成n 维向量，跟一个 nn 的矩阵相乘，再将得出的结果模 26。注意用作加密的矩阵（即密匙） 在mathbb_n必须是可逆的，否则就不可能译码。只有矩阵的行列式和 26 互质，才是可逆的。安全性：希尔密码不是足够安全的, 如今已被证实, 关于希尔密码的破解不在本文范围内, 有兴趣的朋友可以研读相关书籍以了解相关破译方法。希尔密码
2、所需要掌握的前置知识：1. 线性代数基础知识；2. 初等数论基础知识；约定：1. 希尔密码常使用 Z26 字母表 , 在此贴中, 我们也以 Z26 最为字母表进行讲解.在附带源码中有两种字母表选择。2. 大家都知道最小的质数是 2, 1 既不是质数也不是合数. 在此我们定义 1对任何质数的模逆为其本身。3. 因为对于任意质数 n, 有: 1*1 % n = 1 的. 也应该是很好理解的。相关概念：线性代数中的逆矩阵: 在线性代数中, 大家都知道,对于一个 n 阶矩阵 M , 如果存在一个 n 阶矩阵 N ,使得 M * N = E (其中: E 为 n 阶单位矩阵), 则称矩阵 N 为矩阵 M
3、 的逆矩阵, 并记为 M-1. 比如 2 阶矩阵 M = 3,6 , 则很容易得知其逆矩阵 : 2,7 M-1 = 7/9, -2/3 -2/9, 1/3 。关于这个逆矩阵是如何计算出的, 通常的有两种方法: 一是使用伴随矩阵, 通过计算行列式得到. 所用公式为: M-1 = M* / D . (其中 M*为 M 的伴随矩阵, D 为 M 的行列式的值) 二是通过增广矩阵, 在 M 右侧附加一个 n 阶单位矩阵, 再通过初等变换将增广矩阵的左侧变换为一个 n 阶单位矩阵, 这时右侧便是所求的逆矩阵。示例：密文：l 11 242 44 121 22 154 132 44 209 154 154
4、220 187 22 121 220 11 解答：根据第一项，全部除以 11, 因为 l 是第 12 个字母，即 l=12-k，得k=1 按 a=0 z=25,列出字母 WELCOME TO OUR CLUB 希尔密码 加密 例如：密钥(密码学中好象没有“密匙“一词)矩阵 1 3 0 2 明文：HI THERE 去空格，2 个字母一组，根据字母表顺序换成矩阵数值如下，末尾的 E 为填充字元： HI TH ER EE 8 20 5 5 9 8 18 5 HI 经过矩阵运算转换为 IS，具体算法参考下面的说明： |1 3| 8 e1*8+3*9=35 MOD26=9 =I |0 2| 9 e0*8
5、+2*9=18 MOD26=18=S 用同样的方法把“HI THERE”转换为密文“IS RPGJTJ”，注意明文中的两个 E 分别变为密文中的 G 和 T。 解密 解密时，必须先算出密钥的逆矩阵，然后再根据加密的过程做逆运算。 逆矩阵算法公式： |A B| = 1/(AD-BC) * | D -B| |C D| |-C A| 例如密钥矩阵= |1 7| |0 3| AD-BC=1*3-0*7=3 3*X=1 mod26 所以 X=9 因此 |1 7| 的逆矩阵为： 9 * |3 -7| |0 3| |0 1| 假设密文为“FOAOESWO” FO AO ES WO 6 1 5 23 15 15 19 15 9* |3 -7| | 6| = 9*(3*6-7*15)=-783 mod26 = 23=W |0 1| |15| = 9*(0*6+1*15)= 135 mod26 = 5 =E 所以密文“FOAOESWO”的明文为“WEREDONE”
