密碼的設(shè)計、解密及破譯

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

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

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

4、沌、，許多相當(dāng)高深的數(shù)學(xué)知識都被用上，逐步形成了（并仍在迅許多相當(dāng)高深的數(shù)學(xué)知識都被用上，逐步形成了（并仍在迅速發(fā)展的）具有廣泛應(yīng)用面的速發(fā)展的）具有廣泛應(yīng)用面的現(xiàn)代密碼學(xué)現(xiàn)代密碼學(xué) 。 替代密碼替代密碼 移位密碼移位密碼 代數(shù)密碼代數(shù)密碼 代替法密碼代替法密碼采用另一個字母表中的字母來代替明文中的字母，采用另一個字母表中的字母來代替明文中的字母，明文字母與密文字母保持一一對應(yīng)關(guān)系，但采用的符號改變明文字母與密文字母保持一一對應(yīng)關(guān)系，但采用的符號改變了。加密時，把明文換成密文，即將明文中的字母用密文字了。加密時，把明文換成密文，即將明文中的字母用密文字母表中對應(yīng)位置上的字母取代。解密時，則把密

5、文換成明文，母表中對應(yīng)位置上的字母取代。解密時，則把密文換成明文，即把密文中的字母用明文字母表中對應(yīng)位置上的字母代回，即把密文中的字母用明文字母表中對應(yīng)位置上的字母代回，解密過程是加密過程的逆過程。在代替法加密過程中，密文解密過程是加密過程的逆過程。在代替法加密過程中，密文字母表即代替法密鑰，密鑰可以是標(biāo)準(zhǔn)字母表，也可以是任字母表即代替法密鑰，密鑰可以是標(biāo)準(zhǔn)字母表，也可以是任意建立的。意建立的。 1.代替法密碼代替法密碼明文字母表明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表 KLMNOPQRSTUVWXYZABCDEFGHIJ密鑰常用一密鑰單詞或密鑰短語

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

7、母表中去掉密鑰中已有的字母后剩下的字母，得：的字母后剩下的字母，得：明文字母表明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表 CONSTRUABDEFGHIJKLMPQVWXYZ在設(shè)計密鑰時，也可在明文字母表中選擇一個特定字母，然在設(shè)計密鑰時，也可在明文字母表中選擇一個特定字母，然后從該特定字母開始寫密鑰單詞將密鑰單詞隱藏于其中。例后從該特定字母開始寫密鑰單詞將密鑰單詞隱藏于其中。例如，對于上例，選取特定字母如，對于上例，選取特定字母k k，則可得：，則可得： 明文字母表明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表

8、KLMPQVWXYZCONSTRUABDEFGHIJ 方法方法2 2：a)a)選擇一個密鑰單詞或密鑰短語，例如：選擇一個密鑰單詞或密鑰短語，例如： 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)將所得矩陣中的字母按列的順序排出將所得矩陣中的字母按列的順序排出 得：得： cugmyoahpznbiqsdjvrtekwrflx按照此方法

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

10、。混淆字母表由從小到大的順序取矩陣中相應(yīng)列得出。為增加保密性，在使用為增加保密性，在使用代替法時還可利用一些代替法時還可利用一些其他技巧，如單字母表其他技巧，如單字母表對多字母表、單字母對對多字母表、單字母對多字母、多重代替等。多字母、多重代替等。 2.移位密碼體制移位密碼體制移位密碼移位密碼采用移位法進(jìn)行加密，明文中的字母重新排列，本采用移位法進(jìn)行加密，明文中的字母重新排列，本身不變，只是位置改變了。身不變，只是位置改變了。早在早在4000多年前，古希臘人就用一種名叫多年前，古希臘人就用一種名叫“天書天書”的器械的器械來加密消息。該密碼器械是用一條窄長的草紙纏繞在一個來加密消息。該密碼器械是

11、用一條窄長的草紙纏繞在一個直徑確定的圓筒上，明文逐行橫寫在紙帶上，當(dāng)取下紙帶直徑確定的圓筒上，明文逐行橫寫在紙帶上，當(dāng)取下紙帶時，字母的次序就被打亂了，消息得以隱蔽。收方閱讀消時，字母的次序就被打亂了，消息得以隱蔽。收方閱讀消息時，要將紙帶重新繞在直徑與原來相同的圓筒上，才能息時，要將紙帶重新繞在直徑與原來相同的圓筒上，才能看到正確的消息。在這里圓筒的直徑起到了密鑰的作用。看到正確的消息。在這里圓筒的直徑起到了密鑰的作用。 以上移位較易被人破譯，為打破字母表中原有的順序還可采用以上移位較易被人破譯，為打破字母表中原有的順序還可采用所謂路線加密法，即把明文字母表按某種既定的順序安排在一所謂路線加

12、密法，即把明文字母表按某種既定的順序安排在一個矩陣中，然后用另一種順序選出矩陣中的字母來產(chǎn)生密文表。個矩陣中，然后用另一種順序選出矩陣中的字母來產(chǎn)生密文表。 例如，對明文：例如，對明文：THE HISTORY OF ZJU IS MORE THAN ONE HUNDRED YEARS.以以7列矩陣表示如下：列矩陣表示如下：THEHISTORYOFZJUISMORETHANONEHUNDREDYEARS再按事先約定的方式選出密文。例如，如按列選出，得到再按事先約定的方式選出密文。例如，如按列選出，得到密文：密文：touthyhrihueeysanahomndrifoorsszrnetjeed使用

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

14、密鑰，以進(jìn)一步加強保密性，這就是密鑰，以進(jìn)一步加強保密性，這就是鑰控列序加密法鑰控列序加密法。 例如例如，用密鑰單詞，用密鑰單詞 construct對明文對明文MATHEMATICAL MODELING IS USEFUL加密：加密：CONSTRUCT 1 4 36 7 5 928MATHEMATICALMODELI NGI S USEFU L 按混淆數(shù)的順序選出各列，得到密文：按混淆數(shù)的順序選出各列，得到密文： MCNLTLFTLIAAGMDSHMSEOSIIUAEE移位法的使用可重復(fù)多次，只進(jìn)行一次移位加密的稱為一移位法的使用可重復(fù)多次，只進(jìn)行一次移位加密的稱為一 次移位法次移位法，經(jīng)多次

15、移位的則稱，經(jīng)多次移位的則稱 為為多次移位法多次移位法 代替法與移位法密碼的代替法與移位法密碼的破譯破譯 對竊聽到的密文進(jìn)行分析時，對竊聽到的密文進(jìn)行分析時，窮舉法窮舉法和和統(tǒng)計法統(tǒng)計法是最基本的破是最基本的破譯方法譯方法 。窮舉分析法窮舉分析法 就是對所有可能的密鑰或明文進(jìn)行逐一試探，就是對所有可能的密鑰或明文進(jìn)行逐一試探，直至試探到直至試探到“正確正確”的為止。此方法的為止。此方法需要事先知道密碼體需要事先知道密碼體制或加密算法制或加密算法（但不知道密鑰或加密具體辦法）。破譯時（但不知道密鑰或加密具體辦法）。破譯時需將猜測到的明文和選定的密鑰輸入給算法，產(chǎn)生密文，需將猜測到的明文和選定的密

16、鑰輸入給算法，產(chǎn)生密文，再將該密文與竊聽來的密文比較。如果相同，則認(rèn)為該密再將該密文與竊聽來的密文比較。如果相同，則認(rèn)為該密鑰就是所要求的，否則繼續(xù)試探，直至破譯。以英文字母鑰就是所要求的，否則繼續(xù)試探，直至破譯。以英文字母為例，當(dāng)已知對方在采用代替法加密時，如果使用窮舉字為例，當(dāng)已知對方在采用代替法加密時，如果使用窮舉字母表來破譯，那么對于最簡單的一種使用單字母表單字母表來破譯，那么對于最簡單的一種使用單字母表單字母單元代替法加密的密碼，字母表的可能情況有母單元代替法加密的密碼，字母表的可能情況有26！種，種，可見，單純地使用窮舉法，在實際應(yīng)用中幾乎是行不通的，可見，單純地使用窮舉法，在實際

17、應(yīng)用中幾乎是行不通的，只能與其它方法結(jié)合使用。只能與其它方法結(jié)合使用。 統(tǒng)計法統(tǒng)計法是根據(jù)統(tǒng)計資料進(jìn)行猜測的。在一段足夠長且非特別是根據(jù)統(tǒng)計資料進(jìn)行猜測的。在一段足夠長且非特別專門化的文章中，字母的使用頻率是比較穩(wěn)定的。在某些技專門化的文章中，字母的使用頻率是比較穩(wěn)定的。在某些技術(shù)性或?qū)ｉT化文章中的字母使用頻率可能有微小變化。術(shù)性或?qū)ｉT化文章中的字母使用頻率可能有微小變化。 在上述兩種加密方法中字母表中的字母是一一對應(yīng)的，因此，在上述兩種加密方法中字母表中的字母是一一對應(yīng)的，因此，在截獲的密文中各字母出現(xiàn)的概率提供了重要的密鑰信息。根在截獲的密文中各字母出現(xiàn)的概率提供了重要的密鑰信息。根據(jù)權(quán)威

18、資料報道，可以據(jù)權(quán)威資料報道，可以 將將26個英文字母按其出現(xiàn)的頻率大小個英文字母按其出現(xiàn)的頻率大小較合理地分為五組：較合理地分為五組： t,a,o,i,n,s,h,r; e; d,l; c,u,m,w,f,g,y,p,b; v,k,j,x,q,z; 不僅單個字母以相當(dāng)穩(wěn)定的頻率出現(xiàn)，不僅單個字母以相當(dāng)穩(wěn)定的頻率出現(xiàn)，相鄰字母對相鄰字母對和和三字母三字母對對同樣如此。同樣如此。按按頻率大小頻率大小 將雙字母排列如下：將雙字母排列如下：th,he,in,er,an,re,ed,on,es,st,en,at,to,nt,ha,nd,ou,ea,ng,as,or,ti,is,er,it,ar,te,

19、se,hi,of使用最多的三字母按頻率大小排列如下：使用最多的三字母按頻率大小排列如下： The,ing,and,her,ere,ent,tha,nth,was,eth,for,dth統(tǒng)計的章節(jié)越長，統(tǒng)計結(jié)統(tǒng)計的章節(jié)越長，統(tǒng)計結(jié)果就越可靠。對于只有幾果就越可靠。對于只有幾個單詞的密文，統(tǒng)計是無個單詞的密文，統(tǒng)計是無意義的。意義的。下面介紹一下統(tǒng)計觀察的三個結(jié)果：下面介紹一下統(tǒng)計觀察的三個結(jié)果：a)單詞單詞the在這些統(tǒng)計中有重要的作用；在這些統(tǒng)計中有重要的作用；b)以以e，s，d，t為結(jié)尾的英語單詞超過了一半；為結(jié)尾的英語單詞超過了一半；c)以以t，a，s，w為起始字母的英語單詞約為一半。為起

20、始字母的英語單詞約為一半。 對于對于a) ，如果將，如果將the從明文中刪除，那么從明文中刪除，那么t的頻率將要的頻率將要降到第二組中其他字母之后，降到第二組中其他字母之后， 而而h將降到第三組中，將降到第三組中，并且并且th和和he就不再是最眾多的字母了。就不再是最眾多的字母了。以上對英語統(tǒng)計的討論是在僅涉及以上對英語統(tǒng)計的討論是在僅涉及26個字母的假設(shè)條件個字母的假設(shè)條件下進(jìn)行的。實際上消息的構(gòu)成還包括間隔、標(biāo)點、數(shù)字下進(jìn)行的。實際上消息的構(gòu)成還包括間隔、標(biāo)點、數(shù)字等字符。總之，破譯密碼并不是件很容易的事。等字符。總之，破譯密碼并不是件很容易的事。 2.希爾密碼希爾密碼代替密碼與移位密碼的

21、一個致命弱點是代替密碼與移位密碼的一個致命弱點是明文字符明文字符和和密文字密文字符符有相同的有相同的使用頻率使用頻率，破譯者可從統(tǒng)計出來的字符頻率中，破譯者可從統(tǒng)計出來的字符頻率中找到規(guī)律，進(jìn)而找出破譯的突破口。要克服這一缺陷，提找到規(guī)律，進(jìn)而找出破譯的突破口。要克服這一缺陷，提高保密程度就必須改變字符間的一一對應(yīng)。高保密程度就必須改變字符間的一一對應(yīng)。 1929年，希爾利用線性代數(shù)中的矩陣運算，打破了字符間的年，希爾利用線性代數(shù)中的矩陣運算，打破了字符間的對應(yīng)關(guān)系，設(shè)計了一種被稱為希爾密碼的代數(shù)密碼。為了便對應(yīng)關(guān)系，設(shè)計了一種被稱為希爾密碼的代數(shù)密碼。為了便于計算，希爾首先將字符變換成數(shù)，例

22、如，對英文字母，我于計算，希爾首先將字符變換成數(shù)，例如，對英文字母，我們可以作如下變換：們可以作如下變換： 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個一組，用對應(yīng)的數(shù)字代替，就變成了一個個個一組，用對應(yīng)的數(shù)字代替，就變成了一個個n維向量。如果取定一維向量。如果取定一 個個n階的非奇異矩陣階的非奇異矩陣A（此矩陣為主要（此矩陣為主要密鑰），密鑰）， 用用A去乘每一向量，即可起到加密的效

23、果，解密也去乘每一向量，即可起到加密的效果，解密也不麻煩，將密文也分成不麻煩，將密文也分成n個一組，同樣變換個一組，同樣變換 成成n維向量，只維向量，只需用需用A逆去乘這些向量，即可將他們變回原先的明文。逆去乘這些向量，即可將他們變回原先的明文。 定理定理1 ,若若 使得使得 (mod26)，則必有，則必有 =1，其，其中中 為為 與與26的最大公因子。的最大公因子。 0 0, ,. . . ., ,2 25 5 a a 0 0, ,2 25 5 a a1 11 1a aa aa aa a1 11 1g gc cd d a a, ,2 26 6 g gc cd d a a, ,2 26 6 a

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

25、除法一樣）。陣代替矩陣除法一樣）。det(A)det(A)A AA A1 1A Aa 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用希爾密碼體系加密語句用希爾密碼體系加密語句THANK YOU步步1 將將THANK YOU轉(zhuǎn)換成轉(zhuǎn)換成 （20，8，1，14，11，25，15，21）步步2 每一分量乘以每一分量乘以 3并關(guān)于并關(guān)于26取余得取余得 （8，24，3，16，7，23，19，11） 密文為密文為HXCPG WSK現(xiàn)在我們已不難將方法推現(xiàn)在我們已不難將方法推 廣到廣到n為一

26、般整數(shù)為一般整數(shù)的情況了的情況了,只需在乘法運算中結(jié)合應(yīng)用取余，只需在乘法運算中結(jié)合應(yīng)用取余，求逆矩陣時用逆元素相乘來代替除法即可。求逆矩陣時用逆元素相乘來代替除法即可。 例例2 取取A = 則則 (具體求法見具體求法見后后),用用A加密加密THANK YOU,再用再用 對密文解密對密文解密 0 01 13 32 20 01 1A A1 19 98 81 1A A 8 82 20 01 14 41 12 25 51 11 12 21 11 15 5用矩陣用矩陣A左乘各向量加密（關(guān)左乘各向量加密（關(guān) 于于26取余）得取余）得 2410 163 239 115得到密文得到密文 JXCPI WEK

27、解解:(希爾密碼加希爾密碼加 密密)用相應(yīng)數(shù)字代替字符，劃分為兩個元素一用相應(yīng)數(shù)字代替字符，劃分為兩個元素一 組并表示為向量：組并表示為向量：（希爾密碼解密希爾密碼解密）用用A-1左乘求得的向量，即可還原為原來的向量。左乘求得的向量，即可還原為原來的向量。 (自行驗證自行驗證)希爾密碼是以希爾密碼是以矩陣矩陣 法法為基礎(chǔ)的，明文與密文的對應(yīng)由為基礎(chǔ)的，明文與密文的對應(yīng)由n階矩階矩陣陣A確定。矩陣確定。矩陣A的階數(shù)是事先約定的，與明文分組時每組字的階數(shù)是事先約定的，與明文分組時每組字母的字母數(shù)量相同，如果明文所含字?jǐn)?shù)與母的字母數(shù)量相同，如果明文所含字?jǐn)?shù)與n不匹配，則最后不匹配，則最后幾個分量可任

28、意補足。幾個分量可任意補足。 A-1的求法的求法方法方法1 利用公式利用公式 ，例如，若取，例如，若取 ，則則 , , (mod26) ，即，即 方法方法2 利用高斯消去法。將矩陣?yán)酶咚瓜シ?。將矩?A, E)中的矩陣中的矩陣A消為消為E，則原先的則原先的E即被消成了即被消成了A-1，)det(1AAA 01A 323)det( A9)det(1 A 039A1 12 011A 98 如如 01 32 ， 01 10(用用9乘第二行并取同乘第二行并取同 余余) 01 12 ， 01 90第一行減去第二行第一行減去第二行 的的2倍并取同余，得倍并取同余，得 01 10 ， 01 98左端矩陣

29、已化為單位陣，故右端矩陣即為左端矩陣已化為單位陣，故右端矩陣即為 A-1希爾密碼系統(tǒng)的解密依賴于以下幾把鑰匙希爾密碼系統(tǒng)的解密依賴于以下幾把鑰匙 （key）：）：Key1 矩陣矩陣A的階數(shù)的階數(shù)n，即，即 明文是按幾個字母來明文是按幾個字母來 劃分的。劃分的。Key2 變換矩陣變換矩陣A，只有知，只有知 道了道了A才可能推算出才可能推算出Key3 明文和密文由字母表明文和密文由字母表 轉(zhuǎn)換成轉(zhuǎn)換成 n維向量所對維向量所對 應(yīng)的非負(fù)整數(shù)表（上應(yīng)的非負(fù)整數(shù)表（上 面，為方便起見，我面，為方便起見，我 們采用了字母的自然們采用了字母的自然 順序）。順序）。希爾密碼體系為破譯者設(shè)置了多道關(guān)口，加大了破

30、譯難度。破希爾密碼體系為破譯者設(shè)置了多道關(guān)口，加大了破譯難度。破譯和解密是兩個不同的概念，雖然兩者同樣是希望對密文加以譯和解密是兩個不同的概念，雖然兩者同樣是希望對密文加以處理而得到明文的內(nèi)容，但是他們有一個最大的不同處理而得到明文的內(nèi)容，但是他們有一個最大的不同破譯破譯密碼時，解密必需用到的鑰匙未能取得，破譯密碼的一方需要密碼時，解密必需用到的鑰匙未能取得，破譯密碼的一方需要依據(jù)依據(jù)密文的長度密文的長度，文字的本身特征文字的本身特征，以及，以及行文習(xí)慣行文習(xí)慣 等等各方面等等各方面的信息進(jìn)行破譯。破譯密碼雖然需要技術(shù)，但更加重要的是的信息進(jìn)行破譯。破譯密碼雖然需要技術(shù)，但更加重要的是“猜測猜

31、測”的藝術(shù)。的藝術(shù)?！安聹y猜測”的成功與否直接決定著破譯的結(jié)果。的成功與否直接決定著破譯的結(jié)果。破譯希爾密碼的關(guān)鍵是猜測文字被轉(zhuǎn)換成成幾維向量所對應(yīng)的破譯希爾密碼的關(guān)鍵是猜測文字被轉(zhuǎn)換成成幾維向量所對應(yīng)的字母表是怎樣的，更為重要的是要設(shè)法獲取加密矩陣字母表是怎樣的，更為重要的是要設(shè)法獲取加密矩陣A。（希爾密碼的破譯希爾密碼的破譯）由線性代數(shù)的知識可以知道，矩陣完全由線性代數(shù)的知識可以知道，矩陣完全由一組基的變換決定，對由一組基的變換決定，對 于于n階矩陣階矩陣A，只要猜出密文只要猜出密文 中中n個線性無關(guān)的向量個線性無關(guān)的向量 iiApq (i=1, 2, , n) 對應(yīng)的明文對應(yīng)的明文 (i

32、=1, 2, , n)是什么是什么 ，即，即可確定可確定A，并將密碼破譯。，并將密碼破譯。 在實際計算中，可以利用以下方法：在實際計算中，可以利用以下方法：令令則則TnpppP),.,(21 ，TnTAPpppAQ ),.,(211)(, TTAQPPAQ取矩陣取矩陣Q | P,經(jīng)過一系列初等行變換，將由密文決定的經(jīng)過一系列初等行變換，將由密文決定的n維維矩陣矩陣Q化為化為n階單位陣階單位陣 I的時候，由明文決定的矩陣的時候，由明文決定的矩陣P自動化自動化為為 (A-1)T，即，即 ：),)(,()(,11111 TTTAIAQQQQAQQPQ（初等行變換）初等行變換）例例5 有密文如下有密文

33、如下:goqbxcbuglosnfal;根據(jù)英文的行根據(jù)英文的行文習(xí)慣以及獲取密碼的途徑和背景，猜測是兩個字文習(xí)慣以及獲取密碼的途徑和背景，猜測是兩個字母為一組的希爾密碼，前四個明文字母是母為一組的希爾密碼，前四個明文字母是dear，試，試破譯這段秘文。破譯這段秘文。解解： 前兩組明文字前兩組明文字 母母de和和ar 對應(yīng)的二維向量是：對應(yīng)的二維向量是： 按同一對應(yīng)整數(shù)表，密文中對應(yīng)這兩組的二維向量是：按同一對應(yīng)整數(shù)表，密文中對應(yīng)這兩組的二維向量是：TTPP)18, 1(,)5 , 4(21 11(7,15)TqAp， TApq)2 ,17(22 ， TqqQ),(21 由此可得由此可得)(

34、,)26(mod(,1 TAIPQ初初等等行行變變換換），對應(yīng)上例則有，對應(yīng)上例則有 9051,100118514,215177初初等等行行變變換換并并取取同同余余 51)(1 TA 90 , 011A 95利用這一逆矩陣，可對截獲密文進(jìn)行解密，破譯出的電文是利用這一逆矩陣，可對截獲密文進(jìn)行解密，破譯出的電文是Dear Mac God forbid. 這只是對最簡單情況進(jìn)行的舉例，如果加密矩陣的階數(shù)大于這只是對最簡單情況進(jìn)行的舉例，如果加密矩陣的階數(shù)大于2，需要的密文應(yīng)該有較長長度，所需的計算量也是很大的。破需要的密文應(yīng)該有較長長度，所需的計算量也是很大的。破譯的關(guān)鍵是猜中譯的關(guān)鍵是猜中n及及

35、n個獨立的個獨立的n維向量，其后求解加密矩陣的維向量，其后求解加密矩陣的計算量僅為計算量僅為 O(n2 )。希爾密碼體制中有兩個要素非常重要：希爾密碼體制中有兩個要素非常重要： 第一第一是字母是字母 與與n維向量進(jìn)行轉(zhuǎn)換所依維向量進(jìn)行轉(zhuǎn)換所依據(jù)的非負(fù)整數(shù)表，本節(jié)中所舉的是最據(jù)的非負(fù)整數(shù)表，本節(jié)中所舉的是最自然的情況；當(dāng)然如果依據(jù)其它的整自然的情況；當(dāng)然如果依據(jù)其它的整數(shù)表也是完全可以進(jìn)行的，其情況將數(shù)表也是完全可以進(jìn)行的，其情況將會更復(fù)雜一些，破譯的難度就會增大。會更復(fù)雜一些，破譯的難度就會增大。 第二第二個要素是加密矩陣，如何定義、個要素是加密矩陣，如何定義、求解這個矩陣對于密碼的加密和破譯

36、求解這個矩陣對于密碼的加密和破譯更加關(guān)鍵。唯一的要求是加密時應(yīng)選更加關(guān)鍵。唯一的要求是加密時應(yīng)選擇行列式值與擇行列式值與 26無公因子的矩陣。無公因子的矩陣。 RSA公開密鑰體制公開密鑰體制 傳統(tǒng)的密碼通訊只能在事先約定的雙方間進(jìn)行，雙方必須掌傳統(tǒng)的密碼通訊只能在事先約定的雙方間進(jìn)行，雙方必須掌握相同的密鑰，而密鑰的傳送必須使用另外的握相同的密鑰，而密鑰的傳送必須使用另外的“安全信道安全信道”。這樣如果要使這樣如果要使 n個用戶都能夠秘密的交換信息，則每個用戶個用戶都能夠秘密的交換信息，則每個用戶將需要用個密鑰，這種巨大的密鑰量給密鑰的分配與管理帶將需要用個密鑰，這種巨大的密鑰量給密鑰的分配與

37、管理帶來了極大的困難；此外在有些情況下，事先約定密鑰還是不來了極大的困難；此外在有些情況下，事先約定密鑰還是不可能的?？赡艿?。 公開密鑰體制的提出就是為了從根本上解決上述問題。公開密鑰體制的提出就是為了從根本上解決上述問題。其其基基本思想本思想是：是：把密鑰劃分為公開密鑰和秘密密鑰兩部分，兩者把密鑰劃分為公開密鑰和秘密密鑰兩部分，兩者互為逆變換，但幾乎不可能從公開密鑰推出秘密密鑰。每個互為逆變換，但幾乎不可能從公開密鑰推出秘密密鑰。每個使用者均有自己的公開及秘密密鑰。使用者均有自己的公開及秘密密鑰。 雖然只要能解密的密文，從理論上講雖然只要能解密的密文，從理論上講都是可破譯的，但如果破譯所需要

38、都是可破譯的，但如果破譯所需要 的工作量過大，要求花費的時間過的工作量過大，要求花費的時間過 長，以致超過了保密期限，則該密長，以致超過了保密期限，則該密 碼系統(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ù)個數(shù)互素的正整數(shù)個數(shù)記為記為 (n)，稱之為歐拉（稱之為歐拉（Euler L.）函數(shù)。函數(shù)。 不難證明：若不難證明：若 p，q為兩個相異素數(shù)，為兩個相異素數(shù)，n=pq，則，則 (n) =(p-1)(q-1)令令p,q為隨機選取的兩個大素數(shù)（大約為十進(jìn)制為隨機選取的兩個大素數(shù)（大約為十進(jìn)制100位或更位或

39、更大）大）, n=pq, n是公開的，是公開的， 而而p,q則是保密的。僅知道歐拉函則是保密的。僅知道歐拉函數(shù)數(shù)(n) =(p-1)(q-1)，但如果不知道因式分解就不能用這個公但如果不知道因式分解就不能用這個公式計算。隨機選取一個數(shù)式計算。隨機選取一個數(shù)e，e為小于為小于(n)且與它互素的正整且與它互素的正整數(shù)。利用輾轉(zhuǎn)相除法，可以找到整數(shù)數(shù)。利用輾轉(zhuǎn)相除法，可以找到整數(shù)d和和r，使，使 ed+r(n) =1即即 ed 1 (mod (n) 數(shù)數(shù)n,e和和d分別稱為分別稱為模模、加密密鑰加密密鑰和和解密密鑰解密密鑰。 數(shù)數(shù)n和和e組成公組成公開密鑰的開密鑰的加密密鑰加密密鑰，而其余的項，而其

40、余的項p,q, (n)和和 d 組成了秘密陷組成了秘密陷門。很顯然，陷門信息包含了四個相關(guān)的項。門。很顯然，陷門信息包含了四個相關(guān)的項。 若知道若知道(n),則由則由 pq=n p+q=n-(n)+1 )1)()( qppqn可知可知p,q是二次方是二次方 程程x+(n)-n-1)x+n=0的根，可以算出的根，可以算出p和和q，從而將，從而將n因式分解。所以因式分解。所以RSA體制的安全性與因式分解密體制的安全性與因式分解密切相關(guān)，若能知道切相關(guān)，若能知道n的因子分解，該密碼就能被破譯。因此，的因子分解，該密碼就能被破譯。因此，要選用足夠大的要選用足夠大的n，使得在當(dāng)今的條件下要分解它足夠困難

41、。，使得在當(dāng)今的條件下要分解它足夠困難。為加密消息為加密消息 m，首先將它分為小于，首先將它分為小于n（對二進(jìn)制數(shù)據(jù)，選?。▽ΧM(jìn)制數(shù)據(jù)，選取小于小于n的的2的最大次方冪）的數(shù)據(jù)塊，也就是說，如果的最大次方冪）的數(shù)據(jù)塊，也就是說，如果p和和q都為十進(jìn)制都為十進(jìn)制100位的素數(shù)，則位的素數(shù)，則 n 剛好在剛好在200位以內(nèi)，因此每位以內(nèi)，因此每個消息塊的長度也應(yīng)在兩百位以內(nèi)。加密消息個消息塊的長度也應(yīng)在兩百位以內(nèi)。加密消息c由類似劃分由類似劃分的同樣長度的消息塊組成。加密公式為的同樣長度的消息塊組成。加密公式為 eiimc)( (mod n) 要解密消息，取每一個加密塊要解密消息，取每一個加密塊c(I)并計算并計算 (mod n)由公式由公式ed 1 (mod (n