實驗十古典密碼及破譯

1、實驗十密碼加密，解密與破譯數(shù)學(xué)實驗q 保密通訊無論在軍事、政治、經(jīng)濟還是日常保密通訊無論在軍事、政治、經(jīng)濟還是日常生活中都起著非常重要的作用。生活中都起著非常重要的作用。q 為了將信息傳遞給己方的接受者，同時又要為了將信息傳遞給己方的接受者，同時又要防止他人（特別是敵人）知道信息的內(nèi)容，必須防止他人（特別是敵人）知道信息的內(nèi)容，必須將要傳遞的信息（將要傳遞的信息（明文明文）加密，變成）加密，變成密文密文后發(fā)送后發(fā)送出去，這樣，即使敵方得到密文也看不懂，而己出去，這樣，即使敵方得到密文也看不懂，而己方的接受者收到密文后卻可以按照預(yù)先定好的方方的接受者收到密文后卻可以按照預(yù)先定好的方法加以解密。法

2、加以解密。問題背景和實驗?zāi)康膯栴}背景和實驗?zāi)康拿魑拿魑拿芪拿芪拿魑拿魑募用芗用芙饷芙饷躴 密碼可分為古典密碼和現(xiàn)代密碼密碼可分為古典密碼和現(xiàn)代密碼q 本實驗主要介紹古典密碼的加密與破譯原理，本實驗主要介紹古典密碼的加密與破譯原理，同時介紹如何用同時介紹如何用 Matlab 編程來實現(xiàn)加密、解密和編程來實現(xiàn)加密、解密和破譯過程。破譯過程。問題背景和實驗?zāi)康膯栴}背景和實驗?zāi)康膗 古典密碼：古典密碼：以字符為基本加密單元；以字符為基本加密單元；u 現(xiàn)代密碼：現(xiàn)代密碼：以信息塊為基本加密單元。以信息塊為基本加密單元。加密信息傳遞過程加密信息傳遞過程明文明文（信息）（信息）加密器加密器密文密文密文密文明

3、文明文（信息）（信息）解密器解密器普普通通信信道道發(fā)發(fā)送送敵方截獲敵方截獲破譯破譯發(fā)送方發(fā)送方接收方接收方Hill2 密碼的加密過程密碼的加密過程q Hill2 密碼中所用的數(shù)學(xué)手段是密碼中所用的數(shù)學(xué)手段是 矩陣運算矩陣運算。q 加密過程：加密過程： 將漢語拼音的將漢語拼音的 26 個字母個字母 與與 0 到到 25 之間的整數(shù)建之間的整數(shù)建立一一對應(yīng)關(guān)系，稱為字母的立一一對應(yīng)關(guān)系，稱為字母的 表值表值，然后根據(jù)明文字，然后根據(jù)明文字母的表值，母的表值，將明文信息用數(shù)字表示將明文信息用數(shù)字表示。ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161

4、718192021222324250設(shè)通訊雙方所給出的設(shè)通訊雙方所給出的 26 個字母的表值如下：個字母的表值如下：注：這里假定明文中只使用注：這里假定明文中只使用 26 個大寫字母個大寫字母Hill2 密碼的加密過程密碼的加密過程 選擇一個選擇一個 二階可逆整數(shù)方陣二階可逆整數(shù)方陣 A，稱為，稱為Hill2密碼的密碼的 加加密矩陣密矩陣，它是加密體制的，它是加密體制的 “密鑰密鑰”，是加密的關(guān)鍵，是加密的關(guān)鍵，僅僅通訊雙方掌握通訊雙方掌握。 將明文字母分組。將明文字母分組。 Hill2 使用的是二階矩陣，所以將明使用的是二階矩陣，所以將明文字母每文字母每 2 個一組（可以推廣至個一組（可以推

5、廣至Hill n密碼）。查出每個字密碼）。查出每個字母的表值，這樣，每組字母構(gòu)成一個二維列向量母的表值，這樣，每組字母構(gòu)成一個二維列向量 。若最后僅剩一個字母，則補充一個若最后僅剩一個字母，則補充一個沒有實際意義的啞字母沒有實際意義的啞字母（啞元啞元）。這樣使得每組都有）。這樣使得每組都有 2 個字母，個字母， 令令 = A ，由，由 的兩個分量反查字母表值表，得到的兩個分量反查字母表值表，得到相應(yīng)的兩個字母，即為相應(yīng)的兩個字母，即為密文字母密文字母。Hill2 加密舉例加密舉例例：例： 設(shè)明文為設(shè)明文為“HRXYSJX”（華銳學(xué)院數(shù)計系），（華銳學(xué)院數(shù)計系），試給出這段明文的試給出這段明文的

6、 Hill2 密文密文。 將明文字母分組：將明文字母分組： HR XY SJ XX最后的一個字母最后的一個字母 X 為啞字母，無實際意義。為啞字母，無實際意義。解解:, 8241924,18251024A B C D E F G H IJKLM1 2 3 4 5 6 7 89 10 1112 13NOPQRSTUVW XYZ1415161718192021222324250查表得每組字母的表值，得到查表得每組字母的表值，得到 4 個二維列向量：個二維列向量：1203A 將上述將上述 4 個二維向量個二維向量左乘密鑰矩陣左乘密鑰矩陣 A 得：得：44743972, , , 54753072作作模

7、模 26 運算運算，將所有的數(shù)都化為，將所有的數(shù)都化為 0 到到 25 之間的整數(shù)：之間的整數(shù)：4474(mod 26) (mod 26) 54753972(mod 21822223136) (mod 26) 302042207,. Hill2 加密舉例加密舉例反查字母表值得每個向量對應(yīng)的字母組為：反查字母表值得每個向量對應(yīng)的字母組為：HRXYSJXRBVWMDTTHill2 加密加密Hill2 加密舉例加密舉例A B C D E F G H IJKLM1 2 3 4 5 6 7 89 10 1112 13NOPQRSTUVW XYZ141516171819202122232425018221

8、320 , , , 223420 RB VW MD TT問題：問題：怎樣解密？怎樣解密？明文字母明文字母查表值查表值分組分組一組向量一組向量加加密密矩矩陣陣左左乘乘一組新的向量一組新的向量反查表值反查表值密文密文Hill2 加密過程加密過程模運算模運算先查出密文字母先查出密文字母 “RB VW MD TT” 所對應(yīng)的向量：所對應(yīng)的向量：在模運算下解方程組：在模運算下解方程組： A = q 解密：加密的逆過程，解密：加密的逆過程，將加密過程逆轉(zhuǎn)回去即可。將加密過程逆轉(zhuǎn)回去即可。Hill2 解密過程解密過程18221320223420 ，例：例：怎么得到密文怎么得到密文 “RBVWMDTT ” 的

9、原文的原文? 上面的向量是由上面的向量是由 經(jīng)過經(jīng)過模模 26 運算運算得來的，現(xiàn)在的問題是怎樣逆轉(zhuǎn)回去？得來的，現(xiàn)在的問題是怎樣逆轉(zhuǎn)回去？44743972, , , 54753072模模 m 可逆可逆0,1,2,.,1mZm記記定義定義 1：設(shè)設(shè) A 為定義在集合為定義在集合 Zm 上的上的 n 階方陣，若存在一個定階方陣，若存在一個定義在義在 Zm 上的方陣上的方陣 B，使得使得 則稱則稱 A 模模 m 可逆可逆， B 為為 A 的的 模模 m 逆矩陣逆矩陣，記為，記為(mod)ABBAEm 1(mod)BAm 定義定義 2：設(shè)設(shè) a Zm ，若存在，若存在 b Zm 使得使得 ab=1

10、(mod m) ，則，則稱稱 b 為為 a 的的 模模 m 倒數(shù)倒數(shù) 或乘法逆，記作或乘法逆，記作 b = a-1 (mod m) 。注注: a , b 都是都是 Zm 中的數(shù)中的數(shù)命題：命題：定義在集合定義在集合 Zm 上的上的 n 階方陣階方陣 A 模模 m 可逆的充要條可逆的充要條件是：件是：m 和和 det(A) 無公共素數(shù)因子無公共素數(shù)因子，即，即 m 與與 det(A) 互素?；ニ?。Hill2 密碼的加密矩陣必須滿足上述條件。密碼的加密矩陣必須滿足上述條件。m=26m 的素數(shù)因子只有的素數(shù)因子只有 2 和和 13u 定義在定義在 Z26上的方陣上的方陣 A 模模 26 可逆可逆的充

11、要條件是：的充要條件是：模模 m 可逆可逆det(A) 不能被不能被 2 和和 13 整除整除u 問題：問題：是否是否 Zm 中所有的數(shù)都存在中所有的數(shù)都存在模模 m 倒數(shù)倒數(shù)？a 存在唯一的模存在唯一的模 m 倒數(shù)倒數(shù)a 與與 m 無公共素數(shù)因子無公共素數(shù)因子u Z26 中具有模中具有模 26 倒數(shù)的整數(shù)及其模倒數(shù)的整數(shù)及其模 26 倒數(shù)表倒數(shù)表2a1357911 15 17 19 21 23 25a-11921 15319723 11517 25m=26 時的時的 Matlab 程序見教材第程序見教材第 121 頁頁 附錄附錄1程序程序 可以用來判斷一個可以用來判斷一個 2 階矩陣階矩陣在

12、在模模 26 運算運算下是否可逆，并在可逆的前提下給出其模下是否可逆，并在可逆的前提下給出其模 26 逆矩陣。逆矩陣。模模 26 可逆可逆u 思考：思考：如何用如何用 Matlab 編程來找出所有模編程來找出所有模 m 倒倒數(shù)的整數(shù)及其模數(shù)的整數(shù)及其模 m 倒數(shù)？倒數(shù)？nm=26;nfor a=1:mn for i=1:mn if mod(a*i,m)=1n fprintf(%d 的模的模%d倒數(shù)是倒數(shù)是: %dn,a,m,i);break;n end;n end;nend在模運算下解方程組：在模運算下解方程組： A = 1(mo 2d)6A Hill2 解密過程解密過程？(mod26)u 問

13、題：問題：如何計算如何計算 ？1(mo)6d2A , 8241924,1825102418221320223420 ，模模 m 逆矩陣逆矩陣的的計算計算11|AAA l 設(shè)設(shè) B=k A*為為 A 的的 模模 26 逆逆，其中，其中 k 為待定系數(shù)為待定系數(shù) |BAkAE (mo 26d)BAE | 1(mo6d)2kA 1|(mod)26kA A*為為 A 的伴隨矩陣的伴隨矩陣本計算方法可推廣到求矩陣本計算方法可推廣到求矩陣 A 的的 模模 m 逆矩陣逆矩陣Hill2 解密過程解密過程l 設(shè)加密矩陣設(shè)加密矩陣1203A 32|3,01AA 1132(mod)(m262626od)(mod)0

14、13A 1809 1(mo 2d)6BA 329(mod)0126 , 183422206,21823207134520180,43620180BBBB l 用用 B 左乘密文對應(yīng)的向量得：左乘密文對應(yīng)的向量得：l 模模 26 運算后得：運算后得：l 查表后得明文分別為：查表后得明文分別為： HR XY SJ XXMatlab 的的 Hill2 加密程序見加密程序見 附錄附錄 2，相應(yīng)解密程序見，相應(yīng)解密程序見 附錄附錄 3。18221320223420 ，, 8241924,18251024？, 8241924,18251024Hill2 加密過程總結(jié)加密過程總結(jié) 通訊雙方確定通訊雙方確定加

15、密矩陣加密矩陣 ( 密鑰密鑰) 和字母的和字母的表值對應(yīng)表表值對應(yīng)表 將將明文字母明文字母分組，通過查表列出每組字母對應(yīng)的分組，通過查表列出每組字母對應(yīng)的向量向量 令令 = A mod(m) ，由，由 的分量反查字母表值表，的分量反查字母表值表， 得到相應(yīng)的得到相應(yīng)的密文字母密文字母若明文只含奇數(shù)個字母，則補充一個若明文只含奇數(shù)個字母，則補充一個啞元啞元Hill2 解密過程總結(jié)解密過程總結(jié) 將將密文字母密文字母分組，通過查表列出每組字母對應(yīng)的分組，通過查表列出每組字母對應(yīng)的向量向量 求出加密矩陣求出加密矩陣 A 的的 模模 m 逆矩陣逆矩陣 B 令令 = B mod(m) ，由，由 的分量反查

16、字母表值表，的分量反查字母表值表， 得到相應(yīng)的得到相應(yīng)的明文字母明文字母甲方收到乙方（己方）的一個密文信息，內(nèi)容為：甲方收到乙方（己方）的一個密文信息，內(nèi)容為：Hill2 解密舉例解密舉例WKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC按照甲方與乙方的約定，他們之間采用按照甲方與乙方的約定，他們之間采用 Hill2密碼密碼，密鑰，密鑰為為 ，字母表值見下表，問這段密文的原文，字母表值見下表，問這段密文的原文是什么？是什么？1203A ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021

17、222324250Hill2 解密舉例解密舉例 將將密文字母密文字母分組，通過查表列出每組字母對應(yīng)的分組，通過查表列出每組字母對應(yīng)的向量向量 求出加密矩陣求出加密矩陣 A 的的 模模 26 逆矩陣逆矩陣 用用 B 左乘每組密文字母組成的向量，然后再反查字母左乘每組密文字母組成的向量，然后再反查字母表值表，得到相應(yīng)的表值表，得到相應(yīng)的明文字母明文字母1809B 序序號號分組分組密文密文密文密文表值表值明文明文表值表值分組分組明文明文1W K2311721GU2VA22149DI3CP316114AN4EA51139MI5OC153131MA6IX924198SH序序號號分組分組密文密文密文密文表

18、值表值明文明文表值表值分組分組明文明文7GW723925IY8IZ9090IZ9UR211896IF10OQ15172123UW11WA23159EI12BA21109JIHill2 解密舉例解密舉例序序號號分組分組密文密文密文密文表值表值明文明文表值表值分組分組明文明文13LO121525BE14HD841410NJ15KC11391IA16EA51139MI17FC6341DA18LW12231425NY序序號號分組分組密文密文密文密文表值表值明文明文表值表值分組分組明文明文19WC233211UA20VL2212144ND21EM513513EM22IM913913IM23CC3311A

19、AHill2 解密舉例解密舉例即：即：“古典密碼是以古典密碼是以字符為基本加密單元的密碼字符為基本加密單元的密碼”GU DIAN MI MA SHI YI ZI FU WEI JI BEN JIA MI DAN YUAN DE MI MA AWKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC原文原文Hill2 解密舉例解密舉例密文密文ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021222324250經(jīng)分析該密文是用經(jīng)分析該密文是用 Hill2密碼密碼 加密，且密文加密，且密文 ( U

20、, C ) 和和 ( R, S ) 分別對應(yīng)明文分別對應(yīng)明文 ( T, A ) 和和 ( C, O )，問能否破譯這段密文？問能否破譯這段密文？Hill2 密碼破譯舉例密碼破譯舉例MOFAXJEABAUCRSXJLUYHQATCZHWBCSCP我方截獲一段密文我方截獲一段密文l 猜測密文是由猜測密文是由26個字母組成，即個字母組成，即 m=26， 經(jīng)破譯部門通過大量的統(tǒng)計分析和語言分析確定表值經(jīng)破譯部門通過大量的統(tǒng)計分析和語言分析確定表值l 破譯這段密文的關(guān)鍵是找到破譯這段密文的關(guān)鍵是找到“密鑰密鑰”和和字母對應(yīng)的表值字母對應(yīng)的表值 ,URCSTCAO 2118319203,115 A l 密

21、文密文 ( U, C ) 和和 ( R, S ) 分別對應(yīng)明文分別對應(yīng)明文 ( T, A ) 和和 ( C, O )Hill2 密碼破譯舉例密碼破譯舉例查查 字字 母母 表表 值值A(chǔ) 2118 3 20319115A PCPAC 2118203,319115PC PAC 1A PC |(m7od26)P |(mo161d2 )C P、C 模模26可逆可逆可唯一確定加密矩陣可唯一確定加密矩陣 A11AC P 1126262(mod)(m(moodd6)APC Hill2 密碼破譯舉例密碼破譯舉例HE WI LL VI SI TA CO LL EG ET HI SA FT ER NO ON相應(yīng)的相

22、應(yīng)的 Matlab 程序見程序見附錄附錄 4 u 得到加密矩陣的得到加密矩陣的 模模26逆矩陣逆矩陣 后，根據(jù)前面的解后，根據(jù)前面的解密方法即可得密文的原文密方法即可得密文的原文Hill2 密碼破譯舉例密碼破譯舉例m=27;enmat=1 2;0 4;demat=1 13;0 7;ZERO=64;c=;en=;nfprintf(本組成員的姓名為本組成員的姓名為 陳省身陳省身 華羅庚華羅庚 吳文俊吳文俊,拼音為拼音為:n)nfprintf(CHEN XING SHEN HUA LUO GENG WU WEN JUN n)nfprintf(以以1 2;0 4為密鑰對此拼音串加密為密鑰對此拼音串加密

23、n)nastr=CHEN XING SHEN HUA LUO GENG WU WEN JUN ;nan=double(astr);nif mod(length(an),2)=1n an=an,an(length(an);nendnan=an-ZERO;nfor i=1:length(an)n if an(i)=-32n an(i)=0;n endnendnc=reshape(an,2,length(an)/2);ndn=mod(enmat*c,m);nen=reshape(dn,1,length(an);nen=en+ZERO;nfor i=1:length(en)n if en(i)=64n

24、 en(i)=32;n endnendnen=en(1: length(an);ndisp(密文是密文是:,char(en)本組成員的姓名為本組成員的姓名為 陳省身陳省身 華羅庚華羅庚 吳文俊吳文俊, ,拼音為拼音為: :CHEN XING SHEN HUA LUO GENG WU WEN JUN CHEN XING SHEN HUA LUO GENG WU WEN JUN 以以1 2;0 41 2;0 4為密鑰對此拼音串加密為密鑰對此拼音串加密密文是密文是:SEFBUOJBG HEFBPEWDXUXFNAFBG KCSKFBTMVB:SEFBUOJBG HEFBPEWDXUXFNAFBG K

25、CSKFBTMVB nm=27;enmat=1 2;0 4;demat=1 13;0 7;ZERO=64;c=;en=;nfprintf(本組成員的姓名為陳省身本組成員的姓名為陳省身 華羅庚華羅庚 吳文俊吳文俊,拼音密文為拼音密文為:n)nfprintf( SEFBUOJBG HEFBPEWDXUXFNAFBG KCSKFBTMVB n)nfprintf(以以1 13;0 7為密鑰對此拼音串密文解密為密鑰對此拼音串密文解密n)nastr=SEFBUOJBG HEFBPEWDXUXFNAFBG KCSKFBTMVB;nan=double(astr);nif mod(length(an),2)=1

26、n an=an,an(length(an);nendnan=an-ZERO;nfor i=1:length(an)n if an(i)=-32n an(i)=0;n endnendnc=reshape(an,2,length(an)/2);ndn=mod(demat*c,m);nen=reshape(dn,1,length(an);nen=en+ZERO;nfor i=1:length(en)n if en(i)=64n en(i)=32;n endnendnen=en(1: length(an);ndisp(明文是明文是:,char(en)本組成員的姓名為陳省身本組成員的姓名為陳省身 華羅庚

27、華羅庚 吳文俊吳文俊, ,拼音密文為拼音密文為: : SEFBUOJBG HEFBPEWDXUXFNAFBG KCSKFBTMVB SEFBUOJBG HEFBPEWDXUXFNAFBG KCSKFBTMVB 以以1 13;0 71 13;0 7為密鑰對此拼音串密文解密為密鑰對此拼音串密文解密明文是明文是:CHEN XING SHEN HUA LUO GENG WU WEN JUN:CHEN XING SHEN HUA LUO GENG WU WEN JUN相關(guān)相關(guān)Matlab函數(shù)介紹函數(shù)介紹u inputA=input(提示信息)l 其中 提示信息 為字符串l 該命令要求用戶輸入 A 的值，

28、可以是數(shù)、矩陣或字符串n 數(shù)可以直接輸入n 矩陣需要加 n 字符串需要加單引號 A=input(Please input A: )u sizesize(a)相關(guān)相關(guān)Matlab函數(shù)介紹函數(shù)介紹u lengthlength(a)l 如果 a 是向量，則返回其長度；l 如果 a 是矩陣，則返回行數(shù)與列數(shù)中最大的一個。u modmod(m,n)l 求余，返回 m 被 n 整除后的余數(shù)，符號與 n 相同;l 另外一個求余函數(shù)是 remu gcd ：求最大公約數(shù)gcd(m,n)相關(guān)相關(guān)Matlab函數(shù)介紹函數(shù)介紹u det ：計算行列式det(A)u inv ：計算逆矩陣inv(A)u reshape

29、：將矩陣元素按列方向進行重組reshape(A,m,n)l 將 A 排 m 行，n 列的矩陣，要求 A 的元素個數(shù) =m*n相關(guān)相關(guān)Matlab函數(shù)介紹函數(shù)介紹u doubledouble(str)l 當 str 是字符串時，返回所有字符的 ASCII 碼u charchar(a)l 當 a 是整數(shù)時，返回 ASCII 碼等于 a 的字符數(shù)據(jù)輸出數(shù)據(jù)輸出 fprintfl fid 為文件句柄，若缺省，則將變量的值輸出到屏幕上l format 用來指定數(shù)據(jù)輸出時采用的格式，常見的有 %e ( 采用科學(xué)計算形式采用科學(xué)計算形式 ) %f ( 采用浮點數(shù)形式采用浮點數(shù)形式 ) %g ( 由系統(tǒng)自動選

30、取上述兩種格式之一由系統(tǒng)自動選取上述兩種格式之一) %s ( 輸出字符串輸出字符串) l format 中還可以使用一些特殊格式，如：n ( 換行換行 ) t ( 制表符制表符 ) b ( 退格退格 ) ( 反斜桿反斜桿 ) % ( 百分號百分號 ) fprintf(fid,format,variables)按指定的格式將變量的值輸出到指定的文件u fprintf ：格式化輸出數(shù)據(jù)輸出數(shù)據(jù)輸出 fprintf a=Hello; b=2.4; c=100*pi; fprintf(a=%s,b=%f,c=%en,a,b,c)例：例：l format 中的輸出格式要與輸出變量一一對應(yīng)l 可以沒有輸出變量 fprintf( Today is Mondayn)例：例：附錄附錄 1 1：判斷一個：判斷一個 2 2 階方陣是否模階方陣是否模 26 26 意義下意義下可逆；若可逆，求出?？赡?；若可逆，求出模 26 26 意義下的逆矩陣意義下的逆矩陣nm=26;naa=input(輸入一個輸入一個22的矩陣，格式：的矩陣，格式：a11 a12;a21 a22: )nwhile size(aa)=2 2naa=input(輸入一個輸入一個22的矩陣，格式：的矩陣，格式：a11 a