希尔密码（Hill Password）是运用基本矩阵论原理的替换密码，由Lester S. Hill在1929年发明。每个字母当作26进制数字：A=0, B=1, C=2... 一串字母当成n维向量，跟一个n×n的矩阵相乘，再将得出的结果模26。注意用作加密的矩阵（即密匙）在<math>\\mathbb_^n</math>必须是可逆的，否则就不可能译码。只有矩阵的行列式和26互质，才是可逆的。

Hill cipher

希尔密码(Hill Cipher)简介

安全性

希尔密码所需要掌握的前置知识

约定

相关概念

示例(例1 例2 例3 例4)

Hill cipher

三、Hill cipher（希尔密码）

Hill cipher是1929年提出的一种密码体制。

设d是一正整数，定义 。Hill cipher的主要思想是利用线性变换方法，不同的是这种变换是在 上运算。

例如：设d=2，每个明文单元使用 来表示，同样密文单元用 表示，具

体的加密中， 将被表示为 的线性组合。

如：

利用线性代数的知识，可得

这个运算在 上进行，即mod26，密钥K一般取一个m*m的矩阵，记为 。对明文 ，以 ，则加密算法为：

也可表示成 。

希尔密码(Hill Cipher)简介

希尔密码是基于矩阵的线性变换, 希尔密码相对于前面介绍的移位密码以及放射密码而言, 其最大的好处就是隐藏了字符的频率信息, 使得传统的通过字频来破译密文的方法失效.

安全性

希尔密码不是足够安全的, 如今已被证实, 关于希尔密码的破解不在本文范围内, 有兴趣的朋友可以研读相关书籍以了解相关破译方法.

希尔密码所需要掌握的前置知识

1)线性代数基础知识.

2) 初等数论基础知识.

约定

1)希尔密码常使用Z26字母表, 在此贴中, 我们也以Z26最为字母表进行讲解.在附带源码中有两种字母表选择.

2) 大家都知道最小的质数是2, 1 既不是质数也不是合数. 在此我们定义1对任何质数的模逆为其本身.

因为对于任意质数n, 有: 1*1 % n = 1 的. 也应该是很好理解的.

相关概念

线性代数中的逆矩阵: 在线性代数中, 大家都知道,对于一个n阶矩阵 M , 如果存在一个n阶矩阵 N ,使得 M * N = E (其中:

E为n阶单位矩阵), 则称矩阵 N 为矩阵 M 的逆矩阵, 并记为 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阶单位矩阵, 这时右侧便是所求的逆矩阵.

示例

例1

例：对明文attack，利用密钥 进行加密。

第一步：将明文分为两两一组：at ta ck

第二步：计算：

同理，

因此，密文为VBDEKQ

解密算法：因为 ，由于K必须可逆，即 ，所以 ，如何计算K的逆，有两种算法：一种是利用伴随矩阵，另一种是利用初等变换，无论采用何种算法都可以。

例2

例；设 ，求K的逆。

解法一、因为 ，因此K的逆存在。显然在mod26下 的余为1，即337/26=1

或337=x mod26，显然x=1。所以

，即：

注意： ， ， 在mod26下是7。由此我们有在 在mod26下的逆分别是： ， ， ， ， 。

例：密文为：YIFZMA 设密钥为 ，找出它的明文。

解： ，所以

因此明文为cureka。

例3

例子：

原文：Mr Hill made this code.

abcdefghijklmnopqrstuvwxyz

01234567890123456789012345

_______m___r___h___i___l___l___m___a___d___e___t___h___i___s___c___o___d___e

______12__17___7___8__11__11__12___0___3___4__19___7___8__18___2__14___3___4

m_12_144_204__88__96_132_132_144___0__36__48_228__84__96_216__24_168__36__48

r_17_204_289_119_136_187_187_204___0__51__68_323_119_136_306__34_238__51__68

h__7__88_119__49__56__77__77__84___0__21__28_133__49__49_126__14__98__21__28

i__8__96_136__56__64__88__88__96___0__24__32_154__56__56_144__16_112__24__32

l_11_132_187__77__88_121_121_132___0__33__44_209__77__88_198__22_154__33__44

l_11_132_187__77__88_121_121_132___0__33__44_209__77__88_198__22_154__33__44

m_12_144_204__84__96_132_132_144___0__36__48_228__84__96_216__24_168__36__48

a__0___0___0___0___0___0___0___0___0___0___0___0___0___0___0___0___0___0___0

d__3__36__51__21__24__33__33__36___0___9__12__57__21__24__54___6__52___9__12

e__4__48__68__28__32__44__44__48___0__12__16__76__28__32__72___8__56__12__16

t_19_228_323_133_152_209_209_228___0__57__76_361_133_152_342__38_266__57__76

h__7__84_119__49__56__77__77__98___0__21__28_133__49__56_126__14__98__21__28

i__8__96_136__56__64__88__88__96___0__24__32_152__56__56_144__16_112__24__32

s_18_216_306_126_144_198_198_216___0__54__72_342_126_144_324__36_252__54__72

c__2__24__34__14__16__22__22__24___0___6___8__38__14__16__36___4__28___6___8

o_14_168_238__98_112_154_154_168___0__42__56_266__98_112_252__28_169__42__56

d__3__36__51__21__24__33__33__36___0___9__12__57__21__24__54___6__52___9__12

e__4__48__68__28__32__44__44__48___0__12__16__76__28__32__72___8__56__12__16

用其中的一行作为密文既可

例4

例子：

密文：l 11 242 44 121 22 154 132 44 209 154 154 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+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”