代數方程在密碼學中的應用

周曉燕

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

關鍵詞：矩陣 Hill密碼 數學模型

中圖分類號：TP309 文獻標識碼：A 文章編號：1672-3791（2015）08（a）-0207-02

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

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

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

1 加密

（1）根據明文字母的所對應得表值，把明文信息轉換成數字，通常Hill密碼加密是使用26個字母表 A—Z見表1（也可以不只26個，如還有數字、標點符號等）。

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

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

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

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

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

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

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

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

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

2 解密

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

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

E（mod m）表示，矩陣里的每一個元素減去m的整數倍后，就可以化成單位矩陣。例如：

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

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

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

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

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

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

定理：設，且模26可逆，則：

其中是的倒數。顯然為Z中的數。

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

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

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

查表知：

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

3 密碼的破譯

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

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

因為，密文與明文的對應如下：

于是有

，它有模26倒數，所以，在模26意義下線性無關。

同樣地，它有模26倒數，所以，在模26意義下線性無關。

記，，

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

參考文獻

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

[2] 胡章柱.密碼轉換問題的探究[J].數學通訊，2004（2m）：23.

[3] 王庚.現代數學建模方法[M].北京：科學出版社，2008.