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

4.2 密碼的設(shè)計(jì)，解碼與破譯,早期密碼,替代密碼 移位密碼 代數(shù)密碼,1.代替法密碼,明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文字母表 KLMNOPQRSTUVWXYZABCDEFGHIJ,密鑰常用一密鑰單詞或密鑰短語生成混淆字母表。密鑰單詞 或密鑰短語可以存放在識別碼、通行字或密鑰的秘密表格中。,混合一個(gè)字母表，常見的有兩種方法，這兩種方法都采用了一個(gè)密鑰單詞或一個(gè)密鑰短語。,明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文字母表 CONSTRUABDEFGHIJKLMPQVWXYZ,明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文字母表 KLMPQVWXYZCONSTRUABDEFGHIJ,得： cugmyoahpznbiqsdjvrtekwrflx 按照此方法產(chǎn)生的字母表稱為 混淆字母表。,為增加保密性，在使用代替法時(shí)還可利用一些其他技巧，如單字母表對多字母表、單字母對多字母、多重代替等。,2.移位密碼體制,另一種移位 法采用將字母表中的字母平移若干位的方法來構(gòu)造密文字母表，傳說這類方法是由古羅馬皇帝凱撒最早使用的，故這種密文字母表被稱為凱撒字母表。例如，如用將字母表向右平移3位的方法來構(gòu)造密文字母表，可 得：,明文字母表： ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文字母表： DEFGHIJKLMNOPQRTSUVWXYZABC,例如，對明文：THE HISTORY OF ZJU IS MORE THAN ONE HUNDRED YEARS.以7列矩陣表示如下： THEHIST ORYOFZJ UISMORE THANONE HUNDRED YEARS,再按事先約定的方式選出密文。例如，如按列選出，得到密文：touthyhrihueeysanahomndrifoorsszrnetjeed,使用不同的順序進(jìn)行編寫和選擇，可以得到各種不同的路線加密體制。對于同一明文消息矩陣，采用不同的抄寫方式，得到的密文也是不同的。,當(dāng)明文超過規(guī)定矩陣的大小時(shí)，可以另加一矩陣。當(dāng)需要加密的字母數(shù)小于矩陣大小時(shí)，可以在矩陣中留空位或以無用的字母來填滿矩陣。,例如，用密鑰單詞 construct對明文MATHEMATICAL MODELING IS USEFUL加密： CONSTRUCT 1 4 3 675 9 28 MATHEMATI CALMODELI NGISUSEFU L 按混淆數(shù)的順序選出各列，得到密文： MCNLTLFTLIAAGMDSHMSEOSIIUAEE,對竊聽到的密文進(jìn)行分析時(shí) ，窮舉法和統(tǒng)計(jì)法是最基本的破譯方法 。,在上述兩種加密方法中字母表中的字母是一一對應(yīng)的，因此，在截獲的密文中各字母出現(xiàn)的概率提供了重要的密鑰信息。根據(jù)權(quán)威資料報(bào)道，可以 將26個(gè)英文字母按其出現(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;,按頻率大小 將雙字母排列如下： 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,se,hi,of 使用最多的三字母按頻率大小排列如下： The,ing,and,her,ere,ent,tha,nth,was,eth,for,dth,統(tǒng)計(jì)的章節(jié)越長，統(tǒng)計(jì)結(jié)果就越可靠。對于只有幾個(gè)單詞的密文，統(tǒng)計(jì)是無意義的。,以上對英語統(tǒng)計(jì)的討論是在僅涉 及26個(gè)字母的假設(shè)條件下進(jìn)行的。實(shí)際上消息的構(gòu)成還包括間隔、標(biāo)點(diǎn)、數(shù)字等字符?？傊?，破譯密碼并不是件很容易的事。,2.希爾密碼,1929年，希爾利用線性代數(shù)中的矩陣運(yùn)算，打破了字符間的對應(yīng)關(guān)系，設(shè)計(jì)了一種被稱為希爾密碼的代數(shù)密碼。為了便于計(jì)算，希爾首先將字符變換成數(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,用矩陣A左乘各向量加密（關(guān) 于26取余）得,得到密文 JXCPI WEK,希爾密碼系統(tǒng)的解密依賴于以下幾把鑰匙 （key）：,（希爾密碼的破譯）,解： 前兩組明文字 母de和ar 對應(yīng)的二維向量是： 按同一對應(yīng)整數(shù)表，密文中對應(yīng)這兩組的二維向量是：,由此可得,，對應(yīng)上例則有,利用這一逆矩陣，可對截獲密文進(jìn)行解密，破譯出的電文是Dear Mac God forbid.,RSA公開密鑰體制,雖然只要能解密的密文，從理論上講 都是可破譯的，但如果破譯所需要 的工作量過大，要求花費(fèi)的時(shí)間過 長，以致超過了保密期限，則該密 碼系統(tǒng)應(yīng)當(dāng)被認(rèn)為是安全可靠的。,不難證明：若 p，q為兩個(gè)相異素?cái)?shù)，n=pq，則 (n) =(p-1)(q-1) 令p,q為隨機(jī)選取的兩個(gè)大素?cái)?shù)（大約為十進(jìn) 制100位或更大）, n=pq, n是公開的， 而p,q則是保密的。僅知道歐拉函數(shù)(n) =(p-1)(q-1)，但如果不知道因式分解就不能用這個(gè)公式計(jì)算。隨機(jī)選取一個(gè) 數(shù)e，e為小于(n)且與它互素的正整數(shù)。利用輾轉(zhuǎn)相除法，可以找到整 數(shù)d和r，使 ed+r(n) =1 即 ed 1 (mod (n),數(shù)n,e和d分別稱為模、加密密鑰和解密密鑰。 數(shù)n和e組成公開密鑰的加密密鑰，而其余的 項(xiàng)p,q, (n)和 d 組成了秘密陷門。很顯然，陷門信息包含了四個(gè)相關(guān)的項(xiàng)。,(mod n),要解密消息，取每一個(gè)加密 塊c(I)并計(jì)算 (mod n) 由公式ed 1 (mod (n) 我們有ed = 1 - r(n),因此 (mod n) 其中r為某一整數(shù)。這里利用 了歐拉定理: (n) 1(mod n)根據(jù)以上公式從密文恢復(fù)出了明文。,設(shè)使用者取 定 p=47，q=59, 則 N=pq=2773,(n)=(p-1)(q-1)=2668. 取素?cái)?shù)e=17，顯然它與(n)互素，加密者知 道p、q的值，易得出d=157。將(e,n)=(17,2773)作為公開密鑰發(fā)布；嚴(yán)守機(jī)密的秘密密鑰是(157,2773).現(xiàn)在有人要向此使用者傳送一段（英文）明文信息，例如： I love zhejiang university 將這段文字轉(zhuǎn)換為數(shù)字，不計(jì)大小寫，每兩個(gè)詞之間為一個(gè)空格符號，空格符對應(yīng)數(shù) 字00，每個(gè)英文字母對應(yīng)表征其在字母表中位置的兩位數(shù)字，例如：A對應(yīng)01，B對應(yīng)02，Z對應(yīng)26，等等。再從頭向后，將每四位數(shù)字劃歸一組，不足時(shí)補(bǔ)充空格。如此得到以下十三組數(shù)字： 0900 1215 2205 0026 0805 1009 0114 0700 2114 0922 0518 1909 2025 每一組數(shù)字視為一個(gè)數(shù)，用公開密 鑰(17,2773)對其加以變換。,以第一個(gè)數(shù)為例，由于n=2773,比這里任何可能出現(xiàn)的四位數(shù)字均大，故只需計(jì)算每一數(shù)字在 模2773下的17次冪。我們有 900 1510 (mod 2773). 在以上整個(gè)過程中，為減少計(jì)算量應(yīng)隨時(shí)注意取模。這樣900對應(yīng)的密碼是1510。以這一方法得到的密文電碼是： 1510 0417 1524 1445 0542 2692 1684 07