代數(shù)方程在密碼學(xué)中的應(yīng)用

周曉燕

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

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

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

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

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

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

1 加密

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

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

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

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

以上4步即為Hill密碼的加密過(guò)程。

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

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

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

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

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

2 解密

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

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

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

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

定義1 對(duì)于n階方陣，其中中的元素均屬于屬于集合Z，如果存在一個(gè)方陣，中的元素也均屬于集合Z，滿(mǎn)足：

則稱(chēng)為模m可逆，稱(chēng)為為方陣的模m逆矩陣，記作：。

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

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

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

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

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

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

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

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

查表知：

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

3 密碼的破譯

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

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

因?yàn)?，密文與明文的對(duì)應(yīng)如下：

于是有

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

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

記，，

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

參考文獻(xiàn)

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

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

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