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

最先秘密發現「公鑰加密法」的密碼學家
Photo Credit: Sebastiaan ter Burg, CC BY 2.0

我們想讓你知道的是

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

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)在二戰末期的一個計劃,研究由收訊方在通訊渠道加入噪音,以蓋過通訊內容,之後再透過消除噪音來收取訊息。基於各種缺點及限制,這個想法未有付諸實行,但其中一項特點引起艾利斯注意︰收訊方參與加密過程。


Tags: