簡介
Hillcipher（希爾密碼）是1929年提出的一種密碼體制。設d是一正整數，定義。Hillcipher的主要思想是利用線性變換方法，不同的是這種變換是在上運算。
例如：設d=2，每個明文單元使用來表示，同樣密文單元用表示，具
體的加密中，將被表示為的線性組合。
如：
利用線性代數的知識，可得
這個運算在上進行，即mod26，密鑰K一般取一個m*m的矩陣，記為。對明文，以，則加密算法為：
也可表示成。
希爾密碼是基於矩陣的線性變換,希爾密碼相對於前面介紹的移位密碼以及放射密碼而言,其最大的好處就是隱藏了字元的頻率信息,使得傳統的通過字頻來破譯密文的方法失效.
安全性
希爾密碼不是足夠安全的,如今已被證實,關於希爾密碼的破解不在本文範圍內,有興趣的朋友可以研讀相關書籍以了解相關破譯方法.編輯本段
希爾密碼所需要掌握的前置知識
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，利用密鑰進行加密。
第一步：將明文分為兩兩一組：attack
第二步：計算：
同理，
因此，密文為VBDEKQ
解密算法：因為，由於K必須可逆，即，所以，如何計算K的逆，有兩種算法：一種是利用伴隨矩陣，另一種是利用初等變換，無論採用何種算法都可以。
例2
例；設，求K的逆。
解法一、因為，因此K的逆存在。顯然在mod26下的余為1，即337/26=1
或337=xmod26，顯然x=1。所以
，即：
注意：，，在mod26下是7。由此我們有在在mod26下的逆分別是：，，，，。
例：密文為：YIFZMA設密鑰為，找出它的明文。
解：，所以
因此明文為cureka。
例3
例子：
原文：MrHillmadethiscode.
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
例子：
密文：l112424412122154132442091541542201872212122011
解答：根據第一項，全部除以11,因為l是第12個字母，即l=12-k，得k=1按a=0……z=25,列出字母WELCOMETOOURCLUB
希爾密碼
加密
例如：密鑰(密碼學中好象沒有"密匙"一詞)矩陣
13
02
明文：HITHERE
去空格，2個字母一組，根據字母表順序換成矩陣數值如下，末尾的E為填充字元：
HITHEREE
82055
98185
HI經過矩陣運算轉換為IS，具體算法參考下面的說明：
|13|8e1*8+3*9=35MOD26=9=I
|02|9e0*8+2*9=18MOD26=18=S
用同樣的方法把“HITHERE”轉換為密文“ISRPGJTJ”，注意明文中的兩個E分別變為密文中的G和T。
解密
解密時，必須先算出密鑰的逆矩陣，然後再根據加密的過程做逆運算。
逆矩陣算法公式：
|AB|=1/(AD-BC)*|D-B|
|CD||-CA|
例如密鑰矩陣=
|17|
|03|
AD-BC=1*3-0*7=33*X=1mod26所以X=9
因此
|17|的逆矩陣為：9*|3-7|
|03||01|
假設密文為“FOAOESWO”
FOAOESWO
61523
15151915
9*|3-7||6|=9*(3*6-7*15)=-783mod26=23=W
|01||15|=9*(0*6+1*15)=135mod26=5=E
所以密文“FOAOESWO”的明文為“WEREDONE”
