第4講 數(shù)據(jù)加密技術(shù)(古典密碼).ppt

1、一、古典密碼,用近代密碼學(xué)的觀點(diǎn)來(lái)看，許多古典密碼是很不安全的，或者說(shuō)是極易破譯的。 但是我們不能忘記古典密碼在歷史上發(fā)揮的巨大作用。 另外，編制古典密碼的基本方法對(duì)于編制近代密碼仍然有效。,一、古典密碼,C. D. Shannon(1945): 采用混淆、擴(kuò)散和乘積的方法來(lái)設(shè)計(jì)密碼 混淆：使密文和明文、密鑰之間的關(guān)系復(fù)雜化 “混淆”可以隱藏明文、密文和密鑰之間的任何關(guān)系。好的“混亂”可使復(fù)雜甚至強(qiáng)有力的密碼分析工具不得奏效。最容易的方法是“代替（Substitution）”法。,一、古典密碼,擴(kuò)散：將每一位明文和密鑰的影響擴(kuò)大到盡可能多的密文位中。 “擴(kuò)散”是一種將明文冗余度分散到密文中的方

2、法，即將單個(gè)明文或密鑰位的影響盡可能擴(kuò)大到更多的密文中去，不僅將統(tǒng)計(jì)關(guān)系隱藏起來(lái)，也使密碼分析者尋求明文冗余礦度增加了難度。最簡(jiǎn)單的“擴(kuò)散”方法是“置換（Permutation）”法。,一、古典密碼,乘積和迭代：多種加密方法混合使用 對(duì)一個(gè)加密函數(shù)多次迭代 古典密碼編碼方法： 置換，代替，加法,1、置換密碼 把明文中的字母重新排列，字母本身不變，但其位置改變了，這樣編成的密碼稱為置換密碼。 最簡(jiǎn)單的置換密碼是把明文中的字母順序倒過(guò)來(lái)，然后截成固定長(zhǎng)度的字母組作為密文。 明文：明晨5點(diǎn)發(fā)動(dòng)反攻。 MING CHEN WU DIAN FA DONG FAN GONG 密文：GNOGN AFGNO

3、DAFNA IDUWN EHCGN IM,一、古典密碼,例如明文：MING CHEN WU DIAN FA DONG FAN GONG 矩陣：MINGCH 選出順序：按列 ENWUDI ANFADO 改變矩陣大小和取出序列 NGFANG 可得到不同的密碼 ONG 密文：MEANO INNGN NWFFG GUAA CDDN HIOG,把明文按某一順序排成一個(gè)矩陣， 然后按另一順序選出矩陣中的字母以形成密文，最后截成固定長(zhǎng)度的字母組作為密文。,一、古典密碼,2、代替密碼 首先構(gòu)造一個(gè)或多個(gè)密文字母表，然后用密文字母表中的字母或字母組來(lái)代替明文字母或字母組，各字母或字母組的相對(duì)位置不變，但其本身改

4、變了。這樣編成的密碼稱為代替密碼。 單表代替密碼 多表代替密碼 多名代替密碼,一、古典密碼,單表代替密碼 只使用一個(gè)密文字母表，并且用密文字母表中的一個(gè)字母來(lái)代替明文字母表中的一個(gè)字母。 明文字母表：A a0 , a1 ,., an-1 密文字母表：B b0 , b1 ,., bn-1 定義一個(gè)由A到 B的映射：f:AB f(ai )= bi 設(shè)明文：M =（m0 , m1 ,., mn-1 ）, 則密文：C =(f(m0 ),f(m1 ),.,f(mn-1 )。 簡(jiǎn)單代替密碼的密鑰就是映射函數(shù)f或密文字母表 B。,一、古典密碼,單表代替密碼 、加法密碼 A和B是有 n個(gè)字母的字母表。 定義一

5、個(gè)由A到B的映射：f:AB f(ai )= bi=aj j=i+k mod n 加法密碼是用明文字母在字母表中后面第 k個(gè)字母來(lái)代替。 K=3 時(shí)是著名的凱撒密碼。,一、古典密碼,愷撒密碼歷史上第一個(gè)密碼技術(shù) “愷撒密碼”是古羅馬愷撒大帝在營(yíng)救西塞羅戰(zhàn)役時(shí)用來(lái)保護(hù)重要軍情的加密系統(tǒng)（高盧戰(zhàn)記）。 明文：attack gaul 密文：DWWDFN KDXO,一、古典密碼,單表代替密碼 、乘法密碼 A和B是有n個(gè)字母的字母表。 定義一個(gè)由A到B的映射：f:AB f(ai )= bi= aj j=ik mod n 其中，(n,k)=1。 注意：只有(n,k)=1，才能正確解密。,一、古典密碼,單表代

6、替密碼 密鑰詞組代替密碼： 隨機(jī)選一個(gè)詞語(yǔ)，去掉其中的重復(fù)字母，寫到矩陣的第一行，從明文字母表中去掉這第一行的字母，其余字母順序?qū)懭刖仃?。然后按列取出字母?gòu)成密文字母表。,一、古典密碼,舉例： 密鑰： HONG YE 矩陣： HONGYE 選出順序：按列 ABCDFI JKLMPQ 改變密鑰、矩陣大小 RSTUVW 和取出序列，得到不同的 XZ 密文字母表。 密文字母表 : B= HAJRXOBKSZNCLTGDMUYFPVEIQW ,一、古典密碼,、多表代替密碼 單表代替密碼的安全性不高，一個(gè)原因是一個(gè)明文字母只由一個(gè)密文字母代替。 構(gòu)造多個(gè)密文字母表， 在密鑰的控制下用相應(yīng)密文字母表中的一

7、個(gè)字母來(lái)代替明文字母表中的一個(gè)字母。一個(gè)明文字母有多種代替。 Vigenere密碼：著名的多表代替密碼,一、古典密碼,明 文 字 母 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B B C D E F G H I J K L M N O P Q R S T U V W X Y Z A C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B H H I J K L M N O P

8、 Q R S T U V W X Y Z A B C D E F G X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z Z A B C D E F G H I J K L M N O P Q R S T U V W X Y,Vigenre方陣,密 文 字 母,一、古典密碼,Vigenre密碼的代替規(guī)則是用明文字母在Vigenre方陣中的列和密鑰字母在Vigenre方陣中的行的交點(diǎn)處的字母來(lái)代替該明文字母。例如，設(shè)明文字母為P，

9、密鑰字母為Y，則用字母N來(lái)代替明文字母P。 明文：MING CHEN WU DIAN FA DONG FAN GONG 密鑰：XING CHUI PING YE KUO YUE YONG DA JIANG LIU 密文：JQAME OYVLC QOYRP URMHK DOAMR NP 解密就是利用Vigenre方陣進(jìn)行反代替。,一、古典密碼,3、代數(shù)密碼： Vernam密碼 明文、密文、密鑰都表示為二進(jìn)制位： M=m1,m2, ,mn K =k1,k2, ,kn C =c1,c2, ,cn 加密 ： c1= mi ki ,i=1,2, ,n 解密 ： m1= ci ki ,i=1,2, ,n

10、因?yàn)榧咏饷芩惴ㄊ悄?加，所以稱為代數(shù)密碼。 對(duì)合運(yùn)算：f=f-1，模 2加運(yùn)算是對(duì)合運(yùn)算。 密碼算法是對(duì)合運(yùn)算，則加密算法解密算法，工程實(shí)現(xiàn)工作量減半。 Vernam密碼經(jīng)不起已知明文攻擊。,一、古典密碼, 如果密鑰序列有重復(fù)，則Vernam密碼是不安全的。 一種極端情況：一次一密 密鑰是隨機(jī)序列。 密鑰至少和明文一樣長(zhǎng)。 一個(gè)密鑰只用一次。 一次一密是絕對(duì)不可破譯的，但它是不實(shí)用的。 一次一密給密碼設(shè)計(jì)指出一個(gè)方向，人們用序列密碼逼近一次一密。,一、古典密碼,二、古典密碼的窮舉分析,1、單表代替密碼分析 加法密碼 因?yàn)閒(ai )= bi=aj j=i+k mod n 所以k=1,2，. ,

11、n-1,共n-1種可能，密鑰空間太小。以英文為例，只有25種密鑰。 經(jīng)不起窮舉攻擊。,二、古典密碼的窮舉分析,1、單表代替密碼分析 乘法密碼 因?yàn)閒(ai )= bi=aj j=ik mod n，且（k,n）=1。 所以k共有（n）種可能，密鑰空間更小。 對(duì)于英文字母表，n=26，k=1,3,5,7,9,11,15,17,19,21,23,25 取掉1，共11種，比加法密碼更弱。 經(jīng)不起窮舉攻擊。,二、古典密碼的窮舉分析,1、單表代替密碼分析 密鑰詞語(yǔ)代替密碼 因?yàn)槊荑€詞語(yǔ)的選取是隨機(jī)的，所以密文字母表完全可能窮盡明文字母表的全排列。 以英文字母表為例，n=26，所以共有26！種可能的密文字母

12、表。 26！41026 用計(jì)算機(jī)也不可能窮舉攻擊。 注意：窮舉不是攻擊密鑰詞語(yǔ)代替密碼的唯一方法。,三、古典密碼的統(tǒng)計(jì)分析,2、密鑰詞組單表代替密碼的統(tǒng)計(jì)分析 任何自然語(yǔ)言都有自己的統(tǒng)計(jì)規(guī)律。 如果密文中保留了明文的統(tǒng)計(jì)特征，就可用統(tǒng)計(jì)方法攻擊密碼。 由于單表代替密碼只使用一個(gè)密文字母表，一個(gè)明文字母固定的用一個(gè)密文字母來(lái)代替，所以密文的統(tǒng)計(jì)規(guī)律與明文相同。 因此，單表代替密碼可用統(tǒng)計(jì)分析攻破。,三、古典密碼的統(tǒng)計(jì)分析,英語(yǔ)的統(tǒng)計(jì)規(guī)律 每個(gè)單字母出現(xiàn)的頻率穩(wěn)定。 最高頻率字母（1類）E(12%) 次高頻率字母（2類）T A O I N S H R(8%) 中高頻率字母（3類）D L（4%） 低

13、頻率字母(4類)U M W F G Y P B（2%） 最低頻率字母（5類） V K J X Q Z （1%）,三、古典密碼的統(tǒng)計(jì)分析,英語(yǔ)的統(tǒng)計(jì)規(guī)律 頻率最高的雙字母組： TH HE IN ER AN RE ED ON ES ST EN AT TO NT HA ND OU EA NG AS OR TI IS ET IT AR TE SE HI OF,三、古典密碼的統(tǒng)計(jì)分析,英語(yǔ)的統(tǒng)計(jì)規(guī)律 頻率最高的三字母組： THE ING AND HER ERE ENT THA WAS ETH FOR DHT HAT SHE ION HIS ERS VER 其中THE的頻率是ING的3倍！,三、古典密碼的

14、統(tǒng)計(jì)分析,英語(yǔ)的統(tǒng)計(jì)規(guī)律 英文單詞以E，S，D，T為結(jié)尾的超過(guò)一半。 英文單詞以T，A，S，W為起始字母的約占一半。 還有其它統(tǒng)計(jì)規(guī)律！,三、古典密碼的統(tǒng)計(jì)分析,經(jīng)得起統(tǒng)計(jì)分析是對(duì)近代密碼的基本要求！,三、古典密碼的統(tǒng)計(jì)分析,例：給定密文為 UZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESX UDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPD TSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MB ZWP FUPZ HMDJ UD TMOHMQ 排出字母頻率： A B C D E F G H I J K L M N O

15、 P Q R S T U V W X Y Z 2 2 0 6 6 4 2 7 1 1 0 0 8 0 9 16 3 0 10 3 10 5 4 5 2 14,三、古典密碼的統(tǒng)計(jì)分析,高頻字母有：H M O P S U Z 7 8 9 16 10 10 14 這幾個(gè)字母估計(jì)是1、2類的字母。 P,Z之一可能為明文字母e,另一個(gè)為t。 觀察密文，Z經(jīng)常出現(xiàn)在頭和尾，而P只出現(xiàn)在尾，故猜Z為t,P為e。,三、古典密碼的統(tǒng)計(jì)分析,低頻字母Q和T都是兩個(gè)詞的首字母，故很可能是低頻但經(jīng)常作為詞頭的c,w,p,b,f中的一個(gè)。,三、古典密碼的統(tǒng)計(jì)分析,再利用二、三字母組和元音輔音拼寫知識(shí)，猜MB中必有一個(gè)元

16、音字母，一個(gè)輔音字母，而M的頻度高，故M更有可能為元音。 對(duì)于 UZ和UD，要么U為元音，Z和D為輔音，要么相反。考慮后者，那么相應(yīng)的明文可能為me，my或be,by，而U的頻度高，與m、b都不對(duì)應(yīng)。因而前者概率大。,三、古典密碼的統(tǒng)計(jì)分析,UZ QSO VUOHXMOPV GPOZPEVSG ZWSZ .t .a. .e. .e.te.a. that OPFPESX UDBMETSX AIZ VUEPHZ HMDZSHZO .eve.a. .n.a. b.t .e.t .nta.t. WSFP APPD TSVP QUZW YMXUZUHSX have been .a.e .th .t.a.

17、 EPYEPOPDZSZUFPO MB ZWP FUPZ HMDJ UD .e.e.e.tat.ve. . the .et .n. .n TMOHMQ .,三、古典密碼的統(tǒng)計(jì)分析,UZ QSO VUOHXMOPV GPOZPEVSG ZWSZ .t .a. .e. .e.te.a. that 所以，UZ可能為at或it，而S-a，故U為i. QUZW .th 可能為with,即Q-w 因而QSO為was，即O-s,三、古典密碼的統(tǒng)計(jì)分析,如Z是輔音，則ZWP將暗示W(wǎng)或P為元音。 由P和Z的頻度看，ZWP中的P可能為元音。假定選U為元音，Z為輔音，觀察ZWSZ很像that,則ZWP可能為定冠詞the. 由此有： W S F P A P P D h . .e . e e . 可能是have 和been,復(fù)習(xí)題, 已知置換如下： 明文642135 ,密文？ 密文214365 ，明文？ 使加法密碼算法稱為對(duì)合運(yùn)算的密鑰k稱為對(duì)合