人類的創造力：測試 RSA

《新密碼學將需要數百萬年才能破解》——這是馬丁·加德納（Martin Gardner）在 1977 年 8 月《科學美國人》雜誌上的一篇文章標題。這篇文章在廣泛讀者中引起了極大關注，不僅限於像里維斯特（Rivest）、沙米爾（Shamir）和阿德爾曼（Adleman）這樣的職業學者，還包括了眾多業餘愛好者和興趣使然的數學家。

里維斯特回憶道，一旦 RSA 算法開發完成，這三位發明者開始自問，對兩個大質數進行分解究竟有多難：「當時分解問題並不是一個學術研究的熱門領域，它有點像一個業餘愛好者關心的冷門領域，所以我們與一些對這類問題有興趣的人交流。」這引導他們找到了可以幫助他們尋找答案的人——加德納。里維斯特向加德納解釋了公鑰密碼學，並詢問他對大質數分解的難度有何了解。加德納回憶道，當他聽到這一切時，他感到十分激動：「我意識到這對密碼學是一個多麼重大的突破」，並邀請里維斯特到他位於紐約的家中解釋這一發現。加德納決定打破他寫文章的常規——他通常會提前幾個月規劃文章內容——並迅速寫出了這篇創新文章。

加德納的數學遊戲專欄已經連載了二十年，並吸引了許多業餘數學家的忠實讀者，正是這些人群成為了里維斯特、沙米爾和阿德爾曼測試其算法強度的目標讀者。加德納的文章通常以簡單的語言表達，而不是讓讀者被繁複的數學公式嚇退，他以盡可能簡單的散文來傳達要點。加德納的文章宣稱公鑰密碼學是「如此革命性，以至於所有之前的密碼及破解技術可能很快會淹沒在歷史的遺忘之中。」接下來的幾頁中，加德納解釋了迪菲和赫爾曼的突破，然後添加了有關里維斯特、沙米爾和阿德爾曼實現方法的細節。加德納寫道，任何想要了解 MIT 三人組方法的讀者可以寫信到 MIT，附上一個自寫信封並支付 35 分錢的郵資。

為了測試他們的算法，里維斯特創建了一個挑戰密碼，並提供 100 美元的獎金給任何能找到密鑰的人。該 129 位數字的加密消息隨加德納的文章一起刊登。

正如迪菲和赫爾曼在《密碼學新方向》中所觀察到的，雖然歷史上，數學證明曾被用來驗證加密算法的安全性，但這些所謂的安全算法屢屢被破解；因此，數學證明用來驗證安全性的做法「已經不再受人信任，並被加密分析的攻擊所取代。」本質上，為了讓社會接受一個算法是安全的，必須要經過一次集中的、持久的加密分析攻擊，只有當無數領先的密碼分析學者嘗試並失敗後，該算法才會被認為是安全的，或者至少被認為沒有明顯的漏洞。通過《科學美國人》廣泛的讀者群，里維斯特、沙米爾和阿德爾曼希望從那些已經嘗試並失敗的幾百人中獲得驗證。里維斯特估計，進行穷举攻击需要「40萬兆年」，因此唯一的風險是如果發現了算法中的捷徑。

在文章之前，加德納引用了愛德加·愛倫·坡（Edgar Allan Poe）的一句著名的密碼學語錄：「可以斷言，沒有任何人類的創造力能夠設計出一個人類的智慧無法破解的密碼。」文章的結尾，他觀察到不可破解的密碼的後果：「全世界有許多聰明的男人和女人，其中一些是天才，他們終其一生致力於現代密碼分析的掌握……如今這些人正站在即將開啟的陷門上，將被完全拋諸腦後。」加德納認為，坡所說的人類創造力已經達到了巔峰——密碼學家們正站在將永久摒棄密碼分析師的邊緣。

直到 1994 年 4 月，RSA129 挑戰才最終被破解，顯示出明文「THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE」——這些詞語是里維斯特隨機從字典中挑選出來的。破解這個密碼的工作花費了大約 600 名志願者在 20 多個國家進行了 8 個月的努力。阿德爾曼後來評論說，當里維斯特估算 RSA129 需要 40 萬兆年來破解時，「羅恩算錯了」，但那時這已經不再重要，因為所使用的密鑰大小已經大大超過了 129 位。參與此項目的一位成員，德里克·阿特金斯計算出，如果他們正在破解當時推薦的 RSA 1024 位密鑰大小，那麼破解所需的時間將是幾百萬年。