🎥《數毒求戀事件簿》第四集 : 我們私有的戀愛暗號


【密碼學是甚麼?】


來到「密碼學」(Cryptography) 這實用非常及歷史悠久的題目。Cryptography 來自希臘語kryptós「隱藏的」和graphein「書寫」。主要分成古典密碼及現代密碼兩種。古典密碼主要是訊息的保密及傳遞,與及對方的破解方法,所以分成「原碼加密」(Encryption)及「密碼解密」(Decryption) 兩大步驟。而現代密碼學再涉及各種驗證及安全性問題。

由一開始古羅馬的(Caesar Cipher)凱撒密碼到現代的RSA (Rivest-Shamir-Adleman) 加密演算法,創立原因都離不開軍事用途。發展到今時今日,密碼學運用了大量數學理論及計算機科學的運用,古典密碼的簡單加/解密已經不能再用來傳送國家軍事訊息,但卻能在日常生活中的傳話帶點玩味樂趣。

詳情請繼續留意我們《數毒求戀期》的更新。

【密碼之雛形:凱撒密碼】


天下間密碼有好多種,先同大家介紹最易上手的凱撒密碼,也是《數毒求戀事件簿》中Yuler及阿基米德互相傳達愛意的加/解密方法。它是替換式密碼(Substitutions Cipher)中最簡單的一種。凱撒密碼是以羅馬共和國(公元前509年-前27年)時期的凱撒大帝尤利烏斯·凱撒(Julius Caesar) 為名,因有記載凱撒曾用之來與將軍們進行秘密溝通。但相信在之前已有人使用其他類近替換式密碼。

方法:把原碼(plaintext)文字內的每個英文字母用同一固定數目的偏移量(shifting number)向前或向後替換成相對字母。在此設定細階字母是原碼,大階字母是密碼。

例如: 偏移量是3(向前),那麼a加密後變成D,b加密後變成E,z加密後變成C,如此類推。知道偏移量及方向就等於知道加密方法,要解密就十分容易。只要用同一偏移量行相反方向移位,便能還原回原碼:偏移量是3(向後),D解密後變回a,E解密後變回b,C解密後變回z...

所以,阿基米德想跟Yuler説的原碼: i know what a means now

每個英文字向前移三位置就變成密碼: L NQRZ ZKDW D PHDQV QRZ

就是阿基米德在大樹下傳訊出去的信息。至於"a"其實是代表甚麼,為甚麼他們要這樣傳話?請自行重温一套四集的《數毒求戀事件簿》🙃。

ROT13 (Rotate by 13 places 迴轉13位),是當中最常用的凱撒密碼。只要將原碼向前偏移13個位置便能加密。由於英文字母有26個,13是當中的一半,所以將密碼再偏移13位多一次,便能解密會原碼。也就是說,ROT13是它自己本來的逆反。密碼學上,這完全沒有任何安全性,卻廣泛地刺激了網上的字母遊戲及新聞討論群組的文字創作。例如90年代的常用網上俚語 ”furrfu” 就是 ”sheesh” 用ROT13演變而成。

美國著名密碼學及軍事情報作家大衛·卡因(David Khan)在他的著作書籍中提及過,有不少情侶在60年代的倫敦報紙The Times中,運用凱撒密碼來互相傳情。用這種方法來溝通,能放閃之餘又不會過分耀眼吧~

若要以全數學去演繹凱撒密碼: 為何?雖然這看似簡單複雜化,但若多數量,便需要電腦的計算協助。另外,一去到較為深奧及安全性需求較大的加密法,用數學來表達便有系統及清晰得多。

(i)我們要將所有英文字母轉為數字代號,如上圖。

(ii)借用函數概念:


  • En(原碼代號)= 密碼代號


  • Dn(密碼代號)= 原碼代號


  • En 的定義域(Domain)是原碼代號,0至25;值域(Range)是密碼代號,也是0至25。 相反,Dn 的定義域是密碼代號;值域原碼代號。


  • 假如原碼的數值是x,密碼的數值便是x+n。 相反,假如密碼的數值是x,原碼的數值便是x-n。

(iii) n 便是之前所提及的偏移值,我們在此設定加密是向 移動。

(iv) mod(26): 模除26。由於原碼及密碼代號都是由0到25,加密後或解密後一旦離開了0到25這值域便需要加上或減去26,確保答案是在值域之內。或可以說:將越過0到25的數字除以26,然後剩下的餘數便是模除26的答案。例如,若偏移值是5:


  • E5(0)= 0+5 = 5 | a 變成 F


  • E5(1)= 1+5 = 6 | b 變成 G ...


  • E5(24)= 24+5-26 = 3 | y 變成 D


  • E5(25)= 25+5-26 = 4 | z 變成 E


  • D5(5)= 5-5 = 0 | F 變回 a


  • D5(6)= 6-5 = 1 | G 變回 b...


  • D5(3)= 3-5+26 = 24 | D 變回 y


  • D5(4)= 4-5+26 = 25 | E 變回 z

參考資料:

Caesar Cipher. (n.d.). Retrieved from https://www.cs.mcgill.ca/~rwest/wikispeedia/wpcd/wp/c/Caesar_cipher.htm

【凱撒密碼輪盤】


凱撒密碼雖然簡單,但每次也要把所有字母及已移位的字母排出來,總是有點麻煩。今次為大家介紹一個小工具,「凱撒密碼輪盤」 Caesar Cipher Disk。

「密碼輪盤」的始創人是一位文藝復興時期在意大利的建築師、作家、密碼學家的通才萊昂・巴蒂斯搭・阿伯提(Leon Battista Alberti)。他的名著《論建築》(The Architecture of Leon Battista Alberti)討論歐幾里得的數學原理及黃金比例在建築的各種可能性,並在1467年製造了世上第一個密碼輪盤。

這輪盤用兩塊大小不同的同心圓盤疊拼而成。


  • 小的圓盤叫「可動輪」(Mobilis):有26個小階字母作原碼之用。


  • 大的圓盤叫「穩定輪」(Stabilis):有26個大階字母作密碼之用。


  • 輪盤上,也有一個孔展露出由0到25的偏移值。


  • 只要跟對家商量好一個共同的偏移值,然後把「可動輪」轉到從孔中看見偏移值,便可以開始由內到外加密,或從外到內解密。

這密碼盤的設計在美國內戰(America Civil War : 1861-1865)期間被廣用,主要有木製及銅製兩種。

讀者也可以用咭紙自製你自己的凱撒密碼輪盤。網上有很多輪盤模板,其中這個(按Miss Wong的個人意見)是比較美觀的。

另外網上科技也令大眾可快速用凱撒密碼加解密,例如adcode.fr 這網頁程式及App Store內搜尋Caesar Cipher便有很多的手機程式可下載。懂得編寫電腦程式的話,更可嘗試編輯自己的凱撒密碼工具,也是一個不錯的練習。

參考資料:

Alberti cipher disk. (2014, March 10). Retrieved from https://en.wikipedia.org/wiki/Alberti_cipher_disk

🎥【中大邱比特出pool實錄 x 有獎問答遊戲】


中大邱比特年前成日出動幫人識朋友。雖然現在已經收山,但自己也不自覺地毒埋一份,需要出pool的協助。識逢《數毒求戀期》推出凱撒密碼輪盤。此輪盤除了加解密之外,更加可以幫助他在一眾美女中尋找心靈相通有緣份的好朋友。

請即看《特別數毒報導》【數毒求戀 X 中大邱比特】並且參加我們社交媒體 Facebook / Instagram 問答遊戲,10張Apple Store價值200港元等著大家!

🔍Facebook - HKMathRomance

🔍Instagram -HKMathRomance

特別鳴謝:

中大邱比特傾力合作

【頻率分析破奇案】


密碼學中,有一種解密方法叫做頻率分析(Frequency Analysis),用來研究由字母組成的語言中,字母及組合出現的頻率,作為解破替換式密碼(Substitution Cipher)的手段。以下是英語中典型的字母分布:

從中可見, A E T等是最常見的字母; J Q X Z 則最不常見。組合中, ST, NG, TH 是常見的;NZ, QJ 則非常少。

一般的頻率分析就是嘗試在密碼文中,抽取出現頻率最多(或最少)的符號或符號組合,然後與上圖常用的字母作出配對,直到有意思的詞語出現為止。

在2012年,英國有一單槍擊案件,疑犯嘗試用自製的替換式密碼與外界溝通洗脫罪名。最後密碼被司法語言學家運用了頻率分析破解,疑犯反而證實了自己的罪行。

當年Kieron Bryan是一名23歲、在英國曼徹斯特市內的饒舌歌手,別名 “Gunz”。他因涉嫌一單企圖謀殺案及非法持有武器案件而被拘捕。拘留期間,他寫了一封信給他親友,信件中有提及背後有一大段混亂的數字,是玩數字解謎時的草稿,可「不用理會」。但警察看到之後覺得很有可疑,思疑可能是密碼,便聘請了司法語言學家 Dr. John Olsson 協助解碼。Dr. Olsson 一看便知這不是單純的字母偏移密碼。而當中的篇幅也不是長到一個位可以用基本的頻率分析便能解拆。

經驗充足的Dr. Olsson知道,每人也有他自己說話的模式,詢問過之後,得知Bryan是一個十分有禮貌的人。況且在被捕期間,要向外界通訊求助,因此推斷,”please” (請求)這個字出現的可能性極高。

再細心分析信中長長的數字,他發現多次出現同一組數字:38 9 5 10 3 5。於是他嘗試將please這6個字母組成的字,與上述6個數目的數字串並置,即是:p = 38, l = 9, e = 5, a = 10, s = 3, e = 5,然後再利用電腦,找出其他數字相對應的字母,終於破解到整篇數字,果然真的蘊釀著秘密。

原來在密碼信中,Bryan想傳達的訊息,是叫他姐姐用£15,000去賄賂受害者,希望他撤銷控訴。

用這迂迴的方法去為自己擺脫罪名,看得出他是個十分危險及狡猾的人,Bryan最後被判刑25年。

再刁鑽的密碼難題也有它的解密方法。下一次就同大家介紹二戰中德軍引以為榮的Enigma Machine (恩尼格瑪密碼機)及把它破解的數學英雄Alan Turing(艾倫・圖靈)。

參考資料及圖片:

Anonymous. (2012, Feb). Police code-cracker helps jail Manchester gun pair. BBC. Retrieved from https://www.bbc.com/news/uk-england-manchester-17157015

Law, K. H. (2012). Number save the day. Hong Kong: Pearson Education Asia.

Anonymous. (2012, Feb). Codebreaker puts gangland gunman behind bars. Telegraph Media Group Limited. Retrieved from https://www.telegraph.co.uk/news/uknews/crime/9107927/Codebreaker-puts-gangland-gunman-behind-bars.html

【158,962,555,217,826,360,000】


在第二次世界大戰期間,最令納粹德軍自豪的便是重用了Enigma Machine (恩尼格瑪密碼機)加密戰術策略,再遙距傳送,控制戰況,侵略歐洲各地。

這座Enigma 真的有那麼強大的威力,令盟軍大費周章去嘗試破解?利用它加密的話又有幾多種不同可能性的密碼出現?英國數學家艾倫•圖靈(Alan Turing)又是如何與同僚去成功解密?

Enigma 一直從十九世紀末開始就應用於商業加密上,而二戰期的納粹德軍就用上較為複雜,安全性較高的軍用版本。以下是Enigma機的基本介面及操作:

一共有四個部份:旋轉盤、鍵盤、顯示燈泡、接線板。每一個部份內都有大量電線互相接駁着。


  • 旋轉盤(Rotors) : 一共有五個,一般只會使用三個,另外兩個隨時作替換。每個旋轉盤都有26(01-26)個位置被選擇。設置每次密碼設定時用。


  • 鍵盤:用家會從鍵盤上輸入原碼。


  • 顯示燈泡:輸入原碼字母後,密碼會在顯示燈泡上閃出加密後的密碼字母。


  • 接線板(Plugboard):只會出現在軍用的Enigma機上。接線板有10條電線,頭尾有插頭。也有26個字母的接口位。每一條電線都可頭尾選擇兩個字母,接駁後便可將這兩字母位置相換。例:E↔️Q。

設定:

用家一開始從五個旋轉盤中選擇三個。然後從01-26 中選擇三個號碼(可重複),把旋轉盤轉到那組數字顯示在機面上。這跟凱撒密碼轉盤不同,每個旋轉盤每個位置都駁去不同的電流,所以26並不代表自己。 從26字母中選擇10對字母作掉換,在接線板上用電線把每對字母連上。這就是今次加密的設定。

加密的電流過程:

開始在鍵盤上輸入密碼字母。電流會從鍵盤經過接線板為字母位置相換,再經過三個旋轉盤(只要有電流經過旋轉盤會自轉,內部的電源會接駁去另外一個顯示燈泡),電流再返回接線板再進行字母位置相換,然後在顯示燈泡上顯示出最後密碼字母。

圖解例子:一開始輸入的是N,經過接線板後轉換為K(因N同K駁上),經過三個旋轉盤後,電源接駁到去E,再次經過接線板後最後顯示出來的是F(因E同F也駁上)。

這部機的強大之處,就是你無論輸入同一個英文字母多少次,加密後的密碼每次都不同,例:

原碼輸入:AAAAAA⋯⋯

可能密碼:BQLZBO⋯⋯

這與之前介紹過的經典密碼,安全性及破解難度上有天淵之別。

現在讓我們嘗試計算有可能組成的不同密碼數目:


  • 選擇旋轉器: 5 C 3 =60 種選擇


  • 三個旋轉器的設定:26x26x26=17576 種


  • 接線板的10對互相交換的字母: 26!/(6!10!2 10 )=150,738,274,937,250 種


  • 把以上三個步驟乘起,一共有 158,962,555,217,826,360,000不同的密碼可能性。

納粹德軍不同部門都有Enigma在手,只要知道加密時的設定(用那三個旋轉器、每個旋轉器的位置是甚麼、選擇那10對英文字母在接線板上相換),便可自動解密。而以上設定資料,德軍每一個月也會更新。那一天用那個設定,都會記錄在一張大型紙張上,每個軍隊也會擁有一份副本。此紙上資料是用水溶性的墨水記錄,只要一被敵軍捉到,用水便可以把設定資料溶化,以防泄密。

這台Enigma確實令英國皇家海軍非常頭痛,不惜大費金錢聘請大量數學家及解密專家去嘗試破解。但他們大部份只是用人手嘗試每天解碼,過程艱辛及耗損時間。每隔一天之後,密碼設定會改變,前一天付出的努力也付諸流水。一直到1939年英國數學家艾倫•圖靈(Alan Turing)的出現,就改變了以前的局勢及影響深遠。

圖靈與解碼同伴戈登•韋爾什曼(Gordon Welchman)一起建造了一台Bombe機。

Bombe是一部大型電動機械(Electromechanical Device)。機內有大量轉盤,主要是用蠻力攻擊方法 (Bruce Force) 代替人手去測試所有可能的Enigma設定。

若然知道密碼的缺陷,需要測試的設定便可以以排除法 (process of elimination) 逐一減去。

破解密碼的關鍵大概分為兩種:

1️⃣ Enigma設計上的漏洞。原碼及密碼永遠不會是同一個字母,從看之前的例子,

原碼輸入:AAAAAA⋯⋯

可能密碼:BQLZBO⋯⋯

密碼永遠不會有A出現。

2️⃣ 人為的習慣及文章內會出現的文字,簡稱crib。納粹德軍每朝早準時6:00會用密碼傳送天氣報告給隊友。習慣上,可推算出密碼文章開頭會有Wetterbericht 這個德文字(英文是Weather Report,天氣報告意思)。報告接近完結時也會有Heil Hilter (希特拉萬歲)這納粹禮文字的出現。

這兩個漏洞大大減少了Bombe機的工作量。經過多次嘗試及進化,最終Bombe能夠每天用20分鐘左右時間顯示出所有剩餘下來的可能設定,成功破解Enigma加密技術。保守估計,這創舉把納粹德軍投降的時間至少提前了兩年多,也大量減少了傷亡人數。

二戰後,圖靈主要研究生物數學及自動計算引擎(ACE),是現代電腦的雛形。他雖然對世界作出了重大貢獻,卻不能夠安享晚年。在他人生最後的兩年,身為同性戀者的他被社會迫害而被定罪,迫使他用藥進行化學閹割,最後自殺身亡。

參考資料及圖片:

Enigma machine. (n.d.). In Wikipedia. Retrieved June 28, 2019, Retrieved from https://en.wikipedia.org/wiki/Enigma_machine

Rijmenants, Dirk. (2004-2016). Enigma Message Procedures, Retrieved from http://users.telenet.be/d.rijmenants/en/enigmaproc.htm

Numberphile. (2013, Jan 11). 158,962,555,217,826,360,000 (Enigma Machine) [Video file]. Retrieved from https://www.youtube.com/watch?v=G2_Q9FoD-oQ&t=603s

Numberphile. (2013, Jan 15). Flaw in the Enigma Code [Video file]. Retrieved from https://www.youtube.com/watch?v=V4V2bpZlqx8&t=556s

詳細解釋資料。。。將會陸續更新


遲些回來吧~