“謎”與“如謎的解謎者”(十三)

花卷

困難重重

我們之前講過，波蘭人已經(jīng)把他們研究出來的所有資料都交給了英國人，不僅如此，波蘭人還提供了他們制造的復(fù)刻版Enigma密碼機(jī)，以及穿孔紙片、炸彈機(jī)等神器。這些東西當(dāng)初漂洋過海的旅程可都挺不容易的，英國人自然把它們當(dāng)寶貝。

話說回來，即便是圖靈這樣的大牛，面對一個新問題，那也不可能一下子就搞出什么大殺器，必須也得從頭開始研究。既然波蘭人有這么多好東西，那我們就先拿這些玩意兒試試看唄，順便也檢驗(yàn)一下波蘭人的成果到底靠不靠譜。

波蘭人的成果當(dāng)然是靠譜的——只不過，只能說對于1939年之前的通信來說，是靠譜的。我們回憶一下，1938年底，德軍把Eniqma的用法進(jìn)行了升級，原來是3個轉(zhuǎn)輪調(diào)換順序使用，現(xiàn)在多加出來兩個轉(zhuǎn)輪，從5個轉(zhuǎn)輪里面選3個再調(diào)換順序使用。我們高中排列組合學(xué)過：P（3，3）=3！=6，而P（5，3）=5×4×3=60，規(guī)模整整擴(kuò)大了10倍，這困難不是一般的大。這還不算完，1939年1月，德軍又提高了連接板的復(fù)雜度，我們知道連接板的作用是將任意一對字母進(jìn)行交換，之前大概也就換個6對，現(xiàn)在開始升級成換10對了。這里插個題外話，按理說，字母一共有26個，所以連接板最多可以交換13對字母，但是我們可以計(jì)算出來（題外話就不細(xì)講算法了），交換10對才能帶來最大的變化數(shù)量，超過10對的話，反而會讓變化的數(shù)量縮小——看來德國人的數(shù)學(xué)也并不差。

眼看著德國人設(shè)置重重障礙，英國人當(dāng)然也不能就這么破罐破摔了，畢竟他們看到了波蘭人這么努力，而且現(xiàn)在還有圖靈這些數(shù)學(xué)大神的加持，總不能丟了“日不落帝國”的面子。面對現(xiàn)在這個情況，首先炸彈機(jī)基本上是廢掉了，因?yàn)榈聡诵薷牧酥笜?biāo)組的用法，就沒辦法建立雷耶夫斯基所說的那種“循環(huán)模式”了。不過好消息是，齊加爾斯基搞的穿孔紙片還是可以用的，只不過原來只要用6張，現(xiàn)在要用60張，比對起來也需要更多的人力才能完成。

丹尼斯頓心想，我們現(xiàn)在有那么大的一座莊園，還造了一些臨時(shí)板房，政府也答應(yīng)出錢招人，那還等什么，難道我們英國缺人嗎？于是，布萊切利開始大規(guī)模招募密碼分析員，但你可能沒想到的是，這些密碼分析員里大部分都是女性。據(jù)統(tǒng)計(jì)，整個“二戰(zhàn)”期間大約有10000多人在布萊切利莊園工作過，其中四分之三都是女性，至于原因嘛，我想應(yīng)該不難猜——因?yàn)槟腥硕忌锨熬€打仗去了唄。

當(dāng)然了，有很多女性在布萊切利從事密碼分析工作，并不代表當(dāng)時(shí)女性的地位有多高，很無奈的是，大部分女性都只被安排一些基礎(chǔ)的、重復(fù)性的工作——比如監(jiān)聽、轉(zhuǎn)譯、歸檔等等，而且拿的工資也比男性要少多了。制作和比對穿孔紙片也算是一種枯燥的重復(fù)性工作，只要按照預(yù)先規(guī)定好的手冊就可以完成，就跟看著說明書拼裝家具一樣——只不過制作一套60張穿孔紙片工作量非常大，布萊切利只能靠拼人力“996”加班加點(diǎn)。在這樣的情況下，即便速度跟不上，還算是能夠勉強(qiáng)破譯一部分德軍的密電。

遷入布萊切利初期，由于計(jì)劃的屋群還未建好，迪爾文·諾克斯、約翰杰弗里斯和艾倫圖靈等大牛都曾在存放牲畜糧草和馬具的馬棚里工作過。

猜詞游戲

我們之前講過，波蘭人的方法——無論是炸彈機(jī)還是穿孔紙片，都是嚴(yán)重依賴指標(biāo)組來工作的。炸彈機(jī)依賴的是弱指標(biāo)組（比如AAA、BBB）所形成的特殊循環(huán)模式，而穿孔紙片依賴的是指標(biāo)組加密之后出現(xiàn)的等位重復(fù)字符（samiczki）。指標(biāo)組作為一種操作規(guī)程，是很容易被改進(jìn)的，圖靈自然也看出了這個弱點(diǎn)，于是他就琢磨著能不能找到一種更“萬能”的方法，哪怕將來有一天德國人把指標(biāo)組改得連親媽都不認(rèn)識了，我也照樣能應(yīng)付自如。

你還別說，這樣的方法還真有，而且是英國人自己用過的，有過成功經(jīng)驗(yàn)的方法。我們知道，“二戰(zhàn)”中歐洲的軸心國勢力除了德國之外還有意大利，而德國和意大利在“二戰(zhàn)”之前曾經(jīng)支持過西班牙的弗朗哥政權(quán)打內(nèi)戰(zhàn)。既然都是朋友，那么德國自然也向他們提供了Enigma密碼機(jī)——只不過，提供給意大利和西班牙的機(jī)器都是不帶連接板的“閹割版”。連接板提供的額外變化對于破譯來說可以形成非常強(qiáng)大的干擾，如果沒有連接板的話，轉(zhuǎn)輪的變化總共就只有幾萬種，而且還是有規(guī)律的連續(xù)步進(jìn)變化，只要有足夠的材料，破譯起來并沒有那么難。

1937年4月，迪爾文諾克斯就成功破譯了西班牙弗朗哥政權(quán)用的“閹割版”Enigma密碼機(jī)通信，只不過這個事兒英國一直沒告訴別人。之前我們介紹過，諾克斯是個文科生，研究古籍學(xué)的，在他的眼里，密碼就是一種猜詞游戲，即使再加密得天花亂墜，你要傳遞的原始信息也是普通的文字，這種隱藏在原始文字之中的語言特性，是很難通過加密完全抹去的，因?yàn)檎Z言代表的是人類思維的固有模式。

其實(shí)諾克斯在之前破譯德國外長密電的時(shí)候就用過這種猜詞技巧，比如說德國人發(fā)電報(bào)在開頭都有一些固定的稱呼和格式，如果我可以從密文中猜出某一個單詞，那么就可以限定轉(zhuǎn)輪的一串連續(xù)位置，繼而為推測轉(zhuǎn)輪的初始位置提供重要的線索。比如說，如果我知道（靠猜的）電報(bào)中某一組密文（比如“PGIUSSN”）解密之后的明文是單詞“angriff”（進(jìn)攻），那么就可以知道當(dāng)最右側(cè)轉(zhuǎn)輪從某個位置開始連續(xù)步進(jìn)時(shí)，就會有P-a、G-n、I-g、U-r、S-i、S-f、N-f這樣一組限定的對應(yīng)關(guān)系，通過一些技巧進(jìn)行嘗試，就可以找到相對應(yīng)的轉(zhuǎn)輪狀態(tài)。這種猜詞的方法，英國人管它叫作“crib”，就是考試作弊用的小抄，挺生動的吧。

不過，諾克斯的這種方法，面對帶連接板的Enigma密碼機(jī)時(shí)，就有點(diǎn)力不從心了，因?yàn)檫B接板的存在會嚴(yán)重?cái)噥y這些對應(yīng)關(guān)系，也正是因?yàn)檫@個難題，諾克斯才在破譯Enigma這件事上輸給了波蘭人。不過現(xiàn)在好了，咱們英國也請來了數(shù)學(xué)家，說不定他們能讓這個方法起死回生呢？

機(jī)器對抗

圖靈聽說諾克斯的這個方法之后，感覺這主意不錯呀，也正好符合圖靈所提出的“不能依賴指標(biāo)組”的大方向。而且，圖靈的想法還更進(jìn)—步，他覺得猜詞之后找到對應(yīng)的轉(zhuǎn)輪狀態(tài)這件事，靠人力來做實(shí)在太累了，也太慢了，這個其實(shí)可以用機(jī)器來做嘛，你看波蘭人的那個炸彈機(jī)，我們把它改一改可能就行了。其實(shí)，圖靈之前上學(xué)的時(shí)候就特別喜歡擺弄機(jī)器，他在普林斯頓讀博士的時(shí)候，就曾經(jīng)親手制作了一臺二進(jìn)制乘法器（不過好像沒做完），所以無論是邏輯設(shè)計(jì)還是機(jī)械、電路設(shè)計(jì)，圖靈可都是一把好手。

那么，圖靈所說的這種“機(jī)器”，到底是個啥玩意兒呢？其實(shí)它看起來就是一個放大版的波蘭炸彈機(jī)。

炸彈機(jī)復(fù)制品

這張圖是現(xiàn)在展出于布萊切利莊園國家計(jì)算博物館的炸彈機(jī)復(fù)制品，這臺機(jī)器共有3排轉(zhuǎn)輪的槽位，每一排從上到下都有3個轉(zhuǎn)輪，這是因?yàn)镋nigma密碼機(jī)在工作的時(shí)候就是使用3個轉(zhuǎn)輪。這些轉(zhuǎn)輪共有5種顏色，因?yàn)?939年起德國一共啟用了5個不同的轉(zhuǎn)輪，實(shí)際使用的時(shí)候是5選3然后再按不同順序排列。這些轉(zhuǎn)輪的內(nèi)部連線，早就由雷耶夫斯基他們算出來了，所以圖靈他們可以直接批量生產(chǎn)——所以你看，波蘭人的貢獻(xiàn)的確是大大的。

我們可以發(fā)現(xiàn)，這臺機(jī)器當(dāng)中，每組從上到下的3個轉(zhuǎn)輪，就相當(dāng)于一臺Enigma中從左到右的3個轉(zhuǎn)輪，也就是代表一臺Enigma的一種狀態(tài)（當(dāng)然，這里排除了連接板，不過沒關(guān)系，我們后面再說），所以這一臺機(jī)器相當(dāng)于可以同時(shí)處理Enigma的36種狀態(tài)。

我們拿上面一個例子來說，比如我們猜到電文中“PGIUSSN”對應(yīng)的明文是“angriff”，那么我就可以有下面這張表：

我們假設(shè)中轉(zhuǎn)輪和左轉(zhuǎn)輪是不動的（大部分情況下都成立），而右轉(zhuǎn)輪每過一個字母步進(jìn)一格位置，那么當(dāng)我把7組轉(zhuǎn)輪放在一起，并且把右轉(zhuǎn)輪的位置依次錯開一格之后，當(dāng)輸入密文“PGIUSSN”時(shí)，必然會出現(xiàn)某一種狀態(tài)同時(shí)滿足這7個位置上匹配到明文“angriff”。也就是說，我只要讓這7組轉(zhuǎn)輪同步轉(zhuǎn)動（每次每組都步進(jìn)一格位置），必然可以找到一個滿足條件的狀態(tài)（當(dāng)然，前提是猜詞猜對了）。而當(dāng)找到這樣一個狀態(tài)時(shí)，機(jī)器就會停止，這時(shí)就可以人工確認(rèn)機(jī)器找到的這個狀態(tài)是否正確。

可是還有一個問題，連接板要怎么辦呢？之前諾克斯用這種方法，也是卡在了連接板上呀，圖靈能不能破局呢？我們知道，連接板的作用是交換若干對字母，但這些字母必須是成對交換的，比如說（AE）交換，那么所有的A就都變成了E，而所有的E就都變成了A，除此之外沒有其他可能。還是上面的例子，假設(shè)我們在某一個狀態(tài)下得到了下面的對應(yīng)關(guān)系：

我們來試想一下，“ARFEITF”有沒有可能通過連接板的交換就能得到“angriff”呢？

第1個字母A是正確的，我們跳過。第2個字母是R，而正確的字母是N，那我們可以認(rèn)為連接板上有一個（NR）交換。然而，第4個字母是E，而正確的字母是R，這意味著需要一個（ER）交換。我們知道，根據(jù)連接板的原理，不可能同時(shí)存在（NR）和（ER）兩種交換;同理，上面的例子還必須同時(shí)存在（FG）（FT）（FF）三種交換，這也是不可能的。因此這個位置狀態(tài)不可能是正確的，不但這個位置狀態(tài)不可能是正確的，與它相關(guān)聯(lián)的成千上萬個位置狀態(tài)也可以被一起排除掉了。

我們發(fā)現(xiàn)，圖靈的思路非常巧妙，因?yàn)檫B接板的存在雖然會干擾結(jié)果，但是我們依然可以通過邏輯推理來排除那些必定不可能正確的結(jié)果，這樣一來，連接板的干擾效應(yīng)就會被大幅度削弱。那么接下來，圖靈要解決的問題就是，如何在他的機(jī)器上實(shí)現(xiàn)這種邏輯推理和排除。

圖靈設(shè)想了一種方法，通過電路的連接來排除錯誤的狀態(tài)，在按照特定的crib進(jìn)行配置的情況下，只有轉(zhuǎn)輪之間形成一個特定的回路時(shí)，機(jī)器才會停下來。

不過，圖靈這個方法的效率并不是很高，因?yàn)椴⒉皇钦f當(dāng)機(jī)器停下來的時(shí)候，找到的那個解就一定是正確的。這是因?yàn)檎_的解必定可以形成特定的回路，但錯誤的解也有一定概率可以形成特定的回路。因此當(dāng)機(jī)器停下來的時(shí)候，就會有破譯人員過來把機(jī)器當(dāng)前的位置抄下來，然后用一臺復(fù)刻版的Enigma密碼機(jī)去驗(yàn)證一下，看看這個解是不是正確的。

圖靈是個數(shù)學(xué)家，對于他設(shè)計(jì)的這個方法的效率，他自己必然是做過計(jì)算的，這里面使用了概率論和組合數(shù)學(xué)。具體的計(jì)算結(jié)果我們就不列舉了，總之，根據(jù)圖靈的計(jì)算，猜詞人員給出的crib必須包含足夠多的字母數(shù)量（最好10個以上），而且密文和明文之間必須包含足夠多的閉合回路（最好2個以上），這樣才能保證機(jī)器有足夠高的概率檢測到正確的解——換句話說，就是讓機(jī)器停了但是沒找到正確的解這種事發(fā)生的概率變得足夠小。

（然而，符合這種要求的crib可不容易找，別忘了那可是要用猜的，還不能保證猜得準(zhǔn)，因此圖靈設(shè)計(jì)的機(jī)器效率并不高。那么圖靈和他的伙伴們會如何解決這個問題呢？我們下期繼續(xù)講。）