本文轉載自果殼網，作者：吳師傅。個人覺得這篇文章寫得挺好，對于密碼不大了解的同學可以好好學習下。
信息時代，密碼無處不在了，各種密碼術也隨處可見，為愛好者們津津樂道。而在此前很長一段時間，密碼學作為一門行走在暗處的黑色藝術，一直不為大眾所知，只在少數精英間流傳。從凱撒的設計到二戰時期美日間的較量，這個關于秘密通信的歷史，精彩無比。有人設計密碼，就有人破譯密碼，在這場智與智的較量中，遺下無數經典。讓我們來了解幾個最經典的密碼，一起感受密碼學里的藝術。
凱撒密碼
引用 作為一名杰出的軍事領袖，尤里烏斯•凱撒深知指揮官對前方將領的命令對于一場戰爭的重要性，這些信息絕對不能讓敵方知道，于是他設計了一種對重要的軍事信息進行加密的方法，即使這些信息被截獲，敵方也不一定能看懂——這就是著名的凱撒密碼，也算是最早的密碼實例。
在這種密碼中，從A到W的每個字母在加密時用字母表中位于后三位的那個字母代替，字母XYZ分別被替換成ABC。凱撒在這里是將字母向右移動了三位（如下圖）。比如，在三個移位的情況下，信息DOG（這種需要加密的信息統稱“明文”）就變換成GRJ（這種經加密后產生的的信息統稱“密文”）；密文FDW對應的明文則是CAT。可以看到，加密、解密過程都是以字母移位的位數為參照的。這種在加密和解密的算法中依賴的參數則被稱為——密鑰。
引用 當然，移位的選擇并不僅僅限制在三位，從1到25任何數的移位都能產生類似效果。只要通信雙方事先約定好，這個選擇就很任意。很明顯的是，移位方法最多也只有25種，這成為凱撒密碼的致命弱點。一般情況下，窮舉25種移位方法，得到25組新編碼，必有一種編碼是真實的情報內容，由于其它24組多是是毫無意義的字母組合，所以凱撒密碼很容易就能被破譯。
但是凱撒在當時很成功的使用了這種密碼，還在《高盧戰記》中頗為得意的記錄下了這個加密設計。究其原因，只能是他的敵人并沒有意識到他在使用密碼。
改進后的加密法
引用 在凱撒密碼的缺點暴露后，有人便對它做出了改進：用一個按隨機順序排列的字母表來替代正常順序的字母表。這種簡單代換方法達26！種，這個看起來不大的數字，數量級達到了10 26 ，也就是說窮舉法破譯已經失效了。但是，這種方法并非無懈可擊，當它對一段比較長的英文信息加密時，依然容易被破譯。這是英語本身的統計特性決定的。
眾所周知，英語具有統計特性。每個字母的使用頻率不同且差別很大。一篇文章中字母出現的相對預期頻率是可以通過統計大量英語文章確定出來的。比如，英語文章中 E 的出現頻率最高，大約是 12.7% 這樣子；而 J 的出現頻率最低，只有 0.1% 左右。當使用上述的簡單代換密碼時，字母表中特定字母總是被同一個字母代替，導致密文中字母出現的頻率也會出現同樣的不平衡性，再加上破譯者對發密方背景的了解，要確定密文中包含的信息依然不是一件困難的事。
一個好的解決辦法是用多個密文符號來表示同一個字母。每個字母有不同數量的的密文符號替代，替代者的數量與每個字母在英語統計中的頻率成正比。例如，字母 a 在書面英語大約占 8% 的比例，所以我們可以分配8個符號來表示它。明文中出現的字母 a 在密文中可以被這8個符號中任一個替換。這樣一來，每個符號在密文中的頻率都在 1% 左右。類似處理所有英文字母。這樣設計出的一套字母替換表，打亂了密文中的英語統計特性。但由于每個密文符號只代表唯一的明文符號，也會帶來風險：對于一個給定的密鑰，破譯者能匯編出一部已知的明文與密文相對應的詞典。
好幾個世紀以來，上述的幾種加密法保證信息了的安全。不過自從頻度分析這種方法被引進到歐洲后，密碼破譯者終于占據了上風。蘇格蘭瑪麗女王的悲劇充分詮釋了這種密碼的弱點。
“不可破譯”的密碼引用 1586年，英國政府破譯了蘇格蘭瑪麗女王和同黨謀反的密信，瑪麗女王慘遭吊死。而她使用的就是字母替換這種單碼加密法。這個事件也正式宣告上述密碼已經全部失效。
同年，一位名叫維熱納爾的法國外交家出版了一本《密碼理論》，介紹一種以他自己名字命名的新密碼，而這本書一直無人問津。直到兩百年后莫爾斯電碼流行開來，為了防止電報員泄露信息和間諜窺探秘密，維熱納爾密碼才被廣泛應用。
維熱納爾密碼一度被認為是無法破譯的，以致讓一些掌握這種密碼的人洋洋自喜，不過很快，以建立了現代計算機的理論框架而聞名于世的怪才查爾斯•巴貝奇解決了這個難題。
事情起源于一個布里斯托爾的一個牙醫賽瓦特。這個牙醫其實對密碼學知之甚少，1854年，他聲稱發明了一種新密碼，并寫信給《藝術協會雜志》企圖獲取專利。而他只不過是將維熱納爾密碼重新包裝了而已。巴貝奇寫信揭露這個事實，賽維特卻不愿承認，甚至為難巴貝奇讓他破解這個密碼。其實能否破解密碼和密碼是不是新創造的毫無關系，但這已足以激起巴貝奇的好奇心了。很快，他就成功破解了維熱納爾密碼。
對于這樣重要的成果，巴貝奇卻沒有發表它。這也符合他的性格：他一直是這種懶洋洋的態度。而更重要的原因恐怕是英國政府要求巴貝奇保密，從而讓他們可以在這方面領先全世界9年——直到1863年卡西斯基也發現了破譯方法并將它發表。
有趣的是，在美國的南北戰爭期間，南方聯軍仍然在使用黃銅密碼盤生成維熱納爾密碼，自始至終都只主要使用三個密鑰，而那個時候這密碼早就被破譯了，所以北方政府在情報戰上一直是笑而不語的。
維熱納爾密碼的原理
維熱納爾密碼又叫做維吉尼亞密碼。它的加密過程是這樣的：首先選擇一個無重復字母的密鑰詞（比如 MATH ），重復密鑰詞直至它成為一個和明文信息一樣長的字母序列，再利用下面這種方陣加密這條信息。為加密第一個字母 I，此時它下方對應的密鑰詞是 M，于是，加密 I 時由 M 對應的那行中讀出 i 列下的字母即 U，類似的，得出所有密文：
| 信息 | I | L | O | V | E | Y | O | U | | 密匙 | M | A | T | H | M | A | T | H | | 密文 | U | L | H | C | Q | Y | H | B |
這無疑是一種高明的加密手段，維熱納爾密碼用嚴格的輪換方式重復使用一串簡單的代換密碼，很好的偽裝了基礎語言中的字母頻率。它還有很多變化，比如有一種可以允許密鑰詞中出現重復字母。每種變化都會產生一些新的特征，從而引發破譯方式的變化。
查爾斯•巴貝奇是破譯維熱納爾密碼的第一人，他的思路是：在已知密碼周期（即所使用的密碼組件數目，顯然，上述版本的維熱納爾密碼周期就是密鑰詞長度）為 p 的情況下，將密文改寫成 p 行，使得每一列按原來的密文順序排列，例如，p=3，密文 c1c2c3c4c5c6c7c8c9… 就排列成：
c1 c4 c7…
c2 c5 c8…
c3 c6 c9…
這樣排列后，每行都是使用同一簡單代換密碼所得出的，如此就可以對每一行都使用上一節提到過的統計分析了。事實上，對每一行而言，這種簡單的代換密碼正是凱撒密碼。
所以對于維熱納爾密碼的破譯者來說，關鍵就在于確定周期 p，巴貝奇則用了一種精巧的方法：在密文中搜索重復的字符串，它意味著兩個重復模式之間的距離可能等于周期的整數倍！
難題又被破解！再一次，密碼編譯者開始尋找新的方法，繼續這場智的較量。 | 
