Enigma-2

比圖靈更早破解奇謎機的人

比圖靈更早破解奇謎機的人

比圖靈更早破解奇謎機的人

奇謎機登場

1918 年第一次世界大戰結束,隔年在協約國的共識下,長期被俄羅斯、普魯士、奧地利三國瓜分,已亡國 123 年之久的波蘭,終於得以復國。然而,波蘭又和剛從帝制變成共產國家的蘇聯打了兩年仗,才能確立領土。慘痛的歷史教訓讓波蘭不敢鬆懈,深恐宿敵蘇聯與德國仍不甘心,因此特地成立密碼局,以掌握這兩個鄰國的動向。

最初幾年,波蘭密碼局表現良好,大致都能破譯攔截到的電報,但到了 1928 年,德軍的密電突然變得完全無跡可循,怎麼樣都無法瞧出端倪。其實被難倒的不只是波蘭密碼局,早在兩年前,英、法兩國的情報單位就發現德國海軍的密電完全變了個樣,再也無法破譯。

原來德軍採用「奇謎機」(Enigma,也譯為「恩尼格瑪機」) 進行加密。這是德國工程師薛比烏斯 (Arthur Scherbius) 於 1918 年發明的機器,原本相當笨重,獲得軍方採用後,改善成約莫打字機大小。從奇謎機的鍵盤輸入明文後,電子訊號經過三個轉輪和一個反射器轉換成密文;收到密電那一方再從同樣設定的奇謎機輸入密文,就會解譯回明文。

這三個轉輪彼此銜接,每輸入一個字母後,第一個轉輪便轉一格,轉完一圈時,第二個轉輪會被帶動轉一格;第二個轉輪也是如此帶動第三個轉輪,就像里程表的個、十、百位那樣。不過奇謎機的轉輪有 26 格,代表 26 個字母,而且每個轉輪內部的線路配置不同(如圖),每轉動一格,26 個字母的轉換規則就變一次,共有 26 x 26 x 26 = 17,576 種變化,難怪密碼專家束手無策。

奇謎機的每個轉輪有不同接線方式。圖片來源:cryptomuseum.com

一萬兆種可能性

波蘭密碼局體認到光靠語言學家是不夠的,於是在 1929 年元月和波茲南大學 (Poznań University) 數學系合作,開設密碼學課程,希望從學生中發掘出破解密碼的人才。之所以選擇這所大學,是因為波茲南這地區之前被德國佔領,因此這些學生小時候都曾學過德語,才有能力理解德軍電文。

參加密碼學課程的學生中,以 23 歲的瑞耶夫斯基 (Marian Rejewski) 最有天分。不過他才受訓兩個月就取得碩士學位,未待課程結束就前往德國哥廷根大學進修,一年後才又回到波茲南大學,表面上只是教學助理,但其實祕密地在地下防空洞中為密碼局效力。而此時,德軍的加密方式又更上一層,變得更不可能破解了。

由於薛比烏斯曾把商用版的奇謎機也賣給其他對象,德軍為了確保他人無法用來破解密電,於是在1930 年中變更設計,成為 I 型奇謎機。除了將三個轉輪改為活動的,有 6 種排列順序外,還增設了類似電話交換機的接線板,可讓兩個字母彼此互換,任選 6 組就有一千億種組合,這樣乘上 26 x 26 x 26 x 6 = 105,456 種電路變化,等於有一萬兆以上的加密方式。要憑嘗試錯誤的暴力法加以破解當然是絕無可能,而即使知道奇謎機的構造,沒有密鑰(轉輪的排列順序和起始字母,以及接線板的對接組合),也無可奈何。

接線板,可讓兩個字母彼此互換。圖片來源:Wikipedia

法國人取得內部資料

也因此,當法國的情報人員買通德國密碼局的施密特 (Hans-Thilo Schmidt,諷刺的是,他那官拜通訊部參謀長的哥哥魯道夫,正是決定採用奇謎機以及攬他進入密碼局的人),於 1931 年 11 月取得奇謎機操作手冊和 9、10 兩個月的每日密鑰表,分享給情報同盟的英國和波蘭後,英、法兩國都覺得這天文數字般的加密組合根本不可能破解。加上德國當時仍是威瑪共和,納粹還沒執政,看不出有擴張侵略的野心,因此英、法兩國很快就放棄了破解奇謎機的念頭。

但是有亡國之痛的波蘭可不這麼想,對於德、蘇這兩個鄰國的戒慎恐懼之心,驅使他們緊緊抓住任何有助於防衛的機會。這三年多來,他們鑽研德軍密電始終毫無頭緒,如今有了法國取得的這份資料,至少可以一窺德軍的加密原則,解密再怎麼難如登天也值得一試。

瑞耶夫斯基於1932 年中成為波蘭密碼局的正式僱員,前往位於華沙的總部任職。當他從局長那兒拿到這份資料後,朦朧中似乎看到了一絲曙光……。

Marian Rejewski, probably 1932. Photo courtesy of Janina Sylwestrzak, Rejewski’s daughter.

加密兩次

根據法國人取得的奇謎機操作手冊與密鑰表,如今瑞耶夫斯基得知德軍每天會更換一次密鑰,要做的設定包括:

一、 三個轉輪的排列順序,例如 2-1-3(由左到右分別是編號 2、編號 1、編號 3 的轉輪);

二、 每個轉輪的起始位置,例如 M-T-C(由左到右的轉輪依次是字母 M、T、C 朝上。實際上字母並不是刻在轉輪上,而是活動的字母環,以免洩漏真正的核心電路編號,但這裡就先忽略);

三、 接線板六對互換的字母,例如 A⟷T、D⟷F、H⟷Y、L⟷V、O⟷Z、P⟷S(插孔A與插孔T用電線連接,之後以此類推)。

另外,因為每天發的電文多達數百則,為了杜絕敵軍掌握其中規律而找出密鑰,每則電文都用不一樣的訊息密鑰進行加密,也就是說每次發電報,要先將轉輪轉到不同位置再加密本文。訊息密鑰是由發信人自己隨意設定,然後註明在密電開頭,好讓接收方知道轉輪該調到哪個位置。

當然,不可能就這麼把訊息密鑰直接寫出來,必須再予加密才行。假設訊息密鑰是 Q-W-E,那麼發信人先從鍵盤輸入兩次QWE,加密後變成 ADYPJQ,再將這六個字母置於密電開頭。接收方收到密電後,輸入 ADYPJQ,得到 QWEQWE,就知道要將轉輪調成 Q-W-E 再開始解譯這則密電。

訊息密鑰要輸入兩次,是為了讓接收方確認無誤,但這卻給了瑞耶夫斯基一絲線索。如今他知道其中第一個與第四個字母從同一個字母加密來的,第二和第五個字母、第三和第六個字母也是如此,而且這過程只用到最右邊轉輪的連續六個字母。由於轉輪的初始字母每天都會更換,因此兩個月內大概每個字母都有用到,瑞耶夫斯基便能據此推算出三個轉輪與反射器的內部電路。

現在等於有了奇謎機的複製品,只是還沒有接線板而已,再來要做的便是找出從密電反推出當天的轉輪設定以及訊息密鑰的方法。

循環特徵

瑞耶夫斯基發現同一天的密電中,訊息密鑰加密後的六個字母若按 (1, 4)、(2, 5)、(3, 6) 這三對各別整理出所有 26 個字母的關聯性,總會分成幾組循環。例如下圖四則密電上的 (1, 4) 分別是 (B, T)、(L, B)、 (E, L) 和 (T, E),這便是 B → T → E → L → B 的循環。其餘的字母也會形成這樣的循環,但組成的字母個數不見得相同,例如除了上面這 4 個字母的循環,另外可能還有三個循環,分別有 6 個、7 個和 9 個字母。同樣地,(2, 5) 和 (3, 6) 這兩對也會有類似的循環。

瑞耶夫斯基想要尋找其中的模式,但裡面有 12 個字母是被接線板對調過的,得再還原回來。結果他這麼做了許多筆資料後,發現循環的組數與其中的字母個數竟然都沒有因此而改變;這意謂著循環的特徵值只和轉輪與反射器有關,與接線板一點關係都沒有。

這可是重大的突破!原本大家以為一萬兆以上的加密變化根本不可能破解,如今可以先把接線板的一千億種組合撇在一邊不管,只需單獨研究轉輪的 105,456 種電路中,有哪些加密後的循環特徵與所有密電符合就好了。雖然這仍是相當龐大的數目,但至少是花費時間和人力有可能加以破解的。

1933 年初,瑞耶夫斯基帶領小組成員開始進行分析,經過一年的時間,終於整理出所有 105,456 種電路的循環特徵,編寫成一本目錄。原本公認不可能破解的奇謎機,終於被瑞耶夫斯基攻克了;只要先從德軍密電的前六碼找出的循環特徵,再到這本目錄中比對,就知道如何設定當天轉輪,進行解譯。

喔,對了,由於還沒處理接線板對調字母的問題,所以轉譯出來的內容還不是百分之百正確。不過這倒也不是大問題,畢竟只有 12 個字母互換,電文中若有常用的軍事用語或專有名詞,即使其中有幾個字母是錯的,應該還是能夠辨認,或者從前後文推敲出來,這樣就知道接線板的設定了。

透過這個方法,波蘭密碼局從 1934 年開始順利破譯德軍密電。雖然德軍在 1937 年更換反射器,使得瑞耶夫斯基那本循環特徵的目錄失效,但他早已做出一台自動計算循環特徵的機器(如下圖),只要將轉輪調到訊息密鑰加密後的六個字母,再依序打開字母開關,同一循環的字母就會亮燈,因此很快就又重建新的目錄。

自動計算循環特徵的機器。圖片來源:Wikipedia

相同的加密字母

1938 年 9 月中旬,德軍再度變更加密方式,轉輪不再有統一的起始字母,而是由發信人自己決定。如此一來,循環特徵就不再固定不變,瑞耶夫斯基的方法完全派不上用場了。

德軍頻頻更換加密方式不但代表警覺性提高,也反映出納粹德國的擴張野心。奧地利才在 1938 年 3 月併入德國,到了 9 月底,捷克又被迫將主要為德裔人口的蘇台德地區獻給德國。眼見德國的威脅越來越迫在眼前,波蘭密碼局卻又頓時失去破譯密電的能力,他們必須趕快找出新的破譯方法,以掌握德軍動向。

德軍以為用變動的密鑰加密訊息密鑰就安全無慮,卻沒想到連續加密兩次的結果,還是潛藏著一絲破綻。

當年在波茲南大學參加密碼學課程的學生中,除了瑞耶夫斯基,另外還有兩人也被選入密碼局,一位是塞加爾斯基 (Henryk Zygalski),另一位是魯塞茨基(Jerzy Różycki)。他們一起分析循環特徵時,就發現偶而會出現只有一個字母的循環,也就是加密後的六個字母中,第一與第四、第二與第五,或是第三與第六,兩個字母是一樣的,例如 RTKRLB 的 (1, 4) 都是 R。

這種情況不是很常見,只有轉輪設定在某些特定位置時,才會第一個轉輪轉了三格後,某個字母仍加密成同樣的字母。由於這也跟接線板無關,因此只需從 26 x 26 x 26 x 6 = 105,456 種轉輪設定中找出哪些有這樣的特性,再與當日密電比對,就能找出符合的設定,還原訊息密鑰。為了加快破解速度,塞加爾斯基特地設計了 26 格 x 26 格的紙卡,在上面打孔代表兩個轉輪的起始位置,然後再將不同的打孔紙卡相疊,看哪種組合的孔洞與重複的字母相符。

塞加爾斯基設計的打孔紙卡。圖片來源:Wikipedia

炸彈機

這個方法雖然縮短了搜尋的的時間,但是仍不夠快。瑞耶夫斯基馬上在 1938 年 10 月設計出一台機器,以電動馬達驅動齒輪模擬轉輪所有位置,進行檢測。波蘭密碼局造了六台機器同時運作,每台模擬轉輪六種排列組合中的一種,兩個小時內就能找出密鑰。由於運作時滴答滴答作響,像是定時炸彈倒數的聲音,這部由六台機器組成的解碼機便被暱稱為「炸彈機」(波蘭文 ”Bomba”)。

炸彈機的設計圖。圖片來源:Wikipedia

孰料炸彈機才啟用沒多久就失效了。德軍在年底時新增了兩個轉輪,每天從五個轉輪中選三個放入奇謎機,排列組合從 6 種一下子變成 60 種,但波蘭密碼局已經沒有資源再製造 56 台機器。隔月德軍又將接線板上對調的字母從 6 對提高到 10 對,電文更難解譯了。

1939 年 4 月,德國片面撕毀與波蘭的互不侵犯條約,入侵的企圖昭然若揭,波蘭此刻更需要掌握德軍動向,但密碼局已力不從心,決定將多年的心血和盟友分享,希望他們接手後能破解德軍新的加密系統。

7 月 24 日,英、法兩國的相關人員應邀抵達華沙,他們原本只知與奇謎機有關,等到聽取密碼局簡報,發現波蘭人默不吭聲地破譯德軍密電已經好幾年了,無不目瞪口呆。最後密碼局長掀開布幔,展示炸彈機,更讓他們大為震撼,破解奇謎機的自動機器竟然就在眼前!

當然,這台炸彈機再也無法應付更複雜的加密方式,但已證明奇謎機是可以破解的。只要提高炸彈機的運算能力或是改善波蘭人的這套方法,應該就能破譯德軍密電,掌握他們的未來動向。眼見波蘭三位數學家取得如此重大成果,英國政府決定起而效之,招募包括圖靈在內的數學家進駐倫敦近郊的布萊切利莊園 (Bletchey Park),研究如何破解德軍密碼。

筆者攝於布萊切利莊園前 (2022/6/5)。

逃亡

不過就在圖靈等人報到之前,德軍於 1939 年 9 月 1 日發動閃電戰入侵波蘭,波蘭密碼局趕緊銷毀所有文件與機器,以免納粹發現奇謎機並不安全,全面更換加密系統。瑞耶夫斯基等人則以平民身分搭車逃往羅馬尼亞,再坐十幾小時的火車,抵達英國大使館所在地。不料大使館人員竟要他們過幾天再來,他們只好轉往法國大使館求援,才被帶到法國,並於十月開始透過電報電傳打字機和布萊切利莊園交換意見,協助破解奇謎機。

1940 年中,德國攻入法國,瑞耶夫斯基等人先飛往阿爾及利亞避難,幾個月後再回到法國南部繼續破譯密電的工作。隨著德軍步步逼近,瑞耶夫斯基等人不斷搬遷到不同城鎮,他們三人中最年輕的魯塞茨基,不幸於 1942 年的一次撤離行動中溺斃。隔年一月,瑞耶夫斯基和塞加爾斯基被安排攀越庇里牛斯山,前往西班牙。怎知好不容易在三月抵達邊境後,竟遭西班牙警察扣留,一直關了三個多月,才在紅十字會的介入下獲得釋放。他們兩人再輾轉取道葡萄牙、直布羅陀,於八月初抵達英國。

英國政府為了保密,連法國都不知道圖靈早在 1940 年初,就設計出同時模擬 36 種轉輪組合的機器,也取名為炸彈機 (Bombe);提供協助的波蘭數學家也被蒙在鼓裡。如今英國政府仍不讓瑞耶夫斯基和塞加爾斯基與布萊切利莊園有所接觸,只安排他們從事低階的解密工作;英國一位密碼學家對此就感嘆說這猶如讓賽馬去拉馬車。

隱藏的真相

二次大戰結束後,瑞耶夫斯基回到已成為共產國家的波蘭,到老婆娘家處與家人團聚。隔年他 11 歲的兒子死於小兒麻痺,悲痛的瑞耶夫斯基不願再與妻子及女兒分離,寧可放棄波茲南大學的教職,選擇在當地一家電纜公司當業務主管。但他的生活仍不平靜,由於之前與英、法兩國情報單位的密切合作,讓他不斷遭到安全局調查,長達十年之久。

晚年的瑞耶夫斯基與妻子攝於家中。
photo: Irena Jarosinska / Forum

瑞耶夫斯基於 1967 年退休,開始撰寫回憶錄。有件事多年來不時浮上心頭:自己的研究成果究竟有沒有幫英國那批數學家破解奇謎機?這個疑惑直到 1974 年,一本揭露布萊切利莊園巨大貢獻的書出版後,他才終於獲得答案,原來圖靈果真設計出新的炸彈機,成功破譯德軍密電。

瑞耶夫斯基一方面感到欣慰,一方面又覺得不平,奇謎機的破解是基於他們幾個人奠定的基礎,卻只用「波蘭人的協助」模糊帶過。他站出來接受訪問、發表文章,希望他和弟兄的貢獻不被抹滅,但顯然效果有限,至今人們記得的仍是圖靈破解奇謎機。

1980 年 2 月,瑞耶夫斯基因心臟病猝死於家中,隨即光榮地葬於軍人公墓。多年之後,他才又陸續被英、美兩國與許多國際組織追贈獎章與榮譽,多少算是還給這位最早破解奇謎機的幕後英雄一個公道。

參考資料:

  1. Enigma machine – Wikipedia
  2. Marian Rejewski – Wikipedia
  3. Cryptanalysis of the Enigma – Wikipedia
  4. Enigma Cipher Machine (cryptomuseum.com)
  5. Enigma Code-Breaking: Replicating a 1930s Polish Cyclometer – Hackster.io
  6. AMS :: Feature Column :: The Polish Attack on Enigma II: Zygalski sheets
  7. 《碼書》,Simon Singh 著,劉燕芬 譯,台灣商務印書館出版
  8. 《艾倫.圖靈傳》,Andrew Hodges 著,林鶯 譯,時報文化出版
Share on facebook
Share on twitter

更多文章

© 2021 張瑞棋