最先秘密發現「公鑰加密法」的密碼學家

最先秘密發現「公鑰加密法」的密碼學家
Photo Credit: Sebastiaan ter Burg, CC BY 2.0
我們想讓你知道的是

公鑰加密法的最早發現者因為在情報機構工作,要等到24年後才被公眾知悉其研究成果。

唸給你聽
powered by Cyberon

1973年11月20日,第一套「公鑰加密法」正式誕生,這是密碼學——研究加密資訊和破譯密碼的學問——史上最重要的發現,大幅改變了人類文明。

當時只有少數人知道這個發現,不過很快便有其他學者得到相同結果。在24年後,公鑰加密法已有廣泛應用時,大眾才得悉其最早發現者。

首先,讓我們先了解公鑰加密法是甚麼,以及它解決了甚麼難題。

過往加密技術主要應用在軍事上,要下達指令、提供情報又不讓敵軍知道,必須把內容加密,使訊息即使在傳送期間被敵方截取也難以破解。

二次大戰期間,德國採用「謎」密碼機(Enigma machine)加密及解密文件,盟軍借助波蘭密碼專家的發現,以及一眾密碼分析專家——包括現代電腦之父圖靈(Alan Turing)——的秘密工作,破解了部分德軍通訊。

要破解納粹德軍的加密通訊,首先要知道其加密方式,換言之要知道「謎」的運作方式。但取得一部「謎」密碼機還不足夠,因為機器的設計容許多種設定模式,要破譯訊息的話,必須採用發訊者的設定,再把經加密的文字輸入,機器才會顯示出原本的內容。

如果長期使用相同設定傳送訊息,敵軍有機會分析截取到的內容破譯,因此納粹德軍會每天改變「謎」機的設定。要確保通訊順利,所有使用「謎」機通訊的單位均有一份清單(如下圖),列出每天使用的設定,這清單通常每月更新。

這份清單正好凸顯出當時所有加密方法的一大侷限︰發出訊息和接收訊息的雙方,需要同一組資訊(例如「謎」機的設定模式)——稱為密鑰(encyption key)——來加密及解密訊息,因此在首次使用加密通訊之前,雙方必須先協議使用甚麼密鑰。

加密通訊是為了確保傳送機密訊息時,沒有第三方能知道通訊內容而設立,然而密鑰本身亦屬於機密訊息,沒有密鑰又無法使用加密通訊。要解決這問題,似乎只能訴諸加密技術以外的方法,例如雙方先親身見面協定密鑰,或者派專人傳送密鑰。

傳送密鑰的過程不但增加成本,更成為加密通訊的潛在漏洞——派人傳送密鑰的話,這個人可靠嗎?途中會被人奪取密鑰嗎?而且問題看來無法解決。

pop_man_wiretap
Image Credit: Depositphotos

直到1970年代。

1976年,密碼學家迪菲(Bailey W. Diffie)及赫爾曼(Martin E. Hellman)發表劃時代論文〈密碼學的新方向〉,介紹了一套能夠安全而公開交換密鑰的方法,解決了傳送密鑰的難題。這套方法後來被稱為「迪菲—赫爾曼密鑰交換機制」(Diffie–Hellman key exchangem, DH)。[1]

通訊雙方首先在(非加密渠道)通訊時選定一個共用數字,再各自選擇一個秘密數字,DH機制透過巧秒的數論工具,讓雙方在不公開自己的秘密數字下,能夠成功產生相同的密鑰。由於竊聽者最多只能夠知道共用數字,但產生密鑰時須用上不公開的秘密數字,機制從而突破了傳送密鑰的限制。[2]

電腦科學家李維斯特(Ronald Rivest)在讀到迪菲及赫爾曼那篇論文後,說服同在麻省理工學院工作的薩莫爾(Adi Shamir)和阿德曼(Leonard Adleman)一起解決論文提及的一個難題。三人作出多次嘗試仍未成功,但在1977年的某個晚上,李維斯特睡不著而打開數學課本,成功解決了問題。他們於1978年發表論文,提出現稱為「RSA演算法」(以三人姓氏首字母命名)的公鑰加密法。

DH機制讓通訊雙方在毋須傳送密鑰的情況下,產生相同密鑰加密訊息,而RSA演算法則用另一種方法解決傳送密鑰的難題︰把密鑰分成用來加密訊息的「公鑰」(public key)和解密訊息的「私鑰」(private key)。

兩種加密方法
對稱加密法是指加密及解密均用相同密鑰的演算法,即是說,只要知道如何加密訊息,使能夠知道怎樣解密訊息(反之亦然);非對稱加密法則沒有此限制,加密和解密訊息使用不同密鑰。

DH機制在產生密鑰後使用對稱加密法,而RSA演算法則是個非對稱加密法。

公鑰加密系統面世後,密碼學自此變得不一樣,結合電腦和互聯網發展,加密技術已是現代社會不可或缺的工具。

DH機制及RSA演算法都源於美國,其實在迪菲及赫爾曼發表〈密碼學的新方向〉之前,已經有人得到相同結果,只不過要等到1997年底,這些密碼學先驅才獲得承認——因為他們都為英國的情報及國家安全機構「政府通訊總部」(GCHQ)工作,其發現被視作政府機密。

1960年代末期,英國軍方預期每個士兵都可用無線電設備聯絡,然而這得面對傳送密鑰的難題,包括如何運送及維持加密通訊所須的成本。在GCHQ工作的密碼學家艾利斯(James Ellis)於1969年被委託研究傳送密鑰的方法。

艾利斯從GCHQ的文件堆中找到一份匿名報告,內容關於貝爾電話公司(Bell Telephone)在二戰末期的一個計劃,研究由收訊方在通訊渠道加入噪音,以蓋過通訊內容,之後再透過消除噪音來收取訊息。基於各種缺點及限制,這個想法未有付諸實行,但其中一項特點引起艾利斯注意︰收訊方參與加密過程。

在仔細研究之後,艾利斯發現理論上不用派人傳送密鑰,仍可安全進行加密通訊,並於1969年底提交報告講述結果。可是艾利斯只證明了這種加密通訊有可能存在,未能找到可以落實其想法的數學函數,GCHQ的密碼學家努力研究亦未有結果。

Ellis
https://admin.thenewslens.com/post/108621/edit
艾利斯報告配上的插圖。

1973年9月,剛從劍橋大學畢業、主攻數論的數學家考克斯(Clifford Cocks)加入GCHQ。不久後他聽到艾利斯的發現,並得悉GCHQ內未有人能找到「容易算出結果,但難以從結果推算出輸入值」的單向函數——這是落實艾利斯想法的關鍵。

某天晚上考克斯想到艾利斯的問題,他的研究領域一直是數論,自然就想到質因數分解的問題——把兩個大質數相乘不算困難,反過來從結果尋找兩個質數則不然。

結果他利用這個特點,很快便找到滿足艾利斯要求的加密方法,結果只需要一頁紙便能夠寫完,根據文件記錄,1973年11月20日是公鑰加密法正式面世的日子。考克斯的發現同樣被GCHQ列作機密,雖然四年多之後發表的RSA演算法基本上一樣。

質因數分解有多難?想想以下例子︰
以紙筆計算,相信大多數人都能夠在幾分鐘內計算出10601×3797的答案(40251997)。反過來,如果只用紙筆去找出45160001的質因數,則要困難得多(答案是14479×3119)。

考克斯發現公鑰加密演算法後一年,他自12歲相識的朋友威廉森(Malcolm Williamson)加入了GCHQ。考克斯向威廉森提及公鑰加密法的概念,威廉森並不相信這種系統有可能存在,決定嘗試證明考克斯犯錯。

花了多個小時之後,威廉森最終失敗——他無法證明艾利斯的想法有缺陷——反而發現了另一種解決傳送密鑰問題的方法。當然,GCHQ同樣將之列作機密,未有公開,這種方法兩年後被稱為「迪菲—赫爾曼密鑰交換機制」。[3]

直到1997年12月,考克斯獲邀往一個研討會發表論文,內容關於RSA演算法的研究(但未被列作機密)。這個時候GCHQ終於決定公開文件,並讓考克斯在演講前先介紹GCHQ對公鑰加密系統的研究,公眾此時終於知道艾利斯、考克斯及威廉森的發現。可惜的是,艾利斯在此前一個月逝世,無緣見證自己的成果重見天日。

相關文章︰

註︰

  1. 赫爾曼曾提到其中「公開交換密鑰」這個想法源於其學生梅克爾(Ralph Merkle)較早前的論文,因此應稱為「迪菲—赫爾曼—梅克爾密鑰交換機制」(Diffie–Hellman–Merkle key exchange)。
  2. 竊聽者如想透過DH機制中公開交換的數字計算出密鑰,需要解決數論中的「離散對數」(discrete logarithm)問題,然而目前為止未有演算法能夠迅速計算答案。
  3. 有趣的是,在GCHQ內發現兩個方法的先後,跟DH機制及RSA演算法面世的次序相反。

資料來源︰

核稿編輯:王陽翎

或許你會想看
更多『評論』文章 更多『科學』文章 更多『Kayue』文章
Loader