你是否想過，如果互聯網安全層在一夜之間出現了大裂縫怎么辦?如果裂縫深入到密碼算法的數學基礎上怎么辦?現在，這種情況似乎已經出現。近日，德國密碼學家克勞斯·彼得·施諾爾(Claus Peter Schnorr)在其論文中聲稱自己已經找到了一種“破解RSA加密系統”的方法。

此事引起密碼學界和量子密碼界的廣泛關注。雖然該論文內容尚未得到驗證，但是如果事實果真如此，必然會對很多應用產生安全影響，因為目前許多對信息安全性要求較高的領域都在大量采用RSA非對稱加密算法。

面對這種情況，我們不免需要思考兩個問題：一是論文的內容是否真實?二是加密的未來是什么?有沒有能取代RSA的密碼系統，即使在量子計算機時代(后量子密碼)也是安全的?

在撰寫本文時，數學家和密碼學家仍在針對論文內容的真實性進行討論和驗證，而更多的人已經在思考第二個問題，并開始草擬計劃以應對這種災難性的漏洞。他們正在努力創建更牢固的基礎，該基礎建立在通過多種協議實現的多種算法中，從而使切換變得更簡單。

還有一些密碼學家正在尋找RSA的替代品。因為無論此次論文結果真實與否，RSA的安全性問題早已引發業界關注。早在2010年7月，美國國家標準與技術研究所(NIST)就曾要求用戶在2010年12月31日前停止使用1024位RSA算法。根據RSA負責人的說法，雖然目前沒有證據表明RSA 1024位算法已被破解，但破解也只是時間問題，進而引發加密信息泄露、數字簽名被偽造以及通信被竊聽等后果。

除此之外，隨著技術的不斷發展以及量子計算機的應用，RSA安全性將再次遭遇挑戰。谷歌CEO Sundar Pichai曾預言，

密碼學家認為，世界必須變得更加敏捷，因為隨時都可能會出現許多潛在的裂縫。

RSA算法面臨的挑戰

分解大素數

據悉，這份論文名為《通過SVP算法快速分解整數》，作者Claus Schnorr，現年77歲，于2011年從約翰·沃爾夫岡·歌德大學退休。他是一位受人尊敬的密碼學家，Schnorr簽名算法便是以他的名字命名。在密碼學中，Schnorr 簽名是由 Schnorr 簽名算法產生的數字簽名，它是一種數字簽名方案，以其簡單高效著稱，其安全性基于某些離散對數問題的難處理性。由于Schnorr簽名算法可以構建更高效和隱私性更強的區塊鏈系統，一直備受區塊鏈開發者們的關注。

而RSA則是另一種歷史悠久且應用廣泛的算法。它是1977年由羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)共同提出的一種加密算法。這一算法主要依靠分解大素數的復雜性來實現其安全性，由于大素數之積難被分解，因此該密碼就難被破解。

近40年來，RSA算法經歷了各種攻擊的挑戰，根據已披露文件顯示，目前被破解的最長RSA密鑰是768個二進制位。也就是說，長度超過768位的密鑰，還未被破解，至少目前尚未有人公開宣布。

據悉，Schnorr最新發布的論文其實是其最近幾年發表的一系列論文的補充更新，其重述了將大素數分解為數學家有時所說的“在由小得多的數字定義的多維晶格中搜索正確向量”的問題。由于其論文在很大程度上都是理論性的，這也使很多人懷疑RSA算法的安全性是否果真走到了盡頭。不過，到目前為止，尚未有人針對該方法進行具體的公開演示，甚至一些嘗試過的人也表示該方法并不起作用。

修復RSA的困難性

解決新發現的攻擊帶來的問題并不是什么新鮮事。軟件公司通常會發布補丁來修復漏洞，并公開征求錯誤報告，以鼓勵人們報告發現的問題。但是Schnorr的論文，如果得到證實，將會暴露出協議基礎的弱點，并且沒有一家公司對此協議負責。

一家名為“RSA”的公司曾在過去很長一段時間擁有該算法，但其專利已經過期，也就是說現在整個互聯網上使用的大多數RSA實現都已經不再是來自他們。許多受歡迎的程序庫都是開源的，由社區維護。

更糟糕的是，如果真的存在論文中所說的漏洞，那么根本無法簡單地(像許多漏洞或錯誤那樣)通過幾行新代碼就能解決問題。任何有效的解決方案的發布都可能需要數年時間，因為測試和部署任何算法都需要時間。

而且，切換到新算法的過程可能也并不容易，因為許多加密軟件包都支持使用具有不同密鑰長度的不同算法選項。更深層次的挑戰可能來自更新身份驗證基礎架構，該基礎架構將維護用于驗證公鑰的證書等級。一些主流瀏覽器的當前版本都隨附著來自不同證書頒發機構的根證書，而它們大多數都依賴RSA算法。

想要在瀏覽器(或其他工具)中替換根證書，往往需要發行新版本才能實現，而且由于根證書功能十分強大，因此問題變得異常棘手。例如，某些攻擊涉及插入偽造的證書以幫助攻擊者假冒其他站點。截至目前為止，來自諸如Verisign、Amazon、GoDaddy和Entrust的一些主要證書頒發機構的證書都依賴于RSA算法。

量子問題加劇挑戰

如何處理量子計算時代帶來的挑戰，是RSA安全性面臨的另一重大問題。密碼學界從幾年前就已經開始尋找可以抵御量子計算的替代品，因為他們擔心量子計算時代可能很快就會到來。這將威脅像RSA這樣的算法，因為由彼得·索爾(Peter Shor)開發的量子計算最著名的算法之一就是整數的因式分解。

那么量子計算到底有多強大呢?舉個例子，如果我們對四百位整數進行因式分解，現在最快的超級計算機也需要六十萬年，如果換做量子計算機，只需要幾個小時，甚至有人說幾分鐘就可以做到。而早在2012年，研究人員就表示他們已經成功地使用了量子計算機將21分解為7和3的乘積，雖然這兩個數字并不是特別大。但是鑒于RSA加密算法嚴重依賴于大整數素因數分解的計算量以及耗費的時間。RSA算法的核心設計就是通過提高破解成本來提高安全性。因此任何能夠增加計算速度的方法都會威脅到這種常用加密算法的安全性。而量子計算機可以加速Shor算法，安全專家警告稱，總有一天，量子計算能夠輕易破解RSA。而我們必須為這一刻做好準備。

尋找一種新的非RSA密碼系統

由于擔心不法分子會利用量子計算機發動攻擊，為了防止協議和算法被攻破，人們開始不斷對算法進行強化。NIST的做法是建立一種新的“抗量子”或“后量子”算法集合。目前這種加密競賽已經拉開了序幕。

NIST在去年夏天宣布了自2016年底開始第三輪競賽的初步成果。截至目前已經開發出了69種不同的算法，優秀的算法有26種，優中選優的算法為15種。當然在這15種算法中，有7種算法最終突圍，另外8種算法將針對特殊的應用程序或是繼續進行開發研究或是需要繼續完善。

第三輪的7個候選算法，它們分別是：

公鑰加密/KEMs

• Classic McEliece
• CRYSTALS-KYBER
• NTRU
• SABER

數字簽名

• CRYSTALS-DILITHIUM
• FALCON
• Rainbow

第三輪審查結束后，NIST將繼續對上述7名決賽入圍算法進行審查，供下一步制定標準參考。由于CRYSTALS-KYBER、NTRU和SABER都是基于格的方案，NIST打算最多選擇一個作為標準。簽名方案中的CRYSTALS-DILITHIUM 和FALCON也是如此。在NIST看來，這些基于格上困難問題的方案是公鑰加密/KEM和數字簽名方案中“最有前途的通用算法”。

此外，NIST還選擇了由Robert McEliece在1978年開發的一種較舊的簽名方法——Classic McEliece。它由Robert McEliece于1978年設計開發，是一種不對稱加密算法，基于代數編碼理論，使用了一系列糾錯代碼Goppa。這種加密系統使用Goppa代碼作為專用密鑰，并將其編碼為線性代碼作為公共密鑰，要想對公共密鑰進行解碼，就必須知道專用密鑰。

McEliece密碼系統雖然沒有獲得普遍采用，但非常強壯和穩定，唯一的缺點就是公共密鑰太大，長達219-bit，這就使得加密信息要比明文信息大得多，從而提高了傳輸過程中的出錯幾率，另外不對稱特性也使得這種技術無法用于數字認證和簽名。三十年來針對這種加密系統的攻擊和破解一直不斷，但它始終穩如泰山。

最后一個決賽入圍者被稱為Rainbow，它是一種數字簽名方案，基于多元多項式結構構造，屬于多變量密碼體系，而攻擊者難以解決這些變量。

RSA的這些新潛在替代品可能無法輕松地實現替代過程。有些速度要慢得多，而另一些可能無法提供相同的選項來生成簽名或加密數據。許多還在依賴較大的密鑰——可能大于或等于500KB，遠遠大于很多當前的密鑰(可能只有幾百個字節)。

幫助創建公鑰密碼學的密碼學家Whitfield Diffie指出，新提案可能需要更多的計算才能建立。另一位數學家馬丁·赫爾曼(Martin Hellman)則表示，世界可能希望開發結合了多種不同算法的新協議。該協議不僅要簡單地依靠一種算法來創建隨機密鑰以加密某些數據，還應運行多種算法并將所有算法的密鑰組合成一個新密鑰(可能通過XOR或可能具有更詳盡的單向功能)。

Hellman警告稱，即便加密災難尚未到來，制定災難恢復計劃也可以幫助抵御多年來不斷演變加劇的威脅。他表示：

本文翻譯自：

https://www.csoonline.com/article/3613550/whats-next-for-encryption-if-the-rsa-algorithm-is-broken.html