希爾密碼算法原理分析

摘 要： 加密解密是現(xiàn)代生活的需要，建立在矩陣運算的規(guī)律基礎(chǔ)上的希爾密碼為我們提供了一種簡便高效的密碼加密與解密的方法。本文對其加以分析。

關(guān)鍵詞： 希爾密碼 算法原理 加密 解密

一、希爾密碼產(chǎn)生的必然性

隨著科技的日新月異和人們對信用卡、計算機的依賴性的加強，密碼學(xué)顯得愈來愈重要。密碼學(xué)是一門關(guān)于加密和解密、密文和明文的學(xué)科。若將原本的符號代換成另一種符號，即可稱之為廣義的密碼。狹義的密碼主要是為了保密，是一種防止竊文者得知內(nèi)容而設(shè)的另一種符號文字，也是一般人所熟知的密碼。

使用信用卡、網(wǎng)絡(luò)賬號及密碼、電子信箱、電子簽名等都需要密碼。為了方便記憶，許多人用生日、電話號碼、門牌號碼記做密碼，但是這樣安全性較差。

為了使密碼更加復(fù)雜，更難解密，產(chǎn)生了許多不同形式的密碼。密碼的函數(shù)特性是明文對密碼為一對一或一對多的關(guān)系，即明文是密碼的函數(shù)。傳統(tǒng)密碼中有一種叫移位法，移位法基本型態(tài)是加法加密系統(tǒng)-C=P+s（mod m）。一般來說，我們以1表示A，2表示B，……，25表示Y，26表示Z，以此類推。由于s=0時相當(dāng)于未加密，而0≤s≤m-1（s≥m都可用0≤s≤m-1取代），因此，整個系統(tǒng)只有（m-1）種變化。換言之，只要試過（m-1）次，機密的信息就會泄漏出去。

由此看來，日常生活中的密碼和傳統(tǒng)的密碼的可靠性較差，我們有必要尋求一種容易將字母的自然頻度隱蔽或均勻化，從而有利于統(tǒng)計分析的安全可靠的加密方法。希爾密碼［１］能基本滿足這一要求。

二、希爾密碼算法原理

希爾加密算法的基本思想是，將d個明文字母通過線性變換將它們轉(zhuǎn)換為d個密文字母。解密只要作一次逆變換就可以了，密鑰就是變換矩陣本身。

希爾密碼是多字母代換密碼的一種。多字母代換密碼可以利用矩陣變換方便地描述，有時又稱為矩陣變換密碼。令明文字母表為Z，若采用L個字母為單位進行代換，則多碼代換是映射f：Z→Z。若映射是線性的，則f是線性變換，可以用Z上的L×L矩陣K表示，K=（k）為密鑰。若是滿秩的，則變換為一一映射，且存在有逆變換K，使KK=KK=I。將L個字母的數(shù)字表示為Z上的L維矢量m=（m，m，…，m），相應(yīng)的密文矢量c=（c，c，…，c）為mK=c，以K作為解密矩陣，可由c恢復(fù)出相應(yīng)的明文c#8226;K=m。

在軍事通訊中，常將字符（信息）與數(shù)字對應(yīng)（為方便起見，我們將字符和數(shù)字按原有的順序?qū)?yīng)，事實上這種對應(yīng)規(guī)則是極易被破解的）：

abcde…x y z

12345…242526

如信息“NOSLEEPPING”對應(yīng)著一組編碼14，15，19，12，5，5，16，16，9，14，7。但如果按這種方式直接傳輸出去，則很容易被敵方破譯。于是必須采取加密措施，即用一個約定的加密矩陣K乘以原信號B，傳輸信號為C=KB（加密），收到信號的一方再將信號還原（破譯）為B=KC。如果敵方不知道加密矩陣，則很難破譯。

我們通過實例說明希爾密碼是怎樣通過矩陣運算實現(xiàn)加密和解密的。

（一）加密

第一步，設(shè)定加密矩陣為K=112-120113，即在希爾密碼中設(shè)q=26，L=3，選取滿秩3×3階可逆矩陣。我們之所以取3×3可逆方陣，也是為了計算方便，相應(yīng)的安全性就要低一些。

第二步，將信息14，15，19，12，5，5，16，16，9，14，7分為4個列矩陣：X=141519，X=1255，X=16169，X=1470，其中X中的“0”是虛設(shè)的，其目的是為了與列矩陣X，X，X的行數(shù)一致。列矩陣的行數(shù)3和個數(shù)4完全依賴于加密后的信息所對應(yīng)的數(shù)字的多少和加密矩陣階數(shù)決定。

第三步，將信息加密。進行矩陣的乘法運算：

Y=KX=112-120213141519=6716100；

Y=KX=112-1202131255=27-244；

Y=KX=112-12021316169=501675；

Y=KX=112-1202131470=21035。

加密后的新碼為67，16，100，27，-2，44，50，16，75，21，0。Y中的35雖然是多余的信息，但要連同密碼一起發(fā)給對方，對方在破解密碼時要參與計算。

（二）解密

第一步，求密匙矩陣K的逆矩陣［２］K。K可用Mathematica計算。

Inverse123-120213∥MatrixForm=-614-3125-1-3，

即K=-614-3125-1-3。

第二步，由得Y=KX得X=KY（i=1，2，3，4），再次進行矩陣乘法運算：

X=KY=-614-3125-1-3671610=141519；

X=KY=-614-3125-1-327-244=1255；

X=KY=-614-3125-1-3501675=16169；

X=KY=-614-3125-1-321035=1470。

這樣原來的信息編碼為14，15，19，12，5，5，16，16，9，14，7。

第三步，對照編碼表，即可獲得對方發(fā)來的信息內(nèi)容為“NOSLEEPPING”。

三、希爾密碼算法安全性分析

不難看出，希爾密碼算法中有兩個非常重要的條件。第一個條件是字符（信息）與數(shù)字對應(yīng)表，當(dāng)加密矩陣的階數(shù)n（本文實例中的加密矩陣的階數(shù)n=3）越大，破譯的難度就會增大，此時計算量也大，我們可以借助有關(guān)數(shù)學(xué)軟件如Mathematica提高運算效率。第二個條件是加密矩陣，如何定義、求解這個矩陣對于密碼的加密和破譯至關(guān)重要。

從破譯密碼的角度來看，傳統(tǒng)的密碼有一個致命弱點，就是破譯者可從統(tǒng)計出來的字符頻率中找到規(guī)律，進而找出破譯的突破口，尤其是在計算機技術(shù)高度發(fā)達的今天，破譯的速度更快。希爾密碼算法則完全克服了這一缺陷，它通過采用線性代數(shù)中的矩陣乘法運算和逆運算，能夠較好地抵抗頻率分析，很難被攻破。

希爾密碼體系為破譯者至少設(shè)置了三道關(guān)口，加大了破譯難度。破譯希爾密碼的關(guān)鍵是猜測文字被轉(zhuǎn)換成幾維向量（列矩陣的行數(shù)）、所對應(yīng)的字母表是怎樣排列的，更為重要的是要設(shè)法獲取加密矩陣A。要破解密碼，向量的維數(shù)、字母的排列表和加密矩陣三者缺一不可。古今中外的諜報戰(zhàn)中，敵對雙方總是千方百計地獲取破解對方密碼的鑰匙，但要想獲取希爾密碼的三把鑰匙談何容易。

世界上沒有攻不破的密碼，希爾密碼也不例外。希爾密碼算法的缺點在于線性變換的安全性很脆弱，易被攻擊擊破，黑客正是利用各種密碼的弱點來向用戶頻頻發(fā)起攻擊的。盡管如此，希爾密碼仍不失為一種簡便高效的密碼。

參考文獻：

［1］王育民，劉建偉.通信網(wǎng)的安全——理論語技術(shù)［M］.西安電子科技大學(xué)出版社，1999：39-40.

［2］姚慕生，高汝熹.高等數(shù)學(xué)（二）第一分冊線性代數(shù)［M］.武漢大學(xué)出版社，1999：74-75.