巴貝奇對維吉尼亞密碼

19世紀密碼分析界最引人矚目的人物是查理·巴貝奇（Charles Babbage），這位英國怪才最聞名的成就是研發了現代計算機的先驅。他出生于1791年，是富有的倫敦銀行家班杰明·巴貝奇（Benjamin Babbage）的兒子。查理的婚事未得到他父親的贊同，因而與巴貝奇的財產絕緣，但他仍有足夠的金錢，不至于有財務問題。他喜歡過流浪學者的生涯，把心思用在任何能激發他奇想的問題上。他的發明包括速度計和捉牛器。捉牛器是一種固定在蒸氣火車頭上的裝置，用于驅除鐵軌上的牛只。若講到科學性的突破，他是第一位發現樹的年輪寬度跟氣候有關的人，并進而推論，研究古樹可以推斷出以前的氣候。他對統計學也很有興趣，消遣之際畫出一套死亡率統計表，是現今保險業的基本工具。

巴貝奇不自限于處理科學和工程的問題。以往郵資是依信件的運送距離來計費的，巴貝奇卻指出，計算每封信的價格所需的人力成本比郵資成本還高。因此，他提議了這套我們今日仍在使用的系統——所有信件不論收信地址在國內何處，都收取相同的郵資。他也對政治、社會問題有興趣，晚年時發起清除在倫敦游蕩的手風琴手和街頭音樂家的運動。他抱怨這些音樂“時常使得破破爛爛的頑童，有時甚至使得半醉的男人跳起舞來，那些醉漢偶爾還用他們不和諧的聲音來應和這些噪音。另一個大力支持街頭音樂的階級，是那些道德標準伸縮自如且有四海一家主義傾向的淑女們，這些音樂提供她們一個體面的借口，得以敞開窗戶，展示她們的魅力”。結果，這些音樂家反倒在他家門前聚集了大批人群，盡其所能地大聲演奏，以示反擊。

巴貝奇的科學生涯在1821年出現了轉折點，當時他和天文學家約翰·赫謝爾（John Herschel）檢查一組數學表格，那種用于天文學、工程和航海計算的表格。這些表格有很多錯誤，讓這兩個人不勝其煩，因為這些錯誤會使一些重要的計算產生誤差。其中一張“在海上確定緯度和經度的航海星象表”（Nautical Ephemeris for Finding Latitude and Longitude at Sea），有一千個以上的錯誤。很多船難和工程災難的確得歸咎于表格的數據錯誤。

這些數學表格是用手計算出來的，這些錯誤純粹是人為錯誤。巴貝奇因而大叫：“老天，我真希望這些計算是利用蒸氣執行的！”他隨之投注下大把的心力，矢志建立一臺可以無誤地計算出高精度數字的機器。1823年，巴貝奇設計出“差分機一號”（Difference Engine No.1），一部包含兩萬五千個精密零件、很是壯觀的計算器，這部機器將由政府出資制造。巴貝奇是才氣縱橫的創新者，卻不是個挺好的實踐家。辛勤工作十年后，他放棄“差分機一號”，重新提出一份全新的設計，開始著手制造“差分機二號”（Difference Engine No.2）。

巴貝奇放棄他的第一臺機器時，政府對他失去信心，決定從這項計劃抽身，以減少損失——這計劃已經花掉17,470英鎊，足以建造兩艘戰艦了。大概就是這撤回資助的舉動讓巴貝奇后來發出如下的牢騷：“向英國人提議一項原理或一套儀器，不管有多宏偉，你都會發現他們的心思全放在找出它的困難、缺陷或不可能性。如果你跟他談削馬鈴薯機，他會說那是不可能的。你在他面前用這機器削顆馬鈴薯給他看，他又會說這個玩意沒啥用處，因為它不能切菠蘿。”

沒有政府的資助，巴貝奇也就沒能完成差分機二號。這實在是科學界的一大悲劇。巴貝奇的機器已具備程序設計的特征。成功的話，差分機二號不僅能計算一些特定的表格，還能根據指令解決各種數學問題。事實上，差分機二號提供了一套現代計算機的藍本。他的設計包括一個“倉庫”（內存）和“磨坊”（處理器），讓它可以做決策及重復執行指令，相當于現代程序語言的“if...then...”和“loop”指令。

一個世紀后，在第二次世界大戰期間，第一代實現巴貝奇設計的電子設備對密碼分析學有深切的影響。事實上，巴貝奇在他有生之年，對破解密碼的知識也有著同等重要的貢獻：他成功破解了維吉尼亞密碼，這是自9世紀的阿拉伯學者發明頻率分析法破解單套字母密碼法以來，密碼分析學上最偉大的突破。巴貝奇的杰作不需要機械的計算或復雜的運算。他所用到的，不過是那顆靈活的腦袋。

巴貝奇年紀輕輕時，就對密碼產生興趣。他后來回憶道，童年時的嗜好常給他惹上麻煩：“那些大男孩造了一些密碼。通常我只要得到幾個，就能找出鑰匙。展現這巧妙本領的后果有時并不好受：有些密碼的主人會揍我一頓，盡管這該怪他們自己太蠢。”這些痛打并未使他退卻，巴貝奇依舊對分析密碼非常著迷。他在自傳里寫道：“我認為，解譯密碼是最迷人的技藝之一。”

他那密碼分析家的名聲，很快就在倫敦的社交界建立起來，人人都知道他樂于對付任何加密信息，常有陌生人帶著各種問題來找他。例如有位傳記作家無法判讀英國第一任皇家天文學家約翰·弗蘭斯蒂德（John Flamsteed）的速記筆記，絕望之際，獲得巴貝奇的協助。他也協助了一位歷史學者破解查理一世（Charles I）的妻子亨麗葉塔·瑪麗亞（Henrietta Maria）的密碼。1854年，他和一位律師合作，利用密碼分析法揭出一件訴訟案的關鍵證據。長年下來，巴貝奇收集了一大沓厚厚的密碼文件，打算以此為基礎，寫一本堪稱密碼分析學權威的書籍，標題擬為《密碼解譯的哲學》（The Philosophy of Decyphering）。他計劃在此書為每一種密碼法列舉兩個例子，一個由他來示范破解方法，另一個則留給讀者練習解譯。可惜，就如他許多其他宏偉的計劃，這本書從未完成。

正當大部分的密碼分析家已經放棄破解維吉尼亞密碼法的希望時，巴貝奇卻在跟約翰·霍爾·布洛克·斯維特斯（John Hall Brock Thwaites）信件往來之際，興起嘗試破解它的念頭。斯維特斯是來自布里斯托爾（Bristol）的牙醫，對密碼術的發展相當無知。1854年，他宣稱發明了一種新的密碼法，其實正是維吉尼亞密碼法。他顯然不知道自己晚了好幾個世紀，還去信《技術學會期刊》（Journal of the Society of Arts），要為他的主意申請專利。巴貝奇寫信給這個學會，指出：“這個密碼法……歷史非常悠久了，大多數書籍都有提到它。”斯維特斯不認錯，并挑戰巴貝奇破解他的密碼。它能否被破解，跟它是不是新的密碼法，當然是兩回事。不過，巴貝奇倒真的被勾起好奇心，開始著手尋找維吉尼亞密碼法的弱點。

破解困難的密碼，猶如攀爬一面峭立的斷崖。密碼分析家會尋找任何能讓他攀抓的角落或裂縫。在單套字母密碼法里，密碼分析家緊緊抓住字母的頻率，因為最常用的字母，如e、t、a，不管怎么掩飾，都會突顯出來。使用多套字母集的維吉尼亞密碼法，把這些頻率掩飾得均衡多了，因為它使用鑰匙單詞在數套密碼字母之間輪換。所以乍看之下，這片巖面光滑無比，根本沒有可以攀附或落腳的地方。

別忘了，維吉尼亞密碼法之所以難以破解是因為同一個字母有數種加密方法。舉例來說，如果鑰匙單詞是KING，那么明文的每個字母就都有四種可能的加密方式，因為這個鑰匙單詞含有四個字母，而每個字母都代表維吉尼亞方格內的一列密碼字母，如表7所示。標示出方格里e這一直欄后，你可以看到，僅僅考慮輪到以鑰匙單詞的哪個字母來指定密碼字母集，e有以下四種加密可能性：

 

如果用KING的K來加密e，就會產生密碼字母O。

如果用KING的I來加密e，就會產生密碼字母M。

如果用KING的N來加密e，就會產生密碼字母R。

如果用KING的G來加密e，就會產生密碼字母K。

 

同樣地，單詞本身也會有不同的加密可能性。例如，the這個單詞就可能加密成DPR、BUK、GNO或ZRM，僅僅考慮它跟這個鑰匙單詞的相對位置而定。這會使密碼分析工作變得很困難，但并非絕不可能成功。需注意的重點是，如果the這個單詞只有四種加密可能性，而且原始文件用了數次the這個單詞，這四個加密可能性的其中幾個可能會在密碼文里重復出現。例如，假設我們用維吉尼亞密碼法，以KING當鑰匙單詞，加密The Sun and the Man in the Moon（太陽及月亮上的人）這一行單詞，結果如下：

the這個單詞第一次被加密成DPR，第二次和第三次則都加密成BUK。BUK之所以會重復，是因為從第二個the前綴算起，一直到第三個the出現以前，共有八個字母，而八是這個鑰匙單詞長度（四）的倍數。換句話說，第二個the是根據鑰匙單詞中的ING三個字母來選擇密碼字母集，當我們加密到第三個the時，這個鑰匙單詞剛好循環了兩次，于是和第二個the一樣，仍是根據ING來選擇密碼字母集，所以得到的密碼也就相同了。

巴貝奇發現，這種重復性正是他征服維吉尼亞密碼所需的立足點。他定出一些相當簡單的步驟，讓任何密碼分析家只要依循這些要領，即可破解這個到當時為止仍“無法破解的密碼”。我們且試著依巴貝奇的方法來解譯如圖13所示的密碼文，便能了解他高超的技巧。現在，我們只知道它是用維吉尼亞密碼法加密的，但不知道它的鑰匙單詞是什么。

巴貝奇分析法的第一步驟是尋找出現兩次以上的字符串。有兩種情況可能出現重復的密碼文字符串。最可能的情況是，同樣的明文字符串用了鑰匙單詞的相同部分加密。另一種可能性頗低的情況是，不同的明文字符串用了鑰匙單詞的不同部分加密，卻巧合地產生一模一樣的密碼文字符串。我們若把尋找目標限定于較長的字符串，第二種可能性的出現就會大打折扣。在本例，我們只考慮四個字母以上的字符串。表8記錄了這類重復的字符串以及重復字符串之間的間隔值。例如，字符串E-F-I-Q先是出現在這段密碼文的第一行，后來又出現在第五行，向前挪動了95位。

鑰匙單詞既定義明文加密的程序，也是收信人把密碼文還原成明文的依據。因此只要能判定出鑰匙單詞，這段文字很容易就能解譯出來了。在這個階段，我們的信息還不足以解出鑰匙單詞，不過表8提供了很有用的線索，讓我們可以判斷鑰匙單詞的長度。表8的左邊兩欄列出重復出現的字符串和重復的間隔值，右邊各欄列出這些間隔值的因子，亦即可以整除這些間隔值的數字。例如，字串W-C-X-Y-M在20個字母后再度出現，它的因子就是1、2、4、5、10和20，因為這些數字可以整除20，而不留下余數。這些因子提示出六種可能性：

1．這把鑰匙的長度是1個字母，在第一個W-C-X-Y-M字符串和第二個W-C-X-Y-M之間循環了20次。

2．這把鑰匙的長度是2個字母，在兩段字符串間循環了10次。

3．這把鑰匙的長度是4個字母，在兩段字符串間循環了5次。

4．這把鑰匙的長度是5個字母，在兩段字符串間循環了4次。

5．這把鑰匙的長度是10個字母，在兩段字符串間循環了2次。

6．這把鑰匙的長度是20個字母，在兩段字符串間循環了1次。

 

第一個可能性可以馬上排除，因為使用一把長度只有1個字母的鑰匙形同使用單套字母密碼法——整個加密過程只用到維吉尼亞方格中的某一列密碼字母，從頭到尾都不更換密碼字母。編碼者不太可能做這種事。在表8中，我們在適當字段加上v記號，以標出每種可能的鑰匙長度。

欲判定鑰匙長度是2、4、5、10或20個字母，我們必須檢視所有其他間隔值的因子。因為鑰匙字長度似乎小于20個字母，所以表8只列出每個間隔值介于1到20之間的因子。我們看到，這些間隔值傾向為5的倍數。事實上，每個間隔值都可以被5整除。我們可以將第一個重復字符串E-F-I-Q的重復情形解釋成，一個長度為5個字母的鑰匙單詞，在第一次和第二次加密這個字符串之間循環了19次。第二個重復字符串P-S-D-L-P可以解釋成，長度為5的鑰匙單詞，在第一次和第二次之間只循環了1次。第三個重復字符串W-C-X-Y-M可以解釋成，長度為5的鑰匙單詞，在第一次和第二次之間循環了4次。第四個重復字符串E-T-R-L可以解釋成，長度為5的鑰匙單詞，在第一次和第二次之間循環了24次。簡而言之，鑰匙字長度為5個字母的假設，可以符合所有情形。

假定這個鑰匙單詞的長度真的是五個字母，下一個步驟即是找出這個鑰匙單詞的組成分子。我們暫且把這個鑰匙單詞稱為L1-L2-L3-L4-L5, L1代表第一個字母，L2代表第二個字母，以此類推。加密信息時，第一步一定是根據鑰匙單詞的第一個字母L1來加密明文的第一個字母。字母L1指定了某一行維吉尼亞方格的密碼字母，相當于以單套字母替代法加密明文的第一個字母。當加密第二個明文字母時，編碼者則是以字母L2來指定另一行維吉尼亞方格的密碼字母，相當于用另一套密碼字母來進行單套字母替代法的加密。同理，明文的第三個字母會根據L3來加密，第四個根據L4，第五個根據L5。鑰匙字的每個字母都指定一套互異的密碼字母集。然而，明文的第六個字母則又根據L1來加密，明文的第七個字母又再根據L2，如此一直循環下去。換句話說，這一個多套字母密碼法是由五個單套字母密碼法所組成，每一個單套字母密碼法分別負責加密整則信息的五分之一，而更重要的是，我們已經知道如何破解單套字母密碼法了。

我們繼續進行如下的分析。我們知道，由L1所指定的某一行維吉尼亞方格的密碼字母，是被用來加密明文的第1、6、11、16、……個字母。因此，如果檢視密碼文的第1、6、11、16、……個字母，就可以運用老式的頻率分析法來找出這一套密碼字母集。圖14是密碼文的第1、6、11、16……個字母（亦即W、I、R、E、……）的出現頻率分布圖。在此，別忘了，維吉尼亞方格的每一套密碼字母集都只是標準字母集挪移了1至26位罷了。所以，圖14的頻率分布圖形，除了平移一段距離外，應該會跟標準字母集的頻率分布圖形很相似。比較L1的分布圖與標準字母集的分布圖，應該可以判定出挪移位數。圖15是一段英文明文的標準字母頻率分布圖。

標準分布圖會有高峰、平原和山谷，拿來跟L1的分布圖比對時，我們要尋找最明顯的地貌。例如，標準分布圖（圖15）中由R-S-T三個直條所形成的山峰，和接下來U到Z六個字母所形成的一大片洼地，構成非常獨特的地貌。在L1的分布圖（圖14），唯一較相近的地形是V-W-X這三個高高的直條以及隨后從Y到D伸展了六個字母長的洼地。這表示，根據L1所加密的所有字母可能都向后移了四位，也就是說，L1所指定的密碼字母集是E、F、G、H……反推回來，鑰匙單詞的第一個字母L1很可能是E。要檢驗這個假設，我們可以把L1的分布圖向前平移四位，再來跟標準分布圖比較。圖16并列這兩張分布圖以供比較。兩張圖的主要高峰非常相符，表示我們的假設很可靠，鑰匙單詞的第一個字母應該就是E。

歸納一下要點：我們首先尋找密碼文里的重復字符串，以判定鑰匙單詞的長度——得到的答案是五個字母長。根據這個答案，我們把密碼文分成五組，每一組都是根據鑰匙單詞其中某個字母所指定的單套字母密碼法加密的。分析根據鑰匙單詞第一個字母所加密的密碼文片段后，我們推論出字母L1很可能是E。我們必須重復這個步驟，以判定鑰匙單詞的第二個字母。圖17所繪出的，是密碼文的第2、7、12、17……個字母的頻率分布圖，將與標準分布圖比對，以推定它的平移位數。

這個分布圖比較難分析。它沒有明顯的三個相鄰高峰來對應R-S-T。不過從G延展到L的洼地非常明顯，很可能可以對應到標準分布圖中從U到Z的洼地。若是如此，R-S-T高峰應該會出現在D、E、F，可是E卻不是高峰。我們可以暫且假設這個少掉的高峰是統計瑕疵，跟隨初步反應，推定G到L這個凹陷區域是可供辨識平移位數的特征。這表示，根據L2所加密的字母可能都向后挪了12位，也就是說，L2所指定的密碼字母集是M、N、O、P……而鑰匙單詞的第二個字母L2很可能就是M。為了檢驗這個假設，我們可以再次把L2的分布圖往前平移12位，來跟標準分布圖比較。圖18并列這兩張分布圖以供比較。兩張圖的主要高峰非常相符，表示我們的假設很可靠，鑰匙單詞的第二個字母應該就是M。

我不再累述后面的分析過程，直接說明結論：分析第3、8、13、18、……等字母的結果暗示，鑰匙單詞的第三個字母是I；分析第4、9、14、19、……等字母的結果暗示，鑰匙單詞的第四個字母是L；分析第5、10、15、20、……等字母的結果暗示，鑰匙單詞的第五個字母是Y。這個鑰匙單詞是EMILY。現在，我們可以逆向運用維吉尼亞密碼法，完成這項分析工作。密碼文的第一個字母是w，它是根據鑰匙單詞的第一個字母E加密的。反推回去，到維吉尼亞方格以E開頭的那一行找到W，再往上查看這一直欄最上面的字母是什么。它是s，所以本篇文字的第一個字母就是s。重復這個步驟，即可得出如下的明文：sittheedownandhave noshamecheekbyjowl……插入適當的空格與標點符號，最終得到：

 

Sit thee down, and have no shame,

Cheek by jowl, and knee by knee:

What care I for any name?

What for order or degree?

 

Let me screw thee up a peg:

Let me loose thy tongue with wine:

Callest thou that thing a leg ？

Which is thinnest? thine or mine ？

 

Thou shalt not be saved by works:

Thou hast been a sinner too:

Ruined trunks on withered forks,

Empty scarecrows, I and you!

 

Fill the cup, and fill the can:

Have a rouse before the mom:

Every moment dies a man,

Every moment one is bom.

 

這是阿爾弗雷德·丁尼生（Alfred Tennyson,1809年～1892年）標題為《罪惡狂想曲》（The Vision of Sin）的詩句。鑰匙單詞正是丁尼生的妻子愛米莉·塞伍德（Emily Sellwood）的名字。我摘取這首詩來當密碼分析的例子，是因為巴貝奇和這位大詩人對這首詩有一段古怪有趣的討論。身為敏銳的統計學者，又是死亡率統計表的編纂者，巴貝奇對原文的最后兩行“Every moment dies a man, Every moment one is born”（每當一人逝去，同時亦有一人誕生）頗有微詞。他建議丁尼生修正一下這首“否則，倒是很漂亮”的詩：

 

很明顯地，若真如此，這個世界的人口數就會靜止不變了……我想建議你，這首詩再版時，把它改成”Every moment dies a man, Every moment 1 1/16 is born……確實數值太長，一行放不進去，不過我相信1又1/16這個數值對詩作而言夠精確了。

查理·巴貝奇 敬上

 

巴貝奇大概是在1854年，跟斯維特斯發生爭論不久后，就成功地破解維吉尼亞密碼法的，但因為他從未發表結果，所以大家對他的發現毫無所知。這項發現，是20世紀的學者檢視巴貝奇大量的筆記才得見天日的。在這同時，一位普魯士退休軍官弗里德里奇·卡西斯基（Friedrich Wilhelm Kasiski）也發現了這個技巧。1863年，他在《秘密書寫與解密藝術》（Die Geheimschriften und die dechiffrir-kunst）中發表他在密碼分析學上的突破，這項技術從此被稱為卡西斯基測試（Kasiski Test），巴貝奇的貢獻則幾乎完全被忽略。

巴貝奇怎么會沒公開他破解了這么重要的密碼技術呢？他的確是有不把計劃做完，以及不發表他的發現的壞習慣，這可能只是他懶散態度的另一個例子。不過，還有另一種可能性。他是在克里米亞戰爭爆發不久后發現這個方法的，根據某些人的推測，這個方法可以提供給英國對抗俄羅斯的明顯優勢。很有可能是英國的情報當局要求巴貝奇將這項成就保密，讓他們遙遙領先世界其他國家9年。若真是如此，這倒很符合為了國家安全而對密碼解譯成就噤聲不語的悠久傳統——一項直到20世紀仍然存在的傳統。