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