周曉燕

摘 要：線性代數(shù)主要是以向量和矩陣為對象，以實向量空間為背景的一種抽象數(shù)學(xué)工具，它廣泛應(yīng)用于數(shù)學(xué)的各個分支以及物理、化學(xué)和科學(xué)技術(shù)中。該篇通過Hill密碼的數(shù)學(xué)模型闡述以線性代數(shù)為主要工具建立數(shù)學(xué)模型的一般方法和步驟。Hill密碼是基于矩陣的線性變換，其最大的好處就是隱藏了字符的頻率信息，使得傳統(tǒng)的通過字頻來破譯密文的方法失效。該篇主要介紹了明文的加密、加密后的密文的解密以及密碼的破譯。

關(guān)鍵詞：矩陣 Hill密碼 數(shù)學(xué)模型

中圖分類號：TP309 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2015）08（a）-0207-02

Hill密碼是一種常見的傳統(tǒng)密碼體系，它加密過程為：

明文→加密器→密文→普通信道→解密器→明文

矩陣運(yùn)算是完成這個加密過程的基本工具，具體過程如下：

1 加密

（1）根據(jù)明文字母的所對應(yīng)得表值，把明文信息轉(zhuǎn)換成數(shù)字，通常Hill密碼加密是使用26個字母表 A—Z見表1（也可以不只26個，如還有數(shù)字、標(biāo)點符號等）。

（2）通信雙方選擇一個二階可逆整數(shù)方陣，這個方陣就稱為Hill密碼的加密矩陣，它是整個加密過程的“密鑰”（ 只有通信雙方掌握，是加密的關(guān)鍵）。

（3）把明文字母按照文字的順序逐對分組。若Hill密碼的加密矩陣為二階矩陣，則明文字母2個一組（可以按照實際情況擴(kuò)大至每n個明文字母為一組）。若最后一組只有一個字母，則補(bǔ)充一個沒有實際意義的啞字母，這樣使得每一組都由2個明文字母組成.查出每個明文字母的表值，構(gòu)成一個二維列向量。

（4）乘以，得到一個新的二維列向量，由的兩個分量反查字母表值得到的兩個字母即為密文字母。

以上4步即為Hill密碼的加密過程。

例如：對于明文為MI MA XUE；加密矩陣，求這段明文的Hill密碼。

將明文相鄰2個字母分為一組：MI MA XU EE.最后一個字母是啞字母，它是為使最后一組的字母數(shù)為2而添加的，無實際意義。查出每對字母的表值，并構(gòu)造2維列向量：

把加密矩陣分別乘以這4個列向量，得到：

對這4個列向量反查字母表，但是這4個列向量中存在著一些數(shù)不是表值（大于25），無法在26個字母表中查到，我們可以Hill密碼6運(yùn)算，即：對這不在表中的數(shù)，加減26的整數(shù)倍，使其能夠轉(zhuǎn)化為0—25之間的一個整數(shù)，從而進(jìn)行查表對應(yīng)，如：

通過查表，這4個新的二維列向量對應(yīng)的字母為：EA OC NK OO.它就是明文“MI MA XUE”的密文。

2 解密

顧名思義，解密過程就是上述加密過程的逆過程。這就涵蓋了在模運(yùn)算下如何解方程組這一問題。我們知道，對于一個n階方陣可逆的充要條件是。在模m運(yùn)算的條件下矩陣的可逆與一般意義的矩陣可逆略有不同。

在模m的運(yùn)算下，單位矩陣E（mod m）也與通常的單位矩陣E有所不同：

E（mod m）表示，矩陣?yán)锏拿恳粋€元素減去m的整數(shù)倍后，就可以化成單位矩陣。例如：

記整數(shù)集合Z={0，1，2，…，m-1}，m為一正整數(shù)，模m可逆定義如下：

定義1 對于n階方陣，其中中的元素均屬于屬于集合Z，如果存在一個方陣，中的元素也均屬于集合Z，滿足：

則稱為模m可逆，稱為為方陣的模m逆矩陣，記作：。

定義2 對于集合Z中的一個元素，為整數(shù)，如果存在集合Z中的一個元素b，滿足，就把b稱為a的模m倒數(shù)，記作.容易知道：Z中存在著模26倒數(shù)的整數(shù)以及其相應(yīng)的倒數(shù)如下表2所示：

定理：元素屬于Z的方陣模可逆的充要條件是和det沒有公共素數(shù)因子。

推論：元素均屬于集合Z的方陣模26可逆的充分必要條件是det不能被2和13整除。

定理：設(shè)，且模26可逆，則：

其中是的倒數(shù)。顯然為Z中的數(shù)。

這樣，在模26意義下，求解方程組的問題即可解決：

例：要將上述加密后的密文EA OC NK OO解密，只要把這個加密過程逆轉(zhuǎn)回去，即將密文按同樣方式分組，查它們的表值即得下列列向量：

上例所選取的加密矩陣，det=3不能被2和13整除，所以加密矩陣模26可逆。它對應(yīng)的模26逆矩陣可以通過以下運(yùn)算得到：

查表知：

這樣，利用上面描述的方法，破譯出明文為MI MA XU EE。

3 密碼的破譯

密碼破譯的過程顧名思義，就是找到加密矩陣及，前面討論的加密與解密過程，可以看作是在二維向量空間內(nèi)進(jìn)行線性變換與其逆變換。每個明文對應(yīng)的向量都是一個Z上的二維向量，該向量乘以加密矩陣后仍然是一個Z上的二維向量。由于我們要求所選取的加密矩陣應(yīng)該為可逆矩陣，所以，有線性代數(shù)的知識可以知道，如果知道了兩個明文對應(yīng)的二維線性無關(guān)向量以及它們各自對應(yīng)的密文向量，就能通過運(yùn)算找出它的加密矩陣及。

例如：某軍截獲敵方的一份密文，破譯部門通過大量的統(tǒng)計分析與語言分析確認(rèn)為Hill密碼體系，觀察其中出現(xiàn)頻數(shù)最高的雙字母是CD和LW，而在明文語言中，出現(xiàn)頻數(shù)最高的雙字母是AZ和BC.試找出該密文相應(yīng)的加密矩陣。

因為，密文與明文的對應(yīng)如下：

于是有

，它有模26倒數(shù)，所以，在模26意義下線性無關(guān)。

同樣地，它有模26倒數(shù)，所以，在模26意義下線性無關(guān)。

記，，

因此，找出加密矩陣后即可以完整地破譯截獲的密文。

參考文獻(xiàn)

[1] 姜啟源.數(shù)學(xué)模型[M].北京：高等教育出版社，1993.

[2] 胡章柱.密碼轉(zhuǎn)換問題的探究[J].數(shù)學(xué)通訊，2004（2m）：23.

[3] 王庚.現(xiàn)代數(shù)學(xué)建模方法[M].北京：科學(xué)出版社，2008.