花卷
盡管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ù)講。)