實驗四 Hill密碼

1、實驗四實驗四 Hill密碼密碼 實驗?zāi)康模罕緦嶒炛饕婕按鷶?shù)，利用模運(yùn)實驗?zāi)康模罕緦嶒炛饕婕按鷶?shù)，利用模運(yùn)算下的矩陣乘法、求逆矩陣、線性無關(guān)、線性空算下的矩陣乘法、求逆矩陣、線性無關(guān)、線性空間和線性變換等概念和運(yùn)算，學(xué)習(xí)間和線性變換等概念和運(yùn)算，學(xué)習(xí)Hill密碼體制密碼體制的加密、解密和破譯過程。的加密、解密和破譯過程。一、密碼學(xué)基本概念一、密碼學(xué)基本概念明文明文( (plaintext) )：未加密的信息；：未加密的信息；密文密文( (ciphertext) )：加密后的信息；：加密后的信息；加密加密( (encryption) )：從明文到密文的變換；：從明文到密文的變換；解密解密( (

2、decryption) )：從密文到明文的變換：從密文到明文的變換 加密和解密都是在密鑰加密和解密都是在密鑰( (key) )的控制下進(jìn)行的的控制下進(jìn)行的, ,給定一個密鑰給定一個密鑰, ,就可以確定一對具體的加密變換和就可以確定一對具體的加密變換和解密變換解密變換. .二、密碼分類二、密碼分類密密碼碼古典密碼古典密碼現(xiàn)代密碼現(xiàn)代密碼以字符為以字符為基本加密基本加密單元單元以信息塊以信息塊為基本加為基本加密單元密單元三、加密和解密的一般過程三、加密和解密的一般過程明文明文加密器加密器普通信道普通信道密文密文解密器解密器明文明文易被截獲易被截獲四、實際問題四、實際問題(1)(1)甲方收到乙方的一

3、封密文信息甲方收到乙方的一封密文信息, ,密文如下密文如下: :WOWUYSBACPGZSAVCOVKPEWCPADKPPABUJCQLYXQEZAACPP 按約定按約定, ,他們之間采用他們之間采用Hill2密碼通信密碼通信, ,密鑰是二階矩密鑰是二階矩陣陣 ，且漢語拼音的，且漢語拼音的2626個字母與個字母與0-250-25之間的之間的整數(shù)建立一一對應(yīng)關(guān)系整數(shù)建立一一對應(yīng)關(guān)系, ,稱之為字母的稱之為字母的表值表值, ,具體如下具體如下. .問這段密文的原文是什么問這段密文的原文是什么? ? 3021AABCDEFGHIJKLM12345678910 11 12 13NOPQRSTUVWXY

4、Z14 15 16 17 18 19 20 21 22 23 24 250(2)(2)甲方截獲了一段密文甲方截獲了一段密文: :OJWPISWAZUXAUUISEABAUCRSIPLBHAAMMLPJJOTENH經(jīng)分析，這段密文使用經(jīng)分析，這段密文使用Hill2密碼編譯的密碼編譯的, ,且這段且這段密文的字母密文的字母UCRS依次代表字母依次代表字母TACO, ,文能否破譯文能否破譯這段密文的內(nèi)容這段密文的內(nèi)容? ?五、五、Hill2 密碼的數(shù)學(xué)模型密碼的數(shù)學(xué)模型加密過程：加密過程： 1. 1.設(shè)明文信息只需要設(shè)明文信息只需要2626個字母個字母(A-Z),(A-Z),(可能不可能不止這止這2

5、626個個),),通信雙方給出這通信雙方給出這2626個字母的表值個字母的表值, ,根據(jù)根據(jù)表值將明文信息用數(shù)字表示表值將明文信息用數(shù)字表示. . 2. 2.選擇一個二階可逆方陣選擇一個二階可逆方陣 , ,稱為加密矩陣稱為加密矩陣, ,也也就是密鑰就是密鑰. .A 3. 3.將明文字母依次逐對分組將明文字母依次逐對分組. .Hill2密碼的加密密碼的加密矩陣是為二階矩陣，則明文字母矩陣是為二階矩陣，則明文字母2個一組個一組( (Hilln密密碼碼, ,n個明文字母為一組個明文字母為一組),),若最后一組只有一個字母若最后一組只有一個字母, ,則補(bǔ)充一個無意義的字母，稱為啞字母則補(bǔ)充一個無意義的

6、字母，稱為啞字母. .由明文字母由明文字母表值查出每一組表值查出每一組2個明文字母的表值得到一個二維列個明文字母的表值得到一個二維列向量向量 。a解密過程是加密過程的逆過程。解密過程是加密過程的逆過程。例例 明文為明文為YI CHU FA. ,. ,求這段明文的求這段明文的Hill2密文密文. . 3021A將明文相鄰將明文相鄰2個字母分為一組個字母分為一組 YI CH UF AA最后一個字母最后一個字母A為啞字母為啞字母, ,無實際意義無實際意義. .查出每對字母查出每對字母的表值的表值, ,構(gòu)造構(gòu)造2維列向量維列向量: : 4. 4. 左乘以左乘以 得到一個新的二維向量得到一個新的二維向量

7、 , ,由由 的兩個分量反查字母表值得到密文字母的兩個分量反查字母表值得到密文字母. .從而從而完成加密過程完成加密過程. .A A 11,621,83,925將上述將上述4個向量左乘矩陣個向量左乘矩陣 , ,得到得到4個新的列向量個新的列向量: :A 33,1833,2419,2743在反查這在反查這4 4個向量對應(yīng)的字母時個向量對應(yīng)的字母時, ,遇到了問題遇到了問題: :第一第一個第三個向量中含有不在表中的值個第三個向量中含有不在表中的值, ,處理的辦法是處理的辦法是加減加減2626的整數(shù)倍，使其化成的整數(shù)倍，使其化成0-250-25之間的一個整數(shù)之間的一個整數(shù), ,這稱為這稱為模模262

8、6運(yùn)算運(yùn)算: :記為記為4317337(mod26),(mod26)2711818 六、模六、模 運(yùn)算的一些定義和結(jié)論運(yùn)算的一些定義和結(jié)論 m關(guān)于模關(guān)于模 運(yùn)算運(yùn)算, ,可以驗證可以驗證, ,對兩個整數(shù)對兩個整數(shù) , ,進(jìn)行加減進(jìn)行加減或乘的?；虺说哪?運(yùn)算有如下規(guī)律運(yùn)算有如下規(guī)律: :mm21,aa) (mod) (mod() (mod() (mod2121mmamamaa 這樣這樣, ,這這4 4個新的個新的2 2維列向量對應(yīng)的字母為維列向量對應(yīng)的字母為QA SX GR CC這也就是上段明文這也就是上段明文: :”YI CHU FA”的密文的密文. . 定義一定義一: :設(shè)整數(shù)集合設(shè)整數(shù)集

9、合 , ,其中其中 為一正整數(shù)為一正整數(shù). .對對 中的一個整數(shù)中的一個整數(shù) , ,如果存在如果存在 中的中的一個整數(shù)一個整數(shù) , ,使得使得 , ,稱稱 為為 的模的模 倒數(shù)倒數(shù)或乘法逆或乘法逆, ,記作記作 . .例如例如1, 1 , 0 mZmmmZmZb) (mod1mab baam) (mod1mab )26 (mod391 要將這段密文解密，只要將上述加密過程逆轉(zhuǎn)要將這段密文解密，只要將上述加密過程逆轉(zhuǎn)即可即將密文按照同樣的方法分組查它們的表即可即將密文按照同樣的方法分組查它們的表值，但是如何通過密文的表值得到明文的表值？這值，但是如何通過密文的表值得到明文的表值？這就要在模運(yùn)算意

10、義下，如何解方程組：就要在模運(yùn)算意義下，如何解方程組： A一般的階方陣可逆的充要條件為一般的階方陣可逆的充要條件為 . .但在但在模運(yùn)算下的可逆與一般意義下的可逆有所不同模運(yùn)算下的可逆與一般意義下的可逆有所不同n0det A如果如果 與與 無公共素因子無公共素因子, ,則則 有唯一的模有唯一的模 倒數(shù)倒數(shù). .amam 對于一個元素屬于對于一個元素屬于 的的 階方陣階方陣 , ,若存在若存在一個元素屬于一個元素屬于 中的一個中的一個 階方陣階方陣 , ,使得使得mZnAmZnB) (mod mEBAAB 則稱則稱 為模為模 可逆可逆, , 為為 的模的模 可逆矩陣可逆矩陣, ,記作記作: :A

11、mBAm) (mod1mAB 元素屬于元素屬于 的的 階方陣階方陣 模模 可逆的充要條可逆的充要條件是件是, , 和和 沒有公共素數(shù)因子沒有公共素數(shù)因子. .mZnAmmAdet七、七、Hill2密碼的破譯密碼的破譯問題問題(2)(2)屬于破譯問題前面的加密和解密過程類屬于破譯問題前面的加密和解密過程類似于在二維向量空間進(jìn)行線性變換與其逆變換似于在二維向量空間進(jìn)行線性變換與其逆變換. .每每個明文向量是一個個明文向量是一個 上的二維向量上的二維向量, ,乘以加密矩陣乘以加密矩陣后后, ,仍為仍為 上的一個二維向量上的一個二維向量. .由加密矩陣由加密矩陣 可逆可逆, ,所以如果知道了兩個線性無

12、關(guān)的二維明文向量與其所以如果知道了兩個線性無關(guān)的二維明文向量與其對應(yīng)的密文向量對應(yīng)的密文向量, ,就可以求出加密矩陣就可以求出加密矩陣 及及 mZmZAA1 A在問題在問題(2)(2)中中 OCSRATCU ,明文明文 密文密文 明文明文 密文密文 OCASRATACU1531918120321222111 在模在模2626意義下意義下, ,7)26 (mod345)26 (mod1931821),det(21 它有模它有模2626倒數(shù)倒數(shù), ,所以在模所以在模2626意義下意義下 線性無關(guān)線性無關(guān). .類似地類似地, ,可以驗證可以驗證 線性無關(guān)線性無關(guān). .21, 21, 記記 , ,則則

13、 ),(),(2121 CP1, PCAACP在模在模2626意義下進(jìn)行初等行變換意義下進(jìn)行初等行變換, ,求得求得 , ,因而因而求出求出 . .利用利用 即可將問題即可將問題(2)(2)的密文解密的密文解密. .TA )(1 1 A1 A 3239052215115319185221511531918120321)()26)(mod18(5)26(mod2112111rrrrTTCP初等變換過程如下初等變換過程如下: : 917100101917105221513)26)(mod15(3)26(mod9221212rrrrr故故 90171,91701)(11AAT這段密文解密后為這段密文

14、解密后為: :Clinton is going to visit a country in Middle East t.最后一個為啞字母最后一個為啞字母. .練習(xí)題練習(xí)題ABCDEFGHIJKLM523220 10 158418 25016 13NOPQRSTUVWXYZ73119612 24 21 17 14 22 119 1. 1.利用所介紹的利用所介紹的Hill2 2密碼體制的原理密碼體制的原理, ,根據(jù)根據(jù)給定的給定的2626個英文字母的亂序表值個英文字母的亂序表值( (見下表見下表),),設(shè)計和設(shè)計和建立建立HillHill4 4密碼體制的加密和解密的必要的計算機(jī)密碼體制的加密和解密

15、的必要的計算機(jī)程序程序. .設(shè)設(shè)2626個英文字母以下面的亂序表與個英文字母以下面的亂序表與Z Z2626中的中的整數(shù)對應(yīng)。整數(shù)對應(yīng)。(2)(2)設(shè)明文為設(shè)明文為HILL CRYPTOGRAPHIC SYSTEM IS TRADITIONAL利用上述表值和加密矩陣給此明文加密利用上述表值和加密矩陣給此明文加密,編程實現(xiàn)編程實現(xiàn)加密和解密過程加密和解密過程. (1) (1)設(shè)設(shè) ,驗證矩陣驗證矩陣 能否作能否作為為Hill4密碼體制的加密矩陣密碼體制的加密矩陣.編程實現(xiàn)編程實現(xiàn). 4116109485105965968AA (3) (3)已知上述給定表值的一段已知上述給定表值的一段Hill4密碼

16、密文為密碼密文為對應(yīng)的明文為對應(yīng)的明文為能否確定對應(yīng)的加密矩陣能否確定對應(yīng)的加密矩陣?JCOW ZLVB DVLE QMXCDELAY OPERATIONSU 2. 2.設(shè)已知一份設(shè)已知一份Hill2密碼體系密碼體系, ,其中出現(xiàn)頻其中出現(xiàn)頻率最高的雙字母是率最高的雙字母是RH和和NI, ,而在明文語言中而在明文語言中, ,出出現(xiàn)頻率最高的雙字母為現(xiàn)頻率最高的雙字母為TH和和HE. .由這些信息按由這些信息按照下表給出的表值能得到什么樣的加密矩陣照下表給出的表值能得到什么樣的加密矩陣? ?ABCDEFGHIJKLM012345678910 11 12NOPQRSTUVWXYZ13 14 15 16 17 18 19 20 21 22 23 24 25 3. 3.找