維吉尼亞密碼
維吉尼亞密碼（法語：Chiffre de Vigenère，又譯維熱納爾密碼）是使用一系列凱撒密碼組成密碼字母表的加密算法，屬於多表密碼的一種簡單形式。
維吉尼亞密碼曾多次被發明。該方法最早記錄在吉奧萬·巴蒂斯塔·貝拉索（ Giovan Battista Bellaso）於1553年所著的書《吉奧萬·巴蒂斯塔·貝拉索先生的密碼》（意大利語：La cifra del. Sig. Giovan Battista Bellaso）中。然而，後來在19世紀時被誤傳為是法國外交官布萊斯·德·維吉尼亞（Blaise De Vigenère）所創造，因此現在被稱為「維吉尼亞密碼」。
維吉尼亞密碼以其簡單易用而著稱，同時初學者通常難以破解，因而又被稱為「不可破譯的密碼」（法語：le chiffre indéchiffrable）。這也讓很多人使用維吉尼亞密碼來加密的目的就是為了將其破解。[1]
歷史[編輯]
多表密碼最早在1467年左右由意大利文藝復興時期的建築師、哲學家、密碼學家萊昂·巴蒂斯塔·阿爾伯蒂提出，他使用了一個金屬密碼盤來切換密碼表，只是這個系統只能做些有限的轉換。後來1508年時，德國的修道士、鍊金術師、密碼學家約翰尼斯·特里特米烏斯《隱寫術》（Steganographia）中發明的表格法（tabula recta）成為了維吉尼亞密碼的關鍵部分。然而當時此方法只能對密碼表做一些簡單的、可預測的切換。這一加密技術也稱為特里特米烏斯密碼。
這一方法真正出現是在吉奧萬·巴蒂斯塔·貝拉索於1553年所著的書《吉奧萬·巴蒂斯塔·貝拉索先生的算術》中。他以特里特米烏斯的表格法為基礎，同時引入了密鑰的概念。
布萊斯·德·維吉尼亞於1586年亨利三世時期發明了更為簡單卻又更有效的自動密鑰密碼（autokey cipher）。之後，19世紀時貝拉索的方法被誤認為是由維吉尼亞首先發明的。大衛·卡恩在《破譯者（The Codebreakers）》中對此表示遺憾，他寫道「歷史忽略了這一重要貢獻，將其歸功於維吉尼亞，雖然他對此並不知道」。[2]
由於破譯的難度很高，維吉尼亞密碼也因此獲得了很高的聲望。知名作家、數學家查爾斯·路特維奇·道奇森（筆名路易斯·卡羅）在其1868年所編、收於一兒童雜誌的《字母表密碼（The Alphabet Cipher）》中稱其是不可破譯的。1917年，《科學美國人》將維吉尼亞密碼稱為「無法被轉化的」。[3]然而，維吉尼亞密碼卻配不上這樣的稱號。查爾斯·巴貝奇完成了破譯的工作，但他沒有將此發表。[4]之後，弗里德里希·卡西斯基（Friedrich Kasiski）於19世紀完全破解並發表了他的方法。甚至在此之前，一些資深密碼分析家在16世紀就能偶爾將其破解。[2]
維吉尼亞密碼足夠地易於使用使其能夠作為戰地密碼。[5]例如，美國南北戰爭期間南軍就使用黃銅密碼盤生成維吉尼亞密碼。北軍則經常能夠破譯南軍的密碼。戰爭自始至終，南軍主要使用三個密鑰，分別為「Manchester Bluff（曼徹斯特的虛張聲勢）」、「Complete Victory（完全的勝利）」以及戰爭後期的「Come Retribution（報應來臨）」。
吉爾伯特·維爾南（Gilbert Vernam）曾試圖對已被破譯的密碼進行修補（於1918年創造了維爾南-維吉尼亞密碼），然而這終究無濟於事。不過維爾南的發明最終促成了一次性密碼本的誕生，這是一種理論上不可破譯的密碼。
描述[編輯]
在一個凱撒密碼中，字母表中的每一字母都會作一定的偏移，例如偏移量為3時，A就轉換為了D、B轉換為了E……而維吉尼亞密碼則是由一些偏移量不同的凱撒密碼組成。
為了生成密碼，需要使用表格法。這一表格包括了26行字母表，每一行都由前一行向左偏移一位得到。具體使用哪一行字母表進行編譯是基於密鑰進行的，在過程中會不斷地變換。
例如，假設明文為：
ATTACKATDAWN
選擇某一關鍵詞並重複而得到密鑰，如關鍵詞為LEMON時，密鑰為：
LEMONLEMONLE
對於明文的第一個字母A，對應密鑰的第一個字母L，於是使用表格中L行字母表進行加密，得到密文第一個字母L。類似地，明文第二個字母為T，在表格中使用對應的E行進行加密，得到密文第二個字母X。以此類推，可以得到：
明文：ATTACKATDAWN 密鑰：LEMONLEMONLE 密文：LXFOPVEFRNHR
解密的過程則與加密相反。例如：根據密鑰第一個字母L所對應的L行字母表，發現密文第一個字母L位於A列，因而明文第一個字母為A。密鑰第二個字母E對應E行字母表，而密文第二個字母X位於此行T列，因而明文第二個字母為T。以此類推便可得到明文。
用數字0-25代替字母A-Z，維吉尼亞密碼的加密文法可以寫成同餘的形式：
解密方法則能寫成：
密碼破譯[編輯]
對包括維吉尼亞密碼在內的所有多表密碼的破譯都是以字母頻率為基礎的，但直接的頻率分析卻並不適用。例如，如果P是密文中出現次數最多的字母，則P很有可能對應E（前提是明文的語言為英語）。原因在於E是英語中使用頻率最高的字母。然而，由於在維吉尼亞密碼中，E可以被加密成不同的密文，因而簡單的頻率分析在這裏並沒有用。
破譯維吉尼亞密碼的關鍵在於它的密鑰是循環重複的。如果我們知道了密鑰的長度，那密文就可以被看作是交織在一起的凱撒密碼，而其中每一個都可以單獨破解。使用卡西斯基試驗和弗里德曼試驗來得到密鑰的長度。
卡西斯基試驗[編輯]
弗里德里希·卡西斯基於1863年首先發表了完整的維吉尼亞密碼的破譯方法，稱為卡西斯基試驗（Kasiski examination）。早先的一些破譯都是基於對於明文的認識、或者使用可識別的詞語作為密鑰。而卡西斯基的方法則沒有這些限制。然而，在此之前，已經有人意識到了這一方法。1854年，英國數學家、發明家兼機械工程師查爾斯·巴貝奇受到斯維提斯（John Hall Brock Thwaites）在《藝術協會雜誌》（Journal of the Society of the Arts）上聲稱發明了「新密碼」的激勵，從而破譯了維吉尼亞密碼。巴貝奇發現斯維提斯的密碼只不過是維吉尼亞密碼的一個變種而已，而斯維提斯則向其挑戰，讓他嘗試破譯用兩個不同長度的密鑰加密的密文。巴貝奇成功地進行了破譯，得到的明文是丁尼生所寫的詩《罪惡的想像》（The Vision of Sin），使用的密鑰則是丁尼生妻子的名字Emily（艾米莉）。巴貝奇從未對他的方法進行過解釋 。在對巴貝奇生前筆記的研究中發現，早在1846年巴貝奇就使用了這一方法，與後來卡西斯基發表的方法相同。[6]
卡西斯基試驗是基於類似the這樣的常用單詞有可能被同樣的密鑰字母進行加密，從而在密文中重複出現。例如，明文中不同的CRYPTO可能被密鑰ABCDEF加密成不同的密文：
密鑰：ABCDEF AB CDEFA BCD EFABCDEFABCD 明文：CRYPTO IS SHORT FOR CRYPTOGRAPHY 密文：CSASXT IT UKSWT GQU GWYQVRKWAQJB
此時明文中重複的元素在密文中並不重複。然而，如果密鑰相同的話，結果可能便為（使用密鑰ABCD）：
密鑰：ABCDAB CD ABCDA BCD ABCDABCDABCD 明文：CRYPTO IS SHORT FOR CRYPTOGRAPHY 密文：CSASTP KV SIQUT GQU CSASTPIUAQJB
此時卡西斯基試驗就能產生效果。對於更長的段落此方法更為有效，因為通常密文中重複的片段會更多。如通過下面的密文就能破譯出密鑰的長度：
密文：DYDUXRMHTVDVNQDQNWDYDUXRMHARTJGWNQD
其中，兩個DYDUXRMH的出現相隔了18個字母。因此，可以假定密鑰的長度是18的約數，即長度為18、9、6、3或2。而兩個NQD則相距20個字母，意味着密鑰長度應為20、10、5、4或2。取兩者的交集，則可以基本確定密鑰長度為2。
弗里德曼試驗[編輯]
弗里德曼試驗由威廉·F·弗里德曼（William F. Friedman）於1920年代發明。他使用了重合指數（index of coincidence）來描述密文字母頻率的不勻性，從而破譯密碼。指目標語言中兩個任意字母相同的概率（英文中為0.067），指字母表中這種情況出現的概率（英文中為1/26=0.0385），從而密鑰長度可以估計為：
其中，觀察概率為
其中，c是指字母表的長度（英文為26），N指文本的長度，n1到nc是指密文的字母頻率，為整數。
此方法只是一種估計，會隨着文本長度的增加而更為精確。在實踐中，會嘗試接近此估計的多個密鑰長度。[7] 一種更好的方法是將密文寫成矩陣形式，其中列數與假定的密鑰長度一致，將每一列的重合指數單獨計算，並求得平均重合指數。對於所有可能的密鑰長度，平均重合指數最高的最有可能是真正的密鑰長度。[8] 這樣的試驗可以作為卡西斯基試驗的補充。
頻率分析[編輯]
一旦能夠確定密鑰的長度，密文就能重新寫成多列，列數與密鑰長度對應。這樣每一列其實就是一個凱撒密碼，而此密碼的密鑰（偏移量）則對應於維吉尼亞密碼密鑰的相應字母。與破譯凱撒密碼類似的方法，就能將密文破譯。
柯克霍夫方法作為卡西斯基試驗的改進，由奧古斯特·柯克霍夫（Auguste Kerckhoffs）提出。它將每一列的字母頻率與轉換後的明文頻率相對應而得出每一列的密鑰字母。一旦密鑰中每一個字母都能確定，就能很簡單地破譯密文，從而得到明文。如果維吉尼亞字母表表格本身是雜亂而非按通常字母表順序的話，那柯克霍夫方法就會無效，但卡西斯基試驗和重複指數對於決定密鑰長度仍舊是有效的。
變體[編輯]
維吉尼亞密碼的變體滾動密鑰密碼也曾一度被認為是不可破譯的。這種變體的密鑰與密文的長度一致，因此卡西斯基試驗和弗里德曼試驗即變得無效。1920年，弗里德曼首先發現了此方法的弱點。由於滾動密鑰密碼的密鑰是一段真實的語言，因而破譯者便能了解密鑰文本的統計信息，而這種信息也會反映到密文當中。
如果密鑰是完全隨機、與明文的長度一致且只使用過一次，維吉尼亞密碼理論上是不可破譯的。然而，這種情況下密鑰本身而非密文便成了關鍵，這被稱為一次性密碼本。
維吉尼亞本人確實發明了一種更強的維吉尼亞密碼變體——自動密鑰密碼。巴貝奇所破譯的其實是這種自動密鑰密碼，而卡西斯基則通常被認為是首先發表了破譯固定密鑰多表密碼的方法。
還有一種簡單的變體使用維吉尼亞的解碼方法進行加密，同時使用維吉尼亞的加密方法進行解密，這被稱為變異博福特密碼。此方法與弗朗西斯·博福特創造的博福特密碼不同，後者雖然也與維吉尼亞密碼相似，但使用了修改過的加密方式和表格，是一種對等加密。
維吉尼亞密碼表面上的強度並沒能使其在歐洲得到廣泛使用。由Gronsfeld伯爵所創造的Gronsfeld密碼基本與維吉尼亞密碼相同，不過它只使用10個不同的密碼字母表（對應字母0到9）。Gronsfeld密碼的強度很高，這是因為它的密鑰並不是一個單詞，但缺點在於字母表數量過少。儘管如此，Gronsfeld密碼仍在德國和整個歐洲有着廣泛的應用。
參考文獻[編輯]
- ^ Smith, Laurence D. Substitution Ciphers. Cryptography the Science of Secret Writing: The Science of Secret Writing. Dover Publications. 1943: 81. ISBN 048620247X.
- ^ 2.0 2.1 David, Kahn. On the Origin of a Species. The Codebreakers: The Story of Secret Writing. Simon & Schuster. 1999. ISBN 0684831309.
- ^ Knudsen, Lars R. Block Ciphers—a survey. Bart Preneel and Vincent Rijmen (編). State of the Art in Applied Cryptography: Course on Computer Security and Industrial Cryptograph Leuven Belgium, June 1997 Revised Lectures. Berlin ; London: Springer. 1998: 29. ISBN 3540654747.
- ^ Singh, Simon. Chapter 2: Le Chiffre Indéchiffrable. The Code Book. Anchor Books, Random House. 1999: 63–78. ISBN 0-385-49532-3.
- ^ Codes, Ciphers, & Codebreaking （頁面存檔備份，存於互聯網檔案館）（The Rise Of Field Ciphers）
- ^ Franksen, O. I. 1985 Mr. Babbage's Secret: the Tale of a Cipher-And APL. Prentice Hall
- ^ Henk C.A. van Tilborg (編). Encyclopedia of Cryptography and Security First. Springer. 2005: 115. ISBN 038723473X.
- ^ Mountjoy, Marjorie. The Bar Statistics. NSA Technical Journal. 1963, VII (2,4). Published in two parts.
參見[編輯]
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
