密碼風(fēng)云 “謎”與“如謎的解謎者”（七）

花卷

盡管Enigma密碼機在設(shè)計上提供了劃時代的加密強度，但是在實際運用中還是會遇到密鑰配送問題。為了解決這個問題，德軍采用了“每日密碼本”加上“指標組”的組合，即把一個月中每一天的轉(zhuǎn)輪順序和初始位置印成密碼本人工分發(fā)到每個部隊的通訊員手中，然后對于每一封電報，通訊員需要自行設(shè)置一個3個字母長度的“指標組”并重復(fù)兩次，用每日密鑰進行加密后發(fā)出。這一操作方法實際上在安全性上做出了妥協(xié)，也成了日后破譯Enigma的重要突破口。

天降大任

1932年9月1日，波蘭華沙。三位波茲南大學(xué)數(shù)學(xué)系碩士——雷耶夫斯基、齊加爾斯基和魯日茨基，正式來到波蘭密碼局總部報到。第一天上班大家還都只是干點普通的工作，好像也沒什么特別玄乎的任務(wù)，但是密碼局似乎很快就發(fā)現(xiàn)這位小雷同學(xué)有點不一般，畢竟學(xué)霸的光芒是想藏也藏不住的呢。于是，過了沒多久，小雷同學(xué)就被調(diào)到了一個單獨的房間。小雷心想，這是啥情況？在獨立辦公室辦公，這不是老板的待遇么？難道我這么快就升官了？

小雷當然不是去當老板了，等待他的可是一塊燙手的山芋——Enigma。正如我們前面講過的，密碼局之前也嘗試過破譯用Enigma加密的密電，但卻一點辦法都找不到，就在這時小雷他們?nèi)粩?shù)學(xué)專家加入了密碼局，這可真是雪中送暖寶寶啊。特別是小雷，聽說在密碼課程中成績相當不錯，讓這種學(xué)霸破譯那些不入流的密碼，還不如給他個有點挑戰(zhàn)性的玩意兒試試看。于是，小雷剛加入密碼局不久，就被抓去破譯Enigma了，而且這是一項機密任務(wù)，小雷必須單獨關(guān)在一個秘密的房間里工作，還不能跟其他們?nèi)魏稳送嘎端烤乖诟墒裁础獙?，就連跟他一起進來的兩個好基友也不能說！

幾個前輩都搞不出來的Enigma居然落到自己頭上，小雷感覺這個工作壓力山大，而且他手上也沒有太多的資料可以參考，他的秘密辦公室里只有密碼局從正規(guī)渠道買來的一臺商用版Enigma密碼機，以及每天截獲的用Enigma加密的密電文。還記得我們講過的商用版Enigma和軍用版的區(qū)別么？它們主要的區(qū)別就是轉(zhuǎn)輪內(nèi)部的接線方式不一樣，而且商用版Enigma不帶連接板。我們知道，轉(zhuǎn)輪的接線方式是Enigma的三個秘密之一，顯然，商用版的轉(zhuǎn)輪怎么接的拆開看看就知道了，但是軍用版的跟它完全不一樣?。∧鞘遣皇钦f，研究這臺商用版的機器就一點用都沒有了呢？

當然不是，這臺商用版的機器，除了轉(zhuǎn)輪接線方式和連接板之外，其他的部分——比如加密解密的基本原理、轉(zhuǎn)輪的步進方式以及反射器的設(shè)計——這些都跟軍用版是一模一樣的，也就是說，通過研究和分析這臺商用版Enigma，小雷就可以搞清楚它的工作原理，并且還可以把它的加密方式寫成數(shù)學(xué)公式，然后再分析公式中哪些是已知的，哪些是未知的——你看，數(shù)學(xué)家的思路就是跟一般人不一樣！

指標組的暗示

那么小雷通過這些分析，到底發(fā)現(xiàn)了什么玄機呢？他發(fā)現(xiàn)的第一個突破口，就在這個指標組身上。我們之前說過，指標組是一個“妥協(xié)”的產(chǎn)物，而且指標組在發(fā)報時要放在電文開頭，還需要重復(fù)兩次，這對于破譯者來說是一個非常重要的線索——現(xiàn)在這個線索被小雷抓住了！

可是，這個線索有什么用呢？別急，我們慢慢來分析。還是回到上次的例子（如果不記得的話，再回顧一下上一期內(nèi)容吧），假設(shè)今天的“每日密鑰”是BKG，發(fā)報員想出來的指標組是ATX，那么發(fā)報員發(fā)報時，需要先把密碼機的轉(zhuǎn)輪分別轉(zhuǎn)到B、K、G的位置，然后在鍵盤上連續(xù)輸入“ATXATX”，得到一串密文，我們假設(shè)是“GYKPWR”。在“GYKPWR”這6個字母中，如果我們知道德軍運用指標組的規(guī)則（3個字母重復(fù)兩次），那么我們很容易看出：第1個字母G和第4個字母P所對應(yīng)的明文都是A，第2個字母Y和第5個字母W所對應(yīng)的明文都是T，第3個字母K和第6個字母R所對應(yīng)的明文都是X。

既然如此，為什么同一個明文字母，在不同的位置上會得到不同的密文呢？這是個很基礎(chǔ)的問題，我想你可以秒答——因為Enigma每輸入一個字母，轉(zhuǎn)輪就會步進一格呀！沒錯，但這里的關(guān)鍵信息是，每次發(fā)報的時候，轉(zhuǎn)輪的初始位置都是固定的，也就是今天的“每日密鑰”BKG，而且轉(zhuǎn)輪的步進方式是固定的，這意味著什么呢？假如發(fā)報員一天發(fā)了100封電報，那么每封電報的開頭都需要先加上指標組，每封電報的指標組可以都不—樣，但用來加密這些指標組的換字表卻是完全一樣的！

上面這段話似乎不太容易理解？沒事，我們還是看例子。假如發(fā)報員今天發(fā)了100封電報，每封電報的開頭都需要加上指標組，機器轉(zhuǎn)輪的初始位置都是“每日密鑰”BKG。當按下指標組的第1個字母時，最右側(cè)的轉(zhuǎn)輪步進一格，也就是從G轉(zhuǎn)到了H的位置；再按指標組的第2個字母，最右側(cè)的轉(zhuǎn)輪又步進一格，也就是從H轉(zhuǎn)到了I的位置。以此類推，發(fā)報員輸入指標組的6個字母時，所對應(yīng)的最右側(cè)轉(zhuǎn)輪的位置永遠是GHIJKL，別說發(fā)100封，就是發(fā)10000封電報，這個對應(yīng)關(guān)系也都是完全固定的。

特征結(jié)構(gòu)

不過，這個規(guī)律又意味著什么呢？小雷發(fā)現(xiàn)，利用這個規(guī)律，可以把相同明文字母產(chǎn)生的密文字母串聯(lián)起來，形成一種循環(huán)序列。我們還是來舉個例子，假設(shè)小雷每天能夠收到很多封用Enigma加密的電文，每封電文使用的指標組都不一樣，但是用來加密這些指標組的“每日密鑰”卻都是相同的。小雷把每封電文的前6個字母，也就是加密之后的指標組給提取出來，因為指標組是3個字母重復(fù)兩次，所以小雷也把它們寫成3個字母一組，比如有3封電文的前6個字母分別是這樣的：

1.DMO VBN

2.VON PUY

3.PUC FMO

由于指標組里面第1/4、2/5、3/6個位置的明文字母是相同的，轉(zhuǎn)輪步進的距離也是相同的，因此小雷就把這6個字母分為（1/4）（2，5）（3/6）這三個組。先看（1/4）組，電文1的（1，4）組是D和V兩個字母，電文2的（1/4）組是V和P，電文3是P和F，于是我們可以把這3條電文的（1/4）組串聯(lián)起來，寫成DVPF。如果我有更多的電文，這個序列還可以繼續(xù)寫下去，直到又返回第一個字母D為止，這樣就形成了一個循環(huán)序列。只要一天中的電文足夠多，小雷就可以把26個字母全部湊齊，這時就可以得到一個或者多個循環(huán)序列，但每個序列的長度可以不一樣，例如：

（1/4）=（DVPFKXGZYO）（EIJMUNQLHT）（BC）（RW）（A）（S）

我們發(fā)現(xiàn)最后有兩個落單的A和S，這意味著如果第1個字母出現(xiàn)了A或S，那么第4個字母也一定是A或S，也就是說這個循環(huán)序列里只有一個字母。以此類推，（2/5）和（3/6）組也可以用同樣的方法來操作，得到：

（2/5）=（BLFQVEOUM）（HJPSWIZRN）（AXT）（CGY）（D）（K）

（3/6）=（ABVIKTJGFCONY）（DUZREHLXWPSMO）

小雷指出，在每一組循環(huán)序列中，長度相同的序列總是成對出現(xiàn)，比如（1/4）組中的6個序列，長度分別為10、10、2、2、1、1，你看，果然都是成對出現(xiàn)的。你可能要問了，這難道是巧合嗎？別忘了，小雷是個數(shù)學(xué)大牛，對于數(shù)學(xué)家來說，怎么能允許巧合這種東西呢？所有數(shù)學(xué)命題，都是需要進行證明的呀！于是小雷對他發(fā)現(xiàn)的這個規(guī)律進行了證明，這個證明使用了19世紀的法國數(shù)學(xué)天才埃瓦里斯特-迦羅瓦（Evariste Galois）所開創(chuàng)的“群論”這一數(shù)學(xué)領(lǐng)域中的方法。群論這個東西屬于抽象代數(shù)，就算是大學(xué)里的高等數(shù)學(xué)，也只有數(shù)學(xué)、物理這種特別“硬”的專業(yè)才會學(xué)到，所以就連小雷本人在《IEEE計算史紀事》上的那篇文章中都說“證明過程太長，我就省略了”，估計寫出來大部分人也看不懂——當然了，我也是看不懂的，哈哈。

小雷把上面這三組序列稱為“特征結(jié)構(gòu)（characteristic structure）”，由于特征結(jié)構(gòu)只和每日密鑰有關(guān)，很顯然，在同一天里，特征結(jié)構(gòu)是固定不變的。雖然我們沒辦法在這里解釋小雷的數(shù)學(xué)證明，不過我們倒是可以簡單解釋一下為什么會出現(xiàn)這樣的結(jié)構(gòu)。

我們在最早介紹Enigma設(shè)計原理的時候提到過，Enigma上有一個很聰明的設(shè)計叫反射器，有了反射器，一臺Enigma就可以同時完成加密和解密兩種操作，也就是說，當轉(zhuǎn)輪位置相同時，按下明文字母就會得到密文，而按下密文字母就會得到明文。反射器其實也是一個轉(zhuǎn)輪，只不過它不會轉(zhuǎn)，而且一般的轉(zhuǎn)輪兩面各有26個觸點，而反射器只有單面26個觸點，它里面實際上是把這26個觸點兩兩連成了一對，組成了13個反射回路，因此在任何一個狀態(tài)下，字母1沿著回路到達字母2，字母2也一樣能沿著相反的回路回到字母1。

盡管反射器特別好用，可是小雷一看就發(fā)現(xiàn)，這種兩兩結(jié)對的設(shè)計，其中就蘊含了某種數(shù)學(xué)規(guī)律，這個數(shù)學(xué)規(guī)律用簡單的話來說，就是明文字母和密文字母之間的置換是“完全互斥”的。通過這一規(guī)律，小雷就可以證明由指標組產(chǎn)生的特征結(jié)構(gòu)，就必定是由像上面那樣成對出現(xiàn)的循環(huán)序列組成的。

“雷氏定理”

不過話說回來，即便我知道了這個規(guī)律，我怎么用它來破譯密碼呢？要知道，數(shù)學(xué)的精髓就是通過一條規(guī)律推導(dǎo)出更多的規(guī)律，特別是像小雷這種天才數(shù)學(xué)家，一定不會放過這里面所蘊含的玄機。小雷發(fā)現(xiàn)，通過上面這個基本規(guī)律，可以推導(dǎo)出另外一條更重要的規(guī)律：

一對相互置換的字母，在某一組中一定分別位于兩個同長度的不同循環(huán)序列中，且其相鄰的字母（一個在右，另一個在左）也一定為相互置換的關(guān)系。

上面這句話幾乎就是小雷的原話直接翻譯過來的，我們就管它叫“雷氏定理”吧。說實話，這句話到底在說什么，特別是后半句到底是什么意思，我也是琢磨了半天才搞明白，還是拿個例子來解一下吧。

我們假設(shè)德軍有一個發(fā)報員特別偷懶，他經(jīng)常拿AAA、BBB這種重復(fù)的字母組合來做指標組——比如說他今天就用了個AAA吧。然后我們已經(jīng)掌握了今天的特征結(jié)構(gòu)，也就是上面那三組序列，我們可以發(fā)現(xiàn)，在（1/4）組中，有兩個序列分別都只有1個字母，即A和S。根據(jù)雷氏定理，相互置換的字母一定位于兩個同長度的不同循環(huán)序列中，那么A和S一定是相互置換的關(guān)系，換句話說，在第1/4個字母的位置上，A一定會被加密成S，反過來，S也一定會被加密成A。

既然如此，我們就可以把所有形如“S？？S？？”的指標組都給篩選出來，看看它們當中有沒有誰是AAA呢？假如說我們找到了三個符合條件的指標組，分別是：①SUG SMF；②SJM SPO；③SYX SCW。好了，我們繼續(xù)往下驗證。

先看①號選手。假設(shè)它就是AAA，那么第2個字母就是把A加密成了U，換句話說，在第2個字母位置上，A和U應(yīng)該是相互置換的關(guān)系。但是我們看（2/5）組的序列，A所在的序列長度是3，而U所在的序列長度是9，它們并不位于“同長度”的序列中，因此①號選手不可能是AAA。②號選手也栽在了相同的地方：第2個字母J所在的序列長度也是9，所以它也被斃掉了。

現(xiàn)在只剩③號選手。它的第2個字母Y所在的序列長度是3，通過；第3個字母X呢，因為（3/6）組只有兩個長度為13的序列，只要A和X不在同一個序列就OK了，很顯然，這一關(guān)也通過了。我們還發(fā)現(xiàn)，第2個字母Y和第5個字母C，以及第3個字母X和第6個字母W，在各自組的序列中都是相鄰關(guān)系，即（2/5）組中，C在Y的右邊（Y是最右邊一個字母，因此它的右邊就回到了最左邊），（3/6）組中，W在X的右邊，這也符合雷氏定理的后半句。因此，③號選手就極有可能真的是指標組AAA。

通過這種方法，小雷就可以通過猜測一些常見的指標組明文，然后根據(jù)當天的特征結(jié)構(gòu)來驗證和篩選出它所對應(yīng)的指標組密文，這樣一來就可以建立起一些明文和密文的對應(yīng)關(guān)系，在密碼學(xué)上這種方法被稱為“已知明文攻擊（known plaintext attack）”。而尤其值得贊嘆的是，小雷既不需要知道每日密鑰到底是什么，也不需要知道密碼機的每個轉(zhuǎn)輪內(nèi)部的接線方式是什么，只使用數(shù)學(xué)方法就能夠分析出這些信息，這真的是只有數(shù)學(xué)家才能做到的“神之一手”。

（當然，只知道這些信息還并不足以破譯Enigma加密的電文，至于小雷他們到底是如何獲得更多線索的，我們下期繼續(xù)講。）