我想談談，這是第三場演講，關於 RSA 的早期歲月、我們當時認為自己在做的事情、它的發明歷史，以及我們一路走來學到的一些教訓。解決現實世界問題的重要性，我認為非常重要。我想先從這點開始談起。運用電腦科學理論和數論，Len 強調了這兩門學科作為我們工作背景的重要性。我想談談保持樂觀並嘗試做看似不可能的事情的重要性。具體談談 RSA 的發明。然後談談 Moore's Law 對密碼學的重要性。這在很大程度上是公開金鑰密碼學的一個關鍵特徵。在公開場合進行密碼學研究的重要性，這與 Len 最後的發言產生共鳴。密碼學理論的重要性，以及組織和研究的重要性。嘗試解決現實世界的問題是我們最初認為我們正在做的事情的核心。
解決現實世界問題的驅動力
我們受到了 Diffie 和 Hellman 那篇劃時代論文《密碼學的新方向》的啟發，他們在其中說：「我們今天正處於密碼學革命的邊緣。」如果我曾見過預言自我實現，那就是這個。他們在很大程度上真正開啟了密碼學領域的公開研究。他們提出了公開金鑰密碼系統的想法，這是與 Ralph Merkle 共同開發的，並引入了對我來說最令人興奮和最具啟發性的概念：數位簽章的概念。某人可以創建一個任何人都能驗證但無人能偽造的數位簽章，這個想法對我來說是驚人的，並且是一個高度激勵我的想法。我認為這種應用代表了密碼學領域自那以後發生的事情。許多好的密碼學研究都是由應用驅動的，思考現實世界，思考如何將我們的現實生活帶入電子世界，嘗試找出如何安全地映射這些事物。電子商務、心靈撲克、投票、其他選項等都是遊戲的一部分。由於來自應用方面的驅動，這個領域非常豐富。
電腦科學理論與數論的基石
就像 Len 說的，在 76 年，演算法和複雜性理論才剛剛起步。密碼學是這些領域的消費者。它需要對「好人」來說容易解決的問題，比如乘法或尋找質數。它需要對對手來說無法解決的難題。因此，正如 Len 指出的，我們借鑑了這些領域，試圖真正實現公開金鑰密碼系統的首次實現，首次公開實現。我們也借鑑了數論。Diffie 和 Hellman 在他們的論文中已經使用了數論進行金鑰協商。雙方可以利用模冪運算來協商一個秘密金鑰。我們越是尋找公開金鑰密碼系統，就越看到需要某種代數結構。我們不斷地回到這個廣闊而深邃的數論寶庫及其美麗的結果，以及 Len 已經提到的那些開始出現的複雜性理論結果。因數分解的難度開始為人所知。就像 Len 說的，它不是多項式時間。我們不確定它有多難，但它似乎是個值得提出的好東西，而這確實是我們主要的貢獻之一，就是將因數分解引入。
嘗試看似不可能之事的重要性
關於做看似不可能的事情，Diffie 和 Hellman 將實現公開金鑰密碼系統的問題留作懸而未決的開放問題。你能否找到兩個互為反函數的函數 E 和 D，其中 E 可以公開而不洩露 D 的運作方式？我們為此苦苦掙扎，有時認為這是不可能的。我們花時間試圖證明這是不可能的。我們失敗了。但從那以後，我們看到了越來越多的例子，證明一些看似本質上相互矛盾的事情實際上是可以解決的。因此，我想提出這個密碼學的元定理：任何顯然相互矛盾的要求集合，實際上只要有正確的數學方法，就可以得到滿足。令我驚訝的是，這條定理竟然如此頻繁地適用。你看到一組要求，它們看起來就像是這樣（做手勢），但只要有正確的洞察力和正確的數學，你就可以把它們整合在一起。我們嘗試並拋棄了許多方法。其中一些是背包問題類型的方法。而 Len 特別擅長扼殺 Adi 和我提出的一些建議。否則，我們就不會在這裡了。未知大小的群組似乎是一個有趣的概念，還有置換多項式的想法。我們嘗試了許多不同主題的變體。
RSA 的發明
最後，在某個晚上的一次逾越節家宴後，在 Ani Bruce 的家裡，我在公寓裡坐著，我們一直在研究的這些想法似乎都到位了，於是 RSA 系統，也就是現在所知的 RSA，首次構想出來了。正如我們現在所知，它使用兩個大質數的乘積來形成模數 n。加密是取 e 次方模 n。解密是取另一個冪 d 次方模 n。所以公開金鑰是 e 和 n，私密金鑰是 d 和 n，因數分解的難度可以保護（使其難以被攻擊）...阻止對手發現私密金鑰。當時我們不知道這個方案有多難或多安全。這看起來像是一個可行的方案，但我們已經看到太多方案報廢了，所以這似乎又是另一個早上 Len 會看一看然後說：「抱歉，Ron，這個也不行。」但我們越深入研究，它就越站得住腳。我們尋找那些評估過因數分解難度、或許能對該方案安全性提供建議的人，除了我們自己的評估之外。Martin Gardner 聽說了這件事，並對此產生了興趣，在 1977 年 8 月寫了一篇專欄文章描述了這個方案。這確實是 RSA 方案的首次發表，並作為他要求的一個例子，包含了一個我們生成的 129 位數 n，它是兩個質數的乘積，我們願意為任何能分解這個數或解碼我們使用 RSA 加密的相關訊息的人提供 100 美元。我們不知怎麼估計這需要 40 千萬兆年才能破解。我們關於估計過程的筆記目前已遺失。同一篇文章向讀者提供了寄送貼有回郵郵票信封即可獲得我們技術備忘錄的副本的服務，該備忘錄於年初出版。這是左邊這張黃色的。在解決了一些我們之前從未聽說過的出口法問題後，我們最終為研究生們舉辦了一個派對，消費了大量的披薩並將這些文件釘好。我們釘好了大約 4000 份。然後 ACM 在翌年年初發表了我們的文章。這引起了很多宣傳。我們對宣傳量感到非常驚訝。《時代》雜誌在 1978 年寫了一篇文章，其中包含了我們三個的這張照片。當時很少有人注意到我們寫在黑板上的小玩笑。那真是太棒了。黑板上藏著「因此 P 等於 NP」。我們最終合作的群組 ZN Star，即模 N 的乘法群，結果證明是一個適用於各種用途的絕妙群組。從那以後它已被多次使用。因數分解使得對手難以確定該群組的大小或計算該群組中的離散對數。然而，破解 RSA 的難度與因數分解或計算離散對數不太相同。它實際上是取 e 次方模 N。因此，這已成為一個獨立的複雜性理論假設，獨立存在，與因數分解的難度不同。這已成為所謂的 RSA 假設。事實上，隨著該領域的發展，已出現了此假設的擴展。現在經常使用強 RSA 假設，該假設假定取 e 次方模 N 是困難的，即使對手可以選擇指數 e，任何大於一的整數。這就是 RSA 的發明。
Moore's Law 與實用性
然後我們坐下來試圖看看，這真的是一個實用的方案嗎？當我們在工作站上，一台一 MIPS 的 VAX，編程實現它時，它非常慢。執行一次 RSA 操作大約需要 30 秒。對於實際使用來說實在太慢了。尋找質數，你根本不想聽。那真是非常非常慢。IBM PC 不久後出現了，但速度並未快多少。所以我們研究了 RSA 的硬體實現。我們研究了專用電路板。我們為 Adi、Len 和我建造了它，以便參與硬體設計。那本身就是一次非常有趣的嘗試。但我們確實這麼做了。我們也研究了專用 VLSI 晶片，並設計了一款，它能在不到一秒的時間內計算 RSA。我們這樣做部分是為了證明，這對我們來說是一次有趣的體驗，學習這些技術，同時也為了證明 RSA 的實用性。今天，Moore's Law 拯救了我們。軟體現在運行速度提高了數千倍，沒有人再花很多精力為這類事情製作專用硬體。你用軟體就可以做得很好。軟體確實是主導，而網路，正是由 Moore's Law 促成的，為許多實際發生的真正密碼學應用提供了主要動力。這是一張 RSA 晶片的照片。它從未完全正常工作。有些電感問題導致它無法運作，但我們仍然為我們的設計感到驕傲。
在公開場合進行密碼學研究
我認為在公開場合進行研究非常重要，密碼學已經從一個許多研究私下進行的領域，轉變成一個許多研究現在公開進行的領域。密碼學領域因此蓬勃發展，有很多很好的理由。我認為要建立對你所使用密碼學的信心，確實需要
密碼學理論的重要性
當人們檢視所有這些方案時，密碼學理論不斷發展，我認為密碼學理論對這個領域確實很重要。在某些領域，實踐與理論會分歧。密碼學是一個奇妙的領域，實踐與理論如果說有什麼，那就是匯合。理論受到新問題、新應用的啟發，反過來又豐富了實踐。所以這是一個理論與實踐如同雙胞胎般緊密結合的領域。機率加密理論、針對選擇密文攻擊的安全性、數位簽章理論、零知識協議理論、面向實踐的可證明安全性理論，一系列概念已經被發展出來，它們是出色的理論建構，並且與實踐非常相關。因此，密碼學中理論與實踐之間的協同作用令人欣喜。
組織與研究的重要性
最後，我想以強調組織對研究也很重要來結束。ACM，我想再次感謝 ACM 贊助圖靈獎。CACM，由 ACM 經營，早在 1978 年就發表了 RSA 的論文，他們對許多研究導向活動的贊助非常出色。David Chown 是國際密碼學研究協會 (International Association for Cryptologic Research) 的主要創始人之一，該協會從 1981 年開始每年在 UC Santa Barbara 舉辦密碼學會議。這為許多未能進入 Stock 或其他會議的密碼學論文提供了一個論壇。而 RSA 這家公司也贊助會議，並在政府試圖壓制各種形式密碼學時，在許多密碼學政策辯論中擔任領導者，並幫助制定了如 PKS 標準等密碼學標準。