Colossus Mark 2

奇謎與炸彈、鋸鰩與巨像——可程式化數位電腦的誕生

奇謎與炸彈、鋸鰩與巨像——可程式化數位電腦的誕生

奇謎與炸彈、鋸鰩與巨像——可程式化數位電腦的誕生

上一篇〈比圖靈更早破解奇謎機的人〉寫到,最先破解奇謎機的其實是波蘭數學家瑞耶夫斯基,而不是圖靈。不僅如此,由於納粹後來又變更加密方式,結果圖靈設計的炸彈解密機用不到兩年就失去作用,最後破解密碼的是另外由別人設計的「巨像」(Colossus) 電腦,而這也成為史上第一台可程式化的數位電腦。

萬一波蘭人的炸彈機不管用

1939 年七月,英國應邀前往波蘭密碼局,得知三位波蘭數學家已經破解奇謎機後,隨即招募語言學家與數學家進駐布萊切利莊園,秘密展開破譯德軍密電的工作。

其實奇謎機的複雜程度的確難以破解,只因德軍將訊息密鑰重覆加密兩次,產生某種規律,才讓波蘭人發現可以忽略接線板的變化,只要檢測轉輪的十萬種排列組合,就能找出正確設定及密鑰。他們發明炸彈機來進行檢測,六台同時運作,每台測 17,576 種,兩個小時就能破解密鑰。只不過後來德軍將轉輪改為五選三,排列組合增加為十倍,變成一百萬種(註1),資源有限的波蘭密碼局才向英、法求援。

奇謎機,筆者於布萊切利莊園拍攝。

英國當然有能力造出 60 台炸彈機來應付,但萬一哪天德軍發現漏洞,不再重覆加密兩次訊息密鑰,炸彈機就不管用了。因此當布萊切利莊園的「政府代碼與密碼學院」(Government Code and Cypher School,簡稱 GC&CS) 於九月成軍後,便基於這個前提展開研究。

圖靈的炸彈機

根據波蘭密碼局過去幾年所破譯的德軍密電,內文中常會出現特定字詞,例如每天清晨的電報總會提到天氣,而「希特勒萬歲」也常出現在電報結尾。雖然德軍後來變更加密方式,但這些字詞的模式卻依然沒變,成為布萊切利莊園解密的破口。

當然,由於同樣字母每次的加密結果都不一樣,就算在密電中找到這幾個字詞,也無法直接據以破譯整篇內容。然而圖靈在比較它們加密前後的字母後,卻發現了類似瑞耶夫斯基所發現的循環特徵,例如某則電報中,hitler 的密文是 TMRJSH,那麼 h -> T、t -> R、r -> H 便形成一個循環,而這就可以用來檢測密鑰,也就是奇謎機的設定。

在圖靈眼中,這樣的循環就像是遞迴函數,而若以電路的角度,又相當於構成電流迴路。他結合這兩項洞見,於 1940 年初設計出模擬奇謎機的機器,可以自動逐一比對出符合的設定。這台機器高、寬各約兩米,也叫「炸彈機」(Bombe),但原理與構造與波蘭的炸彈機完全不同,共有 108 個轉輪,每 3 個一組模擬一台奇謎機,相當於 36 台不同設定的奇謎機同時運作。

圖靈設計,安裝於布萊切利莊園的炸彈機。圖片來源:Wikipedia

問題是,倘若訊息密鑰的破綻不復存在,接線板互換字母的影響就無法排除,所要面對的可能性將多達 1.59 x 10^20 種(註2),如此龐大的天文數字,怎麼可能一一加以比對?

所幸實際上並不需要進行那麼多種嘗試。既然在同樣設定的奇謎機輸入密電就會還原成明文,代表轉輪在同樣位置時,兩個字母一定是互相轉換,例如輸入 A 轉換成 C,則輸入 C 一定轉換為 A,不會是其它字母,這樣就排除掉很多可能性。圖靈的同事便針對此一特性設計了「對角線電路板」,加裝到炸彈機後,大幅縮短查驗密鑰的時間。此外,經由語言學家協助歸納出特定字母通常會伴隨著哪些字母的機率,圖靈也將貝氏定理(註 3)納入炸彈機的運作規則,可以更快找到密鑰。

鋸鰩現身

第一台炸彈機於 1940 年 3 月安裝啟用,五月成功破譯四月下旬的德軍密電。隨著越來越多台炸彈機完工上線,破解速度也越來快,順利的話一個小時就能找到密鑰,最慢也能在 36 小時內破解。不過到了 1941 年中,突然零星出現迥然不同的密電,上面根本不是摩斯電碼,很可能就是德軍曾在電報中提過的新型加密系統——鋸鰩 (sawfish)。

鋸鰩加密系統是以五碼的國際電傳代碼表示字母,同時改以「羅倫茲加密機」(Lorenz cipher) 進行加密,它不像奇謎機那樣將字母置換成另一個字母,而是將二進位代碼進行 XOR 的邏輯運算。例如明文 A 的代碼是 11000,密鑰 C 是 01110,兩者結合後的密文就成為 10110 (也可以用二進位的加法來理解,加 0 不會改變,加 1 則 0 會變成 1,而 1 會變成 0)。

羅倫茲加密機和奇謎機一樣有環環相扣的轉輪,每加密一個字母,轉輪的位置就會跟著改變;不過它的轉輪多達 12 個,其中 10 個分成兩組,代表兩個 5 碼的密鑰,對明文進行兩次加密。每個轉輪各有 23~61 個數量不等的針頭,針頭有上下兩種位置代表 1 或 0,啟用後要經過 1.6 x 10^19 個字母後才會重新循環(註 4),電報再多也累積不了這麼多字數,不用擔心因此洩密。若要以暴力法測試所有組合更絕無可能,因為全部有 501 個針頭,共有 2^501 種變化,宇宙所有粒子加起來都沒這麼多。

勞倫茲加密機,上方的 10 個轉輪分成左右兩組,各代表一個密鑰。德軍後來在中間又增添了兩個轉輪,以增加複雜度。圖片為筆者在布萊切利莊園拍攝。

不過布萊切利莊園還不知道他們要面對的是比奇謎機更難對付的怪物。他們只知道「魚」(這是他們給這新型密電取的名稱)的密鑰有十碼、加密方式與奇謎機截然不同,因此炸彈機派不上用場,必須從頭來過。然而之前破解奇謎機是基於德國密碼局的內賊所提供的資料,但這次資訊全無,對加密原則與機器構造都一無所知的情況下,根本不知從何下手。沒想到就在大家一籌莫展之際,一名德軍通訊兵的無心之過自動奉上了一個破口。

兩封密電

1941 年 8 月 31 日,英軍截獲兩封「魚」的密電,內容看似不同但開頭竟然完全一樣。原來德軍某單位收到的電報內容不完整,於是要求發送方再傳一次;怎知發送者卻擅自刪改成比較短的版本重發,而且沒按規定更換密鑰,才會開頭一連串的二進位代碼都一樣。

既然知道這兩封密電的內容大同小異,布萊切利莊園的團隊就能加以分析比對。他們很快認出這是國際電傳代碼,而且是以 XOR 的邏輯運算進行兩次加密,但仍看不出加密原則,也就無法推導出羅倫茲加密機的構造。

直到三個月後,剛加入解密團隊沒多久的劍橋大學研究生圖特 (W. T. Tutte) 才打破困局。他在紙上塗塗寫寫,嘗試密文的各種排列方式後,發現第一個轉輪的循環週期是 41。從糾纏一團的毛線球中抓出線頭後,要理出頭緒就容易多了,1942 年初,他們總算搞清楚所有轉輪的週期,羅倫茲加密機的輪廓終於從迷霧中浮現出來。

圖特 (W. T. Tutte)。圖片來源:Wikipedia

不過這只是解密的第一步,鋸鰩的設定有 2^501 種,要從中找出密鑰比大海撈針還難。幸好他們不必盲目地嘗試,因為環環相扣的轉輪有一定的轉動規則,使得加密後的字母與隨機分布仍有偏差,圖靈花了半年時間研究其中脈絡後,發展出一套方法,可大幅縮減搜尋密鑰的工作量。

雖然從大海撈針進展為稻草堆裡找一根針,檢測的範圍仍相當龐大,得靠機器才能處理,就像用炸彈機破解奇謎機那樣。不過此時圖靈已另有要務,無法研發這樣的機器。這是因為德國海軍把原本三個轉輪的奇謎機改成四個轉輪,複雜度大增,需要更多部炸彈機才能及時破解。但一如當年波蘭密碼局求助於英國,如今飽受戰火摧殘的英國也需要美國奧援,才能大量建造炸彈機,而身為設計者的圖靈自然成為派赴美國的不二人選。

紐曼出馬

研發自動機器破解鋸鰩系統的重責大任落到了數學家紐曼 (Max Newman) 身上。紐曼是圖靈念劍橋大學時的數學教授,當年正是因為他的啟發,圖靈才寫出《論可計算數及其在判定性問題上的應用》這篇影響深遠的論文,裡面描述「通用計算機」如何模擬人類的思考。也因為這篇論文,圖靈才被英國政府找來設計破解奇謎機的機器。

圖靈在劍橋大學的數學教授紐曼 (Max Newman) 。圖片來源:Wikipedia

紐曼於 1942 年 8 月來到布萊切利莊園,兩個月後,柏林最高指揮部正式啟用鋸鰩系統,用來和陸軍各戰區的指揮中心聯繫。這代表「魚」的電報內容至關重要,很可能牽一髮而動全身,一定要盡快破譯。

11 月,圖特從圖靈的統計方法衍生出一套搜尋密鑰的演算法,紐曼很快於 1943 年初設計出執行這套演算法的機器「希斯.羅賓遜」(Heath Robinson,取自英國一位漫畫家的名字,他專門畫各種荒謬有趣的機器)。只要將兩卷代表所有可能密鑰的打孔紙帶餵進機器,裡面的電磁閥進行邏輯運算後,就能比對出符合的組合。但由於處理速度只有每秒一千到二千個字元,六月上線後,一天只能破譯一則密電。

負責承製機器的是英國郵政總局,他們的工程部門用電磁閥製造電話交換機已有多年經驗,圖靈的炸彈機也是由他們幫忙打造。其中一位工程師弗勞爾斯 (Tommy Flowers) 一開始就不看好「希斯.羅賓遜」,認為電磁閥的機械動作是拖累運算速度的元凶,唯有改用真空管才能突破瓶頸。事實上,當英國政府要求郵政總局製造更多炸彈機,以因應四個轉輪的奇謎機時,他就主張用真空管改造炸彈機才是正解,無奈建議未被採納。

弗勞爾斯 (Tommy Flowers)。圖片來源:Wikipedia

巨像電腦

其實這也不能怪主事者,畢竟真空管容易燒壞,如果因此中途停機反而前功盡棄,得不償失。不過弗勞爾斯在戰前為了改良電話交換機,用真空管做了不少實驗,對於如何維持真空管的使用壽命已有相當心得,於是他未待「希斯.羅賓遜」完工,二月時就向紐曼大膽請纓,讓他打造一台全面電子化的計算機。

得到紐曼的批准後,弗勞爾斯隨即著手設計,他帶領五十人的團隊經過 11 個月的努力,終於在 1943 年底完成「巨像一號」(Mark 1 Colossus),總共用了 1,600 個真空管,還能透過切換開關與插拔纜線的方式設定解密程式,成為史上第一台可程式化的數位電子計算機(註 5)。1944 年 1 月中,巨像一號運抵布萊切利莊園,2 月正式上線,隔月就能每天破譯 15 則密電,證明真空管計算機的優越性。

在英國政府的要求下,弗勞爾斯設計了「巨像二號」,使用 2,500 個真空管,速度是巨像一號的五倍,於 6 月 1 日安裝啟用。此時距離諾曼地登陸的 D-day 只剩五天,但有些跡象似乎顯示機密外洩,令盟軍猶豫是否要按計畫進行。所幸巨像二號及時破譯柏林最高指揮部的往來密電,確定德軍上下都被蒙在鼓裡,盟軍才放心於 6 月 6 日這天展開決定性的一役。

埋藏三十年的秘密

二次大戰結束後,英國政府為了保密,不但沒有表揚布萊切利莊園的相關人員,還勒令他們三緘其口,不得向任何人透露一絲訊息。這些人默默地回到自己崗位,圖特回劍橋大學完成博士學位後,一直待在學術圈,專門研究圖論;弗勞爾斯則在郵政總局繼續研發電子式電話交換機。

圖靈被「國家物理實驗室」延攬,開發基於馮紐曼架構的通用型電腦 ACE (Automatic Computing Engine)。馮紐曼架構需要有貯存資料與程式的裝置,圖靈找弗勞爾斯幫忙開發,但他表明無心於此,圖靈又一直等不到其他援手,耗了三年後決定放棄,接受老師紐曼的招手。

原來紐曼也在曼徹斯特大學開發馮紐曼架構的電腦,他招攬了當初「巨像」開發團隊中的部分成員,於 1948 年比馮紐曼團隊更早開發出簡易版的原型機。紐曼想到撰寫測試程式的最佳人選自然非圖靈莫屬,他還可以協助開發完整版的「曼徹斯特一號」(Manchester Mark 1)。

曼徹斯特一號」(Manchester Mark 1)。圖片來源:Wikipedia

圖靈欣然加入後,曼徹斯特一號於 1949 年完工啟用,隔年技術轉移給弗蘭提企業 (Ferranti),後者於 1951 年開始量產世上第一台數位化的通用型商用電腦,而馮紐曼自己設計的電腦直到這時才終於順利運作。

曼徹斯特團隊解散後,原本在電腦發展上居於領先地位的英國很快被美國超越。圖靈於 1952 年因同性戀罪名被處以化學去勢後,從此一蹶不振,兩年後他不知有心或無意咬下毒蘋果身亡,英國政府仍默不作聲。直到 1970 年代,布萊切利莊園的一位主管出書揭露這群幕後英雄的事蹟後,世人才知道圖靈等人的巨大貢獻,也才知道英國曾經擁有獨步全球的技術與人才。

註:

1. 原本三個轉輪有 6 種排列方式,每個轉輪有 26 個字母,一共有6 x 26 x 26 x 26 = 105,456 種變化。改為從五個轉輪任取三個後,就有 5 * 4 * 3 = 60 種排列組合,所以有 60 x 26 x 26 x 26 = 1,054,560 種變化。

2. 從 26 個字母任取十對字母互換的方式有:(26 x 25 / 2) x (24 x 23 / 2) x (22 x 21 / 2) x (20 x 19 / 2) x (18 x 17 / 2) x (16 x 15 / 2) x (14 x 13 / 2 ) x (12 x 11 / 2) x (10 x 9 / 2) x (8 x 7 / 2) / 10! ≒ 1.51 x 10^14 種,再乘以轉輪的變化,總共有1.59 x 10^20 種可能性。

3. 貝氏定理是指在已知的一些條件下,某一事件的發生機率。例如已知快篩試劑的敏感性(正確顯示確診者為陽性)是 95%,當快篩出現陽性,並不表示你有 95% 的機率確診,還要將台灣新冠肺炎的盛行率納入計算才知道確診機率。隨著案例的累積,盛行率也會不斷修正。

4. 12 個轉輪的針頭數分別為 43、47、51、53、59、37、61、41、31、29、26、23。由於他們彼此互質,因此最小公倍數就是全部的乘積。

5. 巨像一號、二號是專為破解羅倫茲加密機而設計,無法做其它計算,因此仍不是通用型電腦。第一台可程式化的通用型電子計算機,是美國陸軍於 1946 年發表的「電子數值積分計算機」(Electronic Numerical Integrator And Computer,簡稱ENIAC),但它也是靠切換開關和纜線來設定程式。

參考資料:

  1. Bombe – Wikipedia
  2. Cryptanalysis of the Lorenz cipher – Wikipedia
  3. Colossus computer – Wikipedia
  4. Thomas Harold (“Tommy”) Flowers: Designer of the Colossus Codebreaking Machines (computer.org)
  5. 《艾倫.圖靈傳》,Andrew Hodges 著,林鶯 譯,時報文化出版
Share on facebook
Share on twitter

更多文章

© 2021 張瑞棋