2015年8月16日 星期日

電影「模仿遊戲」與史實

       電影《模仿遊戲》一開始就表明了它是「based on a true story」,意思是說「根據事實改編」,到底改編了多少,其實是隨導演和劇作家高興。所以,電影裡的情節跟史實有非常大的出入。
       我比較有興趣的是電影裡那一部破解密碼編解序號的機器 Bombe 相關的原理,以及它跟電腦的關係。

       首先,Bombe 的原始點子是出自波蘭的數學家,而其原型機 Bomba 也是在波蘭做出來的(波蘭出天才數學家,這也是全球聞名的)。Alan Touring  Bombe 的貢獻是突破性的改良(雖說是改良波蘭的 Bomba,但同時也是破了波蘭數學家無法突破之處)。其次,雖然 Bombe 也勉強可以算是專用型計算機器(computing machine),但它不是我們一般通稱的「電腦」,因為我們一般通稱的電腦必須是通用型的計算機器。

一、 Alan Turing 現代電腦的關係
        Alan Turing 被稱為電腦之父,是因為他在一篇 1937 年的純數學論文 "On computable numbers, with an application to the Entscheidungsproblem" 上提出了現代通用型電腦(可程式化電腦)的基本原理(該文完成於 1936年,但是在 1937 年刊出 ),並且在 1946 年向 National Physical Laboratory 提出了一份相當完整的可程式化電腦設計書(這部電腦被稱為Automatic Computing Engine,簡稱 ACE),把電腦的計算功能與程式記憶分開來。然後 John von Neumann 才在這基礎上進一步發展,而 1947 年提出現代電腦的完整架構
       德國工程師 Konrad Zuse 1941年完成的 Z3 是第一部具有可程式化功能的數位化電腦,但是它的指令集不齊全。美國在 1946 年完成的 ENIAC 具有完整的控制指令,是第一部體現 Alan Turing 1937 年那篇論文構想的「Turing machine」,但是它欠缺電腦程式的記憶單元
       因此,雖然 John von Neumann 經常被稱為現代電腦架構之父,現代可程式化電腦的誕生卻跟 Alan Turing 有更緊密的關係。
       如果想進一步了解 Alan Turing 現代電腦的關係,B. Jack Copeland Diane Proudfoot 合寫了一篇 "Alan Turing: Father of Modern Computer" ,很值得看。

二、破解德國密碼加密機 Enigma machine 的過程
        The Imitation Game」是 Alan Turing 1950 發表的一篇論文 "Computing Machinery and Intelligence的第一章標題,該文內容在討論人工智慧與計算機原理,跟 1940年代完成的各版解碼機 Bombe 沒什麼關係。
       Enigma machine 就是一架具有密碼加密encryption功能的打字機,它讓你在鍵盤上輸入的字母被改變成另一組字母,因而讓有意義的通訊內容變成一堆無法解讀也無意義的字母堆砌。它誕生於1920年代,有商用版和軍事版,結構越複雜,解密越困難。
        因為這個加密的過程可以被寫成數學的矩陣方程式,因此讓數學家有插足之處。
       波蘭因為擔心德國入侵,因此波蘭密碼局(Polish Cipher Bureau)一直想破解結構較複雜的軍用加密器。1929年左右,波蘭密碼局意識到數學家可能會有助於破解加碼機的結構,因此她跟一個大學合作開授密碼學,這個班裡後來有三個人在 1932 年加入波蘭密碼局,其中最有名的就是 Marian Adam Rejewski,是他利用法國情報單位所提供的有限線索倒推出德國軍用加密機 Enigma 的結構原理,並指導波蘭當局複製出德國的加密機。這個複製品被稱為 Polish Enigma doubleMarian Rejewski 同時也在 1938 年發明波蘭版的 Bomba
        德國早期的加密機是用三個滾輪來決定加密的方法,有了波蘭的Polish Enigma double之後,只要決定每一份文件加密時這三個滾輪的所在位置(通常用字母代表這三個滾輪的位置),就可以利用 Polish Enigma double 來破解加密過的文件。
        德國加密文件的規則是:1)每一份文件的前三個字母(譬如「HIT」)用名碼指示接續下來的後面六個字母(譬如「KOSRLB」)要如何解密:如果接收者看到一份文件的前三個字母是「HIT」,他就把 Polish Enigma double 的三個滾輪分別設定在「H」、「I」、「T」三個位置,然後把「KOSRLB」這六個字輸進 Polish Enigma double,會得到「LERLER」,破解出來的字一定是前三字和後三字相同(叫 indicators,以免傳輸過程有任何錯誤。(2)把 Polish Enigma double 的三個滾輪設定在「L」、「E」、「R」三個位置,再把整份文件(不含剛剛已經用掉的前 3+6 個字母)輸入 Polish Enigma double 就會得到破解出來的文件。因此,真正需要破解的不是整份文件,而是只需要破解三個 indicators:用文件前三個未加密的字母和接下來六個加密的字母猜出三個 indicators的字母。Bomba 就是設計來破解出這三個滾輪位置的。
        波蘭人發現,有一個德國加密員永遠用他女朋友的名字「Cillie」拆成兩組,前三個字「Cil」當未加密的前三字母,用「lie」當 indicators,所以只要是他傳送的文件,都不需要猜 indicators,直接可以用 Polish Enigma double 去解密。有些人喜歡把希特勒的名字「HITLER」拆成兩組,「HIT」當前三個未加密的字母,「LER」當  indicators。但是當這些簡單的方法都不適用時,就必須要仰賴 Bomba 的機械化作業來硬解。
        波蘭人破解出德國的 Enigma 後不讓任何國家知道。後來戰事發展越來越激烈,而德國的 Enigma 結構也越來越複雜(譬如,滾輪變成五選三個,而非固定的三個;所以除了要選三個字母,還要猜三個滾輪的位置),波蘭需要跟盟軍合作對抗德國,也需要盟軍協助破解較複雜的 Enigma,因而在 1939 年把他們所知道的機密告知英國和法國。
        英國也在很早的時候就已經聘雇數學家在協助破解密碼。Alan Turing Gordon Welchman 這兩位劍橋畢業的數學家是在 1939 年被招募到電影裡的工作場所 Bletchley,並且聽取有關波蘭破解德國家加密機 Enigma 的相關簡報。Gordon Welchman 被指派的工作跟 Bomba 無關,但是他想出一個簡化分析的技巧,並且告知 Alan Turing,使得 Alan Turing 可以把滾輪所需要解的參數從數千個降低到只剩數個。Alan Turing Gordon Welchman 把他們的設計拿去給一位傑出的工程師 Harold “Doc” Keen,終於在 1940 年造出第一架 Bomba。但是,要到 1941 年英國捕獲一艘 U-110 潛艦,並且獲得艦上完整的機密文件之後,又成功第欺騙德均讓他們以為 U-110 上面所有的文件都已沉沒,破解德國海軍機密電文的工作才算完成。
        所以,Bomba 不是像電影裡那樣地由 Alan Turing 親手打造出來的。而寫信給邱吉爾的並非 Alan Turing,而是他的團隊一起聯名。
        最重要的歷史扭曲是底下這個:Bomba 完成後英軍和聯軍並沒有節制地使用他們破解的情報,或者故意任由補給船被 U-boat 擊沉。事實上英美方不但引導補給船避開 U-boat 的位置,還配出海空軍力去狙殺  U-boat
        1941 年起 U-boat 很難再發現盟軍運輸艦的蹤跡,反而 U-boat 老是被盟軍追殺,艦隊總指揮 Admiral Doenitz 因此懷疑海軍的Enigma 已被破解,而詢問德軍最高統帥層(German High Command), 層峰卻告訴 Admiral Doenitz 不需要擔心,並且把戰局逆轉與情報洩露歸罪於其他原因:英軍的高頻定向器(High-frequency direction finding)技術突飛猛進,因此很容易發現通訊中的 U-boat 位置;盟軍高空偵察技術突破,因而較容易找到 U-boat 位置;可能是德國間諜洩密等。而盟軍也很配合,他們總是在破解出電文並知道 U-boat 位置後,先派出偵察機去該海域偵查,以便讓德軍可以相信盟軍的情報來自於高頻定向與高空偵察技術的突破。
       這還不是故事結束的地方。 Admiral Doenitz 後來還是改了 Enigma,而英軍則繼續設法破解。
       實情遠比電影《模仿遊戲》更複雜而好玩,有興趣可以去看一篇易讀而又可靠的文章 Solving the Enigma: History of the Cryptanalytic Bombe,作者 Jennifer Wilcox 是美國 Center for Cryptologic History, National Security Agency 的館員。
       總之,好萊塢的電影看看就好,跟周星馳的電影一樣,不能太當真!