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

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

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

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

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

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

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

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

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

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

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

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

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

直到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的密碼學家努力研究亦未有結果。

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對公鑰加密系統的研究，公眾此時終於知道艾利斯、考克斯及威廉森的發現。可惜的是，艾利斯在此前一個月逝世，無緣見證自己的成果重見天日。

內容 –

分類 –

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

我們想讓你知道的是

Tags：