花卷
我們之前講過,波蘭人已經把他們研究出來的所有資料都交給了英國人,不僅如此,波蘭人還提供了他們制造的復刻版Enigma密碼機,以及穿孔紙片、炸彈機等神器。這些東西當初漂洋過海的旅程可都挺不容易的,英國人自然把它們當寶貝。
話說回來,即便是圖靈這樣的大牛,面對一個新問題,那也不可能一下子就搞出什么大殺器,必須也得從頭開始研究。既然波蘭人有這么多好東西,那我們就先拿這些玩意兒試試看唄,順便也檢驗一下波蘭人的成果到底靠不靠譜。
波蘭人的成果當然是靠譜的——只不過,只能說對于1939年之前的通信來說,是靠譜的。我們回憶一下,1938年底,德軍把Eniqma的用法進行了升級,原來是3個轉輪調換順序使用,現在多加出來兩個轉輪,從5個轉輪里面選3個再調換順序使用。我們高中排列組合學過:P(3,3)=3!=6,而P(5,3)=5×4×3=60,規(guī)模整整擴大了10倍,這困難不是一般的大。這還不算完,1939年1月,德軍又提高了連接板的復雜度,我們知道連接板的作用是將任意一對字母進行交換,之前大概也就換個6對,現在開始升級成換10對了。這里插個題外話,按理說,字母一共有26個,所以連接板最多可以交換13對字母,但是我們可以計算出來(題外話就不細講算法了),交換10對才能帶來最大的變化數量,超過10對的話,反而會讓變化的數量縮小——看來德國人的數學也并不差。
眼看著德國人設置重重障礙,英國人當然也不能就這么破罐破摔了,畢竟他們看到了波蘭人這么努力,而且現在還有圖靈這些數學大神的加持,總不能丟了“日不落帝國”的面子。面對現在這個情況,首先炸彈機基本上是廢掉了,因為德國人修改了指標組的用法,就沒辦法建立雷耶夫斯基所說的那種“循環(huán)模式”了。不過好消息是,齊加爾斯基搞的穿孔紙片還是可以用的,只不過原來只要用6張,現在要用60張,比對起來也需要更多的人力才能完成。
丹尼斯頓心想,我們現在有那么大的一座莊園,還造了一些臨時板房,政府也答應出錢招人,那還等什么,難道我們英國缺人嗎?于是,布萊切利開始大規(guī)模招募密碼分析員,但你可能沒想到的是,這些密碼分析員里大部分都是女性。據統計,整個“二戰(zhàn)”期間大約有10000多人在布萊切利莊園工作過,其中四分之三都是女性,至于原因嘛,我想應該不難猜——因為男人都上前線打仗去了唄。
當然了,有很多女性在布萊切利從事密碼分析工作,并不代表當時女性的地位有多高,很無奈的是,大部分女性都只被安排一些基礎的、重復性的工作——比如監(jiān)聽、轉譯、歸檔等等,而且拿的工資也比男性要少多了。制作和比對穿孔紙片也算是一種枯燥的重復性工作,只要按照預先規(guī)定好的手冊就可以完成,就跟看著說明書拼裝家具一樣——只不過制作一套60張穿孔紙片工作量非常大,布萊切利只能靠拼人力“996”加班加點。在這樣的情況下,即便速度跟不上,還算是能夠勉強破譯一部分德軍的密電。
遷入布萊切利初期,由于計劃的屋群還未建好,迪爾文·諾克斯、約翰杰弗里斯和艾倫圖靈等大牛都曾在存放牲畜糧草和馬具的馬棚里工作過。
我們之前講過,波蘭人的方法——無論是炸彈機還是穿孔紙片,都是嚴重依賴指標組來工作的。炸彈機依賴的是弱指標組(比如AAA、BBB)所形成的特殊循環(huán)模式,而穿孔紙片依賴的是指標組加密之后出現的等位重復字符(samiczki)。指標組作為一種操作規(guī)程,是很容易被改進的,圖靈自然也看出了這個弱點,于是他就琢磨著能不能找到一種更“萬能”的方法,哪怕將來有一天德國人把指標組改得連親媽都不認識了,我也照樣能應付自如。
你還別說,這樣的方法還真有,而且是英國人自己用過的,有過成功經驗的方法。我們知道,“二戰(zhàn)”中歐洲的軸心國勢力除了德國之外還有意大利,而德國和意大利在“二戰(zhàn)”之前曾經支持過西班牙的弗朗哥政權打內戰(zhàn)。既然都是朋友,那么德國自然也向他們提供了Enigma密碼機——只不過,提供給意大利和西班牙的機器都是不帶連接板的“閹割版”。連接板提供的額外變化對于破譯來說可以形成非常強大的干擾,如果沒有連接板的話,轉輪的變化總共就只有幾萬種,而且還是有規(guī)律的連續(xù)步進變化,只要有足夠的材料,破譯起來并沒有那么難。
1937年4月,迪爾文諾克斯就成功破譯了西班牙弗朗哥政權用的“閹割版”Enigma密碼機通信,只不過這個事兒英國一直沒告訴別人。之前我們介紹過,諾克斯是個文科生,研究古籍學的,在他的眼里,密碼就是一種猜詞游戲,即使再加密得天花亂墜,你要傳遞的原始信息也是普通的文字,這種隱藏在原始文字之中的語言特性,是很難通過加密完全抹去的,因為語言代表的是人類思維的固有模式。
其實諾克斯在之前破譯德國外長密電的時候就用過這種猜詞技巧,比如說德國人發(fā)電報在開頭都有一些固定的稱呼和格式,如果我可以從密文中猜出某一個單詞,那么就可以限定轉輪的一串連續(xù)位置,繼而為推測轉輪的初始位置提供重要的線索。比如說,如果我知道(靠猜的)電報中某一組密文(比如“PGIUSSN”)解密之后的明文是單詞“angriff”(進攻),那么就可以知道當最右側轉輪從某個位置開始連續(xù)步進時,就會有P-a、G-n、I-g、U-r、S-i、S-f、N-f這樣一組限定的對應關系,通過一些技巧進行嘗試,就可以找到相對應的轉輪狀態(tài)。這種猜詞的方法,英國人管它叫作“crib”,就是考試作弊用的小抄,挺生動的吧。
不過,諾克斯的這種方法,面對帶連接板的Enigma密碼機時,就有點力不從心了,因為連接板的存在會嚴重攪亂這些對應關系,也正是因為這個難題,諾克斯才在破譯Enigma這件事上輸給了波蘭人。不過現在好了,咱們英國也請來了數學家,說不定他們能讓這個方法起死回生呢?
圖靈聽說諾克斯的這個方法之后,感覺這主意不錯呀,也正好符合圖靈所提出的“不能依賴指標組”的大方向。而且,圖靈的想法還更進—步,他覺得猜詞之后找到對應的轉輪狀態(tài)這件事,靠人力來做實在太累了,也太慢了,這個其實可以用機器來做嘛,你看波蘭人的那個炸彈機,我們把它改一改可能就行了。其實,圖靈之前上學的時候就特別喜歡擺弄機器,他在普林斯頓讀博士的時候,就曾經親手制作了一臺二進制乘法器(不過好像沒做完),所以無論是邏輯設計還是機械、電路設計,圖靈可都是一把好手。
那么,圖靈所說的這種“機器”,到底是個啥玩意兒呢?其實它看起來就是一個放大版的波蘭炸彈機。
炸彈機復制品
這張圖是現在展出于布萊切利莊園國家計算博物館的炸彈機復制品,這臺機器共有3排轉輪的槽位,每一排從上到下都有3個轉輪,這是因為Enigma密碼機在工作的時候就是使用3個轉輪。這些轉輪共有5種顏色,因為1939年起德國一共啟用了5個不同的轉輪,實際使用的時候是5選3然后再按不同順序排列。這些轉輪的內部連線,早就由雷耶夫斯基他們算出來了,所以圖靈他們可以直接批量生產——所以你看,波蘭人的貢獻的確是大大的。
我們可以發(fā)現,這臺機器當中,每組從上到下的3個轉輪,就相當于一臺Enigma中從左到右的3個轉輪,也就是代表一臺Enigma的一種狀態(tài)(當然,這里排除了連接板,不過沒關系,我們后面再說),所以這一臺機器相當于可以同時處理Enigma的36種狀態(tài)。
我們拿上面一個例子來說,比如我們猜到電文中“PGIUSSN”對應的明文是“angriff”,那么我就可以有下面這張表:
我們假設中轉輪和左轉輪是不動的(大部分情況下都成立),而右轉輪每過一個字母步進一格位置,那么當我把7組轉輪放在一起,并且把右轉輪的位置依次錯開一格之后,當輸入密文“PGIUSSN”時,必然會出現某一種狀態(tài)同時滿足這7個位置上匹配到明文“angriff”。也就是說,我只要讓這7組轉輪同步轉動(每次每組都步進一格位置),必然可以找到一個滿足條件的狀態(tài)(當然,前提是猜詞猜對了)。而當找到這樣一個狀態(tài)時,機器就會停止,這時就可以人工確認機器找到的這個狀態(tài)是否正確。
可是還有一個問題,連接板要怎么辦呢?之前諾克斯用這種方法,也是卡在了連接板上呀,圖靈能不能破局呢?我們知道,連接板的作用是交換若干對字母,但這些字母必須是成對交換的,比如說(AE)交換,那么所有的A就都變成了E,而所有的E就都變成了A,除此之外沒有其他可能。還是上面的例子,假設我們在某一個狀態(tài)下得到了下面的對應關系:
我們來試想一下,“ARFEITF”有沒有可能通過連接板的交換就能得到“angriff”呢?
第1個字母A是正確的,我們跳過。第2個字母是R,而正確的字母是N,那我們可以認為連接板上有一個(NR)交換。然而,第4個字母是E,而正確的字母是R,這意味著需要一個(ER)交換。我們知道,根據連接板的原理,不可能同時存在(NR)和(ER)兩種交換;同理,上面的例子還必須同時存在(FG)(FT)(FF)三種交換,這也是不可能的。因此這個位置狀態(tài)不可能是正確的,不但這個位置狀態(tài)不可能是正確的,與它相關聯的成千上萬個位置狀態(tài)也可以被一起排除掉了。
我們發(fā)現,圖靈的思路非常巧妙,因為連接板的存在雖然會干擾結果,但是我們依然可以通過邏輯推理來排除那些必定不可能正確的結果,這樣一來,連接板的干擾效應就會被大幅度削弱。那么接下來,圖靈要解決的問題就是,如何在他的機器上實現這種邏輯推理和排除。
圖靈設想了一種方法,通過電路的連接來排除錯誤的狀態(tài),在按照特定的crib進行配置的情況下,只有轉輪之間形成一個特定的回路時,機器才會停下來。
不過,圖靈這個方法的效率并不是很高,因為并不是說當機器停下來的時候,找到的那個解就一定是正確的。這是因為正確的解必定可以形成特定的回路,但錯誤的解也有一定概率可以形成特定的回路。因此當機器停下來的時候,就會有破譯人員過來把機器當前的位置抄下來,然后用一臺復刻版的Enigma密碼機去驗證一下,看看這個解是不是正確的。
圖靈是個數學家,對于他設計的這個方法的效率,他自己必然是做過計算的,這里面使用了概率論和組合數學。具體的計算結果我們就不列舉了,總之,根據圖靈的計算,猜詞人員給出的crib必須包含足夠多的字母數量(最好10個以上),而且密文和明文之間必須包含足夠多的閉合回路(最好2個以上),這樣才能保證機器有足夠高的概率檢測到正確的解——換句話說,就是讓機器停了但是沒找到正確的解這種事發(fā)生的概率變得足夠小。
(然而,符合這種要求的crib可不容易找,別忘了那可是要用猜的,還不能保證猜得準,因此圖靈設計的機器效率并不高。那么圖靈和他的伙伴們會如何解決這個問題呢?我們下期繼續(xù)講。)