究竟圖靈是怎樣破解德軍的密碼系統 Enigma ?
http://goo.gl/6o7ylZ

20 十二月 作者 果汁機大叔

http://www.ilord.com/images/enigma/enigma-installed-rotors-100.jpg

相信今天不少人也會留意到關於英國著名數學家、密碼學家、電腦科學之父 阿蘭圖靈
的故事，
原因當然是平安夜當日英國女王伊莉莎白二世赦免了 阿蘭圖靈
於上世紀因同性戀行為而被定的罪。

今天不少媒體也有報導這件事，亦有介紹 圖靈 生前的主要事跡。

當中 圖靈 在二戰時破解了德軍的 Enigma Code，但其實 Enigma 是甚麼，怎樣運作，
又是怎樣被破解的？

有興趣的網友們其實可以看看 Numberphile 關於 Enigma 的特輯，
兩部短片分別介紹了 Enigma 的運作方式 (包括商用及納粹德軍所用的版本)，
以及 圖靈 是如何利用 Enigma 的漏洞破解了這套令德軍引以為傲的密碼系統。

158,962,555,217,826,360,000 (Enigma Machine) - Numberphile
http://youtu.be/G2_Q9FoD-oQ

早於二戰發生之前，Enigma 已在 1920 年代被用於商業之中，
目的是加密商業公司內部的機密文件。

Enigma 的最大特色在於加密時不會像傳統密碼同一明文翻譯成同一密文，
例如 MM 翻譯時必定為 AA/BB 或 CC，
而 Enigma 則可以把源訊息中同一個字母轉換成不同的字母，
例如把訊息 MM 轉成密文 SX。

同時亦可以把不同的字母轉換成同一字母，例如訊息 KL 轉成密文 AA。

換言之，Enigma 並非如傳統密碼中基於密碼表簡單地把訊息加密，
令到普通的解密手法失效。

而 Enigma 的原理在於它有三個旋轉盤，旋轉盤由錯綜複雜的電路組成，
每一旋轉盤共有 26 個電路選項。

透過這些電路，在按下明文某一字母(如 A)時令代表密文某一字母(如 E)的電燈亮著，
因此，商用 Enigma 密碼機
可以擁有 26 × 25 × 26 = 16,900 (注意不是 26×26×26) 個組合，
而且軍用的 Enigma 更是要在共五個旋轉盤
(標記為I,II,III,IV,V)中選擇(其後增為 8 個)
其中三個(即總旋轉盤組合為 5×4×3= 60)。

但是納粹德軍(海軍)所使用的 Enigma 還不是如此簡單。

因為德軍所使用的 Enigma 密碼機還設有 Plugboard (接線板) 的裝置，
可以把共十對的字母互換，例如把 Q 轉換為 E ，E 同時轉換為 Q，
令加密組合數量大幅增加，總共為 158,962,555,217,826,360,000 個組合。

德軍每月都會有一張以可融化的墨製成的 code sheet，
用來選擇當天 Enigma 的旋轉盤，設定旋轉盤及接線板。

密碼表每天都會改變組合，因而德軍認為他們的 Enigma 密碼系統無可能被破解。

Flaw in the Enigma Code - Numberphile
http://youtu.be/V4V2bpZlqx8

可是，Enigma 密碼系統並非完美，因為它存在兩個漏洞，
第一個就是任何字母經過 Enigma 密碼機的轉換後，
永遠無可能是「自己」(即是當輸入明文 A 時，密文必不為 A)。

這個漏洞成為了其中一個破解的關鍵，因此盟軍解密團隊和圖靈就利用這個漏洞，
先估計德軍所發出的訊息的可能詞彙，例如每天 6 時德軍也會發出的「天氣報告」，
德文為「wetterbericht」，再對應盟軍接收到的密文，
以上述漏洞估計訊息中哪一段密文最有可能為「wetterbericht」，
如果發現組合有重覆，例如出現估計密文 T 是明文 T 的話則錯誤，要再次推測。

再而逐一測試德軍 Plugboard 及旋轉盤的組合。

例如一開始估計旋轉盤是 1-1-1，以及 plugboard 上「TA」是連接著一起，
再以此推測其他 Plugboard 的連接方法，但如果後來又遇到「TX」，
當中 T 不可能出現兩次，那麼代表之前所有推測都是錯誤的，包括中間所作的假設，
這就是第二漏洞。

這要再次假設可能「TB」是連接著一起。

直至嘗試到「TZ」或成功解到「wetterbericht」為止。

如果沒有一個是正確，那麼代表旋轉盤的設定錯誤，要嘗試下一個，即 1-1-2。

但是，這樣的人手破解方式實在太慢，圖靈就基於這樣的原理，
製造出專門破解德軍 Enigma 密碼的密碼破解機「炸彈」，不斷嘗試這些組合，
而「炸彈」解密機可以在 20 分鐘內破解出德軍每天的組合，從而得知德軍的加密訊息。

資料來源：維基百科、Numberphile
http://zh.wikipedia.org/wiki/Enigma

--
Q 臺灣人的需求金字塔 ◢◣ █ 安全、無毒的食物
S ◢██◣ █ 有錢結婚生養小孩
W ◢████◣ █ 買得起的房子
E ◢██████◣ █ 被老闆當人看
E ◢████████◣ █ 下班還來得及和親友吃晚餐
T ▄▄▄▄▄▄▄▄▄▄▄▄ █ 租得起房子█ 找得到工作

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.134.89.190
※ 文章網址: https://www.ptt.cc/bbs/ScienceNote/M.1425328756.A.B47.html