國盾小課堂 | 量子計算到底有多厲害？
上期，中國信息協(xié)會量子信息分會的康老師帶我們剖析了量子安全概念的由來，其提出就是為了應(yīng)對量子計算的挑戰(zhàn)，兩者是一矛一盾，一攻一防的關(guān)系。
“不知攻、焉知防”
本期，國小盾繼續(xù)邀請康老師
帶各位同學細探“量子計算”
01?量子計算攻擊的特點
提起量子計算，經(jīng)常聽到的反應(yīng)是量子力學“太抽象”，不確定性原理、量子糾纏等量子力學基本規(guī)律“反直覺”，量子計算又是屬于典型的交叉學科“太綜合”、“很難學”，這堂課不是量子計算教學，只是從量子安全這一角度對其進行一番臨摹。
量子力學是在最基本的層面上針對物質(zhì)和能量的研究，它的目標是揭示自然基本構(gòu)件的屬性和行為。而量子計算是一類遵循量子力學規(guī)律進行高速數(shù)學和邏輯運算、存儲及處理量子信息，解決各類問題的新型計算技術(shù)。廣義的量子計算還包括應(yīng)用可控的量子體系對要研究的物理體系進行模擬，它一般也被稱為量子模擬，1981年Richard Feynman首次提出量子計算機概念時也闡釋為量子計算機能夠?qū)α孔酉到y(tǒng)的演化進行有效模擬。
要理解量子計算，確實離不開這一系列抽象概念，而且同學們會發(fā)現(xiàn)，量子計算的定義在不同著作及論文、在不同場景和語境下也有多種形式的表達，在此以簡潔易懂為原則，以滿足我們對量子安全的理解為需求，而盡量不涉及無關(guān)的概念。
量子計算之所以具有經(jīng)典計算無法比擬的信息攜帶和并行處理能力，是由于它以量子比特為基本單元，通過量子態(tài)的受控演化實現(xiàn)數(shù)據(jù)的存儲和計算，以量子相干疊加和干涉來編碼和處理信息，量子計算對量子相干疊加態(tài)的每一個疊加分量進行變換相當于一次經(jīng)典計算，所有疊加分量變換對應(yīng)的經(jīng)典計算可同時完成，并按一定的概率振幅疊加，給出量子計算輸出結(jié)果。
量子計算機是實現(xiàn)量子計算的物理裝置，它可基于多種不同物理體系實現(xiàn)，如離子阱體系、超導電路體系、半導體量子點體系、腔量子電動力學體系、核磁共振體系、線性光學體系、拓撲體系等，這些物理體系擁有各自的優(yōu)缺點，作為不同技術(shù)路線各自發(fā)展階段和重點、要克服的主要困難也不同，這里就不做展開介紹了。但了解量子計算機的發(fā)展階段對我們了解量子安全發(fā)展態(tài)勢很必要。
第一個階段是實現(xiàn)量子優(yōu)越性（quantum advantage或quantum supremacy，也譯為“量子霸權(quán)”），即針對特定問題的計算能力超越經(jīng)典超級計算機。達到這一目標需要約50個量子比特的相干操縱。這一階段目標已在2019年由Google公司在其超導量子計算系統(tǒng)上率先實現(xiàn)。2020年、2021年中國科學技術(shù)大學在其光量子計算原型機系統(tǒng)“九章”和超導量子計算原型機系統(tǒng)“祖沖之”上再次實現(xiàn)了量子優(yōu)越性且性能顯著提升，中國已成為世界上唯一一個在兩個技術(shù)路線上實現(xiàn)量子優(yōu)越性的國家。
第二個階段是實現(xiàn)具有實際應(yīng)用價值的專用量子模擬系統(tǒng)也就是專用量子模擬機，即相干操縱數(shù)百個量子比特，應(yīng)用于組合優(yōu)化、量子化學、機器學習等特定問題，指導材料設(shè)計、藥物開發(fā)等，達到該階段需要五至十年。例如，實現(xiàn)高斯玻色采樣功能的“九章”量子計算原型機就是專用量子模擬機，還有當前D-Wave公司研發(fā)出來的量子退火機，它被大部分研究者認為還達不到這一階段專用量子模擬機的要求。
第三個階段是實現(xiàn)可編程通用量子計算機，即相干操縱至少數(shù)百萬個量子比特，能在經(jīng)典密碼破解、大數(shù)據(jù)搜索、人工智能等方面發(fā)揮巨大作用。由于量子比特容易受到環(huán)境噪聲的影響而出錯，對于規(guī)?；牧孔颖忍叵到y(tǒng)，通過量子容錯、量子糾錯等技術(shù)來保證整個系統(tǒng)的正確運行是必然要求，也是一段時期內(nèi)面臨的主要挑戰(zhàn)。由于技術(shù)上的難度，何時實現(xiàn)通用量子計算機尚不明確，學術(shù)界一般認為還需要十年到二十年的時間。
如上圖所示，實現(xiàn)容錯量子計算需要一臺擁有大量低錯誤率量子比特的量子計算機，其中虛線對應(yīng)目前達到的錯誤率p=1%，實現(xiàn)通用量子計算需要錯誤率明顯低于0.1%的閾值以及百萬以上的物理量子比特，目前的技術(shù)還是無法實現(xiàn)的。
從上述發(fā)展階段描述容易看出，一是實現(xiàn)實用的通用量子計算機技術(shù)難度很大，是一個需要全球?qū)W界、工業(yè)界長期艱苦努力的任務(wù)。目前研發(fā)出的量子計算機（如谷歌的Sycamore等）屬于中型含噪量子（NISQ）計算階段的初期，仍處于技術(shù)驗證和原理樣機研制階段，仍面臨量子比特數(shù)量少、相干時間短、出錯率高等諸多挑戰(zhàn)。二是比起通用量子計算，專用量子計算（或稱非標準量子計算）會更早實現(xiàn)，對于破譯密碼這一具有戰(zhàn)略價值的需求，是否會提前催生出專擅此道的量子專用機來？我們不得而知。
在此引述量子密碼專家高飛、孫思維在2021年《密碼學報》量子計算與密碼分析專欄序言中開篇一段話作為總結(jié)——“量子計算是一種全新的計算模式，是一項可能對傳統(tǒng)技術(shù)體系產(chǎn)生沖擊、進行重構(gòu)的重大顛覆性技術(shù)創(chuàng)新。量子計算在大整數(shù)分解、離散對數(shù)計算、密鑰窮搜索等多個計算問題上展現(xiàn)出了顯著優(yōu)勢，一旦成規(guī)模的通用量子計算機問世，將對一些密碼體制構(gòu)成嚴重的威脅?！?/strong>
02?典型量子攻擊——Shor算法
1994年，Peter Shor發(fā)現(xiàn)能夠快速分解大數(shù)質(zhì)因子的量子算法，由此展開了研究量子算法的第一次熱潮，可見其重要性。Shor量子算法可以在多項式時間內(nèi)解決大整數(shù)分解和離散對數(shù)求解等復(fù)雜數(shù)學問題，因此可以對廣泛使用的RSA、ECC、DSA、ElGamal等公鑰密碼算法進行快速破解。例如：分解一個400位的大整數(shù)，經(jīng)典計算機約需要5×1022次操作，而量子計算機約需要6×10?次操作，量子計算機所需操作數(shù)僅為經(jīng)典計算機的80萬億分之一。
Shor算法另一個重要特點是，RSA和ECC等公鑰密碼算法無法通過增加密鑰長度抵御未來量子計算機使用Shor算法的攻擊。研究表明，攻擊RSA算法所需的量子比特數(shù)與RSA密鑰的長度大致成線性比例關(guān)系，所需的量子門操作次數(shù)與RSA密鑰的長度成多項式關(guān)系，也就是說，RSA算法無法通過增加密鑰長度來抵御量子計算的指數(shù)加速攻擊。
近期研究論文已表明，破解主流的2048位RSA加密，在可預(yù)見的未來就可能實現(xiàn)。2019年谷歌研究團隊發(fā)文認為量子計算機將在8小時內(nèi)破解2048位RSA加密，但需要2000萬個量子比特。2021年法國研究者發(fā)布的研究成果表明，通過將量子存儲器集成到量子計算機中，13436個量子比特耗費177天就能破解RSA-2048，比此前所需的量子比特數(shù)減少了3個數(shù)量級。根據(jù)IBM和谷歌的技術(shù)路線圖，到2029年將實現(xiàn)百萬量子比特，未來隨著量子比特數(shù)的增加，破解時間將指數(shù)級縮減，Shor算法的實際破解威力也將愈加顯現(xiàn)，密鑰長度再增加也抵御不了這種指數(shù)級增長的攻擊難易程度變化。況且，RSA-2048相較RSA-1024密鑰長度進行了加倍，意味著運算時間、存儲要求這些方面的增加不是簡單的二倍關(guān)系而是更多。簡單的認為現(xiàn)有公鑰可以隨意的將密鑰長度增長下去以抵御量子攻擊是錯誤的。
所以，結(jié)論就是，Shor量子算法對基于大整數(shù)分解和離散對數(shù)問題的公鑰密碼產(chǎn)生的嚴重威脅，無法通過增加密鑰長度解決，需要采用新的、量子安全的密碼算法和技術(shù)加以應(yīng)對。
03?典型量子攻擊——Grover算法
1996年Lov K. Grover提出了Grover量子算法。簡單地說，它能夠?qū)o序數(shù)據(jù)庫的搜索時間降為平方根時間。例如，當需要從N個未分類的客體中搜索出某個特定客體時，經(jīng)典計算機需要一個個查詢，直到找到所要的客體，平均要查（N+1）/2次，而采用Grover算法的量子計算機只需?N^(1/2)?次。
那么，搜索問題是如何擴展應(yīng)用到密碼破解問題上的呢？這是因為，依據(jù)計算復(fù)雜性理論，好的對稱密碼算法設(shè)計能在理論上等價于不可區(qū)分的偽隨機數(shù)生成問題，而對于偽隨機數(shù)的可區(qū)分性問題，一般認為又可以等價為無結(jié)構(gòu)數(shù)據(jù)庫的隨機搜索問題求解這一問題。例如，Grover算法可以有效地攻破DES或輕量級算法等密鑰長度較短的對稱密碼。對于DES破譯而言，其本質(zhì)就是從2?*個可能的密鑰中尋找正確密鑰。若以每秒10*次的運算速率，經(jīng)典計算機要花1000年，而采用Grover算法的量子計算機所需時間低于4分鐘。
對比于Shor算法，Grover算法破解密碼的方式看似比較“暴力”，適用性也強——它同時適用于對稱密碼和公鑰密碼破譯，但破解效率的比對卻沒有Shor算法那么懸殊，也就是Grover量子算法破解密碼比傳統(tǒng)計算機效率更高，但這個加速不是指數(shù)級加速，而是平方級加速，再通俗的說，Grover算法破解密碼的能力基本上等價于將等效密鑰長度減半。這也就直接導致了對Grover算法攻擊的應(yīng)對措施比較“溫和”，密碼界研究者一般公認需將對稱密碼算法使用的密鑰長度加倍；對于無密鑰參與的哈希函數(shù),應(yīng)將哈希函數(shù)輸出長度加倍。
綜合來看，可以用下表定性描述量子計算機對常用各類密碼算法的影響（表格摘自Report on Post-Quantum Cryptography. NIST），可見，量子計算攻擊下，很難有密碼系統(tǒng)能夠“事不關(guān)己”或“獨善其身”。
在闡述量子計算攻擊特點的最后，需要指出，一方面，量子計算、量子算法在快速發(fā)展之中，雖然人們認為，并非所有密碼算法都容易受到量子計算的攻擊，部分算法被認為是量子安全的，但對于評估什么計算問題是量子計算困難的，也要有發(fā)展和動態(tài)的視角。例如目前被認為是量子安全的算法在未來不再安全的可能性依然存在，這種不安全可能來自新的量子破譯算法，也可能來自新的經(jīng)典密碼分析技術(shù)。另一方面，量子計算不是萬能的，它不能完全取代經(jīng)典計算，量子計算究竟能多大程度解決多少有重要實際應(yīng)用價值的計算問題仍在研究和探索中。
04?量子計算攻擊點是密碼防線的軟肋
量子計算作為一種未來可行的攻擊方式，其攻擊對象本來就是密碼這一信息安全的基礎(chǔ)，而從上面，我們知道了量子攻擊是“有兩把刷子”的，那如此厲害的攻擊方式，如果選定的具體攻擊點又很合適，豈不是可能造成的破壞效果要加倍不成。
在此要說，量子計算的主要攻擊點——公鑰密碼特別是基于公鑰密碼的密鑰管理，確實可以稱是現(xiàn)有密碼防線的軟肋。原因如何，我們接著往下看。
密鑰管理是密碼系統(tǒng)的必備基礎(chǔ)功能，在國標GB/T 17901.1-2020中，定義的密鑰管理基本內(nèi)容包括：生成、注冊、認證、注銷、分發(fā)、安裝、存儲、歸檔、撤銷、派生以及銷毀等。密鑰管理內(nèi)涵豐富、作用重大，它對密碼系統(tǒng)起到支撐作用，與密碼應(yīng)用同等重要，可以說沒有密鑰管理也就沒有密碼應(yīng)用。通俗的說，密鑰管理與密碼應(yīng)用類似于樂隊中的指揮與各樂手的關(guān)系，樂隊的發(fā)聲來自樂手，但樂手一定要受指揮的控制，在指揮的無聲操控下，眾多樂手才能奏響和諧的樂章。
現(xiàn)代密碼學者的另一共識就是，密碼算法和協(xié)議應(yīng)當不包含秘密，而且最好是經(jīng)過充分的公開，得到廣泛的評估以保證其中無安全漏洞和缺陷。唯一需要保持秘密的是密鑰。因此，密鑰管理上需要更加嚴格的安全保護，例如安全防護級別應(yīng)該更高，密鑰管理功能的實現(xiàn)應(yīng)單獨組網(wǎng)、物理隔離，技術(shù)體制上也應(yīng)與密鑰應(yīng)用盡可能有所區(qū)別、有獨立性。這點也很容易理解，否則，若哪個密碼應(yīng)用系統(tǒng)被破解，會直接導致密鑰管理系統(tǒng)的失效和被攻破，而且，借助管理系統(tǒng)與管理服務(wù)的“內(nèi)部通道”，敵人很容易“攻破一點，殃及一片”。
形容管理技術(shù)相關(guān)的一句話我們都耳熟能詳了——“三分技術(shù)、七分管理”，應(yīng)用在密鑰管理上也完全適用，因此人們才在高等級密碼系統(tǒng)的密鑰管理上經(jīng)常采用人工遞送的手段。往深入說，就是由于密鑰管理的高度敏感性，新技術(shù)的應(yīng)用人們會更加謹慎，更多的依靠管理上、工程上的重重手段去完成密鑰管理任務(wù)。
從二戰(zhàn)以后，可以說密鑰管理上采用的最顯著技術(shù)革新就是以CA（數(shù)字證書認證中心）為代表的公鑰密碼管理系統(tǒng)，由于公鑰體制適用于商用環(huán)境下動態(tài)的、大規(guī)模的密鑰分發(fā)需求，基于公鑰體制的密鑰管理系統(tǒng)應(yīng)用廣泛，數(shù)量眾多。公鑰系統(tǒng)的安全性歷經(jīng)了“多年考驗”，公鑰系統(tǒng)從效率上、商業(yè)上、管理上各個角度去衡量也無疑是成功的，在此我們也無意對公鑰系統(tǒng)的安全性做具體討論，但隨著量子計算科技的發(fā)展，現(xiàn)用廣泛的公鑰算法受到了量子計算攻擊的嚴重威脅是毋庸置疑的事實。而且就像上面所述一樣，這一威脅不是采取拓展密鑰長度這類工程性做法就都能解決的，必須靠發(fā)展和依靠量子安全的密碼科技才能抵御這一威脅。
下期預(yù)告
下期國盾小課堂將對目前能實現(xiàn)量子安全目標的兩類解決方案——基于數(shù)學的抗量子計算密碼算法和基于物理的量子密碼進行介紹和闡述，敬請期待！
