站在巨人的肩膀上：納粹的最終滅亡

上一期（詳見：《藝術品的解析：恩尼格碼的破解》）我們講到了波蘭數學家馬里安·雷傑夫斯基利用恩尼格碼設計和使用的各種缺陷破解了商用恩尼格碼。但是由於德國軍方對恩尼格碼設計和使用的改進以及戰爭的臨近，波蘭科學家們不得不放棄了對恩尼格碼的研究，並將所有研究成果隨帶著一個波蘭製造的恩尼格碼樣機送到了英國。當時除了英國之外的其他盟國包括法國，蘇聯等都低估了德國的戰力以及恩尼格碼在戰爭中的重要性，並在拿到波蘭科學家研究成果之後草草得出了恩尼格碼不可破解的結論。

唯獨英國在經過各方國力對比之後提出了破解恩尼格碼是提早結束戰爭及傷亡的關鍵。於是波蘭科學家的研究成果以及那台恩尼格碼機便以國家頭等機密被放在了英國的布萊切利公園。當時政府決心不惜一切代價破解恩尼格碼，並聘請了當時國內最有名的語言學家，密碼學家以及數學家們共同研究破解方法。

當時的英國科學家們繼續沿用了波蘭科學家的破解方法，聘請了大量的工作人員使用記錄表（具體參見上一期內容）進行人工對比。但根據上一期的描述，德國人在改進了恩尼格碼的設計和使用方法之後大大增加了恩尼格碼的安全性，使得波蘭科學家們總結出的破解方法很難再破譯改進後的恩尼格碼。不僅如此，德國每天凌晨更改恩尼格碼設置的決定使得破解工作的進展完全無法累積。從德國每天早上六點的第一封電文開始到凌晨12點，如果英國科學家們不能在這18個小時之內破譯出當天的密鑰（恩尼格碼機的初始設置），那麼第二天的破譯工作就必須重新開始。這也使得前期的破譯工作幾乎毫無進展。

圖1：阿倫·圖靈

然而眾多科學家中有一個在當時數學界便鼎鼎有名的人— 阿倫圖靈。 當時的圖靈在破譯團隊中卻比較默默無聞。原因很簡單，首先，當時的圖靈的德語水平遠不及團隊中的其他人。於是當時的團隊並沒有將很重要的任務交於圖靈。試想一個不怎麼會德語的人如何去破解別人的密碼呢？其次，當時的圖靈便看出了當時破譯方法的弊端，於是他也很少和同事們合作，反而致力於設計一個能用相對聰明的窮舉法破解所有恩尼格碼的機器（後被稱為炸彈機）。雖然他也知道普通的窮舉法完全不可能在短短18小時內嘗試所有可能，但他相信存在更聰明的辦法來優化傳統的窮舉法並執著於用機器打敗機器的想法。

根據圖靈傳的描述，圖靈從小便痴迷於對機器的設計及製作。作為數學家的他雖然其手工方面並沒有什麼可圈可點的地方，但他設計的思想在當時來看卻是非常前衛的。那麼圖靈最開始設計這款機器是從哪裡得到的啟發呢？答案就是波蘭科學家馬里安.雷傑夫斯基的發現— 加密字母的循環。

圖2：圖靈傳

上期文章中我們講到了波蘭科學家們利用恩尼格碼無法用同一字母加密的缺陷，通過德國對恩尼格碼機使用時重複鍵入這一特點找出了加密字幕的循環並製作成記錄本。雖然連接板的引入大大增加了加密的可能性，但圖靈相信其中還是會有字母循環的出現。為了一勞永逸，圖靈萌生出了製造解密機器的想法，希望通過機器來代替人工來加速無休止的試驗。為了表述方便，我們使用上期文章中的例子假設字母 A 存在循環關係 A -> F -> W -> A。（請注意，因為接線板的引入，原本的字母循環關係會相應改變，這裡使用這個循環為例只是為了表述方便），並用圖3來表示整個字母的循環關係。

圖3：恩尼格碼運行原理

（細心的讀者可能會問不是說恩尼格碼不會用同樣的字母加密其本身嗎，為什麼經過三次加密之後 A 又回到了 A 呢？筆者在這裡強調一下恩尼格碼不用同樣字母加密其本身的特點指的是同樣字母無論輸入多少次都不會得到該字母的輸出，但如果輸入不同字母得到的輸出則可能是之前輸入過的字母。）

我們先假設字母 A 在連接板上連接著字母 B 並把轉子位子調在000。在這裡，P1 和 P4 的字母應該是相同的，因為接線板的另一頭連接著同樣的字母 A。也就是說，如果我們能檢測出 P1 和 P4 的值是相等的，那麼這時的轉子及連接板的設置可能就是正確的當日密鑰。如果檢測出不正確，那麼我們便假設接線板上 A 連接著字母 C，並以此類推。如果在試驗了 A 和另外 25 個字母連接之後都不能得到 P1 = P4， 那麼其中一個轉子的位子便會移動一位。如果我們能試驗所有接線板連接以及所有轉子設置，那麼我們一定能在某一時刻或者某幾個時刻得 P1 = P4。當然，這只是字母 A 輸入所得到的當日密鑰，我們還需要測試其餘 25 個字母。

這就是圖靈希望製造炸彈機最初的想法。在此想法之後，圖靈便開始著手設計炸彈機。從圖4大家可以看到炸彈機上有很多三個一組的轉子，每組轉子都相當於一個恩尼格碼機器，用於並行試驗上述的每種可能性。炸彈機在得到當日密鑰之後會自動停止轉動，並顯示出窮舉後所得來的當日密鑰。但問題是，這樣的炸彈機根本不會停止。原因很簡單，因為上述的方法還是傳統的窮舉法。而在第二期的文章里已經講到了這種窮舉法的不可行性。於是圖靈對炸彈機的設計進行了改進。

細心地讀者可能已經發現了上述窮舉法所存在的不必要的重複。因為如果某一轉子設置（比如000）的情況下 A 在連接板上連接 B 不能得到 P1 = P4， 我們不僅能得出在該轉子設置的情況下 A 和 B 是錯誤連接，我們還能得到 P2 和F，P3 和 W 的連接也是錯誤的。我們在接下來相同轉子設置的試驗中就可以不測試這幾種可能性了。這個發現不僅大大減少了試驗的可能性（特別是在字母循環很長的情況下），電路的設計也使得機器可以瞬間檢測到這些多餘的可能性並同時取消對這些可能性的試驗。

雖然有了上述的改進，炸彈機的效率仍然很低，這也一度困擾了圖靈及其整個團隊很長一段時間。直到1941年英國海軍捕獲德國 U110 潛艇並獲得密碼本和密碼機之後情況才得到了好轉。恩尼格碼的密碼本（詳見上期文章）記錄著一個月每天的當日密鑰。英國人利用這段時間破譯了大量的德國電文並從中發現了致命的規律，比如每天早上六點德國會定點發送天氣預報，每封電文的結尾都會提到希特勒萬歲。正是這個規律性的使用瓦解了恩尼格碼的傳奇。因為英國人可以用一個已知解密後的固定辭彙，比如 wetter（天氣），來對比加密後的文字。因為恩尼格碼不能用同樣的字母加密其本身，在對比過程中便能直接去除很多可能性。

如圖5所示，我們將 wetter 這個詞逐字對比密文，如果出現同樣的字母（顯示為紅色）便向右移動一個字母在進行比對，直到沒有相同字母出現為止，我們得到 wetter 可能對應的密文是 ERSMCW （來自位置2的對比）。這時我們可以得到一個字母循環 W -> E -> R -> W。我們把這個循環按照圖3的方式排列並對比 P1 和 P4 的值。在知道明文和密文的對應之後，我們便知道了轉子之間的距離。比如在這個情況下，如果轉子1的位置為0，那麼轉子2的位置一定為1，（經過一次加密所得）同樣轉子3的距離一定為5（經過5次加密所得）。知道轉子間的固定距離之後，炸彈機便可以再次減少大量的試驗次數。經過這次改進之後，炸彈機的效率再次得到了提高。

圖5：明文及密文對比

值得一提的是，在同事湯米弗勞爾斯的幫助下，圖靈和同事們再次改進了炸彈機的硬體設施，使得炸彈機的效率再次得到提高。至此，炸彈機能夠在20分鐘左右的時間內破譯恩尼格碼的當日密鑰，使得二戰的局面得到了改善。

其實炸彈機可以說只是圖靈在機器設計概念上的一次實踐。早在戰爭前，圖靈便投入大量精力進行數學和機器的研究，為現代計算機的誕生打下了堅實的基礎，特別是其在1936年提出的圖靈機概念更是現代計算機，程序及演算法設計的雛形和基礎。從下期開始，我們將從探索圖靈機開始，打開現代計算機及程序設計的大門。

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！