1現代密碼學

理論與實踐第二章古典密碼學林喜軍linxj77@163.com人類使用密碼的歷史幾乎和使用文字的時間一樣長

——《破譯者》2主要內容2.1置換密碼2.2代換密碼2.2.1移位密碼2.2.2單表代換密碼2.2.3維吉尼亞密碼2.3轉輪機密碼2.4古典密碼的統計分析2.4.1單表代換密碼的分析2.4.2維吉尼亞密碼的分析32.1置換密碼置換，又稱易位，是古典密碼中用到的一種最基本的處理技術；置換密碼是改變明文中各字符的相對位置，但明文字符本身的取值不變；典型代表：周期置換密碼4周期置換密碼工作原理將明文按一定長度m進行分組，把每組的字符按位置變換規則π重排位置。π就是對位置{1，2，…，m}的一個置換5舉例例：m=6時，置換π如下明文gohome……密文HEGMOO……解密時需要逆置換π-1x123456π(x)351642y123456π-1(y)361524明文字符位置變換后的位置6周期置換密碼的密鑰空間密鑰就是置換π，在π的描述中還包含了分組長度m的信息。密鑰空間大小是多少？m!72.2代換密碼代換，又稱替換，是古典密碼中用到的另一種最基本的處理技術工作原理先建立一張或多張代換表(明文字符到密文字符的對應關系、映射)加密時將明文字符依次通過查表，找到相應的密文字符明文字符被逐個替換后，生成無任何語義的字符串，即密文。8代換密碼的密鑰就是代換表根據加解密時使用代換表多少的不同，代換密碼又可分為兩類單表代換密碼：使用一張固定的代換表多表代換密碼：使用多張代換表92.2.1移位密碼移位密碼是單表代換密碼的一個特例工作原理加密:把明文中每個字母代換為字母表中其后的第k個字母。解密:與加密相反，把密文中每個字母代換為字母表中其前的第k個字母。明文字母abcd…wxyz密文字母FGHI…BCDEk=5時的情況10移位密碼舉例——凱撒密碼凱撒密碼(k=3)是移位密碼的典型代表

加解密舉例： 明文：veni,vidi,vici

密文：YHQL,YLGL,YLFL

明文字母abcd…wxyz密文字母DEFG…ZABC引自《高盧戰記》JuliusCaesar(100BC–44BC)11移位密碼是不安全的密鑰是什么？就是k密鑰最多有多少個？只有26個，k=0,1,…,25。密鑰空間很小窮舉攻擊可以在很短時間內破譯因此，它是不安全的122.2.2單表代換密碼單表代換密碼使用一張固定的代換表明文字符到密文字符的對應關系不一定像移位密碼那樣有規律。代換表可以是字符表上的任意置換13文學作品中的單表代換密碼福爾摩斯探案集·跳舞的小人14單表代換密碼的密鑰空間密鑰空間很大26個字母的不同排列形成不同的密鑰，共有26!=4×1026

個窮舉攻擊在計算上是不可行的，即使1微秒試一個密鑰，遍歷全部密鑰需要1013年。正如前面提到的，很大的密鑰空間并沒有使單表代換密碼成為安全的密碼體制。有其他攻擊方法可以輕松破譯它。15單表代換密碼的弱點密文字母的唯一性。明文中相同的字母(比如a),在密文中總是以另一個字母(比如E)代替。即，明文中出現a的地方，在密文中相應的都會出現E這導致明文中單字母的頻率分布與密文中的相同。這一弱點成為單表代換密碼的硬傷,利用這一弱點進行攻擊，比窮舉攻擊更加有效161587年2月8日,蘇格蘭女王瑪麗·斯圖亞特被送上斷頭臺Enmafinestmoncommencement歷史的教訓17單表代換密碼的改進——同音密碼abcde…●▽⊙￥?

□◎☆℉

★▲§＄

※⊕¤明文字符密文字符18同音密碼(1)——大密碼路易十四與“大密碼”路易十四巴士底獄《鐵面人》19同音密碼(2)——十二宮殺手密碼60年代末，美國加州出現一名自稱Zodiac的連環殺手他給報社寄去信，稱信中408個符號的密文(408密碼)包含他的身份信息。盡管408密碼被密碼愛好者海登夫婦破譯，但信中并沒有殺手的身份信息。Zodiac繼續犯下多起謀殺案后，又寫了一封340個符號的密文（340密碼），要求報社將它放在頭版頭條。至今仍沒有人破譯340密碼。408密碼的密文和明文20維吉尼亞密碼最早記錄在貝拉索于16世紀所著的書中。19世紀時被誤傳為是法國外交官維吉尼亞所創，因此現在被稱為“維吉尼亞密碼”。維吉尼亞密碼以其簡單易用而著稱，同時初學者通常難以破解，因而又被稱為“不可破譯的密碼”。應用：南北戰爭中的南軍維吉尼亞2.2.3維吉尼亞密碼21維吉尼亞密碼是多表代換密碼的典型代表多表代換密碼使用多個代換表,以隱藏單字母出現的頻率分布，每個代換表都可以看成是一個單表代換密碼中的代換表。多表代換密碼的工作原理將明文劃分為長度相同的消息單元，稱為明文分組對明文成組地進行代換，根據每次使用的不同的代換表，同一個明文字母可以變換成不同的密文字母。從而改變了單表代換密碼中密文唯一性的弱點，使密碼分析更加困難。22維吉尼亞密碼的工作原理該密碼體制有一個參數m(密鑰的長度)加解密時，將消息分為m個字母一組進行變換。變換時，使用26張代換表，根據不同的密鑰字母，每個明文字母使用不同的代換表進行加解密。注意：在維吉尼亞密碼中，代換表不再是密鑰了。23維吉尼亞代換表每行都由前一行向左偏移一位得到。實際就是26個移位密碼的代換表具體使用哪一行代換表，是基于密鑰進行的，在代換過程中會不斷地變換。24明文：ATTACKATDAWN

密鑰：LEMON(m=5)加密明文：ATTACKATDAWN

列密鑰：LEMONLEMONLE

行密文：LXFOPVEFRNHR(明文第1個字母A，對應密鑰第1個字母L。使用表格L行代換表進行加密，得到密文的第1個字母L。其他明文字母依此類推）解密的過程與加密相反。舉例25維吉尼亞密碼的密鑰空間密鑰空間與密鑰長度m有關共有26m個密鑰，即使m很小，窮舉攻擊也不太現實假設m=5，密鑰空間超過1.1×107，已超出手工計算進行窮舉攻擊的能力范圍。但這并不表示維吉尼亞密碼無法用手工破譯。26維吉尼亞密碼的弱點對所有多表代換密碼的破譯都是以字母頻率為基礎的。同一個明文字母可被加密成不同密文字母，簡單的頻率分析行不通。破譯的關鍵在于它的密鑰是重復使用的。故而，維吉尼亞密碼的弱點當相同字母間隔密鑰長度倍數時，被加密成相同字母破譯的突破口利用此弱點，尋找密鑰長度明文：ATTACKATDAWN密鑰：LEMONLEMONLE密文：LXFOPVEFRNHR272.3轉輪機密碼產生背景大量密碼體制被攻破無線電的普遍使用，增加了對密碼技術的需求轉輪機密碼是密碼技術與電子和機械技術相結合的產物。人們擺脫了手工作坊式的操作，使得加解密變得更加簡單易用，而且可以構造更復雜的密碼體制。它標志著加密機械化的開始28轉輪機的典型代表——Enigma發明者：德國工程師亞瑟·謝爾比烏斯起初用于商用，后來主要應用于軍事。在二戰期間，不但德國使用Enigma，意大利、日本等軸心國成員也都在使用人們估計，約有十萬臺Enigma被制造出來。二戰結束后，盟軍把繳獲的Enigma賣給了一些發展中國家。29Enigma的結構基本結構一個鍵盤、若干燈泡、一系列轉輪鍵盤一共有26個鍵，鍵盤上方是標示了字母的26個小燈泡當某個鍵被按下時，與相應密文字母對應的小燈泡就亮了起來。在顯示器的上方是幾個轉輪，每個轉輪是26個字母的任意組合。轉輪1轉輪2轉輪n指示燈鍵盤…30Enigma的工作原理每個轉輪有26個輸入引腳和26個輸出引腳，內部連線將每個輸入引腳連接到一個對應的輸出引腳，這樣每個轉輪內部相當于一個單表代換密碼。當按下某一鍵時，電信號從第一個轉輪的輸入引腳進入，通過內部連線經過每個轉輪，從最后一個轉輪的輸出引腳輸出對應密文字母（點亮）。2425260102030405060708091011121314151617181920212223210315011910142620081607220411051709122318022506241331Enigma的工作原理(續)這些轉輪被稱作轉子。為了實現復雜的多表代換，打破明文與密文之間固定的代換關系，在每次擊鍵輸出密文字母后，轉子都要發生轉動。以此改變相鄰轉子之間的對應關系，從而實現復雜的多表代換功能。實際上，轉子的初始設置就是密鑰32Enigma的工作原理(續)對于3個轉子的情況(德國國防軍版)，根據每個輪子轉動快慢不同，分為慢轉子、中轉子和快轉子快轉子轉動26次后，中轉子就轉動一個位置；中轉子轉動26次后，慢轉子就轉動一個位置。在加密（或解密）263=17,576個字母后，所有轉子就會恢復到初始狀態。有n個轉輪的轉輪機是一個周期長度為26n

的多表代換密碼。另外，還利用鍵盤和第一個轉子之間的連接板實現的簡單代換，以增加輸出的復雜性來對抗窮舉攻擊。ABCDEFGHIJKLMNOPQRSTUVWXYZ242526010203040506070809101112131415161718192021222321031501191014262008160722041105170912231802250624132601020304050607080910111213141516171819202122232425200106041503141223051602221911182524130710082109261726010203040506070809101112131415161718192021222324251408182617202210031311042305240912251619061521020701ABCDEFGHIJKLMNOPQRSTUVWXYZ慢中快在一次擊鍵后的設置ABCDEFGHIJKLMNOPQRSTUVWXYZ242526010203040506070809101112131415161718192021222321031501191014262008160722041105170912231802250624132601020304050607080910111213141516171819202122232425200106041503141223051602221911182524130710082109261701020304050607080910111213141516171819202122232425260818261720221003131104230524091225161906152102070114ABCDEFGHIJKLMNOPQRSTUVWXYZ慢中快初始設置A→BB→IC→E……A→EB→QC→T……34對Enigma的破譯1931，德國密碼處工作的施密特向法國情報人員提供了兩份有關Enigma的操作和轉子內部線路的資料(這說明做到絕對保密算法比較困難)但是法國人無法破譯它。法軍認為，《凡爾賽條約》限制了德軍的發展，即使無法破譯德軍的密碼，將來在戰場上相遇也不會吃多大虧。在得出德軍密碼“無法破譯”的結論之后，法國人就再也沒有用心地研究它了。35對Enigma的破譯(續)波蘭是一戰后新獨立的國家，但夾在德、蘇兩大軍事強國之間，而兩國都對波蘭領土垂涎三尺。殘酷的國際形勢迫使波蘭需要時刻了解德、蘇的內部信息。波蘭從法國那里得到施密特透露的情報，并成功破譯了Enigma。(破譯突破口是德國人使用Enigma不當造成的）36對Enigma的破譯(續)二戰爆發后，英、法獲知了破譯Enigma的方法，并投入大量人力和資金對改進型Enigma進行破譯。盟軍設計的專門用來破譯Enigma的機器“炸彈”也大大提高了布萊切利莊園的工作效率。37對破譯Enigma做出貢獻的人雷耶夫斯基、羅佐基、佐加爾斯基

——

波蘭三杰

1954年7月7日，圖靈自殺，時年42歲382.4古典密碼的統計分析置換密碼、單表代換密碼、維吉尼亞密碼等對己知明文攻擊都是非常脆弱的。即使用唯密文攻擊，大多數古典密碼體制都容易被攻破，因為它們不能很好地隱藏明文消息的統計特征。下面就針對單表代換密碼、維吉尼亞密碼，介紹利用英文語言的統計特征和密碼特點，運用唯密文攻擊破譯古典密碼的基本方法。392.4.1單表代換密碼的分析本質上，密文字母表是明文字母表的一種排列。企圖使用計算機窮舉密鑰來破譯某些單表代換密碼(如密鑰詞組代換密碼)也是計算上不可行的。但可以利用自然語言的統計特性進行分析。英文的每個字母出現的頻率不一樣。這正是進行統計分析的基礎，也是單表代換密碼的硬傷。字母和字母組合的統計數據十分重要，它們提供了有關密鑰的許多信息。40字母出現頻率字母出現頻率a0.082n0.067b0.015o0.075c0.028p0.019d0.043q0.001e0.127r0.060f0.022s0.063g0.020t0.091h0.061u0.028i0.070v0.010j0.002w0.023k0.008x0.001l0.040y0.020m0.024z0.001表中字母出現頻率為字母出現次數除以文本字母總數41通過對26個英文字母出現頻率的分析，可以有以下結果：e出現的頻率最大；t、a、o、i、n、s、h、r出現的頻率約在0.06～0.09之間；d、l出現的頻率約為0.04；c、u、m、w、f、g、y、p、b出現的頻率約在0.015～0.023；v，k，j，x，q，z出現的頻率小于0.01。42除考慮單字母統計特性外，雙字母、三字母的統計特性以及字母之間的連綴關系等信息也很有用。出現頻率最高的30個雙字母組合依次是：

th he in er an re ed ones st en at to nt ha

nd ou ea ng as or ti iset it ar te se hi of43出現頻率最高的20個三字母組合依次是：

the ing and her ereent tha nth wasethfor dthhat she ioninthissth ersver

特別的，the出現的頻率幾乎是ing的3倍，這在密碼分析中很有用。44此外，統計資料還表明超過一半的英文單詞以e、s、d、t字母結尾。約一半的英文單詞以t、a、s、w開頭。對于攻擊者來說，這些都是十分有用的信息。除此之外，對明文相關知識的掌握對破譯密碼也是十分重要的。(回想一下納瓦霍語密碼的優勢)45破譯方法=統計分析+大膽猜測有了上述知識，下面便可以采用唯密文攻擊對單表代換密碼進行破譯了。基本思想字母e比其它字母的頻率高得多，可以預計大多數密文都將包含一個頻率比其它字母都高的字母。當出現這種情況時，猜測這個密文字母對應的明文字母是e。然后，進一步比較密文中其他字母的頻率統計分布，便可確定出密鑰，從而破譯單表代換密碼。46破譯的大致過程統計密文各字母的出現頻率，如果密文量比較多，完成這步便可確定出大部分密文字母；分析雙字母、三字母密文組合，以區分元音和輔音字母；在這一過程中大膽使用猜測的方法；如果猜對一個或幾個單詞，便會大大加快破譯過程。47單表代換密碼破譯舉例考慮下面的密文：

YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVFJBTXCDDUMJNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZNZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJXZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR48單表代換密碼破譯舉例(續)統計密文中各字母的出現次數Z出現的次數遠高于其他字母，所以可以猜測其對應的明文字母是e。出現次數超過10的字母有{C、D、F、J、M、R、Y}，它們可能對應{t、a、o、i、n、s、h、r}，但不能確定是哪一個49考慮形如-Z和Z-的雙字母組合ZW出現4次，WZ一次也沒出現，同時W出現的頻率為0.048，故可猜測W對應于d。50考慮出現次數都很高的DZ和ZD因為DZ出現4次，ZD出現2次，故可猜測D可能對應{r,s,t}中的某一個。在W對應d的猜測下，考慮字母RR在密文中頻繁出現，RW出現了2次。n是一個英文中出現頻率較高的字母，nd是一個英文中常見的字母組合，因此可以猜測R對應n。51到目前為止，已經得到了3個密文字母可能對應的明文字母，列出它們的對應關系：

endenede

YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVFJBTXCDDUMJ—————————————————————

eendeneeNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ—————————————————————

ennedeenendeeNZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ—————————————————————

edneeddenXZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR—————————————————————52考慮NZ和ZNNZ是密文中出現較多的字母組合(3次)，ZN沒出現，所以可以猜測N對應h。如果這個猜測正確，根據明文片段ne－ndhe又可以猜測C對應a(可能為neandhe形式的明文)。53結合這個假設，進一步有：

endaeanedhe

a

YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVFJBTXCDDUMJ—————————————————————heaeaanhadaenaeheNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ—————————————————————heannedeeneandheeNZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ—————————————————————

edanhhaaeedadhenXZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR—————————————————————

至此，以e為突破口的分析到此結束54現在考慮出現次數排在第二的密文字母M已知密文段RNM對應的明文為nh-，這說明h-可能是一個單詞的首字母，所以M可能代表一個元音字母。因為已經猜測了{e,a}對應的密文字母，所以猜測M可能對應{i,o}中的某一個。在此前的分析中，我們觀察出現了aM。因為明文雙字母ai比ao的出現次數更多，所以先猜測M對應i。55據此進一步有：iendaieainedhieai

YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVFJBTXCDDUMJ—————————————————————hieaieaainhadaenaehieNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ—————————————————————heaniniedeeineandheeNZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ—————————————————————

edainhihaiaeiedadhenXZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR—————————————————————56下面再確定明文o對應的密文o是常見的明文字母，可以猜測相應的密文中常出現的字母{D,F,J,Y}中的某一個。密文出現CFM、CJM，如果o對應F或J,明文中將出現aoi的元音組合，這在英文中不太可能。因此，猜測Y對應o。

(此前猜測D對應{r,s,t})

57再考慮{D、F、J}，可能對應{r,s,t}。密文中NMD出現了2次，故可猜測D對應s。這樣，密文NMD對應的明文三字母組合為his。

(這與前面假設D對應{r,s,t}是一致的)58據此進一步有：oiendoaiseainedhiseassi

YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVFJBTXCDDUMJ—————————————————————hsiseasieaoainhadaenaehieNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ—————————————————————heasnooinioedsoeoeineandheseNZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ—————————————————————

edainhishaiaeiedoadshesnXZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR—————————————————————59考慮三字母組合HNCMF可猜測它對應的明文可能是chair。由此又猜測H對應c，F對應r。這樣，可以排除J對應t的可能性。60據此進一步有：oriendroariseainedhiserassi

YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVFJBTXCDDUMJ—————————————————————hsrriseasieaorainhadaenacehieNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ—————————————————————heasnooinioredsoeoreineandheseNZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ—————————————————————

edacinhischairaceiedoardshesnXZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR—————————————————————61利用與上述分析類似的方法，可以很容易地確定其余密文字母和明文字母的對應關系。最后，恢復完整的明文如下：

OurfriendfromParisexaminedhisemptyglasswithsurprise，asifevaporationhadtakenplacewhilehewasn’tlooking．Ipouredsomemorewineandhesettledbackinhischair,facetilteduptowardsthesun．622.4.2維吉尼亞密碼的分析多表代換密碼從一定程度上隱藏了明文消息的一些統計特征，破譯相對較為困難；在多表代換密碼的分析中，首先要確定密鑰的長度，也就是要確定所使用的加密表格的個數，然后再分析確定具體的密鑰；確定密鑰長度的常用方法有兩種，即Kasiski測試法、重合指數法。63下面以維吉尼亞密碼為例來說明多表代換密碼的分析方法。維吉尼亞密碼的特點：用給定的m個字母表周期性地對明文字母加密；當兩個相同的明文段間隔的字母數為m的整數倍時，將加密成相同的密文段；假設密文中出現兩個相同的段落，對應的明文段不一定相同，但相同的可能性很大。64考慮下面一個維吉尼亞密碼的簡單例子：明文：ues