密碼設(shè)計(jì)解碼破譯

1、密碼的設(shè)計(jì)和使用至少可從追溯到四千多年前的埃及密碼的設(shè)計(jì)和使用至少可從追溯到四千多年前的埃及 ,巴比巴比倫、羅馬和希臘，歷史極為久遠(yuǎn)倫、羅馬和希臘，歷史極為久遠(yuǎn) 。古代古代隱藏信息的方法隱藏信息的方法 主主要有兩大類：要有兩大類： 其一其一為為隱藏信息載體，采用隱寫術(shù)隱藏信息載體，采用隱寫術(shù) 等；等； 其二其二為為變換信息載體，使之無(wú)法為一般人所理解變換信息載體，使之無(wú)法為一般人所理解 。 在密碼學(xué)中，信息代碼被稱為在密碼學(xué)中，信息代碼被稱為 密碼密碼，加密，加密前的信息被稱為前的信息被稱為 明文明文，經(jīng)加密后不為常人，經(jīng)加密后不為常人所理解的用密碼表示的信息被稱為所理解的用密碼表示的信息被稱

2、為 密文密文(ciphertext)，將明文轉(zhuǎn)變成密文的過(guò)程被，將明文轉(zhuǎn)變成密文的過(guò)程被稱為稱為加密加密(enciphering)，其逆過(guò)程則被稱，其逆過(guò)程則被稱為為解密解密(deciphering)，而用以加密、解密，而用以加密、解密的方法或算法則被稱為的方法或算法則被稱為 密碼體制密碼體制(crytosystem)。記全體明文組成的集合記全體明文組成的集合 為為u，全體密文組成的集合，全體密文組成的集合 為為v，稱，稱u為明文空間，為明文空間，v為密文空間。加密常利用某一被稱為密鑰的東為密文空間。加密常利用某一被稱為密鑰的東西來(lái)實(shí)現(xiàn)，它通常取自于一個(gè)被稱為密鑰空間的含有若干參西來(lái)實(shí)現(xiàn)，它通

3、常取自于一個(gè)被稱為密鑰空間的含有若干參數(shù)的集合數(shù)的集合k。按數(shù)學(xué)的觀點(diǎn)來(lái)看，加密與解密均可被看成是一。按數(shù)學(xué)的觀點(diǎn)來(lái)看，加密與解密均可被看成是一種變換：取一種變換：取一kk， uu，令，令 ，v為明為明文文u在密鑰在密鑰k下的密文，而解碼則要用下的密文，而解碼則要用 到到k的逆變換的逆變換k-1，。由，。由此可見，密碼體系雖然可以千姿百態(tài)，但其關(guān)鍵還在此可見，密碼體系雖然可以千姿百態(tài)，但其關(guān)鍵還在 于于密鑰密鑰的選取的選取。 v vv vu uk k隨著計(jì)算機(jī)與網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，大量各具特色的密碼體隨著計(jì)算機(jī)與網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，大量各具特色的密碼體系不斷涌現(xiàn)。離散數(shù)學(xué)、數(shù)論、計(jì)算復(fù)雜性、混

4、沌、系不斷涌現(xiàn)。離散數(shù)學(xué)、數(shù)論、計(jì)算復(fù)雜性、混沌、，許多相當(dāng)高深的數(shù)學(xué)知識(shí)都被用上，逐步形成了（并仍在迅許多相當(dāng)高深的數(shù)學(xué)知識(shí)都被用上，逐步形成了（并仍在迅速發(fā)展的）具有廣泛應(yīng)用面的速發(fā)展的）具有廣泛應(yīng)用面的 現(xiàn)代密碼學(xué)現(xiàn)代密碼學(xué) 。 替代密碼替代密碼 移位密碼移位密碼 代數(shù)密碼代數(shù)密碼 代替法密碼代替法密碼采用另一個(gè)字母表中的字母來(lái)代替明文中的字母，采用另一個(gè)字母表中的字母來(lái)代替明文中的字母，明文字母與密文字母保持一一對(duì)應(yīng)關(guān)系，但采用的符號(hào)改變明文字母與密文字母保持一一對(duì)應(yīng)關(guān)系，但采用的符號(hào)改變了。加密時(shí)，把明文換成密文，即將明文中的字母用密文字了。加密時(shí)，把明文換成密文，即將明文中的字母用

5、密文字母表中對(duì)應(yīng)位置上的字母取代。解密時(shí)，則把密文換成明文，母表中對(duì)應(yīng)位置上的字母取代。解密時(shí)，則把密文換成明文，即把密文中的字母用明文字母表中對(duì)應(yīng)位置上的字母代回，即把密文中的字母用明文字母表中對(duì)應(yīng)位置上的字母代回，解密過(guò)程是加密過(guò)程的逆過(guò)程。在代替法加密過(guò)程中，密文解密過(guò)程是加密過(guò)程的逆過(guò)程。在代替法加密過(guò)程中，密文字母表即代替法密鑰，密鑰可以是標(biāo)準(zhǔn)字母表，也可以是任字母表即代替法密鑰，密鑰可以是標(biāo)準(zhǔn)字母表，也可以是任意建立的。意建立的。 1.代替法密碼代替法密碼明文字母表明文字母表 abcdefghijklmnopqrstuvwxyz密文字母表密文字母表 klmnopqrstuvwxyz

6、abcdefghij密鑰常用一密鑰單詞或密鑰短語(yǔ)生成混淆字母表。密鑰單詞密鑰常用一密鑰單詞或密鑰短語(yǔ)生成混淆字母表。密鑰單詞 或密鑰短語(yǔ)可以存放在識(shí)別碼、通行字或密鑰的秘密表格中?；蛎荑€短語(yǔ)可以存放在識(shí)別碼、通行字或密鑰的秘密表格中。 混合一個(gè)字母表，常見的有兩種方法，這兩種方法都采用混合一個(gè)字母表，常見的有兩種方法，這兩種方法都采用了一個(gè)了一個(gè)密鑰單詞密鑰單詞或一個(gè)或一個(gè)密鑰短語(yǔ)密鑰短語(yǔ)。 方法方法1：a)選擇一個(gè)密鑰單詞或密鑰短語(yǔ)，例如：選擇一個(gè)密鑰單詞或密鑰短語(yǔ)，例如：constructb)去掉其中重復(fù)的字母，得：去掉其中重復(fù)的字母，得：construc)在修改后的密鑰后面接上從標(biāo)準(zhǔn)字母

7、表中去掉密鑰中已有在修改后的密鑰后面接上從標(biāo)準(zhǔn)字母表中去掉密鑰中已有的字母后剩下的字母，得：的字母后剩下的字母，得：明文字母表明文字母表 abcdefghijklmnopqrstuvwxyz密文字母表密文字母表 construabdefghijklmpqvwxyz在設(shè)計(jì)密鑰時(shí)，也可在明文字母表中選擇一個(gè)特定字母，然在設(shè)計(jì)密鑰時(shí)，也可在明文字母表中選擇一個(gè)特定字母，然后從該特定字母開始寫密鑰單詞將密鑰單詞隱藏于其中。例后從該特定字母開始寫密鑰單詞將密鑰單詞隱藏于其中。例如，對(duì)于上例，選取特定字如，對(duì)于上例，選取特定字 母母 k k，則可得：，則可得： 明文字母表明文字母表 abcdefghijk

8、lmnopqrstuvwxyz密文字母表密文字母表 klmpqvwxyzconstruabdefghij 方法方法2 2：a)a)選擇一個(gè)密鑰單詞或密鑰短語(yǔ)，例如：選擇一個(gè)密鑰單詞或密鑰短語(yǔ)，例如： constructconstructb)b)去掉其中重復(fù)的字母，得：去掉其中重復(fù)的字母，得：construconstruc)c)這些字母構(gòu)成矩陣的第一行，矩陣的后續(xù)各行由標(biāo)準(zhǔn)字母這些字母構(gòu)成矩陣的第一行，矩陣的后續(xù)各行由標(biāo)準(zhǔn)字母表中去掉密鑰單詞的字母后剩下的字母構(gòu)成表中去掉密鑰單詞的字母后剩下的字母構(gòu)成d)d)將所得矩陣中的字母按列的順序排出將所得矩陣中的字母按列的順序排出 得：得： cugmyo

9、ahpznbiqsdjvrtekwrflx按照此方法產(chǎn)生的字母表稱為按照此方法產(chǎn)生的字母表稱為 混淆字母表混淆字母表。還可以使用還可以使用混淆數(shù)混淆數(shù)。混淆數(shù)由以下方法產(chǎn)生：。混淆數(shù)由以下方法產(chǎn)生：a)選一密鑰單詞或密鑰短語(yǔ)，例如：選一密鑰單詞或密鑰短語(yǔ)，例如：constructb)按照這些字母在標(biāo)準(zhǔn)字母表中出現(xiàn)的相對(duì)順序給它們編號(hào)，按照這些字母在標(biāo)準(zhǔn)字母表中出現(xiàn)的相對(duì)順序給它們編號(hào)，對(duì)序列中重復(fù)的字母則自左向右編號(hào)，得對(duì)序列中重復(fù)的字母則自左向右編號(hào)，得 ：construct 143675928c)自左向右選出這些數(shù)自左向右選出這些數(shù) 字字,得到一個(gè)混淆數(shù)字得到一個(gè)混淆數(shù)字 組組:14367

10、5928，混淆字母表由從小到大的順序取矩陣中相應(yīng)列得出?；煜帜副碛蓮男〉酱蟮捻樞蛉【仃囍邢鄳?yīng)列得出。為增加保密性，在使用為增加保密性，在使用代替法時(shí)還可利用一些代替法時(shí)還可利用一些其他技巧，如單字母表其他技巧，如單字母表對(duì)多字母表、單字母對(duì)對(duì)多字母表、單字母對(duì)多字母、多重代替等。多字母、多重代替等。 2.移位密碼體制移位密碼體制移位密碼移位密碼采用移位法進(jìn)行加密，明文中的字母重新排列，本采用移位法進(jìn)行加密，明文中的字母重新排列，本身不變，只是位置改變了。身不變，只是位置改變了。早在早在4000多年前，古希臘人就用一種名多年前，古希臘人就用一種名 叫叫“天書天書”的器械的器械來(lái)加密消息。該密碼

11、器械是用一條窄長(zhǎng)的草紙纏繞在一個(gè)來(lái)加密消息。該密碼器械是用一條窄長(zhǎng)的草紙纏繞在一個(gè)直徑確定的圓筒上，明文逐行橫寫在紙帶上，當(dāng)取下紙帶直徑確定的圓筒上，明文逐行橫寫在紙帶上，當(dāng)取下紙帶時(shí)，字母的次序就被打亂了，消息得以隱蔽。收方閱讀消時(shí)，字母的次序就被打亂了，消息得以隱蔽。收方閱讀消息時(shí)，要將紙帶重新繞在直徑與原來(lái)相同的圓筒上，才能息時(shí)，要將紙帶重新繞在直徑與原來(lái)相同的圓筒上，才能看到正確的消息。在這里圓筒的直徑起到了密鑰的作用?？吹秸_的消息。在這里圓筒的直徑起到了密鑰的作用。 另一種移位另一種移位 法法采用將字母表中的字母平移若干位的方法來(lái)構(gòu)造采用將字母表中的字母平移若干位的方法來(lái)構(gòu)造密文字

12、母表，傳說(shuō)這類方法是由古羅馬皇帝凱撒最早使用的，密文字母表，傳說(shuō)這類方法是由古羅馬皇帝凱撒最早使用的，故這種密文字母表被稱為凱撒字母表。例如，如用將字母表向故這種密文字母表被稱為凱撒字母表。例如，如用將字母表向右平移右平移3位的方法來(lái)構(gòu)造密文字母表，可位的方法來(lái)構(gòu)造密文字母表，可 得：得： 明文字母表明文字母表： abcdefghijklmnopqrstuvwxyz密文字母表密文字母表： defghijklmnopqrtsuvwxyzabc因此因此 “thank you” “wkdqn brx” 以上兩種移位較易被人破譯，為打破字母表中原有的順序還可以上兩種移位較易被人破譯，為打破字母表中原有

13、的順序還可采用所謂路線加密法，即把明文字母表按某種既定的順序安排采用所謂路線加密法，即把明文字母表按某種既定的順序安排在一個(gè)矩陣中，然后用另一種順序選出矩陣中的字母來(lái)產(chǎn)生密在一個(gè)矩陣中，然后用另一種順序選出矩陣中的字母來(lái)產(chǎn)生密文表。文表。 例如，對(duì)明文：例如，對(duì)明文：the history of zju is more than one hundred years.以以7列矩陣表示如下：列矩陣表示如下：thehistoryofzjuismorethanonehundredyears再按事先約定的方式選出密文。例如，如按列選出，得到再按事先約定的方式選出密文。例如，如按列選出，得到密文：密文：t

14、outhyhrihueeysanahomndrifoorsszrnetjeed使用不同的順序進(jìn)行編寫和選擇，可以得到各種不同的路使用不同的順序進(jìn)行編寫和選擇，可以得到各種不同的路線加密體制。對(duì)于同一明文消息矩陣，采用不同的抄寫方線加密體制。對(duì)于同一明文消息矩陣，采用不同的抄寫方式，得到的密文也是不同的。式，得到的密文也是不同的。 當(dāng)明文超過(guò)規(guī)定矩陣的大小時(shí)，可以另加一矩陣。當(dāng)需要當(dāng)明文超過(guò)規(guī)定矩陣的大小時(shí)，可以另加一矩陣。當(dāng)需要加密的字母數(shù)小于矩陣大小時(shí)，可以在矩陣中留空位或以加密的字母數(shù)小于矩陣大小時(shí)，可以在矩陣中留空位或以無(wú)用的字母來(lái)填滿矩陣。無(wú)用的字母來(lái)填滿矩陣。 移位法也可和代替法結(jié)合

15、使用，并使用約定的單詞或短語(yǔ)作移位法也可和代替法結(jié)合使用，并使用約定的單詞或短語(yǔ)作密鑰，以進(jìn)一步加強(qiáng)保密性，這就密鑰，以進(jìn)一步加強(qiáng)保密性，這就 是是鑰控列序加密鑰控列序加密 法法。 例如例如，用密鑰單詞，用密鑰單詞 construct對(duì)明文對(duì)明文mathematical modeling is useful加密：加密：construct 1 4 3 675 9 28mathematicalmodelingisusefu l 按混淆數(shù)的順序選出各列，得到密文：按混淆數(shù)的順序選出各列，得到密文： mcnltlftliaagmdshmseosiiuaee移位法的使用可重復(fù)多次，只進(jìn)行一次移位加密的稱

16、為一移位法的使用可重復(fù)多次，只進(jìn)行一次移位加密的稱為一 次移位法次移位法，經(jīng)多次移位的則稱，經(jīng)多次移位的則稱 為為多次移位法多次移位法 代替法與移位法密碼代替法與移位法密碼 的的破譯破譯 對(duì)竊聽到的密文進(jìn)行分析時(shí)對(duì)竊聽到的密文進(jìn)行分析時(shí) ，窮舉法窮舉法和和統(tǒng)計(jì)法統(tǒng)計(jì)法是最基本的是最基本的破譯方法破譯方法 。窮舉分析法窮舉分析法 就是對(duì)所有可能的密鑰或明文進(jìn)行逐一試探，就是對(duì)所有可能的密鑰或明文進(jìn)行逐一試探，直至試探到直至試探到“正確正確”的為止。此的為止。此 方法方法需要事先知道密碼體需要事先知道密碼體制或加密算法制或加密算法（但不知道密鑰或加密具體辦法）。破譯時(shí)（但不知道密鑰或加密具體辦法）

17、。破譯時(shí)需將猜測(cè)到的明文和選定的密鑰輸入給算法，產(chǎn)生密文，需將猜測(cè)到的明文和選定的密鑰輸入給算法，產(chǎn)生密文，再將該密文與竊聽來(lái)的密文比較。如果相同，則認(rèn)為該密再將該密文與竊聽來(lái)的密文比較。如果相同，則認(rèn)為該密鑰就是所要求的，否則繼續(xù)試探，直至破譯。以英文字母鑰就是所要求的，否則繼續(xù)試探，直至破譯。以英文字母為例，當(dāng)已知對(duì)方在采用代替法加密時(shí)，如果使用窮舉字為例，當(dāng)已知對(duì)方在采用代替法加密時(shí)，如果使用窮舉字母表來(lái)破譯，那么對(duì)于最簡(jiǎn)單的一種使用單字母表單字母表來(lái)破譯，那么對(duì)于最簡(jiǎn)單的一種使用單字母表單字母單元代替法加密的密碼，字母表的可能情況母單元代替法加密的密碼，字母表的可能情況 有有26！種，

18、種，可見，單純地使用窮舉法，在實(shí)際應(yīng)用中幾乎是行不通的，可見，單純地使用窮舉法，在實(shí)際應(yīng)用中幾乎是行不通的，只能與其它方法結(jié)合使用。只能與其它方法結(jié)合使用。 統(tǒng)計(jì)法統(tǒng)計(jì)法是根據(jù)統(tǒng)計(jì)資料進(jìn)行猜測(cè)的。在一段足夠長(zhǎng)且非特別是根據(jù)統(tǒng)計(jì)資料進(jìn)行猜測(cè)的。在一段足夠長(zhǎng)且非特別專門化的文章中，字母的使用頻率是比較穩(wěn)定的。在某些技專門化的文章中，字母的使用頻率是比較穩(wěn)定的。在某些技術(shù)性或?qū)ｉT化文章中的字母使用頻率可能有微小變化。術(shù)性或?qū)ｉT化文章中的字母使用頻率可能有微小變化。 在上述兩種加密方法中字母表中的字母是一一對(duì)應(yīng)的，因此，在上述兩種加密方法中字母表中的字母是一一對(duì)應(yīng)的，因此，在截獲的密文中各字母出現(xiàn)的概

19、率提供了重要的密鑰信息。根在截獲的密文中各字母出現(xiàn)的概率提供了重要的密鑰信息。根據(jù)權(quán)威資料報(bào)道，可以據(jù)權(quán)威資料報(bào)道，可以 將將26個(gè)英文字母按其出現(xiàn)的頻率大小個(gè)英文字母按其出現(xiàn)的頻率大小較合理地分為五組：較合理地分為五組：i. t,a,o,i,n,s,h,r; ii. e; iii. d,l; iv. c,u,m,w,f,g,y,p,b; v. v,k,j,x,q,z; 不僅單個(gè)字母以相當(dāng)穩(wěn)定的頻率出現(xiàn)，不僅單個(gè)字母以相當(dāng)穩(wěn)定的頻率出現(xiàn)，相鄰字母對(duì)相鄰字母對(duì)和和三字母三字母對(duì)對(duì)同樣如此。同樣如此。按按頻率大小頻率大小 將雙字母排列如下：將雙字母排列如下：th,he,in,er,an,re,ed

20、,on,es,st,en,at,to,nt,ha,nd,ou,ea,ng,as,or,ti,is,er,it,ar,te,se,hi,of使用最多的三字母按頻率大小排列如下：使用最多的三字母按頻率大小排列如下： the,ing,and,her,ere,ent,tha,nth,was,eth,for,dth統(tǒng)計(jì)的章節(jié)越長(zhǎng)，統(tǒng)計(jì)結(jié)統(tǒng)計(jì)的章節(jié)越長(zhǎng)，統(tǒng)計(jì)結(jié)果就越可靠。對(duì)于只有幾果就越可靠。對(duì)于只有幾個(gè)單詞的密文，統(tǒng)計(jì)是無(wú)個(gè)單詞的密文，統(tǒng)計(jì)是無(wú)意義的。意義的。下面介紹一下統(tǒng)計(jì)觀察的三個(gè)結(jié)果：下面介紹一下統(tǒng)計(jì)觀察的三個(gè)結(jié)果：a)單詞單詞the在這些統(tǒng)計(jì)中有重要的作用；在這些統(tǒng)計(jì)中有重要的作用；b)以以e，

21、s，d，t為結(jié)尾的英語(yǔ)單詞超過(guò)了一半；為結(jié)尾的英語(yǔ)單詞超過(guò)了一半；c)以以t，a，s，w為起始字母的英語(yǔ)單詞約為一半。為起始字母的英語(yǔ)單詞約為一半。對(duì)于對(duì)于a) ，如果，如果 將將the從明文中刪除，那從明文中刪除，那 么么t的頻率將要降的頻率將要降到第二組中其他字母之后，到第二組中其他字母之后， 而而h將降到第三組中，并將降到第三組中，并 且且th和和he就不再是最眾多的字母了。就不再是最眾多的字母了。以上對(duì)英語(yǔ)統(tǒng)計(jì)的討論是在僅涉以上對(duì)英語(yǔ)統(tǒng)計(jì)的討論是在僅涉 及及26個(gè)字母的假設(shè)條件個(gè)字母的假設(shè)條件下進(jìn)行的。實(shí)際上消息的構(gòu)成還包括間隔、標(biāo)點(diǎn)、數(shù)字下進(jìn)行的。實(shí)際上消息的構(gòu)成還包括間隔、標(biāo)點(diǎn)、數(shù)

22、字等字符?？傊?，破譯密碼并不是件很容易的事。等字符。總之，破譯密碼并不是件很容易的事。 2.希爾密碼希爾密碼代替密碼與移位密碼的一個(gè)致命弱點(diǎn)代替密碼與移位密碼的一個(gè)致命弱點(diǎn) 是是明文字符明文字符和和密文字密文字符符有相同的有相同的使用頻率使用頻率,破譯者可從統(tǒng)計(jì)出來(lái)的字符頻率中找破譯者可從統(tǒng)計(jì)出來(lái)的字符頻率中找到規(guī)律，進(jìn)而找出破譯的突破口。要克服這一缺陷，提高到規(guī)律，進(jìn)而找出破譯的突破口。要克服這一缺陷，提高保密程度就必須改變字符間的一一對(duì)應(yīng)。保密程度就必須改變字符間的一一對(duì)應(yīng)。 1929年，希爾利用線性代數(shù)中的矩陣運(yùn)算，打破了字符間的年，希爾利用線性代數(shù)中的矩陣運(yùn)算，打破了字符間的對(duì)應(yīng)關(guān)系，

23、設(shè)計(jì)了一種被稱為希爾密碼的代數(shù)密碼。為了便對(duì)應(yīng)關(guān)系，設(shè)計(jì)了一種被稱為希爾密碼的代數(shù)密碼。為了便于計(jì)算，希爾首先將字符變換成數(shù)，例如，對(duì)英文字母，我于計(jì)算，希爾首先將字符變換成數(shù)，例如，對(duì)英文字母，我們可以作如下變換：們可以作如下變換： abc de fg h i j k l m n o p q r s t u v w x y z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0將密文分成將密文分成 n個(gè)一組，用對(duì)應(yīng)的數(shù)字代替，就變成了一個(gè)個(gè)一組，用對(duì)應(yīng)的數(shù)字代替，就變成了一個(gè) 個(gè)個(gè)n維向量。如果取定一維向量。

24、如果取定一 個(gè)個(gè)n階的非奇異矩階的非奇異矩 陣陣a（此矩陣為主（此矩陣為主要密鑰），要密鑰）， 用用a去乘每一向量，即可起到加密的效果，解密去乘每一向量，即可起到加密的效果，解密也不麻煩，將密文也分也不麻煩，將密文也分 成成n個(gè)一組，同樣變換個(gè)一組，同樣變換 成成n維向量，維向量，只需用去乘這些向量，即可將他們變回原先的明文。只需用去乘這些向量，即可將他們變回原先的明文。 定理定理1 ,若若 使得使得 (mod26)，則必有，則必有 =1，其，其中中 為為 與與26的最大公因子。的最大公因子。 0 0, ,. . . ., ,2 25 5 a a0,250,25a a1 11 1a aa aa

25、 aa a1 11 1g gc cd d a a, ,2 26 6 g gc cd d a a, ,2 26 6 a a證證 任取任取 0 0, ,. . . ., ,2 25 5 p p，令，令q q2 26 6k ka ap p，于是，于是k k26a26ap p26k)26k)(ap(apa aq qa aapapa a1 11 11 11 1，故，故k k26a26a1)p1)pa a(a(a1 11 1，由，由p p的任意性可知必有的任意性可知必有 1 1a aa a1 1 (mod26) 即即 1 126k26ka aa a, ,k k1 1上式說(shuō)明必有上式說(shuō)明必有1 1g gc

26、cd d a a, ,2 26 6 ，不然它將整，不然它將整 除除1，而這是不可能的。，而這是不可能的。在具體實(shí)施時(shí)在具體實(shí)施時(shí) ，我們很快會(huì)發(fā)現(xiàn)一些困，我們很快會(huì)發(fā)現(xiàn)一些困難：難： (1) 為了使數(shù)字與字符間可以互換，必須為了使數(shù)字與字符間可以互換，必須使用取自使用取自025之間的整數(shù)之間的整數(shù) (2)由線性代數(shù)知識(shí)，由線性代數(shù)知識(shí)， ，其中，其中 為為a的伴隨矩陣。由于使用了除法，的伴隨矩陣。由于使用了除法，在在 求求a的逆矩陣時(shí)可能會(huì)出現(xiàn)分?jǐn)?shù)。不的逆矩陣時(shí)可能會(huì)出現(xiàn)分?jǐn)?shù)。不解決這些困難，上述想法仍然無(wú)法實(shí)現(xiàn)。解決這些困難，上述想法仍然無(wú)法實(shí)現(xiàn)。解決的辦法是引進(jìn)同余運(yùn)算，并用乘法解決的辦法

27、是引進(jìn)同余運(yùn)算，并用乘法來(lái)代替除法，（如同線性代數(shù)中用逆矩來(lái)代替除法，（如同線性代數(shù)中用逆矩陣代替矩陣除法一樣）。陣代替矩陣除法一樣）。det(a)det(a)a aa a1 1a a 此外，我們還不難證明這樣的此外，我們還不難證明這樣的1 1a a還是由還是由a a唯一確定的。事實(shí)上設(shè)有唯一確定的。事實(shí)上設(shè)有 1 126k26ka aa a1 11 11 1 和和 1 126k26ka aa a2 21 12 2 ) )0,.,260,.,26a a, ,(a(a1 12 21 11 1則則 ) )k k26(k26(k)a)aa a(a(a2 21 11 12 21 11 1 故必有故必有

28、2 21 1k kk k （也因?yàn)椋ㄒ惨驗(yàn)? 1g gc cd d a a, ,2 26 6 ），即），即1 12 21 11 1a aa a 由定理由定理1，026中除中除13以外的奇數(shù)均可取作這里的以外的奇數(shù)均可取作這里的a a，下表為經(jīng)計(jì)算求得的逆元素，下表為經(jīng)計(jì)算求得的逆元素 a a 1 3 5 7 9 11 15 17 19 21 23 251 1a a 1 9 21 15 3 19 7 23 11 5 17 25例例1 取取a = 3用希爾密碼體系加密語(yǔ)句用希爾密碼體系加密語(yǔ)句thank you步步1 將將thank you轉(zhuǎn)換成轉(zhuǎn)換成 （20，8，1，14，11，25，15，21

29、）步步2 每一分量乘以每一分量乘以 3并關(guān)于并關(guān)于26取余得取余得 （8，24，3，16，7，23，19，11） 密文為密文為hxcpg wsk現(xiàn)在我們已不難將方法推現(xiàn)在我們已不難將方法推 廣到廣到n為一般整數(shù)為一般整數(shù)的情況了的情況了,只需在乘法運(yùn)算中結(jié)合應(yīng)用取余，只需在乘法運(yùn)算中結(jié)合應(yīng)用取余，求逆矩陣時(shí)用逆元素相乘來(lái)代替除法即可。求逆矩陣時(shí)用逆元素相乘來(lái)代替除法即可。 例例2 取取a = 則則 (具體求法見具體求法見后后),用用a加密加密thank you,再用再用 對(duì)密文解密對(duì)密文解密 0 01 13 32 20 01 1a a1 19 98 81 1a a 8 82 20 01 14

30、41 12 25 51 11 12 21 11 15 5用矩陣用矩陣a左乘各向量加密（關(guān)左乘各向量加密（關(guān) 于于26取余）得取余）得 2410 163 239 115得到密文得到密文 jxcpi wek 解解:(希爾密碼加希爾密碼加 密密)用相應(yīng)數(shù)字代替字符，劃分為兩個(gè)元素一用相應(yīng)數(shù)字代替字符，劃分為兩個(gè)元素一 組并表示為向量：組并表示為向量：（希爾密碼解密希爾密碼解密）用用a-1左乘求得的向量，即可還原為原來(lái)的向量。左乘求得的向量，即可還原為原來(lái)的向量。 (自行驗(yàn)證自行驗(yàn)證)希爾密碼是以希爾密碼是以矩陣矩陣 法法為基礎(chǔ)的，明文與密文的對(duì)為基礎(chǔ)的，明文與密文的對(duì) 應(yīng)由應(yīng)由n階矩階矩陣陣a確定。

31、矩陣確定。矩陣a的階數(shù)是事先約定的，與明文分組時(shí)每組字的階數(shù)是事先約定的，與明文分組時(shí)每組字母的字母數(shù)量相同，如果明文所含字?jǐn)?shù)母的字母數(shù)量相同，如果明文所含字?jǐn)?shù) 與與n不匹配，則最后不匹配，則最后幾個(gè)分量可任意補(bǔ)足。幾個(gè)分量可任意補(bǔ)足。 a-1的求法的求法方法方法1 利用公式利用公式 ，例如，若取，例如，若取 ，則則 , , (mod26) ，即，即 方法方法2 利用高斯消去法。將矩利用高斯消去法。將矩 陣陣(a, e)中的矩陣中的矩陣a消為消為e，則原先的則原先的e即被消成了即被消成了a-1，)det(1aaa 01a 323)det( a9)det(1 a 039a1 12 011a 98

32、 如如 01 32 ， 01 10(用用9乘第二行并取同乘第二行并取同 余余) 01 12 ， 01 90第一行減去第二行第一行減去第二行 的的2倍并取同余，得倍并取同余，得 01 10 ， 01 98左端矩陣已化為單位陣，故右端矩陣即為左端矩陣已化為單位陣，故右端矩陣即為 a-1希爾密碼系統(tǒng)的解密依賴于以下幾把鑰匙希爾密碼系統(tǒng)的解密依賴于以下幾把鑰匙 （key）：）：key1 矩陣矩陣a的階數(shù)的階數(shù)n，即，即 明文是按幾個(gè)字母來(lái)明文是按幾個(gè)字母來(lái) 劃分的。劃分的。key2 變換矩陣變換矩陣a，只有知，只有知 道了道了a才可能推算出才可能推算出key3 明文和密文由字母表明文和密文由字母表 轉(zhuǎn)

33、換成轉(zhuǎn)換成 n維向量所對(duì)維向量所對(duì) 應(yīng)的非負(fù)整數(shù)表（上應(yīng)的非負(fù)整數(shù)表（上 面，為方便起見，我面，為方便起見，我 們采用了字母的自然們采用了字母的自然 順序）。順序）。希爾密碼體系為破譯者設(shè)置了多道關(guān)口，加大了破譯難度。破希爾密碼體系為破譯者設(shè)置了多道關(guān)口，加大了破譯難度。破譯和解密是兩個(gè)不同的概念，雖然兩者同樣是希望對(duì)密文加以譯和解密是兩個(gè)不同的概念，雖然兩者同樣是希望對(duì)密文加以處理而得到明文的內(nèi)容，但是他們有一個(gè)最大的不處理而得到明文的內(nèi)容，但是他們有一個(gè)最大的不 同同破破譯密碼時(shí)，解密必需用到的鑰匙未能取得，破譯密碼的一方需譯密碼時(shí)，解密必需用到的鑰匙未能取得，破譯密碼的一方需要依要依 據(jù)

34、據(jù)密文的長(zhǎng)度密文的長(zhǎng)度，文字的本身特征文字的本身特征，以及，以及行文習(xí)慣行文習(xí)慣 等等各等等各方面的信息進(jìn)行破譯。破譯密碼雖然需要技術(shù)，但更加重要的方面的信息進(jìn)行破譯。破譯密碼雖然需要技術(shù)，但更加重要的是是“猜測(cè)猜測(cè)”的藝術(shù)。的藝術(shù)?！安聹y(cè)猜測(cè)”的成功與否直接決定著破譯的結(jié)的成功與否直接決定著破譯的結(jié)果。果。破譯希爾密碼的關(guān)鍵是猜測(cè)文字被轉(zhuǎn)換成成幾維向量所、對(duì)應(yīng)破譯希爾密碼的關(guān)鍵是猜測(cè)文字被轉(zhuǎn)換成成幾維向量所、對(duì)應(yīng)的字母表是怎樣的，更為重要的是要設(shè)法獲取加密矩的字母表是怎樣的，更為重要的是要設(shè)法獲取加密矩 陣陣a。（希爾密碼的破譯希爾密碼的破譯）由線性代數(shù)的知識(shí)可以知道，矩陣完全由線性代數(shù)的知

35、識(shí)可以知道，矩陣完全由一組基的變換決定，對(duì)由一組基的變換決定，對(duì) 于于n階矩陣階矩陣a，只要猜出密文只要猜出密文 中中n個(gè)線性無(wú)關(guān)的向量個(gè)線性無(wú)關(guān)的向量 iiapq (i=1, 2, , n) 對(duì)應(yīng)的明文對(duì)應(yīng)的明文 (i=1, 2, , n)是什么是什么 ，即，即可確定可確定a，并將密碼破譯。，并將密碼破譯。 在實(shí)際計(jì)算中，可以利用以下方法：在實(shí)際計(jì)算中，可以利用以下方法：令令則則tnpppp),.,(21 ，tntappppaq ),.,(211)(, ttaqppaq取矩陣取矩陣q | p,經(jīng)過(guò)一系列初等行變換，將由密文決定經(jīng)過(guò)一系列初等行變換，將由密文決定 的的n維矩陣維矩陣q化為化為n

36、階單位陣階單位陣 i的時(shí)候，由明文決定的矩的時(shí)候，由明文決定的矩 陣陣p自自動(dòng)化為動(dòng)化為 (a-1)t，即，即 ：),)(,()(,11111 tttaiaqqqqaqqpq（初等行變換）初等行變換）例例5 有密文如下有密文如下:goqbxcbuglosnfal;根據(jù)英文的行根據(jù)英文的行文習(xí)慣以及獲取密碼的途徑和背景，猜測(cè)是兩個(gè)字文習(xí)慣以及獲取密碼的途徑和背景，猜測(cè)是兩個(gè)字母為一組的希爾密碼，前四個(gè)明文字母母為一組的希爾密碼，前四個(gè)明文字母 是是dear，試破譯這段秘文。試破譯這段秘文。解解： 前兩組明文字前兩組明文字 母母de和和ar 對(duì)應(yīng)的二維向量是：對(duì)應(yīng)的二維向量是： 按同一對(duì)應(yīng)整數(shù)表，

37、密文中對(duì)應(yīng)這兩組的二維向量是：按同一對(duì)應(yīng)整數(shù)表，密文中對(duì)應(yīng)這兩組的二維向量是：ttpp)18, 1(,)5 , 4(21 tapq)15, 7(11 ， tapq)2 ,17(22 ， tqqq),(21 由此可得由此可得)( ,)26(mod(,1 taipq初初等等行行變變換換），對(duì)應(yīng)上例則有，對(duì)應(yīng)上例則有 9051,100118514,215177初等行變換并取同余初等行變換并取同余 51)(1 ta 90 , 011a 95利用這一逆矩陣，可對(duì)截獲密文進(jìn)行解密，破譯出的電文是利用這一逆矩陣，可對(duì)截獲密文進(jìn)行解密，破譯出的電文是dear mac god forbid. 這只是對(duì)最簡(jiǎn)單情況

38、進(jìn)行的舉例，如果加密矩陣的階數(shù)大于這只是對(duì)最簡(jiǎn)單情況進(jìn)行的舉例，如果加密矩陣的階數(shù)大于2，需要的密文應(yīng)該有較長(zhǎng)長(zhǎng)度，所需的計(jì)算量也是很大的。破需要的密文應(yīng)該有較長(zhǎng)長(zhǎng)度，所需的計(jì)算量也是很大的。破譯的關(guān)鍵是猜譯的關(guān)鍵是猜 中中n及及n個(gè)獨(dú)立的個(gè)獨(dú)立的n維向量，其后求解加密矩陣維向量，其后求解加密矩陣的計(jì)算量?jī)H為的計(jì)算量?jī)H為 o(n2 )。希爾密碼體制中有兩個(gè)要素非常重要：希爾密碼體制中有兩個(gè)要素非常重要： 第一第一是字母是字母 與與n維向量進(jìn)行轉(zhuǎn)換所依維向量進(jìn)行轉(zhuǎn)換所依據(jù)的非負(fù)整數(shù)表，本節(jié)中所舉的是最據(jù)的非負(fù)整數(shù)表，本節(jié)中所舉的是最自然的情況；當(dāng)然如果依據(jù)其它的整自然的情況；當(dāng)然如果依據(jù)其它的整

39、數(shù)表也是完全可以進(jìn)行的，其情況將數(shù)表也是完全可以進(jìn)行的，其情況將會(huì)更復(fù)雜一些，破譯的難度就會(huì)增大。會(huì)更復(fù)雜一些，破譯的難度就會(huì)增大。 第二第二個(gè)要素是加密矩陣，如何定義、個(gè)要素是加密矩陣，如何定義、求解這個(gè)矩陣對(duì)于密碼的加密和破譯求解這個(gè)矩陣對(duì)于密碼的加密和破譯更加關(guān)鍵。唯一的要求是加密時(shí)應(yīng)選更加關(guān)鍵。唯一的要求是加密時(shí)應(yīng)選擇行列式值與擇行列式值與 26無(wú)公因子的矩陣。無(wú)公因子的矩陣。 rsa公開密鑰體制公開密鑰體制 傳統(tǒng)的密碼通訊只能在事先約定的雙方間進(jìn)行，雙方必須掌傳統(tǒng)的密碼通訊只能在事先約定的雙方間進(jìn)行，雙方必須掌握相同的密鑰，而密鑰的傳送必須使用另外握相同的密鑰，而密鑰的傳送必須使用另

40、外 的的“安全信安全信道道”。這樣如果要使。這樣如果要使 n個(gè)用戶都能夠秘密的交換信息，則每個(gè)用戶都能夠秘密的交換信息，則每個(gè)用戶將需要用個(gè)密鑰，這種巨大的密鑰量給密鑰的分配與個(gè)用戶將需要用個(gè)密鑰，這種巨大的密鑰量給密鑰的分配與管理帶來(lái)了極大的困難；此外在有些情況下，事先約定密鑰管理帶來(lái)了極大的困難；此外在有些情況下，事先約定密鑰還是不可能的。還是不可能的。 公開密鑰體制的提出就是為了從根本上解決上述問(wèn)題公開密鑰體制的提出就是為了從根本上解決上述問(wèn)題 。其其基本思想基本思想是：是：把密鑰劃分為公開密鑰和秘密密鑰兩部分把密鑰劃分為公開密鑰和秘密密鑰兩部分 ,兩者兩者互為逆變換，但幾乎不可能從公開

41、密鑰推出秘密密鑰互為逆變換，但幾乎不可能從公開密鑰推出秘密密鑰 .每個(gè)每個(gè)使用者均有自己的公開及秘密密鑰。使用者均有自己的公開及秘密密鑰。 雖然只要能解密的密文，從理論上講雖然只要能解密的密文，從理論上講都是可破譯的，但如果破譯所需要都是可破譯的，但如果破譯所需要 的工作量過(guò)大，要求花費(fèi)的時(shí)間過(guò)的工作量過(guò)大，要求花費(fèi)的時(shí)間過(guò) 長(zhǎng)，以致超過(guò)了保密期限，則該密長(zhǎng)，以致超過(guò)了保密期限，則該密 碼系統(tǒng)應(yīng)當(dāng)被認(rèn)為是安全可靠的。碼系統(tǒng)應(yīng)當(dāng)被認(rèn)為是安全可靠的。 定義定義1 設(shè)設(shè)n為一正整數(shù)，將小為一正整數(shù)，將小 于于n且與且與n互素的正整數(shù)個(gè)數(shù)互素的正整數(shù)個(gè)數(shù)記為記為 (n)，稱之為歐拉（稱之為歐拉（eul

42、er l.）函數(shù)。函數(shù)。 不難證明：若不難證明：若 p，q為兩個(gè)相異素?cái)?shù)，為兩個(gè)相異素?cái)?shù)，n=pq，則，則 (n) =(p-1)(q-1)令令p,q為隨機(jī)選取的兩個(gè)大素?cái)?shù)（大約為十進(jìn)為隨機(jī)選取的兩個(gè)大素?cái)?shù)（大約為十進(jìn) 制制100位或更位或更大）大）, n=pq, n是公開的，是公開的， 而而p,q則是保密的。僅知道歐拉函則是保密的。僅知道歐拉函數(shù)數(shù)(n) =(p-1)(q-1)，但如果不知道因式分解就不能用這個(gè)公但如果不知道因式分解就不能用這個(gè)公式計(jì)算。隨機(jī)選取一個(gè)式計(jì)算。隨機(jī)選取一個(gè) 數(shù)數(shù)e，e為小于為小于(n)且與它互素的正整且與它互素的正整數(shù)。利用輾轉(zhuǎn)相除法，可以找到整數(shù)。利用輾轉(zhuǎn)相除法

43、，可以找到整 數(shù)數(shù)d和和r，使，使 ed+r(n) =1即即 ed 1 (mod (n) 數(shù)數(shù)n,e和和d分別稱為分別稱為模模、加密密鑰加密密鑰和和解密密鑰解密密鑰。 數(shù)數(shù)n和和e組成公組成公開密鑰的開密鑰的加密密鑰加密密鑰，而其余的，而其余的 項(xiàng)項(xiàng)p,q, (n)和和 d 組成了秘密組成了秘密陷門。很顯然，陷門信息包含了四個(gè)相關(guān)的項(xiàng)。陷門。很顯然，陷門信息包含了四個(gè)相關(guān)的項(xiàng)。 若知道若知道(n),則由則由 pq=n p+q=n-(n)+1 )1)()( qppqn可知可知p,q是二次方是二次方 程程x+(n)-n-1)x+n=0的根，可以算的根，可以算 出出p和和q，從而將，從而將n因式分解

44、。所因式分解。所 以以rsa體制的安全性與因式分體制的安全性與因式分解密切相關(guān)，若能知解密切相關(guān)，若能知 道道n的因子分解，該密碼就能被破的因子分解，該密碼就能被破譯。因此，要選用足夠大譯。因此，要選用足夠大 的的n，使得在當(dāng)今的條件下要分解，使得在當(dāng)今的條件下要分解它足夠困難。它足夠困難。為加密消息為加密消息 m，首先將它分為小，首先將它分為小 于于n（對(duì)二進(jìn)制數(shù)據(jù)，選取（對(duì)二進(jìn)制數(shù)據(jù)，選取小于小于n的的2的最大次方冪）的數(shù)據(jù)塊，也就是說(shuō)，如的最大次方冪）的數(shù)據(jù)塊，也就是說(shuō)，如 果果p和和q都為十進(jìn)制都為十進(jìn)制100位的素?cái)?shù)，則位的素?cái)?shù)，則 n 剛好在剛好在200位以內(nèi)，因此每位以內(nèi)，因此每個(gè)消息塊的長(zhǎng)度也應(yīng)在兩百位以內(nèi)。加密消息個(gè)消息塊的長(zhǎng)度也應(yīng)在兩百位以內(nèi)。加密消息c由類似劃分由類似劃分的同樣長(zhǎng)度的消息塊組成。