3、第三講-古典密碼課件

計(jì)算機(jī)安全保密

第三講古典密碼wzy@武漢大學(xué)計(jì)算機(jī)學(xué)院1古典密碼

雖然用近代密碼學(xué)的觀點(diǎn)來(lái)看，許多古典密碼是很不安全的，或者說(shuō)是極易破譯的。但是我們不能忘記古典密碼在歷史上發(fā)揮的巨大作用。另外，編制古典密碼的基本方法對(duì)于編制近代密碼仍然有效。2第三講古典密碼換位法替代法3置換密碼把明文中的字母重新排列，字母本身不變，但其位置改變了，這樣編成的密碼稱為置換密碼。最簡(jiǎn)單的置換密碼是把明文中的字母順序倒過(guò)來(lái)，然后截成固定長(zhǎng)度的字母組作為密文。明文：明晨5點(diǎn)發(fā)動(dòng)反攻。

MINGCHENWUDIANFADONGFANGONG密文：GNOGNAFGNODAFNAIDUWNEHCGNIM4

例如：明文：MINGCHENWUDIANFADONGFANGONG矩陣：MINGCH選出順序：按列

ENWUDIANFADO改變矩陣大小和取出序列

NGFANG可得到不同的密碼

ONG密文：MEANOINNGNNWFFGGUAACDDNHIOG把明文按某一順序排成一個(gè)矩陣，然后按另一順序選出矩陣中的字母以形成密文，最后截成固定長(zhǎng)度的字母組作為密文。5古典密碼換位法思路打亂明文中各字母的順序，使明文中的單詞錯(cuò)亂，隱蔽其含義6古典密碼換位法方法加密時(shí)，將明文的字符（一維數(shù)據(jù)）按照一定順序放入高維空間（一維以上）中，然后按照另一種順序取出字符，形成密文（一維數(shù)據(jù)）解密時(shí)，先將密文按照相應(yīng)順序放入高維空間中，再按照原始順序取出明文7古典密碼換位法舉例明文：M=INTELLIGENT放入3×4的矩陣8古典密碼換位法加密方法整體加密，取列向量密文為 Ek(M)=ILENLNTITEG按行加密，取列順序2413密文為 Ek(M)=NEITLGLINET9古典密碼雙軌密碼：1861~1865年明文： DiscreteAndSystem加密： DsrtAdytm iceenSse密文： DsrtAdytmiceenSse

10理論上：①、置換密碼的加密鑰是置換矩陣p

，

解密鑰是置換矩陣p-1

。②、置換密碼經(jīng)不起已知明文攻擊。

123…na1a2a3…anP=11習(xí)題已知換位密碼的換位表為：（2,7,5,3,8,4,6,1），試對(duì)明文software加密。答案：12習(xí)題已知換位密碼的換位表為：（2,7,5,3,8,4,6,1），試對(duì)明文software加密。答案：orwfetas13古典密碼換位法算法特點(diǎn)：易于手工操作，明密文都是字符串且等長(zhǎng)算法缺陷：明文密文中的各字母出現(xiàn)次數(shù)是相同的，只是位置不同，密碼分析員可以通過(guò)移動(dòng)字母順序進(jìn)行破譯14古典密碼替代法簡(jiǎn)單替代多表替代同音替代組合替代15替代法簡(jiǎn)單替代思路將明文中字母按照一定規(guī)律替換成其他字母，隱蔽其含義方法設(shè)定規(guī)則，將明文中的字母x替換成字母f(x)16替代法簡(jiǎn)單替代舉例設(shè)密鑰為k，加密規(guī)則是f(x)=(x+k)mod26當(dāng)k=3時(shí)明文M =FIGHTATNIGHT，被加密成密文Ek(M) =ILJKWDWQLJKWC語(yǔ)言的實(shí)現(xiàn)方式c=((a-’A’)+k)%26)+’A’;選擇具有自反特點(diǎn)的加密函數(shù)f(a)=(k-a)mod2617替代法簡(jiǎn)單替代特點(diǎn)易于手工操作，明密文都是字符串且等長(zhǎng)，明文中的字母在密文中都以其他字母所取代缺陷明文字母的出現(xiàn)次數(shù)與相應(yīng)密文字母的出現(xiàn)次數(shù)是相同的，因而明文中的字母統(tǒng)計(jì)特性在密文中也存在，容易被攻擊。（例如：明文中字母e出現(xiàn)得最多，而加密后字母h出現(xiàn)得最多）18替代法多表替代思路采用多個(gè)代替密鑰交替加密明文，以減弱頻率特性19替代法多表替代Vigenere密碼設(shè)明文字母為a，當(dāng)前密鑰字母為ki，則密文字母為fi(a)=(a+ki)mod26舉例20替代法多表替代舉例設(shè)明文M = INTELLIGENT密鑰 k = PLAYPLAYPLA密文Ek(M) = XYTCAMIETYT2122例：用Vigenere密碼加密明文：intrusiondetection，密鑰為NEU。答案：vrneymvsh

qinrgnvshM=int

rusiondet

ectionK=neu

neu

neu

neu

neu

neuC=vrn

eym

vsh

qin

rgn

vsh23替代法多表替代特點(diǎn)明文字母周期性地被不同的密鑰字母加密缺陷被相同密鑰字母加密的密文仍然具有頻率統(tǒng)計(jì)特性。一旦密碼分析員猜對(duì)了密碼長(zhǎng)度后，容易在密文中發(fā)現(xiàn)頻率統(tǒng)計(jì)特性，然后分別對(duì)每個(gè)密鑰字母破譯24替代法多表替代攻擊思路：首先猜測(cè)密鑰長(zhǎng)度，即加密周期，再分別破譯各密鑰字母猜測(cè)周期的方法重合度（indexofcoincidence）粗糙度（measureofroughness）25替代法游動(dòng)密鑰密碼思路采用很長(zhǎng)的、不重復(fù)的密鑰加密明文，避免密鑰周期方法利用諸如字典、圣經(jīng)等，又長(zhǎng)又不重復(fù)的文本作為密鑰，采用多表替換加密明文26替代法同音代替密碼思路對(duì)于出現(xiàn)頻率較高的明文字母采用多個(gè)不同的密文表示，以消除密文中的頻率統(tǒng)計(jì)特性方法根據(jù)明文字母表中各字母的一般出現(xiàn)概率，為每個(gè)明文字母分配一定數(shù)量的不重復(fù)的隨機(jī)數(shù)，加密時(shí)從中隨機(jī)選取一個(gè)作為密文27替代法同音代替密碼舉例設(shè)加密矩陣為28替代法同音代替密碼舉例設(shè)明文

M=PLAINPILOT則加密的結(jié)果可能為：C=9144566559330876287829替代法同音代替密碼特點(diǎn)單字母頻率特性在密文中被消除，不易破譯缺陷多字母頻率特性仍不能完全消除30替代法組合替代思路：一次替代明文中的多個(gè)字母特點(diǎn)：一定程度上消除字母頻率統(tǒng)計(jì)特性明文字母之間產(chǎn)生了相關(guān)性，其基本思想被應(yīng)用于后面將詳細(xì)講述的對(duì)稱分組密碼31代數(shù)密碼：①

Vernam密碼

明文、密文、密鑰都表示為二進(jìn)制位：

M=m1,m2,…,mn

K

=k1,k2,…,knC=c1,c2,…,cn②

加密：c1=mi⊕ki

,i=1,2,…,n

解密：m1=ci⊕ki

,i=1,2,…,n③因?yàn)榧咏饷芩惴ㄊ悄?加，所以稱為代數(shù)密碼。④對(duì)合運(yùn)算：f=f-1，模2加運(yùn)算是對(duì)合運(yùn)算。

密碼算法是對(duì)和運(yùn)算，則加密算法＝解密算法，工程實(shí)現(xiàn)工作量減半。⑤Vernam密碼經(jīng)不起已知明文攻擊。32

Vernam密碼與一次一密密碼Vernam密碼：加密：ci=mi+kimod2解密：mi=ci+ki

mod2例：1100010010＝01010一次一密：密鑰為一個(gè)隨機(jī)且不重復(fù)的字符序列。33代數(shù)密碼：⑥

如果密鑰序列有重復(fù)，則Vernam密碼是不安全的。⑦一種極端情況：一次一密

?密鑰是隨機(jī)序列。

?密鑰至少和明文一樣長(zhǎng)。

?一個(gè)密鑰只用一次。⑧一次一密是絕對(duì)不可破譯的，但它是不實(shí)用的。⑨一次一密給密碼設(shè)計(jì)指出一個(gè)方向，人們用序列密碼逼近一次一密。34古典密碼的窮舉分析單表代替密碼分析①加法密碼因?yàn)閒(ai)=bi=aj

j=i+kmodn所以k=1,2，...,n-1,共n-1種可能，密鑰空間太小。以英文為例，只有25種密鑰。經(jīng)不起窮舉攻擊。35古典密碼的窮舉分析單表代替密碼分析密鑰詞語(yǔ)代替密碼因?yàn)槊荑€詞語(yǔ)的選取是隨機(jī)的，所以密文字母表完全可能窮盡明文字母表的全排列。

以英文字母表為例，n=26，所以共有26！種可能的密文字母表。

26！≈41026用計(jì)算機(jī)也不可能窮舉攻擊。注意：窮舉不是攻擊密鑰詞語(yǔ)代替密碼的唯一方法。36古典密碼的統(tǒng)計(jì)分析密鑰詞組單表代替密碼的統(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ì)分析攻破。37單字母頻率分布圖38古典密碼的統(tǒng)計(jì)分析英語(yǔ)的統(tǒng)計(jì)規(guī)律

每個(gè)單字母出現(xiàn)的頻率穩(wěn)定。

最高頻率字母E

次高頻率字母TAOINSHR

中高頻率字母DL

低頻率字母CUMWFGYPB

最低頻率字母VKJXQZ39古典密碼的統(tǒng)計(jì)分析英語(yǔ)的統(tǒng)計(jì)規(guī)律

頻率最高的雙字母組：

THHEINERANREEDONESSTENATTONTHANDOUEANGASORTIISETITARTESEHIOF

40古典密碼的統(tǒng)計(jì)分析英語(yǔ)的統(tǒng)計(jì)規(guī)律

頻率最高的三字母組：

THEINGANDHEREREENTTHAWASETHFO