量子計算是目前全世界范圍內的前沿研究熱點，并可能正以量子體積每年翻倍的“量子摩爾定律”向前發展。然而，由于量子計算機的強大運算能力，一旦“量子霸權”成為現實，現有密碼體制可能發生顛覆性的崩塌。本文就量子計算對現有密碼算法的影響進行了分析，并總結了抗量子計算攻擊的公鑰密碼算法的發展現狀。

一、量子計算簡介

1、量子計算原理概述

量子計算（Quantum Computing）以量子比特為基本單元，通過量子態的受控演化實現數據的存儲計算，具有經典計算無法比擬的信息攜帶能力和并行處理能力。量子計算機的原理架構示意圖如圖1所示。

圖1：量子計算機示意圖

1）量子信息攜帶能力

由于量子疊加態的存在，與經典比特相比，量子比特可攜帶更多的信息。

·量子疊加：在無外界觀測干擾時，一個量子系統可以處在不同量子態的疊加態上，即著名的“薛定諤的貓”。

·量子比特（Qubit）：一個量子比特可以表示0、1或0和1的疊加，因此其搭載的信息量遠超只能表示0或1的經典比特。

一個n經典比特存儲器只能存儲2^n種可能的n比特數中的一個，而一個n量子比特存儲器可以同時存儲2^n個數，且其存儲信息的能力隨n的增加而指數上升。

2）量子并行處理能力

由于量子疊加效應，量子計算過程中的幺正變換可以對處于疊加態的所有分量同時進行操作。因此，量子計算機可以同時進行多路并行運算，這也是量子計算機超強信息處理能力的源泉。

·在經典計算中，所謂并行性只是對一個確定的狀態進行分時處理。

·在量子計算中，由于量子比特的疊加態特性，可對所有可能狀態進行同時處理。

2、量子計算發展進程

量子計算自概念誕生起發展至今經歷了理論探索、算法研究、技術驗證等階段，具體如圖2所示。

圖2：量子計算發展歷程

2019年，谷歌宣布實現所謂的“量子霸權（Quantum Supremacy）”，即量子計算機擁有一項超越經典計算機的計算能力，其使用更穩定的53量子比特可編程超導處理器僅用200秒就完成了隨機量子線路采樣任務，而超級計算機通常需要上萬年的時間才能完成。但是，由于計算功能局限性等因素，谷歌是否真正實現了“量子霸權”受到了包括IBM在內的業界質疑。

需要注意的是，以上所述量子比特數量指的都是物理比特。由于噪聲的存在以及物理比特的不穩定性，需要約800個物理比特的冗余糾錯才能實現1位邏輯比特，而目前沒有任何一家機構能實現1位邏輯比特的編碼。

二、量子計算對密碼體制的影響1、對對稱密碼算法的影響

1）Grover算法

量子計算中的Grover隨機數據庫搜索算法能夠以“指數減半”的效果提升空間搜索效率。對稱密碼的安全性如果以窮舉搜索密鑰的攻擊復雜度進行衡量，將導致對稱密碼的安全性減半，即在經典計算環境下2^128安全的對稱密碼算法，在量子計算環境下只有2^64安全。

影響：量子計算可使DES、AES、SM4等分組密碼算法和流密碼算法的安全性降低為原來的1/2。但由于Grover算法需要指數級內存，其對于對稱密碼算法的實際影響不大。

2）應對策略

增加密鑰長度：為了達到2^128的量子計算安全，需將對稱密碼的有效密碼尺寸設計為至少256比特。需要注意的是，密鑰長度增加對加解密運算速度有影響，但影響可控，從密鑰長度128bit的約450MB/s降低至密鑰長度256bit的約320MB/s。

·AES算法：支持256比特密鑰長度，可暫時滿足量子計算安全。

·SM4國密算法：密鑰長度固定為128比特，可能受到影響。

2、對哈希摘要算法的影響

1）量子隨機行走算法

量子隨機行走算法可提高經典搜索算法的時間效率，進而增加一定時間內隨機找到兩個碰撞原像的概率，實現對抗碰撞性的暴力破解，降低哈希摘要算法的安全性。

影響：量子計算可使MD5、SHA、SM3等哈希摘要算法的安全性降低為原來的2/3。

2）應對策略

增加摘要長度：量子計算對哈希摘要算法的影響不大，只需采用摘要長度較大的算法即可。

·SHA算法：最高支持SHA-512，可暫時滿足量子計算安全。目前認為SHA-256在經典計算環境下是安全的，所以量子計算環境下至少應使用SHA-384。

·SM3國密算法：摘要長度固定為256比特，可能受到影響。

3、對公鑰密碼算法的影響

1）Shor算法

Shor量子算法可以在多項式時間內破解大整數分解問題和離散對數問題。破解2048比特強度的RSA密鑰可能需要經典計算機耗費10億年以上的時間，而谷歌稱2000萬量子比特的量子計算機只需8小時就可破解2048比特RSA算法。

影響：量子計算可破解RSA等基于大整數分解的公鑰密碼算法和ECDSA、SM2等基于離散對數的ECC橢圓曲線公鑰密碼算法。

2）應對策略

更換新的算法：大整數分解和離散對數困難問題在量子并行計算環境下可被輕易破解，因此可考慮選取無法高效并行計算的數學困難問題構造抗量子公鑰密碼算法。

4、對密碼算法安全級別的影響總覽

各類密碼算法在經典計算環境和量子計算環境的安全級別對比如表1所示。

表1：密碼算法安全級別對比

三、抗量子密碼算法進展

1、國內外抗量子密碼計劃

1）美國

2015年8月，美國國家安全局（NSA）宣布將美國政府使用的密碼套件進行安全性升級，用于2015年至抗量子密碼算法標準正式發布前的過渡期，如表2所示。

表2：美國過渡期標準

2016年4月，美國國家標準與技術研究院（NIST）公布了抗量子密碼標準化計劃：

·2016年秋-2017年11月，面向全球征集抗量子密碼算法；

·2017年-2022年，進行3-5年的密碼分析工作；

·2022年-2023年，完成抗量子密碼標準的起草與發布。

截至目前，NIST抗量子密碼算法征集的實際進展如圖3所示。

圖3：NIST抗量子密碼算法征集實際進展

NIST共收到82個算法，首輪公布前即淘汰了13個算法。在剩下的69個候選算法中，2019年初第二輪僅剩26個有效候選算法，其中17個為公鑰加密與密鑰協商算法，9個為數字簽名算法。

·公鑰加密與密鑰協商算法：BIKE、ClassicMcEliece、CRYSTALS-KYBER、FrodoKEM、HQC、LAC、LEDAcrypt、NewHope、NTRU、NTRUPrime、NTS-KEM、ROLLO、Round5、RQC、SABER、SIKE、ThreeBears

·數字簽名算法：CRYSTALS-DILITHIUM、FALCON、GeMSS、LUOV、MQDSS、Picnic、qTESLA、Rainbow、SPHINCS+

與RSA等傳統非對稱密碼算法同時支持加密與簽名等功能不同，抗量子密碼體制對公鑰加密/密鑰協商算法和數字簽名算法進行分別構造。

2）歐洲

2015年3月，歐洲電信標準協會ETSI成立“量子密碼安全工業標準工作組”，主要負責抗量子密碼算法的征集、評估和標準制定。同年，歐盟相繼啟動抗量子密碼算法項目PQCRYPTO和SAFECRYPTO。

歐洲在抗量子密碼算法方面的策略是全力配合美國NIST的算法征集，并基于NIST的算法推動抗量子密碼遷移工作。

3）亞洲

中國、日本、韓國等國家于2016年開始組織“亞洲抗量子密碼論壇”，分別在中日韓三國舉辦。

在國內，中國密碼學會于2019年開展了全國密碼算法設計競賽，在征集到的算法中不乏抗量子密碼算法。據報道，中國或將于2022年左右開展抗量子密碼算法標準化工作，于2025年左右實現應用落地。

2、抗量子公鑰密碼算法

由于現有非公鑰密碼算法存在可抵抗量子計算攻擊的版本，因此抗量子密碼主要討論的是公鑰密碼體制在量子計算下的替代方案。

1）抗量子密碼定義

抗量子密碼體制也稱為后量子密碼體制（Post-Quantum Cryptography），是指既能抵抗現有經典計算攻擊又能抵抗未來量子計算攻擊的密碼體制，至少應滿足以下要求：

·能夠抵抗已知經典攻擊方法；

·能夠抵抗已知量子計算攻擊方法（如Shor算法）；

·尚不存在已知的量子攻擊方法在多項式內成功攻擊的密碼算法。

一些困難問題無法利用量子離散傅里葉變換解決，如格上的最短向量問題（SVP）/最近向量問題（CVP）、非線性方程組求解問題、背包問題等，可考慮基于此類問題構造抗量子密碼算法。

2）抗量子密碼分類

抗量子密碼算法包含基于格的密碼、多變量密碼、基于Hash的密碼、基于編碼的密碼等類型，具體如表3所示。

表3：抗量子密碼分類

在NIST抗量子密碼算法征集的第二輪26個算法中，有12個基于格的密碼、7個基于編碼的密碼、4個多變量密碼、2個基于Hash的密碼、1個超奇異同源密碼。其中，基于格的LAC算法由國內的中科院信工所研究團隊提交。

3）基于格的密碼

基于格的密碼（Lattice-Based Cryptography）是目前抗量子公鑰密碼算法中最具代表性的一類。格是一種與群、環、域并列的代數結構，LWE（帶錯誤的學習）是格上的困難問題。2005年，Regev提出LWE問題并通過量子算法將LWE歸約到格上的最短向量困難問題（SVP），并給出了基于LWE的公鑰密碼方案。與之前出現的格上困難問題比較，LWE在構建密碼系統時更方便。

Ring-LWE（環上帶錯誤的學習）是LWE的變體。在基于Ring-LWE的密碼中，密鑰由若干個多項式表示，而不是LWE中的矩陣，因而減小了密鑰大小，同時提高了加解密速度。

4）各類抗量子密碼特點

基于格的密碼、多變量密碼、基于Hash的密碼、基于編碼的密碼等各類抗量子密碼算法的特點如表4所示。

表4：各類抗量子密碼特點

四、總結

目前，傳統計算領域已有可分解768位RSA整數的算法，而量子計算機僅成功分解了整數56153（約16比特）。然而，RSA算法目前建議的安全長度為2048比特，需要2000萬量子比特的量子計算機才能通過Shor量子算法實現破解，而目前量子計算機還未突破100位，因此量子計算機對現有密碼體制不具有短期威脅。

雖然“量子霸權”還未真正意義上實現，但為了未來能夠快速向后量子密碼體制遷移，業界在布局長期應用時需要考慮后量子密碼算法的兼容性。

責任編輯：韓希宇