多表密碼攻防戰（五）

花卷

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

意想不到的動機

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

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

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

化繁為簡

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

注意看，我們的口令是FANS，只有4個字母，但要加密的原文有12個字母，因此口令就得重復3次。巴貝奇正是注意到了這一點，因為凡是會“重復”的東西都一定是有規律可循的。想想看，維熱納爾方表為什么難以用傳統方法破譯呢？就是因為它通過口令切換了不同的置換表，這樣就沒辦法從整體上用頻率分析來對付了，不過我們也不難發現，正是因為口令決定了所使用的置換表，那么相同的口令字母所對應的原文字母，也就是用相同的置換表來加密的。更重要的是，口令是循環重復的，那么在某一相同間隔下，相同的口令字母必然會重復出現，巴貝奇覺得這就是他苦苦尋找的突破口了。

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

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

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

首先，從整篇密文中找出重復出現的片段，每個片段必須包含3個或更多的字母，比如說一篇密文中我們找到了兩處“FVQT”，這就是一組重復的片段。為什么要找重復的片段呢？因為相同的字母排列之所以會重復出現，很大可能性是“相同的原文字母序列，經過相同的口令序列加密”之后所得到的結果。之所以一定要3個字母以上，就是為了盡量排除“原文字母和口令都不同，但依然得到了相同的密文”這種偶然情況。

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

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

殊途同歸

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

不管是出于哪種原因，巴貝奇的名字很遺憾地沒能跟這種劃時代的破譯方法綁定起來。1863年，德國密碼學家弗雷德里希·卡西斯基（Friedrich Kasiski）發表了一部題為《密碼與破譯藝術》（Die Geheimschriften und die Dechiffrir-Kunst）的著作。在這本書里，卡西斯基提出了一種針對多表密碼的破譯方法，后來人們發現這種方法跟巴貝奇的方法本質上是完全一樣的，只不過比巴貝奇晚了差不多10年，誰讓巴爺沒發表自己的成果呢？你看，功勞讓德國人給搶去了吧。直到現在，我們依然管這種破譯方法叫“卡西斯基測試（Kasiski examination）”，不過估計以巴爺的性格，他大概也不會計較這種名分吧，反正他的名分已經很多了。

其實卡西斯基提出的這個方法在當時也沒有得到多大的關注，在出版這本著作的時候，卡西斯基已經從軍隊退休了，后來他一看這本書沒什么人看嘛，于是晚年又改行研究考古學去了，也是夠寂寞的?？墒菫槭裁催@樣一種巧妙的破譯方法居然會遇冷呢？我覺得主要還是因為以維熱納爾方表為代表的多表密碼本身在當時并沒有得到大規模的運用。

多表密碼與自動化時代

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

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

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

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

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

（完）endprint