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

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

我們想讓你知道的是

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

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演算法面世的次序相反。

資料來源︰

核稿編輯:王陽翎