你是否想過，如果互聯(lián)網(wǎng)安全層在一夜之間出現(xiàn)了大裂縫怎么辦？如果裂縫深入到密碼算法的數(shù)學(xué)基礎(chǔ)上怎么辦？現(xiàn)在，這種情況似乎已經(jīng)出現(xiàn)。近日，德國密碼學(xué)家克勞斯·彼得·施諾爾（Claus Peter Schnorr）在其論文中聲稱自己已經(jīng)找到了一種“破解RSA加密系統(tǒng)”的方法。
此事引起密碼學(xué)界和量子密碼界的廣泛關(guān)注。雖然該論文內(nèi)容尚未得到驗(yàn)證，但是如果事實(shí)果真如此，必然會(huì)對(duì)很多應(yīng)用產(chǎn)生安全影響，因?yàn)槟壳霸S多對(duì)信息安全性要求較高的領(lǐng)域都在大量采用RSA非對(duì)稱加密算法。
面對(duì)這種情況，我們不免需要思考兩個(gè)問題：一是論文的內(nèi)容是否真實(shí)？二是加密的未來是什么？有沒有能取代RSA的密碼系統(tǒng)，即使在量子計(jì)算機(jī)時(shí)代（后量子密碼）也是安全的？
在撰寫本文時(shí)，數(shù)學(xué)家和密碼學(xué)家仍在針對(duì)論文內(nèi)容的真實(shí)性進(jìn)行討論和驗(yàn)證，而更多的人已經(jīng)在思考第二個(gè)問題，并開始草擬計(jì)劃以應(yīng)對(duì)這種災(zāi)難性的漏洞。他們正在努力創(chuàng)建更牢固的基礎(chǔ)，該基礎(chǔ)建立在通過多種協(xié)議實(shí)現(xiàn)的多種算法中，從而使切換變得更簡單。
還有一些密碼學(xué)家正在尋找RSA的替代品。因?yàn)闊o論此次論文結(jié)果真實(shí)與否，RSA的安全性問題早已引發(fā)業(yè)界關(guān)注。早在2010年7月，美國國家標(biāo)準(zhǔn)與技術(shù)研究所（NIST）就曾要求用戶在2010年12月31日前停止使用1024位RSA算法。根據(jù)RSA負(fù)責(zé)人的說法，雖然目前沒有證據(jù)表明RSA 1024位算法已被破解，但破解也只是時(shí)間問題，進(jìn)而引發(fā)加密信息泄露、數(shù)字簽名被偽造以及通信被竊聽等后果。
除此之外，隨著技術(shù)的不斷發(fā)展以及量子計(jì)算機(jī)的應(yīng)用，RSA安全性將再次遭遇挑戰(zhàn)。谷歌CEO Sundar Pichai曾預(yù)言，
“5-10年間，量子計(jì)算將會(huì)打破我們?nèi)缃袼赖募用芗夹g(shù)”。
密碼學(xué)家認(rèn)為，世界必須變得更加敏捷，因?yàn)殡S時(shí)都可能會(huì)出現(xiàn)許多潛在的裂縫。
RSA算法面臨的挑戰(zhàn)
分解大素?cái)?shù)
據(jù)悉，這份論文名為《通過SVP算法快速分解整數(shù)》，作者Claus Schnorr，現(xiàn)年77歲，于2011年從約翰·沃爾夫?qū)?middot;歌德大學(xué)退休。他是一位受人尊敬的密碼學(xué)家，Schnorr簽名算法便是以他的名字命名。在密碼學(xué)中，Schnorr簽名是由Schnorr簽名算法產(chǎn)生的數(shù)字簽名，它是一種數(shù)字簽名方案，以其簡單高效著稱，其安全性基于某些離散對(duì)數(shù)問題的難處理性。由于Schnorr簽名算法可以構(gòu)建更高效和隱私性更強(qiáng)的區(qū)塊鏈系統(tǒng)，一直備受區(qū)塊鏈開發(fā)者們的關(guān)注。
而RSA則是另一種歷史悠久且應(yīng)用廣泛的算法。它是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）共同提出的一種加密算法。這一算法主要依靠分解大素?cái)?shù)的復(fù)雜性來實(shí)現(xiàn)其安全性，由于大素?cái)?shù)之積難被分解，因此該密碼就難被破解。
近40年來，RSA算法經(jīng)歷了各種攻擊的挑戰(zhàn)，根據(jù)已披露文件顯示，目前被破解的最長RSA密鑰是768個(gè)二進(jìn)制位。也就是說，長度超過768位的密鑰，還未被破解，至少目前尚未有人公開宣布。
據(jù)悉，Schnorr最新發(fā)布的論文其實(shí)是其最近幾年發(fā)表的一系列論文的補(bǔ)充更新，其重述了將大素?cái)?shù)分解為數(shù)學(xué)家有時(shí)所說的“在由小得多的數(shù)字定義的多維晶格中搜索正確向量”的問題。由于其論文在很大程度上都是理論性的，這也使很多人懷疑RSA算法的安全性是否果真走到了盡頭。不過，到目前為止，尚未有人針對(duì)該方法進(jìn)行具體的公開演示，甚至一些嘗試過的人也表示該方法并不起作用。
修復(fù)RSA的困難性
解決新發(fā)現(xiàn)的攻擊帶來的問題并不是什么新鮮事。軟件公司通常會(huì)發(fā)布補(bǔ)丁來修復(fù)漏洞，并公開征求錯(cuò)誤報(bào)告，以鼓勵(lì)人們報(bào)告發(fā)現(xiàn)的問題。但是Schnorr的論文，如果得到證實(shí)，將會(huì)暴露出協(xié)議基礎(chǔ)的弱點(diǎn)，并且沒有一家公司對(duì)此協(xié)議負(fù)責(zé)。
一家名為“RSA”的公司曾在過去很長一段時(shí)間擁有該算法，但其專利已經(jīng)過期，也就是說現(xiàn)在整個(gè)互聯(lián)網(wǎng)上使用的大多數(shù)RSA實(shí)現(xiàn)都已經(jīng)不再是來自他們。許多受歡迎的程序庫都是開源的，由社區(qū)維護(hù)。
更糟糕的是，如果真的存在論文中所說的漏洞，那么根本無法簡單地（像許多漏洞或錯(cuò)誤那樣）通過幾行新代碼就能解決問題。任何有效的解決方案的發(fā)布都可能需要數(shù)年時(shí)間，因?yàn)闇y試和部署任何算法都需要時(shí)間。
而且，切換到新算法的過程可能也并不容易，因?yàn)樵S多加密軟件包都支持使用具有不同密鑰長度的不同算法選項(xiàng)。更深層次的挑戰(zhàn)可能來自更新身份驗(yàn)證基礎(chǔ)架構(gòu)，該基礎(chǔ)架構(gòu)將維護(hù)用于驗(yàn)證公鑰的證書等級(jí)。一些主流瀏覽器的當(dāng)前版本都隨附著來自不同證書頒發(fā)機(jī)構(gòu)的根證書，而它們大多數(shù)都依賴RSA算法。
想要在瀏覽器（或其他工具）中替換根證書，往往需要發(fā)行新版本才能實(shí)現(xiàn)，而且由于根證書功能十分強(qiáng)大，因此問題變得異常棘手。例如，某些攻擊涉及插入偽造的證書以幫助攻擊者假冒其他站點(diǎn)。截至目前為止，來自諸如Verisign、Amazon、GoDaddy和Entrust的一些主要證書頒發(fā)機(jī)構(gòu)的證書都依賴于RSA算法。
量子問題加劇挑戰(zhàn)
如何處理量子計(jì)算時(shí)代帶來的挑戰(zhàn)，是RSA安全性面臨的另一重大問題。密碼學(xué)界從幾年前就已經(jīng)開始尋找可以抵御量子計(jì)算的替代品，因?yàn)樗麄儞?dān)心量子計(jì)算時(shí)代可能很快就會(huì)到來。這將威脅像RSA這樣的算法，因?yàn)橛杀说?middot;索爾（Peter Shor）開發(fā)的量子計(jì)算最著名的算法之一就是整數(shù)的因式分解。
那么量子計(jì)算到底有多強(qiáng)大呢？舉個(gè)例子，如果我們對(duì)四百位整數(shù)進(jìn)行因式分解，現(xiàn)在最快的超級(jí)計(jì)算機(jī)也需要六十萬年，如果換做量子計(jì)算機(jī)，只需要幾個(gè)小時(shí)，甚至有人說幾分鐘就可以做到。而早在2012年，研究人員就表示他們已經(jīng)成功地使用了量子計(jì)算機(jī)將21分解為7和3的乘積，雖然這兩個(gè)數(shù)字并不是特別大。但是鑒于RSA加密算法嚴(yán)重依賴于大整數(shù)素因數(shù)分解的計(jì)算量以及耗費(fèi)的時(shí)間。RSA算法的核心設(shè)計(jì)就是通過提高破解成本來提高安全性。因此任何能夠增加計(jì)算速度的方法都會(huì)威脅到這種常用加密算法的安全性。而量子計(jì)算機(jī)可以加速Shor算法，安全專家警告稱，總有一天，量子計(jì)算能夠輕易破解RSA。而我們必須為這一刻做好準(zhǔn)備。
尋找一種新的非RSA密碼系統(tǒng)
由于擔(dān)心不法分子會(huì)利用量子計(jì)算機(jī)發(fā)動(dòng)攻擊，為了防止協(xié)議和算法被攻破，人們開始不斷對(duì)算法進(jìn)行強(qiáng)化。NIST的做法是建立一種新的“抗量子”或“后量子”算法集合。目前這種加密競賽已經(jīng)拉開了序幕。
NIST在去年夏天宣布了自2016年底開始第三輪競賽的初步成果。截至目前已經(jīng)開發(fā)出了69種不同的算法，優(yōu)秀的算法有26種，優(yōu)中選優(yōu)的算法為15種。當(dāng)然在這15種算法中，有7種算法最終突圍，另外8種算法將針對(duì)特殊的應(yīng)用程序或是繼續(xù)進(jìn)行開發(fā)研究或是需要繼續(xù)完善。
第三輪的7個(gè)候選算法，它們分別是：
公鑰加密/KEMs
Classic McEliece
CRYSTALS-KYBER
NTRU
SABER
數(shù)字簽名
CRYSTALS-DILITHIUM
FALCON
Rainbow
第三輪審查結(jié)束后，NIST將繼續(xù)對(duì)上述7名決賽入圍算法進(jìn)行審查，供下一步制定標(biāo)準(zhǔn)參考。由于CRYSTALS-KYBER、NTRU和SABER都是基于格的方案，NIST打算最多選擇一個(gè)作為標(biāo)準(zhǔn)。簽名方案中的CRYSTALS-DILITHIUM和FALCON也是如此。在NIST看來，這些基于格上困難問題的方案是公鑰加密/KEM和數(shù)字簽名方案中“最有前途的通用算法”。
此外，NIST還選擇了由Robert McEliece在1978年開發(fā)的一種較舊的簽名方法——Classic McEliece。它由Robert McEliece于1978年設(shè)計(jì)開發(fā)，是一種不對(duì)稱加密算法，基于代數(shù)編碼理論，使用了一系列糾錯(cuò)代碼Goppa。這種加密系統(tǒng)使用Goppa代碼作為專用密鑰，并將其編碼為線性代碼作為公共密鑰，要想對(duì)公共密鑰進(jìn)行解碼，就必須知道專用密鑰。
McEliece密碼系統(tǒng)雖然沒有獲得普遍采用，但非常強(qiáng)壯和穩(wěn)定，唯一的缺點(diǎn)就是公共密鑰太大，長達(dá)219-bit，這就使得加密信息要比明文信息大得多，從而提高了傳輸過程中的出錯(cuò)幾率，另外不對(duì)稱特性也使得這種技術(shù)無法用于數(shù)字認(rèn)證和簽名。三十年來針對(duì)這種加密系統(tǒng)的攻擊和破解一直不斷，但它始終穩(wěn)如泰山。
最后一個(gè)決賽入圍者被稱為Rainbow，它是一種數(shù)字簽名方案，基于多元多項(xiàng)式結(jié)構(gòu)構(gòu)造，屬于多變量密碼體系，而攻擊者難以解決這些變量。
RSA的這些新潛在替代品可能無法輕松地實(shí)現(xiàn)替代過程。有些速度要慢得多，而另一些可能無法提供相同的選項(xiàng)來生成簽名或加密數(shù)據(jù)。許多還在依賴較大的密鑰——可能大于或等于500KB，遠(yuǎn)遠(yuǎn)大于很多當(dāng)前的密鑰（可能只有幾百個(gè)字節(jié)）。
幫助創(chuàng)建公鑰密碼學(xué)的密碼學(xué)家Whitfield Diffie指出，新提案可能需要更多的計(jì)算才能建立。另一位數(shù)學(xué)家馬丁·赫爾曼（Martin Hellman）則表示，世界可能希望開發(fā)結(jié)合了多種不同算法的新協(xié)議。該協(xié)議不僅要簡單地依靠一種算法來創(chuàng)建隨機(jī)密鑰以加密某些數(shù)據(jù)，還應(yīng)運(yùn)行多種算法并將所有算法的密鑰組合成一個(gè)新密鑰（可能通過XOR或可能具有更詳盡的單向功能）。
Hellman警告稱，即便加密災(zāi)難尚未到來，制定災(zāi)難恢復(fù)計(jì)劃也可以幫助抵御多年來不斷演變加劇的威脅。他表示，
“從今天起50甚至100年后，如今的機(jī)密數(shù)據(jù)仍然應(yīng)該是機(jī)密的。因此，必須警惕任何可能會(huì)對(duì)如今受保護(hù)數(shù)據(jù)構(gòu)成威脅的發(fā)展趨勢，并時(shí)刻做好應(yīng)對(duì)準(zhǔn)備。”
本文翻譯自：https://www.csoonline.com/article/3613550/whats-next-for-encryption-if-the-rsa-algorithm-is-broken.html
