iT邦幫忙

2021 iThome 鐵人賽

DAY 3
1

納粹德國的超強機器,唯有機器才能破解機器。

今天來介紹二戰時期被納粹大規模使用的加密機器 - Enigma
他是一種機械式密碼、並非由數學計算進行加密。
不過我覺得蠻有趣的,所以今天來了解一下。

使用方式

首先先說說他怎麼操作,這樣比較好理解。

Enigma 是一台像打字機的東西,只是除了用來打字的鍵盤之外,他還有每個字母專屬的燈泡。
當你按下鍵盤中的某個字母,會有一顆燈泡亮起來,而亮起來的字母就是加密後的字母。
假設你按下A,而G的燈泡亮起來了,那就代表把A加密成G。

當然,機器所做的事情只包含你給他一個字母,他回傳一個字母,並沒有紀錄的功能,
所以紀錄是由人工的方式進行。

那這樣有什麼好厲害的,好像只比凱薩密碼厲害一點點嘛,
我們一樣可以用字母頻率分析來破解啊。

答案是不行,
舉個例子好了,假設你要加密這段文字:my name is alan.
那麼依序按下字母之後你可能會得到 :kc qmtt wf cjeo
這是我用線上 Enigma模擬器 ( 連結我放在底下 )加密後的結果。

MY NAME IS ALAN

KC QMTT WF CJEO

發現問題了嗎,三個A分別對應到了M、C、E
而中間兩個字M、E都對應到了T

為什麼會有這種結果呢?

構造

來看一下把 Enigma 的上蓋打開來後長什麼樣子。

右上角空的地方是拿來放電池的、中間有燈泡。
Enigma最厲害的地方就是左上角那顆看起來像行李箱密碼鎖的東西。

旋轉盤

這個項行李箱密碼鎖的東西叫做旋轉盤( Rotors ),
一台 Enigma 有三個旋轉盤,每個旋轉盤有26格。

當每按下一個字母,最右邊的旋轉盤就會轉一格。
而每一次旋轉盤旋轉,就會讓底下的電路產生變化,進而讓不同的燈泡亮。
所以,就算同一個字母被連續按了兩次,他也會對應到不同的字母。

還沒完,
當第一個旋轉盤轉一圈,就會帶動第二個旋轉盤轉一格,
接著第二旋轉盤轉一圈,會帶動第三旋轉盤的一格。

也就是說讓第三旋轉盤轉完一圈需要按下26×26×26 = 17576個字母。

更誇張的是這個旋轉盤式可拆卸的,
總共有五個旋轉盤,
而每次都可以決定使用哪三個旋轉盤以及分別插在哪個位置。

也就是說增加了5×4×3 = 60倍的可能性。

接線板

另外看到最底下有許多的孔洞,每個孔洞也都代表一個字母。
這個設計叫做接線板 ( Plugboard ) ,是為了讓 Enigma 的加密更加完備。

接線板需要使用一種雙頭的線,也就是可以把孔洞兩兩配對。
被配對的兩個孔洞會調換。舉例來說,我把A跟K連在一起,那麼我按下A的時候其實代表K,而按下K的時候其實代表A。

這樣的線總共有十條,於是增加的可能性是
https://chart.googleapis.com/chart?cht=tx&chl=C_%7B10%7D%5E%7B16%7D%2F2%5E%7B10%7D%20%3D%20150%2C738%2C274%2C937%2C250(倍)

反射器

Enigma作為一台加密機,同時也是一台解密機的原因就在於這個反射器 ( Reflector ),
他可以保證明文和密文是對應的。

意思是說:假設A對應到F,那麼在同樣的設置下,F就會對應回A。
這樣的優點是只要設定相同,解密員只需要將收到的密文直接輸入Enigma裡面,就可以得到相對應的明文。

而這同樣業是他的缺點,
因為一個字母必定加密成另一個字母,也就是A不可能對應到A。
而這也成為後來破解Enigma的漏洞之一。

設置

德軍每個月都會印一張表,上面表示著每一天 Enigma 的初始設置。
設置表上會標明日期、用哪三個旋轉盤、旋轉盤的順序、旋轉盤轉到哪一格、接線板上要接那些字母。

接著,假設今天的旋轉盤表定設置是PGT,那麼加密前就把旋轉盤轉到PGT,然後隨機傳送三個字母作為此篇的密鑰,
假設GJE好了,那就把旋轉盤轉到GJE,開始加密後面的文字。
所以收到訊息的人就要先用初始設置解密前三個字,獲得GJE,再把旋轉盤轉到GJE,開始後續的解密。

這樣的好處是讓統計效果失效,
因為因為如果今天的每篇文字都用PGT來加密的話,就有可能提高用統計方法破密的可能。

運算複雜度

最終,一台 Enigma 加密同一段文字所得到的密文,
有將近1590萬兆種可能。

如果有十個人,每分鐘都查一個設定,24小時不休息,要花2000萬年才能解完。
而且這還只是一天的量。

對於沒有電腦的二戰時期,這個天文數字就代表著破解是不可能的事。
(所以他們就發明了電腦)
這台電腦叫做圖靈機,由Alan Turing 所發明 ( 跟我同名灑花 )
最後是用20分鐘破解了Enigma。

但並不是說圖靈機在20分鐘之內解完了1590萬兆種可能。
圖靈的破解方式說白了確實是一種暴力破解,不過是做過簡化的暴力破解。
德國每天都一定會傳送特定幾個字,如天氣、希特勒萬歲之類的,
圖靈就是利用這些特定的字簡化了他所需要計算的量。

Kerckhoffs's principle

"即使密碼系統的任何細節已為人悉知,只要密鑰沒有被洩漏,它也應是安全的。"

Enigma 就是Kerckhoffs's principle 很好的例子,
就算英國獲得了Enigma機器,如果不知道當天的設定,是沒有辦法破解的。

注意到,Enigma之所以最後被破解,是因為德軍傳送訊息的漏洞所造成。

最後如果你對 Enigma 有興趣的話,可以去看一部2014年的電影,叫做"模仿遊戲(The Imitation Game, 2014)",
是一部以Alan Turing的視角所拍的電影 ( 內容大部分真實 ),蠻好看的。
另外底下的第三個連結是我所使用的模擬Enigma機,
雖然我不知道他是不是會跟真實的enigma加密的一樣,
不過它的基本性質是正確的,所以可以玩玩看。

參考資料:
https://www.youtube.com/watch?v=G2_Q9FoD-oQ
https://www.easyatm.com.tw/wiki/enigma
https://cryptii.com/pipes/enigma-machine
https://www.2worldwar2.com/enigma.htm


上一篇
DAY 2- 編碼跟加密-凱薩密碼
下一篇
DAY 4- 對稱式、非對稱式加密概要
系列文
學密碼學也猜不到你的手機密碼30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言