希爾密碼
Hill Password
希爾密碼（Hill Password）是運用基本矩陣論原理的替換密碼，由Lester S. Hill在1929年發明。每個字母當作26進位數字：A=0, B=1, C=2... 一串字母當成n維向量，跟一個n×n的矩陣相乘，再將得出的結果MOD26。
希爾密碼是運用基本矩陣論原理的替換密碼，由Lester S. Hill在1929年發明。
每個字母當作26進位數字：A=0, B=1, C=2... 一串字母當成n維向量，跟一個n×n的矩陣相乘，再將得出的結果模26。
注意用作加密的矩陣（即密匙）在\mathbb_^n必須是可逆的，否則就不可能解碼。只有矩陣的行列式和26互質，才是可逆的。
Hill cipher（希爾密碼）
Hill cipher是1929年提出的一種密碼體制。
設d是一正整數，定義。Hill cipher的主要思想是利用線性變換方法，不同的是這種變換是在 上運算。
例如：設d=2，每個明文單元使用 來表示，同樣密文單元用 表示，具
體的加密中，將被表示為 的線性組合。
如：
利用線性代數的知識，可得
也可表示成。
例：對明文attack，利用密鑰 進行加密。
第一步：將明文分為兩兩一組：at ta ck
第二步：計算：
同理，
因此，密文為VBDEKQ
解密演演算法：因為，由於K必須可逆，即，所以，如何計算K的逆，有兩種演演算法：一種是利用伴隨矩陣，另一種是利用初等變換，無論採用何種演演算法都可以。
例；設，求K的逆。
解法一、因為，因此K的逆存在。顯然在mod26下 的余為1，即337/26=1
或337=x mod26，顯然x=1。所以
，即：
注意： ， ，在mod26下是7。由此我們有在 在mod26下的逆分別是： ， ， ， ， 。
例：密文為：YIFZMA 設密鑰為，找出它的明文。
解： ，所以
因此明文為cureka。
希爾密碼是基於矩陣的線性變換，希爾密碼相對於前面介紹的移位密碼以及放射密碼而言，其最大的好處就是隱藏了字元的頻率信息，使得傳統的通過字頻來破譯密文的方法失效.
希爾密碼不是足夠安全的，如今已被證實，關於希爾密碼的破解不在本文範圍內，有興趣的朋友可以研讀相關書籍以了解相關破譯方法.
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右側附加一個n階單位矩陣，再通過初等變換將增廣矩陣的左側變換為一個n階單位矩陣，這時右側便是所求的逆矩陣.
例：對明文attack，利用密鑰 進行加密。
第一步：將明文分為兩兩一組：at ta ck
第二步：計算：
同理，
因此，密文為VBDEKQ
例；設，求K的逆。
解法一、因為，因此K的逆存在。顯然在mod26下 的余為1，即337/26=1
或337=x mod26，顯然x=1。所以
，即：
注意：， ，在mod26下是7。由此我們有在 在mod26下的逆分別是：， ， ， ，。
例：密文為：YIFZMA 設密鑰為，找出它的明文。
解：，所以
因此明文為cureka。
例子：
原文：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__84__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
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
用其中的一行作為密文既可
例子：
密文：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=R
用同樣的方法把“HI THERE”轉換為密文“IR 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”
基本信息
- 提出者
- Lester S. Hill
- 提出時間
- 1929年
- 原理
- 基本矩陣論
- 類別
- 替換密碼
- 外文名
- Hill Cipher