从CaesarCipher到VigenèreCipher凯萨密表.PPT

PART I-02 古典密碼的設計與破譯 Vigenère Cipher 從Caesar Cipher到Vigenère Cipher Vigenère Cipher 在十六世紀末，由一位法國的外交官─Blaise de Vigenère (勃雷茲?維吉尼亞)，提出了Poly-alphabetic Cipher─Vigenère Cipher 在Vigenère密表中，每一列都是Caesar密表的一種。 互通訊息的雙方透過是先約定的金鑰(Key)，決定明文用哪些列來加密。 優點：不會顯現英文單字頻率，若非真正的訊息接收者，就無法藉由「頻率分析法」推導出明文。 Vigenère Cipher 假設以「SECURE」為金鑰。 加密「JINGLE BELLS JINGLE BELLS JINGLE ALL THE WAY」。 得到密文是「BMPACITINFJNARIFVFWPNMAMFKNYRPDXJYNEQ」。 Vigenère Cipher 最大特色：能隱藏出明文中字母的頻率，改善了單套字母密碼法的缺點。 由於字母位移與金鑰相關，即使明文重複出現JINGLE BELLS，密文卻不顯露出重複的痕跡，以J為例： 當明文J遇上金鑰S，在密文中變成字母B。 當明文J遇上金鑰E，在密文中變成字母N。 當明文J遇上金鑰R，在密文中變成字母A。 Kasiski Test (卡西斯基測試) Vigenère Cipher加密法，到十九世紀才有人找出方法破譯它，這個破譯技巧被稱為Kasiski Test (卡西斯基測試)。 Vigenère Cipher是由於金鑰詞的不斷重複，使得密文可推敲出金鑰的長度而破譯，得到明文。 讓Vigenère Cipher難以破解 所以當金鑰的長度與明文一樣長，甚至比明文更長，將會增加其破譯的困難度，甚至無法被敵人破譯。 而長度長的金鑰當然也能是約定好的某本書，但是在發送接收訊息時也就必須要有金鑰本在手邊，由於是有規則性地推移字母，即使無密本也可逐字推算。 Enigma machine World War II 德國所使用 名稱源自希臘語，意指“ 不可思議的東西”或“謎” Enigma是突破性地結合機器來進行加密，使得密碼更不易被破解 基本元件與原理 其中最基本的三大部分為鍵盤、轉子和顯示器。鍵盤共有26個鍵，分別為26個英文字母，其排列接近我們現在所使用的計算機鍵盤。為了使消息盡量簡短且更難破譯，空格和標點符號都被省略。 鍵盤、轉子和顯示器由電線相連，轉子本身也集成了26條線路，把鍵盤的信號對應到顯示器不同的小燈上去，每一個字母都一一對應替換為另一個字母 。 轉子(Rotors) 當鍵盤上一個鍵被按下時，相應的密文在顯示器上顯示，轉子的方向就自動地轉動一個字母的位置。 但是如果連續鍵入26個字母，轉子就會整整轉一圈，回到原始的方向上，這時編碼就和最初重複了。 於是S先生在機器上又加了一個轉子。當第一個轉子轉動整整一圈以後，它上面有一個齒撥動第二個轉子，使得它的方向轉動一個字母的位置。用這樣的方法，要26*26=676個字母後才會重復原來的編碼。而事實上Enigma裡有三個轉子，不重複的方向個數將達到26*26*26=17576個。 反轉輪(Reflector) S先生十分巧妙地在三個轉子的一端加上了一個反轉輪，他把鍵盤和顯示器中的相同字母用電線連在一起。 反轉輪雖然沒有像轉子那樣增加可能的不重複之方向，但是它可以使解碼的過程和編碼的過程完全一樣。 反轉輪帶來的一個副作用就是一個字母永遠也不會被加密成它自己，因為反轉輪中一個字母總是被連接到另一個不同的字母，這也使它成為一個被破解的導火線。 連接板(Plug－board) S先生在鍵盤和第一轉子之間增加了一個連接板。這塊連接板允許使用者用一根連線把某個字母和另一個字母連接起來，這樣這個字母的信號在進入轉子之前就會轉變為另一個字母的信號。 種連線最多可以有六根（後期的Enigma具有更多的連線），這樣就可以使6對字母的信號互換，其他沒有插上連線的字母保持不變。當然連接板上的連線狀況也是收發訊息的雙方需要預先約定好的。 Plug-board Enigma的金鑰 三個轉子不同的方向組成了26*26*26=17576種不同可能性。 三個轉子間不同的相對位置為6種可能性。 連接板上兩兩交換6對字母的可能性數目非常巨大，有72282089880000種。 於是一共有：17576*6*72282089880000=7622580070385280000，大約為1016種可能性。 連接板與轉子對Enigma的重要 其實連接板對可能性的增加貢獻最大，那麼為什麼S先生要那麼麻煩地設計轉子之類的東西呢？原因在於連接板本身其實就是一個