現(xiàn)代密碼學(xué)第2章：經(jīng)典密碼學(xué)

1、1經(jīng)典密碼學(xué)現(xiàn)代密碼學(xué)第2章2本章主要內(nèi)容 1 1、密碼體制的定義與分類(lèi)、密碼體制的定義與分類(lèi) 2 2、代替密碼與移位密碼、代替密碼與移位密碼 3 3、變換密碼、變換密碼 4 4、乘積密碼、乘積密碼 5 5、密碼機(jī)的發(fā)展歷史、密碼機(jī)的發(fā)展歷史31. 密碼體制的定義密碼體制的定義一個(gè)密碼體制密碼體制是一個(gè)六元組：（M, C, K1, K2, E, D )其中，M -明文空間C -密文空間K1 -加密密鑰空間K2 -解密密鑰空間E -加密變換空間D -解密變換空間4密碼體制的理解密碼體制的理解明文（明文（) )乃信息的原始形式，一般是信息的基本單元（字母、數(shù)字或符號(hào)等）的有限排列；密文（密文（)

2、)乃明文經(jīng)過(guò)加密以后的結(jié)果形式，一般沒(méi)有明確意義；密鑰（密鑰（) )乃用于加解密變換的關(guān)鍵信息，視其用于加解密而分別稱為加密密鑰與解密密鑰；5密碼體制的理解密碼體制的理解一個(gè)加密變換加密變換乃一個(gè)下列形式的一一映射：E: MK1 C 一般對(duì)于給定的kK1,把E(-,k)記為Ek; 一個(gè)解密變換解密變換乃對(duì)應(yīng)一個(gè)加密變換E而言，其實(shí)是一個(gè)以下形式的映射：D: CK2 M 并且適合（對(duì)于給定的kK2,也把D(-,k)記為Dk）：6密碼體制的理解密碼體制的理解：對(duì)任一kK1,都能找到k”K2,使得Dk”(Ek(m)=m，mM。7一般性說(shuō)明一般性說(shuō)明u我們常將26個(gè)英文字母(不區(qū)分大小寫(xiě)) 與整數(shù)02

3、5依次一一對(duì)應(yīng)。u記 Zq=0,1,2, ,q-1稱之為模q剩余類(lèi)環(huán)；當(dāng)q為素?cái)?shù)時(shí)，該環(huán)進(jìn)一步形成為域，可改寫(xiě)為Fq 。8一般性說(shuō)明一般性說(shuō)明u一般說(shuō)來(lái)，一個(gè)密碼體制的任一密鑰控制下的加密變換都要求把明文按n（最少必要的固定數(shù)）個(gè)信息單元進(jìn)行分組。照理，一個(gè)密碼體制的明文空間M應(yīng)該是所有可能明文的集合，但人們卻習(xí)慣于把它寫(xiě)成前述所有n個(gè)信息單元組的集合；如此，密文空間C以及加解密變換的定義也有相應(yīng)的變通。9簡(jiǎn)單密碼舉例 密碼學(xué)的歷史已有4000多年 古埃及人曾把象形文字寫(xiě)在石碑上10簡(jiǎn)單密碼舉例簡(jiǎn)單密碼舉例例例1. 凱撒（Caesar)密碼凱撒密碼是古羅馬人Julius Caesar發(fā)明的一種

4、密碼體制，它是使用最早的密碼體制之一。凱撒密碼用于對(duì)英文信息進(jìn)行加密，它依據(jù)下列代替表（由英文字母表左環(huán)移3位得到）對(duì)信息中26個(gè)英文字母進(jìn)行替換：明文字母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 密文字母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 C11簡(jiǎn)單密碼舉例簡(jiǎn)單密碼舉例若明文為：Substitution cryptosystem 則相應(yīng)的密文是： VXEVWLWXWLRQ FUBSWRVBVWHP在上述凱撒密碼體制中，英文字母代替表即相當(dāng)于密鑰；若將英文字母表左環(huán)移k

5、(0k1）稱該密碼為分組（塊）密碼。25密碼體制的分類(lèi)密碼體制的分類(lèi)：加解密速度快，無(wú)錯(cuò)誤擴(kuò)散；一般用于實(shí)際的安全產(chǎn)品。：適合數(shù)據(jù)庫(kù)加密，組內(nèi)有錯(cuò)誤擴(kuò)散；一般用于公開(kāi)的理論研究。26密碼體制的分類(lèi)密碼體制的分類(lèi)v依據(jù)密鑰分類(lèi)依據(jù)密鑰分類(lèi)單鑰密碼單鑰密碼( (傳統(tǒng)密碼，對(duì)稱鑰密碼）傳統(tǒng)密碼，對(duì)稱鑰密碼）雙鑰密碼雙鑰密碼( (公鑰密碼公鑰密碼, ,非對(duì)稱鑰密碼非對(duì)稱鑰密碼) )基于計(jì)算復(fù)雜性，人們可以設(shè)計(jì)出這樣的密碼體制：加密變換與相應(yīng)的解密變換分別使用不同的密鑰k與k”，并且kk”在計(jì)算上不可行（盡管理論上應(yīng)該能夠）。如此，用戶選擇該體制的一對(duì)加解密密鑰(k,k”)后，可以將前者公開(kāi)而后者私存。

6、區(qū)別于傳統(tǒng)上加解密密鑰一致或相近而必須都保密的觀念,稱之為非對(duì)稱(公開(kāi))鑰密碼體制。27密碼體制的分類(lèi)密碼體制的分類(lèi)一般說(shuō)來(lái)，單鑰密碼體制（包括分組、序列密碼）都是基于計(jì)算安全性的，而雙鑰密碼體制是基于可證明安全性的。這兩種安全性都是從計(jì)算量來(lái)考慮，但不盡相同。計(jì)算安全要算出或估計(jì)出破譯它的計(jì)算量下限，而可證明安全則要從理論上證明破譯它的計(jì)算量不低于解已知數(shù)學(xué)難題的計(jì)算量。28密碼體制的分類(lèi)密碼體制的分類(lèi)單鑰密碼優(yōu)點(diǎn)：運(yùn)行速度快，具有可靠的保密強(qiáng)度； 不足：不便密鑰交換和管理。雙鑰密碼優(yōu)點(diǎn)：便于密鑰交換和管理，還可用于消息認(rèn)證（數(shù)字簽名）； 不足：運(yùn)行速度緩慢，其安全性所 依賴的數(shù)學(xué)難題的復(fù)雜

7、性一般都未能證明。29早期密碼體制大都比較簡(jiǎn)單，其中許多經(jīng)不起計(jì)算機(jī)的破譯攻擊。這些體制一般都是直接針對(duì)原始的信息單元（字母或符號(hào)等）設(shè)計(jì)，而并不象現(xiàn)代密碼體制那樣非常重視和體現(xiàn)信息的數(shù)字化與數(shù)學(xué)處理。 但對(duì)早期密碼體制的討論可以說(shuō)明構(gòu)造和破譯的基本原理和方法，對(duì)于理解、構(gòu)造和分析現(xiàn)代復(fù)雜的實(shí)用密碼體制有著起碼的利益。2. 代替密碼代替密碼30早期密碼體制基本上可以按照下述分類(lèi)籠統(tǒng)起來(lái)：n代替密碼n移位密碼以下我們便按照這樣的分類(lèi)來(lái)依次學(xué)習(xí)早期的密碼體制及其破譯。2. 代替密碼代替密碼312. 代替密碼代替密碼一個(gè)代替密碼，若其任何密文可以看成是對(duì)相應(yīng)明文的各組信息單元使用同一個(gè)代替表進(jìn)行替換

8、而得到，則稱其為單表代替密單表代替密碼碼； 否則，即有密文是依次對(duì)相應(yīng)明文的各組信息單元使用有限個(gè)周期性重復(fù)的或無(wú)限多的固定代替表進(jìn)行替換而得到，稱其為多多表代替密碼。表代替密碼。32單表代替密碼 每個(gè)字母可以用其它任何一個(gè)字母替換（不能重復(fù)） 每個(gè)字母可以隨機(jī)的映射到其它一個(gè) 因此密鑰長(zhǎng)度是26個(gè)字母 單字母替換密碼（ Monoalphabetic Substitution Cipher ） 例如： 明文: ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文: DKVQFIBJWPESCXHTMYAUOLRGZN Plaintext: IFWEWISHTOREPLACELETTERS

9、 Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA33單表代替密碼舉例給定密鑰字 “STARWARS”，去掉重復(fù)字母得到 “STARW”，填寫(xiě)剩余字母： STARW BCDEF GHIJK LMNOP QUVXY Z 按列讀取字母得到密文： Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher: SBGLQZTCHMUADINVREJOXWFKPY 可以用這個(gè)密鑰加密、解密 例如 Plaintext: I KNOW ONLY THAT I KNOW NOTHING Ciphertext: H UINF NIAP OCSO H UINF INO

10、CHIT 34單表代替密碼 需要一種簡(jiǎn)單方法指定密鑰。 有多種方法，一種簡(jiǎn)單方法是寫(xiě)沒(méi)有重復(fù)字母的“密鑰字密鑰字”，其它字母按順序?qū)懺诿荑€字最后字母后面。 例如， 給定密鑰字 JULIUSCAESAR Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher: JULISCASRTVWXYZBDFGHKMNOPQ 35單表代替密碼的密碼分析 根據(jù)頻率統(tǒng)計(jì)進(jìn)行分析，確定每個(gè)字母被映射到什么字母，單個(gè)字母出現(xiàn)的可能是A或I（since know single words are A or I ） 一般來(lái)說(shuō)個(gè)字母出現(xiàn)的可能是THE或AND，還可以用其他通常出現(xiàn)的雙字母或三字母

11、組合。 還可以應(yīng)用其它很少應(yīng)用的字母36單表代替密碼構(gòu)造方法單表代替密碼構(gòu)造方法u舉例例例1.1. 一個(gè)英文單表代替密碼例例2.2. 方格密碼例例3.3. 普萊費(fèi)爾(Playfair)密碼u構(gòu)造方法構(gòu)造單表代替密碼的關(guān)鍵是構(gòu)造一張明密代替表(可能以對(duì)應(yīng)Z26的觀點(diǎn)寫(xiě)成一個(gè)數(shù)學(xué)公式)。 以后不加聲明，總假定M=C =a,b, c,z(記為A ), Z26, 或它們的n-直積。37單表代替密碼構(gòu)造方法單表代替密碼構(gòu)造方法密鑰字法該法形成明密代替表如下：首先依次列出密鑰字中字母(去掉其中的重復(fù))，然后依次列出字母表中其余的字母。特點(diǎn)：便于由記憶的密鑰字構(gòu)造出明密代替表；但密鑰空間K由所有可能的密鑰字

12、構(gòu)成，其實(shí)密鑰量|K|比較小。38洗牌法該法就是將寫(xiě)有每個(gè)英文字母的26張紙牌打亂次序后重新排列形成明密代替表。如例1。特點(diǎn)：密鑰空間K由26個(gè)英文字母的所有可能的全排列構(gòu)成（|K|=26?。荑€的保密性較好，但不便于記憶。單表代替密碼構(gòu)造方法單表代替密碼構(gòu)造方法39仿射法該法的加密變換Ek為：Ek(m)=k1m+k2 (mod 26), mZ26其中，k=(k1,k2)為密鑰；為使上述加密變換是一一的（從而才有相應(yīng)的解密變換），必要且只要(k1, 26)=1。特點(diǎn)：便于用計(jì)算機(jī)實(shí)現(xiàn)，但密鑰空間K =(k1,k2) | k1,k2Z26, (k1, 26)=1，密鑰量|K|=1226-1=3

13、11較小。單表代替密碼構(gòu)造方法單表代替密碼構(gòu)造方法40多項(xiàng)式法該法的加密變換Ek為(t為取定自然數(shù))：Ek(m)=ktmt+ kt-1mt-1+ k1m+k0 (mod 26), mZ26其中，k=(kt,kt-1, ,k1,k0)為密鑰。仿射法其實(shí)是上述多項(xiàng)式法當(dāng)t=1時(shí)的特例。有關(guān)多項(xiàng)式法的加密變換Ek何時(shí)是一一的以及對(duì)密鑰空間K 的討論已超出本課程的知識(shí)范圍，在此不去涉及。單表代替密碼構(gòu)造方法單表代替密碼構(gòu)造方法41矩陣法該法的思想是：將明文組m=(m1m2mn)通過(guò)Z26上可逆的線性變換轉(zhuǎn)換為密文組c=(c1c2cn) 。如此，密鑰空間K =(kij)| (kij)為Z26上n階可逆方

14、陣(有關(guān)討論超出本課程的知識(shí)范圍)；對(duì)于k= (kij)K ，加密變換Ek為：Ek(m1m2mn)=(c1c2cn), miZ26其中，ci=ki1m1+ki2m2+kinmn (mod 26)。單表代替密碼構(gòu)造方法單表代替密碼構(gòu)造方法42（2）多表代替密碼）多表代替密碼多表代替密碼是依次對(duì)明文的各組信息單元使用有限個(gè)周期性重復(fù)的或無(wú)限多的固定代替表進(jìn)行替換來(lái)得到密文的：若是使用無(wú)限多的固定代替表（相對(duì)于明文變化是隨機(jī)的），則稱其為一次一密代一次一密代替密碼替密碼；若是使用有限個(gè)周期性重復(fù)的固定代替表，則稱其為周期多表代替密碼周期多表代替密碼。43（2 2）多表代替密碼）多表代替密碼一次一密密

15、碼是在理論上唯一不可破解的密碼，這種密碼對(duì)于明文的特點(diǎn)可實(shí)現(xiàn)完全隱藏，但由于需要的密鑰量與明文所含信息單元的個(gè)數(shù)一樣大，故其難以實(shí)用。周期多表代替密碼的實(shí)際情形如下：在給定的密鑰(d個(gè)代替表排列T1T2Td)之下，加密明文m= m1m2m3的結(jié)果是c=T1(m1)Td(md) T1(md+1)Td(m2d) d稱為該周期多表代替密碼的周期。44周期多表代替密碼周期多表代替密碼u 舉例例例1.1.四表代替密碼。例例2.2.維吉尼亞(Vigenere)密碼。45 Blaise de Vigenre 發(fā)明了多字母替換密碼（polyalphabetic substitution cipher） 使用多

16、個(gè)單字母替換表 因此一個(gè)字母可以被多個(gè)字母替換。 方法：用一個(gè)密鑰選擇對(duì)每個(gè)字母使用哪個(gè)字母表，密鑰的第I個(gè)字母表示使用第 ith 個(gè)字母表，依次使用每個(gè)字母表，當(dāng)密鑰的字母使用完后，在從頭開(kāi)始。Vigenre Cipher46 例： 寫(xiě)出明文，在明文下重復(fù)寫(xiě)出密鑰字； 依次使用每個(gè)字母作為caesar cipher 的密鑰，加密對(duì)應(yīng)的明文字母。 Plaintext THISPROCESSCANALSOBEEXPRESSED Keyword CIPHERCIPHERCIPHERCIPHERCIPHE Plaintext VPXZTIQKTZWTCVPSWFDMTETIGAHLH Vigenre

17、 Example47 C - CDEFGHIJKLMNOPQRSTUVWXYZAB C - CDEFGHIJKLMNOPQRSTUVWXYZAB I - IJKLMNOPQRSTUVWXYZABCDEFGH I - IJKLMNOPQRSTUVWXYZABCDEFGH P - PQRSTUVWXYZABCDEFGHIJKLMNO P - PQRSTUVWXYZABCDEFGHIJKLMNO H - HIJKLMNOPQRSTUVWXYZABCDEFG H - HIJKLMNOPQRSTUVWXYZABCDEFG E - EFGHIJKLMNOPQRSTUVWXYZABCD E - EFGHIJ

18、KLMNOPQRSTUVWXYZABCD R - RSTUVWXYZABCDEFGHIJKLMNOPQ R - RSTUVWXYZABCDEFGHIJKLMNOPQ ABCDEFGHIJKLMNOPQRSTUVWXYZ ABCDEFGHIJKLMNOPQRSTUVWXYZ to map the above plaintext letters. to map the above plaintext letters. T uses key C maps to V H uses key I maps to P I ises key P maps to X。Vigenre Example48 可以看出

19、，越安全的密碼使用起來(lái)越復(fù)雜，因此，在有些場(chǎng)合還可以看到單碼替換密碼，隨著破譯單碼密碼的技術(shù)提高，使得vigenre cipher 逐漸被各國(guó)使用，1854年，首次被 Charles Babbage 攻破，但沒(méi)有公開(kāi)。 Friedrich Kasiski 與1863年攻破并發(fā)表了此密碼的各種變形被沿用到20世紀(jì)。History of the Vigenre Cipher49周期多表代替密碼例例3.3.博福特(Beaufort)密碼。例例4.4.弗納姆(Vernam)密碼該密碼是美國(guó)電報(bào)電話公司的G.W.Vernam在 1917年發(fā)明的。他將英文字母編成五位二元波多電碼(Baudot code)

20、，參見(jiàn)P.47表3.2.9。選擇隨機(jī)的二元密鑰序列k= k1k2ki，對(duì)字母變換成二元碼后的明文m= m1m2mi加密以后得到c= c1c2ci，其中ci= mi ki，i=1,2,50周期多表代替密碼周期多表代替密碼思考：怎樣理解上述弗納姆密碼是周期多表代替密碼？其實(shí)，弗納姆密碼可以看成周期d=明文長(zhǎng)(明文所含字母數(shù)目)的多表代替密碼。一般地,我們稱周期d=明文所含信息單元組數(shù)目的多表代替密碼為滾動(dòng)密鑰滾動(dòng)密鑰(Running-(Running-key)key)密碼密碼。51周期多表代替密碼周期多表代替密碼對(duì)于一個(gè)滾動(dòng)密鑰密碼,其密鑰序列(即依次決定d個(gè)代替表的系列對(duì)應(yīng)要素，如弗納姆密碼所用

21、的二元密鑰序列)若能真正隨機(jī)產(chǎn)生，則該種代替密碼便相當(dāng)于一次一密的了；一般密鑰序列要由一給定主密鑰作為初態(tài)的某密鑰源偽隨機(jī)地產(chǎn)生。52周期多表代替密碼周期多表代替密碼u構(gòu)造方法照理，周期為d的多表代替密碼的密鑰空間應(yīng)為K =T1T2Td|Ti為代替表,i=1,2,d,但在實(shí)際應(yīng)用之中的密鑰變化量往往較?。喝藗兪紫葮?gòu)造出dd個(gè)代替表T1,T2, Td，然后以T1,T2,Td取出d個(gè)的排列為密鑰空間。如例1、2、3。上述在T1,T2,Td中取出d個(gè)排列起來(lái)的過(guò)程一般是借助決定d個(gè)代替表的系列對(duì)應(yīng)要素進(jìn)行，因此稱之為構(gòu)造密鑰序列。53周期多表代替密碼周期多表代替密碼顯然，周期多表代替密碼的構(gòu)造可以歸

22、結(jié)為： 多個(gè)代替表（稱為底表）的構(gòu)造 密鑰序列的構(gòu)造一個(gè)周期多表代替密碼的密鑰其實(shí)是上述密鑰序列，底表預(yù)先定義，而在加密中每次應(yīng)用哪一底表完全由該密鑰序列來(lái)控制。54周期多表代替密碼周期多表代替密碼 底表的構(gòu)造一個(gè)底表一般為二維表，并且要求每個(gè)密文單元所在的行或列中出現(xiàn)一次且只出現(xiàn)一次，即該二維表應(yīng)構(gòu)成一個(gè)拉丁方陣。有關(guān)拉丁方陣的研究和構(gòu)造可參見(jiàn)一些組合學(xué)書(shū)籍或刊物。55周期多表代替密碼周期多表代替密碼要求底表為一個(gè)拉丁方陣是必要的：因一般來(lái)說(shuō)，底表的行、列分別對(duì)應(yīng)明文和密鑰：若橫行有重碼，則加密變換便不是一一的；若縱列有重碼，則即使密鑰序列是隨機(jī)選取的，但明碼中的不平衡性，也會(huì)造成密碼的不平

23、衡，從而使破譯者僅從密碼的統(tǒng)計(jì)分析即可獲得明文的部分信息，這不利于保密。當(dāng)然，若周期較大，則對(duì)保密性而言，底表的作用不大，其完全取決于密鑰序列。56周期多表代替密碼周期多表代替密碼 密鑰序列的構(gòu)造人們當(dāng)然希望所產(chǎn)生的密鑰序列具有盡可能好的隨機(jī)性。一般可有下述三種構(gòu)造方法：主觀密鑰源該種密鑰源是以一本書(shū)或一個(gè)文件的選擇內(nèi)容作為密鑰序列k1k2kd。評(píng)價(jià)評(píng)價(jià)：由于書(shū)本或文件中各信息單元出現(xiàn)的頻率差異很大，故該種密鑰源的保密性能不佳。57周期多表代替密碼周期多表代替密碼隨機(jī)密鑰源該種密鑰源是以某種隨機(jī)的方式產(chǎn)生密鑰序列k1k2kd。例如，對(duì)維吉尼亞密碼或博福特密碼，使用者可將分別刻有26個(gè)英文字母的

24、26個(gè)小球放在壇子里，然后用有放回地隨機(jī)揀球方法產(chǎn)生密鑰序列。評(píng)價(jià)評(píng)價(jià)：該種密鑰源的保密性能最佳，但當(dāng)d較大時(shí)一則難以實(shí)現(xiàn)，另則必須將此產(chǎn)生的較長(zhǎng)密鑰序列完全傳送給接收方、或要由接收方妥善保管、等等，實(shí)有諸多不便。58周期多表代替密碼周期多表代替密碼偽隨機(jī)密鑰源該種密鑰源是根據(jù)現(xiàn)代的編碼方法，利用計(jì)算機(jī)硬件或軟件實(shí)時(shí)地產(chǎn)生密鑰序列k1k2kd。評(píng)價(jià)評(píng)價(jià)：該種密鑰源往往以一給定的主密鑰作為初態(tài)，產(chǎn)生一個(gè)自身呈周期性的密鑰序列。但設(shè)計(jì)者可根據(jù)實(shí)際保密強(qiáng)度的要求，預(yù)期密鑰序列的周期遠(yuǎn)遠(yuǎn)大于一般所加密明文的長(zhǎng)度，而且還具有良好的隨機(jī)性；此時(shí)可以認(rèn)為偽隨機(jī)密鑰源在保密性能上已近似于隨機(jī)密鑰源了。59周期

25、多表代替密碼周期多表代替密碼一個(gè)值得重視的問(wèn)題是：密鑰序列自身的保密性能固然重要，但若是應(yīng)用不當(dāng)，再好的密鑰序列也可能無(wú)濟(jì)于整個(gè)體制的安全。比如，密鑰序列重用(這一現(xiàn)象稱為重亂）就會(huì)給相應(yīng)的周期多表代替密碼體制帶來(lái)危害，有關(guān)的具體情形以后會(huì)講到。60多表代替密碼的特點(diǎn)多表代替密碼的特點(diǎn)q 單表代替密碼的特點(diǎn)單表代替密碼的特點(diǎn)：具有明密異同規(guī)律，一般容易破譯。q 周期多表代替密碼的特點(diǎn)周期多表代替密碼的特點(diǎn)： 在一定程度上打破了明密異同規(guī)律 當(dāng)周期d較小時(shí)，可確定之，并通過(guò)對(duì)密文重排，使其破譯問(wèn)題轉(zhuǎn)化為對(duì)單表代替密碼的破譯 對(duì)周期d較大且密鑰序列是偽隨機(jī)的，可達(dá)到實(shí)際保密 對(duì)周期d較大且密鑰序列

26、是隨機(jī)的,可達(dá)到理論保密q 一次一密代替密碼的特點(diǎn)一次一密代替密碼的特點(diǎn)：無(wú)規(guī)律可循613. 變換密碼 transposition ciphers 變換密碼（或置換密碼） 方法：通過(guò)重新編排消息字母隱藏信息 特點(diǎn)：沒(méi)有改變?cè)瓉?lái)消息的字母集62（1）Scytale 密碼 一種早期的 希臘變換密碼 一張紙條環(huán)繞在一個(gè)圓柱上 消息沿著圓柱橫寫(xiě) 紙條上的字母看起來(lái)是一些隨機(jī)字母 并不十分安全，密鑰是紙條和圓柱的寬度63 以不同的行寫(xiě)下消息字母 按行讀取消息 Plain: I A E S W C N U R D C M I A I O Q E E Cipher: IAESW CNURD CMIAI OQ

27、EE （2）軌道欄桿密碼 Rail Fence cipher64 以一種形式寫(xiě)下消息，以另一種形式讀取消息 （3）幾何圖形密碼65 變換密碼的關(guān)鍵思想 按一定規(guī)則寫(xiě)出明文，按另一規(guī)則讀出密文。 密鑰：用于讀密文的方法和寫(xiě)明文的方法變換密碼的關(guān)鍵思想66（4）行變換密碼-Row transposition ciphersgroup the message and shuffle letters within each group more formally write letters across rows then reorder the columns before reading off

28、the rows always have an equivalent pair of keys (Read off vs Write In) 67Plain: THESIMPLESTPOSSIBLETRANSPOSITIONSXXKey (R): 2 5 4 1 3 Key (W): 4 1 5 3 2 T H E S I S T I E H M P L E S E M S L P T P O S S S T S O P I B L E T E I T L B R A N S P S R P N A O S I T I T O I I S O N S X X X O X S N Cipher:

29、 STIEH EMSLP STSOP EITLB SRPNA TOIIS XOXSN 行變換密碼68 可以用一個(gè)英文單詞做密鑰，指定以字母順序做為讀取密文（或明文）Plain: CONVENIENTWAYTOEXPRESSTHEPERMUTATION Key (W): C O M P U T E R Key (W): 1 4 3 5 8 7 2 6 A N O V I N C EE W T A O T N Y E R P E T S X SH E P R T U E M A O I N Z Z T Z Cipher: ANOVI NCEEW TAOTN YERPE TSXSH EPRTU EM

30、AOI NZZTZ 行變換密碼69 用密鑰 sorcery 加密下列消息: Key(R): sorcery = 6 3 4 1 2 5 7 laser beams can be modulated to carry more intelligence than radio waves = erasb lecam snabd umole atoed ctamo ryrre elntl iicee ntgha dnria oesav w 行變換密碼舉例70 步驟: 按列寫(xiě)出消息 按解密密鑰讀取明文 行變換密碼解密算法71 頻率分析能夠提供語(yǔ)言輪廓 基本思想:猜測(cè)密鑰周期,再對(duì)可能的行列變換進(jìn)行猜測(cè)

31、. 利用常出現(xiàn)的雙字母對(duì)或3字母對(duì).Cryptanalysis of Row Transposition ciphers72密碼分析舉例 給定密文: LDWOE HETTS HESTR HUTEL OSBED EFIEV NT 對(duì)連續(xù)周期測(cè)試, 對(duì)前面一些字母重新排列. 2: LD WO EH ET TS HE ST RH UT EL OS BE DE FI EV NT - NO 3: LDW OEH ETT SHE STR HUT ELO SBE DEF IEV NT - NO 4: LDWO EHET TSHE STRH UTEL OSBE DEFI EVNT - NO 5: LDWOE

32、HETTS HESTR HUTEL OSBED EFIEV NT - NO 6: LDWOEH ETTSHE STRHUT ELOSBE DEFIEV NT - YES! note 第二組可能提供 THESET or TTHESE 可以猜測(cè)6字密鑰能夠給出這種密文 key 5,6,1,4,2,3 恢復(fù)明文如下: WEHOLD THESET RUTHST OBESEL FEVIDE NT or WE HOLD THESE TRUTHS TO BE SELF EVIDENT 73（5）塊（Block ）變換密碼 另一類(lèi)變換密碼 消息按行寫(xiě)，按列讀出。 按列讀出的順序由密鑰給出。74 為方便起見(jiàn)，把

33、消息寫(xiě)成滿矩陣形式 Key(R): s o r c e r y s o r c e r y Key(R): 6 3 4 1 2 5 7 6 3 4 1 2 5 7 l a s e r b e l a s e r b e a m s c a n b a m s c a n b e m o d u l a e m o d u l a t e d t o c a t e d t o c a r r y m o r e r r y m o r e i n t e l l I i n t e l l i g e n c e t h g e n c e t h a n r a d i o a n r a

34、d i o w a v e s w a v e s q r matrix incompleteincomplete completecomplete 塊變換密碼舉例75續(xù) 由密鑰給出的順序讀出密文（4, 5, 2, 3, 6, 1, 7) ecdtm ecaer auool edsam merne nasso dytnr vbnlc rltiq laetr igawe baaei hor 76塊變換密碼解密 計(jì)算密文行數(shù) (by dividing message length by key length) 按列寫(xiě)出密文消息（密鑰給出順序） 按行讀出明文消息77塊變換密碼分析 首先要知道是否塊變

35、換密碼，通過(guò)消息長(zhǎng)度猜測(cè)距陣大小，簡(jiǎn)單 測(cè)試每個(gè)密鑰，按列寫(xiě)出消息 最一般的，利用自動(dòng)工具實(shí)驗(yàn)所有置換，可以對(duì)一些可能單詞組合形式的變換進(jìn)行實(shí)驗(yàn)。78密碼分析例子 給定密文: HADVF NITHB CTSBE HTEGE SRYRN AMINR IAIST TETOO ETSAN GLIET GTDRS CYGAI TANAH FLNAU ETIEM EOHUE AELYR IIS 假設(shè)對(duì)行變換失敗現(xiàn)猜測(cè)是塊變換尋找THE，實(shí)驗(yàn)各種大小的密鑰 try 2, use command b 2 /THE - none match try 3, use command b 3 /THE - none

36、 match try 4, use command b 4 /THE - 2 matches, both rubbish try 5, use command b 5 /THE - 1st match gives answer - b 5 /THE THEGR EATES TDISC OVERY OFMYG ENERA TIONI STHAT AHUMA NBEIN GCANA LTERH ISLIF EBYAL TERIN GHISA TTITU DES Accept (y/n/q)?y79Nihilist ciphers 更復(fù)雜的變換密碼（行變換和列變換同時(shí)應(yīng)用）80 僅僅基于替換或置換的

37、密碼是不安全的 前面的得例子可以看到這一點(diǎn) 這是由于他們不能克服語(yǔ)言結(jié)構(gòu)的特點(diǎn) 因此考慮連續(xù)使用幾種密碼克服, 注: 兩個(gè)替換密碼只能提高很少的復(fù)雜度 兩個(gè)置換也只能提高很少的復(fù)雜度 但替換與置換連用，可以提高較高的復(fù)雜密碼增加密碼的安全性814. 乘積密碼 是一種替換與變換合用的密碼，一般情況下，手工破譯是非常困難的。 一種有名的乘積密碼“ADFGVX cipher” 在第一次世界大戰(zhàn)中使用。82ADFGVX 乘積密碼 這樣命名是因?yàn)樽儞Q僅依賴與 ADFGVX，在WW1有德國(guó)人使用，并被英國(guó)人破譯。 方法：使用一個(gè)固定的替換表，把每個(gè)明文字母映射成一個(gè)字母對(duì) (row-col index)，在用一個(gè)帶密鑰的塊變換把每個(gè)對(duì)分解then 利用帶密鑰的塊變換寫(xiě)下所有字母對(duì)，寫(xiě)出密文（按塊密碼形式）。83ADFGVX Substitution