線性代數(shù)方法建模3 Hill密碼的數(shù)學(xué)模型數(shù)學(xué)建模案例分析

1、數(shù)學(xué)建模3 Hill密碼的數(shù)學(xué)模型Hill密碼是一種傳統(tǒng)的密碼體系，它的加密過程可以描述如下：明文加密器密文普通信道解密器明文在這個過程中，運用的手段是矩陣運算，具體步驟如下：一、加密1、根據(jù)明文字母的表值，將明文信息用數(shù)字表示，設(shè)明文信息只需要26個英文字母AZ（也可以不只26個，如還有數(shù)字、標(biāo)點符號等），通信雙方給出這26個字母表值（見下表）。ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ14151617181920212223242502、選擇一個二階可逆整數(shù)方陣，稱為Hill密碼的加密矩陣，它是這個加密體制的“密鑰”（是加密的關(guān)鍵，僅通信雙方掌握

2、）。3、將明文字母依次逐對分組。Hill密碼的加密矩陣為二階矩陣，則明文字母2個一組（可以擴充至每n個明文字母為一組）。若最后一組只有一個字母，則補充一個沒有實際意義的啞字母，這樣使得每一組都由2個明文字母組成。查出每個明文字母的表值，構(gòu)成一個二維列向量。4、乘以，得到一個新的二維列向量，由的兩個分量反查字母表值得到的兩個字母即為密文字母。 以上4步即為Hill密碼的加密過程。例 明文為YI CHU FA。，求這段明文的Hill密碼。將明文相鄰2個字母分為一組：YI CH UF AA。最后一個字母是啞字母，它是為使最后一組的字母數(shù)為2而添加的，無實際意義。查出每對字母的表值，并構(gòu)造2維列向量：

3、 （1）將上述4個列向量左乘矩陣，得到4個新的列向量： （2）在反查這4個向量對應(yīng)的字母時，遇到了問題：第1個向量與第三個向量中的43與33不是表值，處理的辦法是加減26的整數(shù)倍，使其化為025之間的一個整數(shù)，這稱為模26運算，記為： （3）這樣，這4個新的二維列向量對應(yīng)的字母為：QA SX GR CC。它就是明文“YI CHU FA”的密文。二、解密解密過程即為上述過程的逆過程。這是在模運算下如何解方程組的問題。一般一個n階方陣可逆的充要條件是。在模26運算下矩陣可逆與一般的矩陣可逆有所不同。記整數(shù)集合Z=0，1，2，m-1，m為一正整數(shù)，模m可逆定義如下：定義1 對于一個元素屬于集合Z的n

4、階方陣，若存在一個元素屬于集合Z的方陣，使得稱為模m可逆，為的模m逆矩陣，記為。E（mod m）的意義是，每一個元素減去m的整數(shù)倍后，可以化成單位矩陣。例如：定義2 對Z的一個整數(shù)a，若存在Z的一個整數(shù)b，使得ab=1（mod m），稱b為a的模m倒數(shù)，記作。Z中有模26倒數(shù)的整數(shù)及其倒數(shù)見下表：13579111517192123251921153197231151725可以證明，如果a與m無公共素數(shù)因子，則a有唯一的模m倒數(shù)。利用這點，可以證明下述命題：命題 元素屬于Z的方陣模m可逆的充要條件是m和det 沒有公共素數(shù)因子。 顯然，所選加密矩陣必須符合該命題的條件。 這里所選項的明文字母共2

5、6個，m=26，26的素數(shù)因子為2和13，所以Z上的方陣可逆的充要條件是det (mod m)不能被2和13整除。 設(shè)，若滿足命題的條件，不難驗證：其中是的倒數(shù)。顯然為Z中的數(shù)。這樣，在模26意義下，求解方程組的問題即可解決： （4）例 要將一段密文QA SX GR CC解密，只要將上述加密過程逆轉(zhuǎn)回去，即將密文按同樣方式分組，查它們的表值即得： （5）根據(jù)上述命題與表值，所選加密矩陣的行列式det =3沒有2與13這兩個素數(shù)因子，所以模26可逆。這樣，由（4）和（5）中的向量可得到（1）中的向量，明文為YI CH UF AA。三、密碼的破譯 密碼破譯實際上就是破譯加密矩陣及，前面的加密與解密

6、過程類似于在二維向量空間進行線性變換與其逆變換。每個明文向量都是一個Z上的二維向量，乘以加密矩陣后仍為一個Z上的二維向量。由于為可逆矩陣，所以，如果知道了兩個線性無關(guān)的二維明文向量與其對應(yīng)的密文向量，就可以求出它的加密矩陣及。 下面以一個具體例子說明這種方法。 有一段密文：QJWPISWAZUXAUUISEABAUCRSIPLBHAAMMLPJJOTENH。經(jīng)分析是用Hill密碼編譯的，且這段密文的字母UCRS依次代表字母TACO（通常這是由破譯部門通過大量的統(tǒng)計分析與語言分析確定的），這樣密文與明文的對應(yīng)為于是有 在模26意義下，它有模26倒數(shù)，所以，在模26意義下線性無關(guān)。類似地，也可以驗證在模26意義下線性無關(guān)。 記，則。這樣，可以利用模26意義下的初等行變換求得，因而可以求出。初等行變換的過程如下：故，。利用即可將密文解密，得到這段密文的明文：CL IN TO NI SG OI NG TO VI SI TA CO UN