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

花卷

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

意想不到的動(dòng)機(jī)

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

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

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

化繁為簡(jiǎn)

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

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

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

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

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

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

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

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

殊途同歸

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

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

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

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

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

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

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

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

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

（完）endprint