機密文件如何編碼,又如何破解?-《演算法星球》
- 編按:演算法隨著網路與電腦的普及無所不在,是現代人無法忽視的思考方式。《<演算法星球>一書中,作者用各種簡單風趣的案例來解釋演算法是什麼?又與從電話簿裡找號碼、搜尋引擎的原理、幫孩子分蛋糕以及為想婚男女配對等挑戰有何關係?本文選自該書第 4 章「萬有引力的西邊」,世界上有各種非決定性多項式問題,例如編碼,如何套用演算法的思考來解決?
人類傳送機密訊息已長達幾千年。一開始,訊息沒有被編碼,只是隱藏而已。不管是信差郵包裡的夾層或是機密文件,隱藏訊息的過程本身也必須是隱密的。(知道如何隱藏訊息的人,也知道如何找出訊息。)機密訊息建立於訊息攔截者與溝通者的不對稱性;當我們今天為自己的資訊編碼的時候,基本上我們並沒有發現不對稱性的倒轉就在其中。(為資訊編碼並寄送出資訊的我們,一點都不了解編碼技術,犯罪者與情報單位卻通曉一切。)
機密溝通在過去是主權者的特權。1977 年,破除這種情勢的點子出現了:藉由複雜性為資訊編碼—一個今天每個人都知道的編碼技術,取代了過去那個被保護得很好的秘密保密程序;然而,每個人也還是只能為自己的個人資訊解碼。如此,每位公民都能藉由編碼保護自己的個人資訊,不被任何權威侵犯。這樣的技術既非不可知、秘密或是更昂貴的東西(我們其實可以更常使用它),問題在於有沒有編碼的意願。
藉由複雜性進行編碼的核心設計,是把資訊包裝成一個困難問題的解答,只要擁有正確的秘訣,就可以輕易破解它。非決定性多項式問題的特質完全適合這項任務,不過卻造成編碼動作執行上的另一個問題,因而產生的疑慮是:它是否又屬於非決定性多項式中最困難的問題層級呢?我們還是一個一個來看吧。
機密文件
編碼的基本任務如下:我想要告知你一件事,但不能讓別人知道。問題是,我只能透過公開管道送出我的信息,而無法對你悄悄耳語。每個人都可以閱讀這則信息,所以我們必須想出一個辦法,讓信息內容只對你產生資訊意義。於是,你需要一把能解開信息的鑰匙。如此一來,對其他人而言,這個信息只不過是一疊發出沙沙聲響的紙而已。
今天在許多狀況中我們都信任編碼,典型的例子是購買火車票。在購買的過程中,類似信用卡號碼這類敏感的資訊會在網路上傳遞,成為通訊的一部分。鐵路局透過網站賣票,要求取得你的卡片號碼。網站會讓你下載一個小程式到你的筆記型電腦上,接著要你填入個人資料至表格裡,就在那兒—你的筆記型電腦裡—這個程式為你的資料進行了編碼。
然後,程式寄送出你編碼後的資料,穿越浩瀚無垠的網際網路,去到鐵路局的伺服器那頭。(沒有編碼就把資料送上網路旅程的人,可能會馬上印出一張機票。)當訊息穿越網際網絡移動時,沒有人能解讀你的資料,但鐵路局得馬上閱讀這份資料。那麼,該怎麼做呢?
從最簡單的狀況開始思考。我們想為世界上最小的資訊編碼,因此只說「呼」或「哈」,來表示「男生」或「女生」。我們想傳送一個位元,然後不讓其他人知道答案是女生還是男生,所以我們事先約定好,答案若是男生就說「呼」,若是女生則說「哈」,或是顛倒過來,如此就可以毫無掛慮地釋出訊息,甚至加注:「以下訊息『呼』透露答案是男生或是女生。」其他人則沒辦法知道我們的答案。這個編碼非常完美,而且還很簡單。
接下來,每個訊息都可以是「呼」或「哈」,或是以廣為人知的 0 或 1 來表示。我們甚至可以使用公開熟知的標準,將 0 與 1 轉換成一段文件,並且轉換回來。唯一需要事先約定好的是,是否每個 0 就以 0 來書寫,每個 1 就以 1 表示,還是顛倒過來書寫。這和為一個位元編碼的原則完全一樣。不過,這樣卻可能無法成功編碼,因為其他人可以用兩種可能對訊息進行試驗,一次是 1 就是 1,另一次是 1 則為 0,如此多半能透過其中的一種可能,看出訊息原本的意義。如果寄出的是較長的資訊,資訊本身的結構則有可能展現出已經編碼過的文件為何,如此編碼就會被破解;相反地,一位元編碼則因為兩種可能的結果都具有意義,因而排除了舉一反三而被識破的可能。
這麼做對於稍微複雜的編碼也有效果,比如一份其每個拼字都由其他字母甚至空格來取代的機密文件。(聽起來機密度非常高。)不過,太多清楚的內文結構,例如一個字母重覆兩次時還是會被辨識出來。比如說,哪個記號最常出現,就很可能是空格;只要認出空格,就能看出非常短的字。然而非常短的字並不多。依此類推,編碼的神秘面紗很快就會被揭開。
馬塔潘角與失落的 L
一個破解機密文件的實例故事來自二次世界大戰。當時,德國納粹與同盟為其機密訊息運用了恩尼格瑪密碼機(Enigma machine)。此密碼機最高竿的秘訣,在於會更換機密訊息的每個字母;同一字母在訊息的不同處,會由不同字母來替換。在一定的時間間隔中,機密訊息第一個字的首位字母之替代字母,又會被另一個新的替換字母所取代;從那時起,恩尼格瑪密碼機便自動使用新的替換字母,取代每個新出現的字母。這讓事情變得相當棘手。
即使如此,英國布萊切利園(Bletchley Park)的解碼專家—圖靈亦是他們的成員之一,還是看出相當的規律性,從而破解了納粹訊息。當時,瑪薇絲.貝提(Mavis Batey)與圖靈一同職掌海軍訊息的解密。(貝提負責義大利海軍。人們一般認為,她所破解的敵方機密命令,讓英澳海軍在希臘瑪塔潘角的大勝,是極為關鍵性的幫助。)
貝提認為,恩尼格瑪密碼機有個弱點—其實那原是設計者相當聰明的點子:恩尼格瑪密碼機從來不使用文件真正的字母本身來編碼,因此 L 可能是所有其他字母,唯一不是的就是 L 本身。(如果一個字母用自己來編碼未免也太蠢了。)有一天,一則訊息送到貝提的辦公桌上,該訊息完全不含 L 字母,貝提開始進行一件連演算法至今都很難做到的事:她開始思考,特別對那位坐在鍵盤前發出訊息的訊息傳遞者進行思考。她認為,義大利敵友非常可能只是不斷敲著 L 鍵,寫了一封測試訊息。因為恩尼格瑪密碼機從來不用 L 為 L 編碼,顯示該訊息根本不會有字母 L。編碼過的訊息洩露內容,是因為訊息本身仍展現出夠多未經編碼的訊息結構。貝提因而找出了當天恩尼格瑪密碼機起始設定的字母。
即使是長訊息,也能像解開一位元編碼般被完美解開。只需將每個訊息寄出的 0 和 1 組合分開或隨機固定下來。是否在此處以 11 表示 00,或是相反?(這個操作方法相當完美。)誰要是擁有無盡長的每個字母之編碼單,就能輕輕鬆鬆解碼。對其他人而言,這條訊息與偶然的紙張沙沙聲則沒有任何差別。(唯一的問題是針對每張火車票、每個最後一分鐘禮物、每本在網路上被訂購的書所做的編碼單,它和人們寄出的訊息一樣長。)
圖片來源:422737 @ pixabay
留言討論