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

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

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

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

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

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

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

RSA算法面臨的挑戰(zhàn)

分解大素數(shù)

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

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

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

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

修復RSA的困難性

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

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

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

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

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

量子問題加劇挑戰(zhàn)

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

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

尋找一種新的非RSA密碼系統(tǒng)

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

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

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

公鑰加密/KEMs

• Classic McEliece
• CRYSTALS-KYBER
• NTRU
• SABER

數(shù)字簽名

• CRYSTALS-DILITHIUM
• FALCON
• Rainbow

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

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

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

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

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

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

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

本文翻譯自：

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