藝術品的解析：恩尼格碼的破解

題記：破解恩尼格碼， 先從給圖靈提供肩膀的巨人—馬里安.雷傑夫斯基講起。

上一期我們介紹了恩尼格碼機的原理及其在商業及軍事方面的運用（閱讀：《硝煙中的藝術品——恩尼格碼》）。 那麼如此周密的加密系統最後是如何被科學家們破解的呢？本期我們先從1932年波蘭人最開始嘗試破解商用恩尼格碼的時候講起。

早在第二次世界大戰開始之前， 德國便在商業情報交換上使用了恩尼格碼機。 當時在德國密碼處工作的施密特非常厭惡納粹專制， 便向法國情報人員提供了有關恩尼格碼機的操作和設計的資料。

但法國並沒有重視這件事， 畢竟當時德法兩國國力還是存在相當的差距， 法國人覺得即便是沒有破解這種密碼也不會對戰爭造成太大的影響， 便在提出德軍密碼無法破解之後草草放棄對恩尼格瑪機的研究。 然而當時波蘭的處境卻遠遠比法國危險。 由於凡爾賽條約將德國的大片領土劃歸給波蘭， 波蘭便是德國發動戰爭的第一目標國家。 這樣險峻的形勢促使了波蘭密碼學的大躍進。 在波蘭的要求下， 法國把從施密特那裡得來的情報交給了波蘭人。 波蘭人通過恩尼格碼設計和使用上的缺陷破譯了商用恩尼格碼機。

當時的商用恩尼格碼機上只有三個轉子。 每封電文的金鑰（轉子起始位置）由電報發送方隨機選取， 並重複兩次輸入並由當日金鑰加密後在電報最開始的地方發給接收方。 例如發送方選取ABC作為該電文的金鑰， 操作人員會在恩尼格碼機上連續輸入兩次ABC， 並由當日金鑰加密成為六個字母。 該六個字母便被放到了每封電文的最前面。

接收方在接到電文之後由當日金鑰解密最開始的六個字母， 並按照解密後的資訊將轉子位置設為ABC, 並開始解密電文。

這種商用恩尼格瑪機在設計和操作上存在著致命的缺點。 在設計上， 首先無論一個字母被加密多少次， 都不會得到同樣的字母。

也就是說字母A無論被加密多少次都不可能得到字母A。 其次， 恩尼格瑪機畢竟是機械產品， 其轉子總會有規律地週期迴圈。 在操作上， 每封電文最開始的六個字母也是由迴圈所得。 基於這些缺陷， 波蘭數學家馬里安.雷傑夫斯基在每天截獲的大量電文中找出了判斷轉子初始位子的方法。 現使用《The Mathematics of Encryption: An Elementary Introduction》一書中的一個例子來說明具體的判斷方式。

假設波蘭人截獲四封電文， 其中每封電文的開頭六個字母分別為：

根據上述的操作方式， 每封電文的第一個和第四個字母是同一字母加密而來， 於是通過上面四封電文， 我們可以得到第一個及第四個字母的聯繫如下：

如果每天可以得到足夠多的電文， 那麼上面的關係表便可以補充完整如下：

仔細觀察這個表格， 我們不難發現字母關係中會有如下迴圈：

同樣對第二和第五， 第三和第六個字母我們也可以寫出類似的迴圈。 由於每天的當日金鑰不同， 我們所得到的迴圈也不會相同。 由於當時商用的恩尼格碼機還沒有使用連接板， 窮舉法便是一件可以實施的方法了（具體原因請參見上期內容）。於是波蘭人按照施密特提供的情報複製出了恩尼格碼機，並一個接一個的實驗轉子的不同位置然後記錄下他們所產生的字母迴圈。例如：

第一個和第四個字母對應表中有4個迴圈，長度分別為 3， 9， 7， 7

第二個和第五個字母對應表中有4個迴圈，長度分別為 2， 3， 9， 12

......

為了將窮舉法自動化，雷傑夫斯基在恩尼格碼的基礎上設計了一台能同時驗證所有轉子位置的機器。並取名為炸彈（La Bomba）。當對所有轉子位置所產生的迴圈及長度都記錄下來之後（此稱記錄表），波蘭人便從每日截獲的大量電文中寫出字母迴圈圈，然後根據迴圈圈的數目和長度從記錄表中檢索出相對應的轉子位子，即是當日的金鑰。得到當日金鑰之後，波蘭人便用其破解每封電文的前六個字母來獲得電文的金鑰，並用之破解了剩餘的電文。

然而波蘭人對恩尼格碼的破解在1938年結束。為了戰爭準備，德國人同時在幾個方面加強了恩尼格碼的加密能力。首先，德國軍方將原來的3個轉子增加到了5個，使用時隨機在5個轉子中選3個。這意味著光這點改變波蘭然便需要5 x 4 x 3 = 60 台原先的“炸彈”才能破譯恩尼格碼。這已經大大超出了波蘭當時的預算。其次，德國人在恩尼格碼機上加入了接線板，允許6組字母交換，並最終增加到允許10組字母交換。從上期內容我們知道，接線板的加入大大增加了金鑰的總數。最後，德國意識到了重複操作的隱患，取消了每封電文開頭用當日金鑰加密電文金鑰的方式，取而代之的是一張密碼紙，列出一個月內每天的金鑰。每天的金鑰在密碼紙的設定下于第二天更新，而這張密碼紙每月更新。為了增加保密性，密碼紙經過特殊處理，紙上的內容遇水即消失。同時更新如此多的加密方式大大的超出了波蘭的預期。由於時間的緊迫以及預算的短缺，波蘭不得不放棄了對軍用恩尼格碼的繼續研究。1939年9月，德國閃襲波蘭佔領華沙，波蘭滅亡。所幸的是對恩尼格碼的研究成果並未隨著波蘭的滅亡而消失。波蘭在戰前已將波蘭製造的恩尼格碼機以及“炸彈”的設計圖紙交給了英國和法國。恩尼格碼便這樣度過了英吉利海峽來到了英國。在那裡等待它的將是最後的滅亡。

經過上述一系列的改進， 商用恩尼格碼機的缺陷基本上已經不存在了。轉子的增加及接線板的設計使得轉子機械運動所帶來的週期迴圈的缺陷變得微不足道。改變後的操作方法也杜絕了之前每封電文開頭所出現的規律性重複。在本文開頭中所提到的種種缺陷，如今僅剩的便是恩尼格瑪機不會用一個字母加密其本身這一特性了。那麼英國的科學家們又是如何在波蘭人研究的基礎上，從這個僅剩的缺陷中撕開一條口子破解了恩尼格碼呢？且看下回分解。

歡迎關注《走進電腦文化史》的系列文章：

十大熱門文章

END

長按指紋 > 識別圖中二維碼 > 添加關注

窮舉法便是一件可以實施的方法了（具體原因請參見上期內容）。於是波蘭人按照施密特提供的情報複製出了恩尼格碼機，並一個接一個的實驗轉子的不同位置然後記錄下他們所產生的字母迴圈。例如：

第一個和第四個字母對應表中有4個迴圈，長度分別為 3， 9， 7， 7

第二個和第五個字母對應表中有4個迴圈，長度分別為 2， 3， 9， 12

......

為了將窮舉法自動化，雷傑夫斯基在恩尼格碼的基礎上設計了一台能同時驗證所有轉子位置的機器。並取名為炸彈（La Bomba）。當對所有轉子位置所產生的迴圈及長度都記錄下來之後（此稱記錄表），波蘭人便從每日截獲的大量電文中寫出字母迴圈圈，然後根據迴圈圈的數目和長度從記錄表中檢索出相對應的轉子位子，即是當日的金鑰。得到當日金鑰之後，波蘭人便用其破解每封電文的前六個字母來獲得電文的金鑰，並用之破解了剩餘的電文。

然而波蘭人對恩尼格碼的破解在1938年結束。為了戰爭準備，德國人同時在幾個方面加強了恩尼格碼的加密能力。首先，德國軍方將原來的3個轉子增加到了5個，使用時隨機在5個轉子中選3個。這意味著光這點改變波蘭然便需要5 x 4 x 3 = 60 台原先的“炸彈”才能破譯恩尼格碼。這已經大大超出了波蘭當時的預算。其次，德國人在恩尼格碼機上加入了接線板，允許6組字母交換，並最終增加到允許10組字母交換。從上期內容我們知道，接線板的加入大大增加了金鑰的總數。最後，德國意識到了重複操作的隱患，取消了每封電文開頭用當日金鑰加密電文金鑰的方式，取而代之的是一張密碼紙，列出一個月內每天的金鑰。每天的金鑰在密碼紙的設定下于第二天更新，而這張密碼紙每月更新。為了增加保密性，密碼紙經過特殊處理，紙上的內容遇水即消失。同時更新如此多的加密方式大大的超出了波蘭的預期。由於時間的緊迫以及預算的短缺，波蘭不得不放棄了對軍用恩尼格碼的繼續研究。1939年9月，德國閃襲波蘭佔領華沙，波蘭滅亡。所幸的是對恩尼格碼的研究成果並未隨著波蘭的滅亡而消失。波蘭在戰前已將波蘭製造的恩尼格碼機以及“炸彈”的設計圖紙交給了英國和法國。恩尼格碼便這樣度過了英吉利海峽來到了英國。在那裡等待它的將是最後的滅亡。

經過上述一系列的改進， 商用恩尼格碼機的缺陷基本上已經不存在了。轉子的增加及接線板的設計使得轉子機械運動所帶來的週期迴圈的缺陷變得微不足道。改變後的操作方法也杜絕了之前每封電文開頭所出現的規律性重複。在本文開頭中所提到的種種缺陷，如今僅剩的便是恩尼格瑪機不會用一個字母加密其本身這一特性了。那麼英國的科學家們又是如何在波蘭人研究的基礎上，從這個僅剩的缺陷中撕開一條口子破解了恩尼格碼呢？且看下回分解。

歡迎關注《走進電腦文化史》的系列文章：

十大熱門文章

END

長按指紋 > 識別圖中二維碼 > 添加關注