多表密碼攻防戰(zhàn)（五）

花卷

上期我們講到，經(jīng)過了好幾位密碼學(xué)大師的不懈努力之后，多表密碼終于出現(xiàn)了一個(gè)“集大成”的作品，那就是維熱納爾方表。維熱納爾方表把特里特米烏斯的“方表”系統(tǒng)和貝拉索的“口令”系統(tǒng)進(jìn)行了完美的整合，這種密碼在幾百年來一直被認(rèn)為是“無法破譯”的。不過，到了19世紀(jì)，終于有兩個(gè)牛人提出了破譯這種密碼的系統(tǒng)性方法，其中一個(gè)就是堪稱“計(jì)算機(jī)之父”之一的英國數(shù)學(xué)家和工程師查爾斯·巴貝奇。那么巴貝奇到底是用什么方法破譯維熱納爾方表的呢？另一個(gè)牛人又是誰呢？

意想不到的動機(jī)

巴貝奇這個(gè)人不知道是太牛呢還是太牛呢，總之，除了發(fā)明了兩臺計(jì)算機(jī)之外，他還干過很多神奇的事情，比如說幫助英國建立了現(xiàn)代郵政體系（主要是幫他們把郵費(fèi)該怎么收這件事給算清楚了），比如說編寫了第一套可靠的精算表格，比如說還搞過一大堆各種各樣的發(fā)明專利。巴貝奇一輩子干了這么多事，破譯密碼只能算是他的“業(yè)余愛好”了。不過他本人貌似還挺喜歡玩這個(gè)的，據(jù)說巴貝奇小時(shí)候就經(jīng)常破譯其他小伙伴的密碼，以此對小伙伴在智商上進(jìn)行無情地碾壓。巴貝奇在自傳中說：“在我看來，破譯密碼是迷人的藝術(shù)之一?！彼哉f，巴爺覺著破譯密碼這種事是“藝術(shù)”，跟音樂什么的算是一類的，哦對了，巴爺也很喜歡音樂，好像還造過街頭表演用的便攜式風(fēng)琴。

當(dāng)巴貝奇第一次得知維熱納爾方表的時(shí)候，他也覺得這真是一個(gè)天才的設(shè)計(jì)。不過他的觀察力也特別敏銳，馬上又發(fā)現(xiàn)這種密碼不可能像傳說中那樣“無法破譯”，這里面肯定有漏洞可以挖。但是我們都知道，巴爺很忙，于是很長一段時(shí)間內(nèi)他就把這件事給忘了。后來，一個(gè)偶然的機(jī)會，有個(gè)不務(wù)正業(yè)的牙醫(yī)（按現(xiàn)在的話說就是民科），給藝術(shù)學(xué)會的期刊投了個(gè)稿，介紹自己發(fā)明的一種新密碼，還說要申請專利。碰巧巴貝奇看到了這篇稿，他一瞅新密碼本來還挺有興趣的，看完之后卻大呼上當(dāng)：這什么新密碼啊，不是跟維熱納爾方表一模一樣嘛。于是他就給這位牙醫(yī)回了一封信，說你這個(gè)密碼根本就不是什么新東西，幾百年前就已經(jīng)有了，很多密碼學(xué)的專著中都有記載，你回去再補(bǔ)習(xí)一下吧。

本來巴貝奇以為這件事就這么過去了，可沒想到這位牙醫(yī)特別執(zhí)著，跟巴貝奇還“懟”上了。牙醫(yī)回信說，如果你說我這個(gè)密碼老早就有了，那你把它破譯了給我看看唄？其實(shí)吧，就連小學(xué)生都能看出來，這位牙醫(yī)就是在賭氣抬杠吶，你這個(gè)密碼是不是你首創(chuàng)的，跟我能不能破譯它有哪門子關(guān)系?。堪拓惼娈?dāng)然也知道對方在抬杠，但是他是個(gè)不信邪的人，你不是懟我么，那我就破譯給你看看，到時(shí)候狠狠打你的臉。

化繁為簡

那么巴貝奇到底用了什么樣的方法來破譯維熱納爾方表呢？我們先來回憶一下維熱納爾方表的結(jié)構(gòu)。維熱納爾方表是用口令來切換置換表的，而相對于整篇文章來說，口令通常是一個(gè)比較短的單詞，因此需要把口令不斷重復(fù)才能加密完整篇文章。我們再把之前的那個(gè)例子搬出來看一看：

注意看，我們的口令是FANS，只有4個(gè)字母，但要加密的原文有12個(gè)字母，因此口令就得重復(fù)3次。巴貝奇正是注意到了這一點(diǎn)，因?yàn)榉彩菚爸貜?fù)”的東西都一定是有規(guī)律可循的。想想看，維熱納爾方表為什么難以用傳統(tǒng)方法破譯呢？就是因?yàn)樗ㄟ^口令切換了不同的置換表，這樣就沒辦法從整體上用頻率分析來對付了，不過我們也不難發(fā)現(xiàn)，正是因?yàn)榭诹顩Q定了所使用的置換表，那么相同的口令字母所對應(yīng)的原文字母，也就是用相同的置換表來加密的。更重要的是，口令是循環(huán)重復(fù)的，那么在某一相同間隔下，相同的口令字母必然會重復(fù)出現(xiàn)，巴貝奇覺得這就是他苦苦尋找的突破口了。

上面這段太繞了？我們還是拿例子說話吧。例子中，我們的口令“FANS”長度是4個(gè)字母，重復(fù)了3次，那么就意味著，每隔4個(gè)字母，我們就會遇到相同的口令字母，而相同的口令字母就意味著用相同的置換表加密，比如例子中第1、5、9個(gè)位置的口令字母都是“F”，那么這三個(gè)原文字母“T”“O”“I”就是用同一張置換表來加密的。

發(fā)現(xiàn)了這個(gè)有什么用呢？當(dāng)然有用！我們剛才說過，“多表”是抵御頻率分析的最大障礙，如果我們把“多表”密碼中使用相同置換表加密的那些字母給抽出來，那這些字母不就相當(dāng)于是“單表”了嗎？如果是單表，那頻率分析就可以重振雄風(fēng)了呀！拿上面的例子來看，如果我知道口令的長度是4個(gè)字母，那我就可以把整篇文章以4為間隔拆成4份：第1、5、9個(gè)字母為一份；第2、6、10個(gè)字母為一份；第3、7、11個(gè)字母為一份；第4、8、12個(gè)字母為一份。我們之前分析過，這樣拆分之后，每一份里面的字母都是用同一張置換表加密的，也就是相當(dāng)于用單表加密的，我們就可以對每一份分別使用頻率分析，然后再合起來就可以得到非常多的破譯線索，最終破譯整篇文章。

就這么簡單？No，no……要想把多表密碼給拆分成單表密碼，我們需要知道一個(gè)關(guān)鍵的信息，那就是口令的長度?？蓡栴}是，怎樣才能知道口令的長度呢？口令的長度可以是從1開始的任意正整數(shù)，不過一般都不會很大，我們可以從1開始往上猜，但問題是我們怎么判斷猜對了沒有呢？巴貝奇用的方法大概是這樣的：

首先，從整篇密文中找出重復(fù)出現(xiàn)的片段，每個(gè)片段必須包含3個(gè)或更多的字母，比如說一篇密文中我們找到了兩處“FVQT”，這就是一組重復(fù)的片段。為什么要找重復(fù)的片段呢？因?yàn)橄嗤淖帜概帕兄詴貜?fù)出現(xiàn)，很大可能性是“相同的原文字母序列，經(jīng)過相同的口令序列加密”之后所得到的結(jié)果。之所以一定要3個(gè)字母以上，就是為了盡量排除“原文字母和口令都不同，但依然得到了相同的密文”這種偶然情況。

接下來，計(jì)算每組重復(fù)片段中，字母序列重復(fù)出現(xiàn)的間隔。比如說，剛才我們找到了兩處“FVQT”，我們就數(shù)一數(shù)第一個(gè)“FVQT”和第二個(gè)“FVQT”之間隔了多少個(gè)字母，注意是從第一個(gè)“F”數(shù)到第二個(gè)“F”為止，假設(shè)這個(gè)間隔是90。我們應(yīng)該找到不止一組重復(fù)片段，對于每一組重復(fù)片段都要數(shù)出每次重復(fù)之間的間隔，這樣我們就得到了若干個(gè)間隔。endprint

最后，我們對這些間隔的值進(jìn)行因數(shù)分解，并找到它們的公因數(shù)。如果我們找到了足夠多的重復(fù)片段，那么一般來說只能找出唯一的公因數(shù)，如果找不到公因數(shù)，就看所有的因數(shù)中哪個(gè)出現(xiàn)的次數(shù)最多。比如說，我們找到了三組重復(fù)片段，它們的重復(fù)間隔分別是90、10和35，那么我們就可以找出它們的唯一公因數(shù)——5，而這個(gè)公因數(shù)“極有可能”就是口令的長度。

殊途同歸

巴貝奇找出破譯維熱納爾方表的方法大概是在1854年，不過我們天才的巴爺有個(gè)很不好的習(xí)慣，他有很多成果都是做出來了之后懶得整理發(fā)表，只留下一大堆神奇的手稿，這一點(diǎn)倒是跟傳奇人物達(dá)芬奇有點(diǎn)像，畢竟這倆人都是多才多藝的大忙人。更何況破譯密碼對于巴貝奇來說本來就是業(yè)余愛好，所以毫無懸念地，這個(gè)破譯維熱納爾方表的方法最終沒有被發(fā)表出來，是后來人們整理他的筆記的時(shí)候才發(fā)現(xiàn)的。當(dāng)然，也有人認(rèn)為這可能是英國軍方的要求，畢竟涉及密碼的事情，英國人都很謹(jǐn)慎，就算已經(jīng)破譯了一種密碼也要裝傻充愣，讓別的國家以為這種密碼還挺安全的，繼續(xù)再用個(gè)幾十年，然后自己在背地里就可以偷窺人家的機(jī)密了，這種暗爽的事兒英國可真沒少干。

不管是出于哪種原因，巴貝奇的名字很遺憾地沒能跟這種劃時(shí)代的破譯方法綁定起來。1863年，德國密碼學(xué)家弗雷德里?！たㄎ魉够‵riedrich Kasiski）發(fā)表了一部題為《密碼與破譯藝術(shù)》（Die Geheimschriften und die Dechiffrir-Kunst）的著作。在這本書里，卡西斯基提出了一種針對多表密碼的破譯方法，后來人們發(fā)現(xiàn)這種方法跟巴貝奇的方法本質(zhì)上是完全一樣的，只不過比巴貝奇晚了差不多10年，誰讓巴爺沒發(fā)表自己的成果呢？你看，功勞讓德國人給搶去了吧。直到現(xiàn)在，我們依然管這種破譯方法叫“卡西斯基測試（Kasiski examination）”，不過估計(jì)以巴爺?shù)男愿瘢蟾乓膊粫?jì)較這種名分吧，反正他的名分已經(jīng)很多了。

其實(shí)卡西斯基提出的這個(gè)方法在當(dāng)時(shí)也沒有得到多大的關(guān)注，在出版這本著作的時(shí)候，卡西斯基已經(jīng)從軍隊(duì)退休了，后來他一看這本書沒什么人看嘛，于是晚年又改行研究考古學(xué)去了，也是夠寂寞的。可是為什么這樣一種巧妙的破譯方法居然會遇冷呢？我覺得主要還是因?yàn)橐跃S熱納爾方表為代表的多表密碼本身在當(dāng)時(shí)并沒有得到大規(guī)模的運(yùn)用。

多表密碼與自動化時(shí)代

我們在這個(gè)主題的開頭就講過，16、17世紀(jì)的歐洲，盡管以維熱納爾方表為代表的多表密碼已經(jīng)出現(xiàn)了，也證明了它的確比單表密碼更安全可靠，但我們看到的大量史料都表明，當(dāng)時(shí)單表+辭典的nomenclator密碼依然穩(wěn)穩(wěn)地占據(jù)著主導(dǎo)地位，多表密碼則很少大規(guī)模推廣，可這是為什么呢？

其中最主要的一個(gè)原因是多表密碼用起來效率太低了，換句話說，就是太麻煩了。當(dāng)時(shí)，無論是加密還是解密都是靠人工來完成的，一個(gè)小黑屋里面坐一大堆秘書，一天到晚專門干這個(gè)事兒。然而隨著國家之間的秘密通信越來越多，軍隊(duì)里面的秘密通信還要多，于是密碼就被迫要在安全性和效率之間做出權(quán)衡，魚和熊掌不可兼得。

單表+辭典的nomenclator在效率上的優(yōu)勢很明顯。一來這種密碼已經(jīng)運(yùn)用了很長時(shí)間，也就存在大量的熟練人才儲備。二來單表密碼不需要輪換密鑰，比較符合人類的記憶習(xí)慣，也就是說，一個(gè)人可以通過一定時(shí)間的訓(xùn)練熟練掌握一種單表密碼的加密和解密，對于大部分常見單詞甚至不需要查表就可以默寫出來，但多表密碼就不行，因?yàn)槊總€(gè)字母都要輪換置換表，以人腦要處理這么復(fù)雜的規(guī)則，實(shí)在是太吃力了。

于是，多表密碼雖然比單表密碼安全，但無奈效率太低了，實(shí)在沒辦法大規(guī)模推廣，只能用在少數(shù)需要較高安全級別的場合。也正是出于這個(gè)原因，多表密碼的價(jià)值一直被低估，所以卡西斯基破譯多表密碼的書也就沒什么人關(guān)心了，畢竟大部分人連這種密碼本身都還不太了解呢，還談什么破譯呢？

然而，是金子總會發(fā)光的。多表密碼在安全性上的優(yōu)勢毋庸置疑，而且只要改進(jìn)密鑰輪換的方式，就可以進(jìn)一步提高強(qiáng)度。到了19世紀(jì)，隨著兩次工業(yè)革命的到來，人類開始邁入機(jī)械和自動化時(shí)代，密碼學(xué)當(dāng)然也跟著沾了光。機(jī)械可以提高手工勞動的效率，那么它能不能提高多表密碼的效率呢？不用說，答案顯然是肯定的。在兩次世界大戰(zhàn)時(shí)期，各國都搞出了各式各樣的“密碼機(jī)”，其中就包括大名鼎鼎的傳奇密碼機(jī)“Enigma”。實(shí)際上，這些密碼機(jī)就相當(dāng)于能夠自動輪換密鑰的多表密碼，也就是說，到了機(jī)械和自動化時(shí)代，多表密碼才得以真正發(fā)揮它的威力。

（完）endprint