公鑰密碼的量子攻擊研究現(xiàn)狀與展望

崔富鑫，王 輩，劉 焱，李 葉

(合肥本源量子計算科技有限責(zé)任公司，安徽 合肥 230000)

0 引言

公鑰密碼體制是密碼學(xué)史上一類極為重要的發(fā)明，它將數(shù)學(xué)、計算機與密碼學(xué)緊密結(jié)合，并解決了對稱密碼體制的三大問題：密鑰分發(fā)、密鑰管理和提供不可否認(rèn)服務(wù)。自1976年Diffie與Hellman[1]提出公鑰密碼的思想以來，密碼學(xué)家設(shè)計了多個具有代表性的公鑰密碼算法，如Diffie-Hellman密鑰交換協(xié)議、RSA密碼體制、ElGamal加密體制、橢圓曲線密碼體制(Elliptic Curve Cryptography，ECC)，這些密碼算法的安全性建立在一些數(shù)學(xué)困難問題上。

公鑰密碼體制的安全性隨著Shor算法的提出受到了威脅。近些年，量子計算的蓬勃發(fā)展，也在推動著公鑰密碼攻擊的研究與實現(xiàn)。本文主要總結(jié)公鑰密碼在量子算法攻擊下的國內(nèi)外研究進(jìn)展，重點介紹RSA和ECC的量子算法攻擊現(xiàn)狀。結(jié)合后量子密碼遷移工作的緊迫性，進(jìn)一步展望后量子密碼的未來發(fā)展以及量子算法對后量子密碼攻擊的可能性，為從事量子計算和信息安全領(lǐng)域的產(chǎn)學(xué)研工作者提供思路。

本文主要介紹幾類公鑰密碼加密算法和相關(guān)量子攻擊算法,介紹量子算法攻擊公鑰密碼的研究現(xiàn)狀,并對后量子密碼的發(fā)展以及產(chǎn)學(xué)研融合的未來作出總結(jié)與展望。

1 背景介紹

1.1 公鑰加密算法

在現(xiàn)代密碼學(xué)中，根據(jù)密鑰的不同特征，主要分為對稱密碼體制和公鑰密碼體制。前者在加解密算法中使用相同的密鑰，而后者則是使用不同的密鑰。

公鑰密碼體制中最著名的三個算法分別是RSA密碼體制、ElGamal密碼體制以及ECC體制。下面著重介紹RSA和ECC密碼體制的加密算法。

1.1.1 RSA加密算法

RSA算法是由Rivest、Shamir、Adleman[2]三人在1977年提出的，該算法也是首次實現(xiàn)的公鑰密碼算法，算法流程如下：

(1)密鑰生成：Alice選取兩個長度相等的大素數(shù)p和q，令N=pq；

(2)Alice選取e，d∈Z，并滿足ed=1 modφ(N)，其中φ(N)=(p-1)(q-1)，稱e為加密指數(shù)，d為解密指數(shù)，數(shù)對(N，e)為公鑰，(N，d)為私鑰，將公鑰對外公開；

(3)加密過程：Bob將消息M使用公鑰加密，得到密文C=Memod N后向外發(fā)送；

(4)解密過程：Alice接收到Bob的消息后利用私鑰解密，即Cd=Med=M mod N。

算法的安全性是基于數(shù)學(xué)中整數(shù)分解問題(Integer Factoring Problem，IFP)的困難性，因而在密鑰生成階段選取的素數(shù)越大，該算法越安全。但是RSA的攻擊問題是否等價于整數(shù)分解問題目前學(xué)界還沒有定論[3-4]，文獻(xiàn)[5]總結(jié)了對RSA的不同攻擊方式。當(dāng)前整數(shù)分解最高效的算法——廣義數(shù)域篩法(General Number Field Sieve，GNFS)的時間復(fù)雜度依然是(亞)指數(shù)級的[6]，并且人們普遍相信這一問題在經(jīng)典計算領(lǐng)域沒有多項式級別的算法。

1.1.2 ECC加密算法

基于離散對數(shù)問題(Discrete Logarithms Problem，DLP)的ElGamal加密算法最早由ElGamal[7]在1985年中提出。這一算法的困難問題可以簡潔地作如下表述：已知α，β=αx，求x mod ord(α)。橢圓曲線加密算法的困難問題與ElGamal加密算法的困難問題在形式上類似，該算法首先是由Miller在1985年[8]和Koblitz在1987年[9]分別獨立提出的。算法的流程如下：

(1)Alice選擇一條橢圓曲線Ep(a，b)，并選擇曲線上一點作為基點G；

(2)Alice選擇k作為私鑰，并計算K=kG作為公鑰公開，一起公開的還有橢圓曲線Ep(a，b)和基點G；

(3)Bob在收到公開的信息后，將要傳遞的信息編碼到橢圓曲線上一點M上，同時產(chǎn)生一個隨機數(shù)r；

(4)Bob計算A1=M+rK以及A2=rG；

(5)Bob將A1和A2發(fā) 送給Alice；

(6)Alice收到消息后計算A1-kA2=M+rK-krG=M，即可得到信息M。

ECC算法的安全性是基于橢圓曲線群運算上的離散對數(shù)問題(Elliptic Curve Discrete Logarithm Problem，ECDLP)的 困 難 性：已 知K，G∈Ep(a，b)且K=[k]G，求k mod ord(G)。該算法相較RSA算法能夠使用更短的密鑰達(dá)到相當(dāng)?shù)陌踩?，代價是增加了加密和解密時的計算量，美國國家標(biāo)準(zhǔn)技術(shù)研究院(NIST)在2016年的分析中指出，256位的ECC和3 072位RSA所達(dá)到的安全級別相同。

1.2 量子算法

1.2.1 Shor算法求解整數(shù)分解

1994年，美國數(shù)學(xué)家Shor[10]提出一個能夠在量子計算機上指數(shù)級加速大數(shù)分解問題和離散對數(shù)問題算法。利用該算法可以實現(xiàn)量子多項式時間復(fù)雜度的整數(shù)分解問題，完整的算法步驟如下：

首先將整數(shù)分解問題轉(zhuǎn)化為求階問題，假設(shè)要分解的整數(shù)為N，并且有最小的整數(shù)r使得ar=1 mod N，這里不妨假設(shè)r是偶數(shù)，則有：

然后進(jìn)入算法的量子部分，量子部分的核心思想在于充分利用量子計算的特性，將周期信息編碼到基矢上然后讀出。量子部分的輸入為a，N，輸出為周期r的一個估計。該部分流程如下：

(1)取n=「log2N，其中「為向上取整函數(shù)；

(2)初始化t=2n個量子比特|0>t作為第一個量子寄存器，初始化n個量子比特得到量子態(tài)|0>n-1?|1>作為第二個量子寄存器，從而初始態(tài)為：

(3)對第一個量子寄存器制備最大疊加態(tài)：

(4)對兩個寄存器作用一系列模指數(shù)運算U2i，得到：

上述態(tài)也可以近似化簡為：

(5)對第一個量子寄存器作用量子傅里葉逆變換：

(6)測量第一個量子寄存器，得到比特串m。

上述流程為算法的量子部分，二進(jìn)制比特串需經(jīng)過后處理才能得到周期r。由上面的過程可知是某個的近似，由求r的過程稱為連分式算法，該算法可以將寫成一系列分?jǐn)?shù)的形式，并且分?jǐn)?shù)列與逐漸靠近，周期r大概率就隱藏在某個分?jǐn)?shù)的分母中。算法的可行性由定理1保證。

定理1[11]設(shè)是一個滿足的有理數(shù)，則是的連分式的一個漸進(jìn)值，從而可以利用連分式算法在O(t3)時間復(fù)雜度內(nèi)計算。

讀取到上面的r后，需要判定r是否為a的周期，若否，重新進(jìn)行算法的量子過程，直到找到周期，還需要判斷是否為偶數(shù)，若否，返回第一步重新取a。

關(guān)于Shor算法的時間復(fù)雜度有定理2成立。

定理2[10]n比特的整數(shù)分解可以在量子計算機上以O(shè)(Poly(n))次操作外加多項式復(fù)雜度的經(jīng)典處理完成。

上述定理相較于數(shù)域篩法分解同比特數(shù)的整數(shù)所需的exp(Θ(n1/3log2/3n))次操作是一個巨大的飛躍。

與Shor算法十分類似，離散對數(shù)問題也可以通過與上述過程類似的量子線路來實現(xiàn)指數(shù)級的加速。

1.2.2 離散對數(shù)問題求解

Shor在文獻(xiàn)[10]中利用量子算法以多項式復(fù)雜度解決的另一個問題就是離散對數(shù)問題。即給定a和b=as，確定s，可以將這一問題進(jìn)行轉(zhuǎn)化?？紤]二元函數(shù)為：f(x1，x2)=asx1+x2mod N，易得該函數(shù)為周期函數(shù)，并且周期是一個二元組，通過計算二元組能得到原離散對數(shù)問題的周期s。求解二元函數(shù)周期的量子算法流程如下：

(1)依然是取n=「log2N，其中「為取整函數(shù)，設(shè)r是使得armod N=1的最小正整數(shù)；

(2)初始化t=O(log(r))個量子比特|0>t作為第一個量子寄存器，重復(fù)該步驟兩次，再初始化n個量子比特|0>n得到三個初始化的量子寄存器為：

(3)對前兩個量子寄存器分別作制備最大疊加態(tài)為：

(4)對三個寄存器作用一系列白盒Uf，得到：

上述態(tài)也可以近似寫成：

(5)對前兩個量子寄存器作用量子傅里葉逆變換：

(6)測量前兩個量子寄存器，得到兩個比特串(m1，m2)，可以利用廣義連分?jǐn)?shù)算法得出s，此外，Eker?[12]通過多次測量得到{(m1j，m2j)}構(gòu)造格，之后通過經(jīng)典的格基約化算法求得s。

與整數(shù)分解的Shor算法類似，可以證明上述算法(包含經(jīng)典部分的處理)的時間復(fù)雜度同樣是多項式量級的。

需要注意的是，這里給出的是有限域上的離散對數(shù)問題及其量子算法求解，而ECC算法依托的ECDLP則是將有限域上的四則運算替換成了有限域上橢圓曲線的有理點加運算。

1.2.3 量子優(yōu)化算法

量子優(yōu)化算法是一種在理念上完全不同于上述邏輯運算的量子算法。優(yōu)化算法一般是將一個經(jīng)典問題轉(zhuǎn)化為一個組合優(yōu)化問題，下一步搭建一個能夠反映該優(yōu)化問題的物理模型，最后利用量子退火機的特性(量子漲落及隧穿效應(yīng))求解該模型的最小值，由于量子隧穿效應(yīng)的存在，使得上述求解在一般情形下能夠得到全局最優(yōu)解。需要注意的是，由于絕熱量子計算被證明是等價于通用量子計算[13]，因而一些利用絕熱演化求解的優(yōu)化問題也可以被通用量子計算機近似求解。

這種優(yōu)化思路對攻擊RSA算法的困難問題——整數(shù)分解問題提供了一種全新的思路。將整數(shù)分解問題視作一個優(yōu)化問題最早是由Burges[14]在2001年提出的，該方法在2007年被Schaller等人[15]改進(jìn)。算法的一般流程如下：

(1)選擇兩個待定數(shù)字(設(shè)兩個數(shù)字為N的因子)，寫出兩個數(shù)字的二進(jìn)制乘法表(表1為35的待定分解)，令t=「log(N)，該步驟的復(fù)雜度為O(t)；

表1 二進(jìn)制乘法表

(2)將乘法表和N進(jìn)行比對，化簡方程組，減少待定數(shù)字,該步驟的時間復(fù)雜度為O(t3)；

(3)將上述問題轉(zhuǎn)化為二次無約束布爾優(yōu)化問題(Quadratic Unconstrained Boolean Optimization，QUBO)，該步驟時間復(fù)雜度為O(t3)；

(4)針對上一步驟的二次優(yōu)化問題構(gòu)建伊辛模型，該步驟時間復(fù)雜度為O(1)；

(5)利用量子退火機求解該模型得到最優(yōu)解，量子計算時間復(fù)雜度為O(t2)。

上述步驟的復(fù)雜度由文獻(xiàn)[16]給出。不同于Shor算法需要在通用量子計算機上執(zhí)行，量子優(yōu)化算法一般在量子專用機上處理，這為優(yōu)化算法開辟了完全不同的賽道，也在一定程度上規(guī)避了大規(guī)模通用量子計算機發(fā)展緩慢的困難。

2 量子算法攻擊公鑰密碼的研究

2.1 量子算法攻擊RSA的研究

2.1.1 Shor算法攻擊RSA

Shor算法被提出后引起了人們的廣泛關(guān)注，此后的時間不斷有基于Shor算法的改進(jìn)方案被提出。改進(jìn)工作在多個不同的角度同時進(jìn)行，比如，致力于減少算法所需的邏輯比特數(shù)或者物理比特數(shù)，使用模擬計算不斷提高可分解的比特數(shù)或者將Shor算法與高性能算法相結(jié)合等。下面假設(shè)分解的數(shù)字為N，并且n=「log2N，算法運行中選取的隨機數(shù)為a。

(1)實現(xiàn)Shor算法所需邏輯比特數(shù)的改進(jìn)

1995年，Vedral等人[17]首次給出了邏輯比特一個確定的上界7n+1，并且確定了線路復(fù)雜度為O(n3)量級，還進(jìn)一步指出了將量子比特降到4n+3的可能性。

1996年，Beckman[18]等人基于離子阱量子計算機的工作將上述結(jié)果修改為5n+1，同時指出了繼續(xù)降低輔助比特數(shù)的可行性。1998年，Zalka[19]采用了并行算法計算加法以及快速傅里葉變換加速乘法等兩種改進(jìn)方法，將量子比特繼續(xù)降到3n。

2003年，Beauregard[20]提出一種切實可行的2n+3型方案。該方案在兩個方面進(jìn)行了改進(jìn)，一是利用序列傅里葉變換(semi-classical Fourier transform)替代傳統(tǒng)的量子傅里葉變換，這使得控制比特的數(shù)量下降到1，取而代之的是需要O(n2)級別的經(jīng)典信息傳輸來還原所需的傅里葉逆變換。另一處改進(jìn)是借助了Draper[21]在2000年的一種利用傅里葉變換構(gòu)造加法模塊的技術(shù)，從而構(gòu)造更加節(jié)省比特數(shù)目的模指數(shù)運算模塊。然后在2021年，Rossi等人[22]將上述2n+3方法進(jìn)行了部分優(yōu)化，并在IBM的量子虛擬機運行該方法分解了51和57，并將該方法分解成功的概率與一般Shor算法之間進(jìn)行了詳細(xì)的比較。值得注意的是，該方法相比原始Shor算法中針對無法完成分解的對(N，a)提高了一定的成功概率。

2006年，Takahashi和Kunihiro[23]首 先對上述結(jié)果進(jìn)行了改進(jìn)，總量子比特數(shù)降到2n+2，線路復(fù)雜度和線路深度分別為O(n3logn)與O(n3)，該線路的復(fù)雜度相較于文獻(xiàn)[20]縮減了近一半。2016年，H?ner等人[24]又提出了一種不同的思路實現(xiàn)2n+2比特數(shù)，該算法的線路復(fù)雜度與線路深度都和文獻(xiàn)[23]保持一致，并且與之前算法不同的是該算法實現(xiàn)模乘的模塊僅使用了Toffoli門和Clifford門。

仍然是在2006年，Zalka[25]給出了一種僅需要1.5n+2的理論模型，該文章還將Parker、Plenio在2000年給出的結(jié)論[26]進(jìn)行了優(yōu)化。文獻(xiàn)[26]指出，2n個控制比特中的一半不需要初始化到|0>(盡管仍需要2n次測量)，而Zalka則證明所有的控制比特都不需要初始化，不需要初始化的量子比特可以是任意態(tài)，也稱為“臟”(dirty)量子比特。

2017年，Gidney[27]將總比特數(shù)再次修改到2n+1，盡管這一數(shù)字大于1.5n+2，但該算法所需的初始化的比特數(shù)更少，需要n+2個初始化的量子比特和n-1個臟量子比特。

綜上所述，改進(jìn)Shor算法攻擊RSA所需邏輯比特數(shù)的具體研究進(jìn)程如表2所示。

表2 Shor算法攻擊RSA所需邏輯比特數(shù)的改進(jìn)時間表

(2)Shor算法攻擊RSA的規(guī)模估計

2009年，Van等人[28]設(shè)計了一種分布式量子計算模型，該模型的結(jié)果顯示，攻擊RSA-2048所需的量子比特數(shù)可能在65億左右，此外，該算法采用了6n邏輯比特，總的Toffoli門數(shù)量約為3 200億，攻擊耗費的總時間預(yù)計為409天。

2010年，Jones等人[29]通過構(gòu)造一種分層量子計算機模型將上述問題所需的比特數(shù)縮減到了6.2億左 右。2017年，O′Gorman和Campbell[30]通 過 詳 細(xì) 分析糾錯理論將該問題所需的量子比特數(shù)進(jìn)一步縮減到2.3億左右。

2019年，Gheorghiu和Mosca[31]將量子比特數(shù)縮減到1.7億左右，文獻(xiàn)中采用的邏輯比特為4 098(即2n+2模型)，理論上的攻擊時間為24小時。同年，Gidney等人[32]對上述結(jié)果做出較大改進(jìn)，將所需量子比特數(shù)縮減到2 000萬左右。盡管他們使用的是邏輯比特數(shù)為3n理論模型，但是成功地將線路深度下降到500n2+n2logn，理論上的攻擊時間也縮短到8小時。

2021年，Gouzien和Sangouard[33]采 用 時 間 換 量 子 體積的思路給出一種同樣是基于Shor算法(該算法的理 論 部 分 來 自Eker?和H?stad的 工 作[12])的 構(gòu) 造，使用該構(gòu)造攻擊RSA-2048所需的邏輯量子比特數(shù)為8 284，但所需的物理比特數(shù)僅僅只有13 436，相比兩千萬這是巨大的飛躍，甚至可能將攻擊RSA-2048的時刻表拉入近二十年之內(nèi)。盡管理論上的運行時間有177天，但相較千萬級物理比特數(shù)目的差距這完全是可接受的。此外，文章還指出，可以通過增加量子比特的形式來減少運行時間，比如，當(dāng)物理比特數(shù)增加到184 000時，運行時間可縮短至68天。

綜上，Shor算法攻擊RSA-2048所需量子比特數(shù)的預(yù)估發(fā)展如表3所示。

表3 攻擊RSA-2048所需總比特數(shù)的進(jìn)展

除了上述兩個主要的方向的進(jìn)展外，量子模擬計算[33-35]、Shor算法與高性能計算相結(jié)合[36]，Shor算法結(jié)合數(shù)論方法采用特殊處理[37]等方法均有相應(yīng)的進(jìn)展。

2.1.2 量子優(yōu)化算法攻擊RSA

將整數(shù)分解問題轉(zhuǎn)化為優(yōu)化問題后，后續(xù)的工作進(jìn)展主要集中在利用量子近似優(yōu)化算法(Quantum Approximate Optimization Algorithm，QAOA)、量子退火以及絕熱演化等算法求解模型的方法研究[38]。

首先是2008年，Peng等人[39]第一次物理上實現(xiàn)了量子絕熱算法分解因數(shù)，本次實驗使用3量子比特分解了21，在當(dāng)時也是首次實現(xiàn)對大于15的數(shù)字的量子算法分解。

2012年，Xu等 人[40]利 用 優(yōu) 化 理 論 及NMR技 術(shù)在只使用4量子比特的情況下分解了143，與前人的方法相較，該文章在分解前進(jìn)行了部分?jǐn)?shù)學(xué)上的預(yù)處理(解方程)，從而可以用更少的量子比特數(shù)來分解較大的數(shù)字。

隨后在2014年，Dattani等人[41]利用相同的算法和4個量子比特得到了44 929和56 153的分解，對比2012年的類似結(jié)果，之所以能夠有如此大的改進(jìn)，得益于經(jīng)典部分的數(shù)據(jù)處理，比如56 153的情況多數(shù)限制方程組都可以被約化，使得最后目標(biāo)函數(shù)或者哈密頓量所具有的自由度與分解143的情況無異。

2016年，Pal等人[42]將經(jīng)典處理和絕熱演化相結(jié)合，在僅使用三個量子比特的情況下成功分解了551。2017年，Li等人[43]再次利用該思想在僅使用3個量子比特的情形下分解了291 311。

此外，在2016年，Dridi和Alghassi[44]利用D-Wave 2000Q實現(xiàn)了小于223 357=401×557的一般分解，并且指出了如何利用Gr?bner基來減少哈密頓量的自由度以實現(xiàn)減少所需量子比特數(shù)的目的。

2018年，Jiang等人[45]提出一個理論框架，該框架可以將整數(shù)分解問題轉(zhuǎn)化成優(yōu)化問題進(jìn)而構(gòu)建為可執(zhí)行的伊辛模型。對于給定的數(shù)字N，文章給出了算法所需的量子比特數(shù)O(log2(N))，并且文中展示了如何分別使用4、12、59、94個邏輯比特完成15、143、59 989以及376 289的分 解。驗 證過 程 同樣使用的是D-Wave 2000Q。

2020年，Saxena等人[46]提出了一種經(jīng)典-量子混合方案，該方案可以看作是文獻(xiàn)[40]和[42]的一個推廣，特點是將量子絕熱基態(tài)搜尋轉(zhuǎn)變?yōu)榭稍谝话懔孔佑嬎銠C上執(zhí)行的量子線路(將演化過程按時間切割，得到一系列酉矩陣，然后用通用門來表示這些酉矩陣)，文章還通過IBM的量子計算機展示了上述方法分解35的過程。

同年，Wang等人[16]將優(yōu)化方法的理論進(jìn)行了細(xì)致的整理，給出了每個步驟的復(fù)雜度信息，并且借助D-wave給出了10 000以內(nèi)的一般分解和最大到20比特(1 028 171)的數(shù)字分解。

2020年，IBM的Karamlou等 人[47]成 功 分 解1 099 551 473 989，使用的依然是變分方法，這也是當(dāng)前文獻(xiàn)可考的使用量子算法分解的最大數(shù)字。不過這一數(shù)字遠(yuǎn)沒有通用機上分解的最大數(shù)字21更有意義，原因在于：理論上，只要選取足夠大的相近素數(shù)相乘得到N，比如一對靠近2m的孿生素數(shù)，通過經(jīng)典處理大概率能夠以4個以內(nèi)量子比特實現(xiàn)N的分解。事實上，IBM的這篇文章也正是這么做的，注意到如下事實：1 099 551 473 989=1 048 589×1 048 601以及220=1 048 576。

2.2 量子算法攻擊DLP與ECDLP的進(jìn)展

2016年，Eker?和H?stad[12]討 論 了 如 何 利 用 格 基約化算法在Shor算法求解DLP后處理中的作用。此外，有關(guān)量子算法攻擊DLP的文獻(xiàn)非常少，物理實現(xiàn)更是幾乎沒有，直到2021年，Aono等人[48]才第一次利用IBM的量子計算機解決一個2比特的離散對數(shù)問題。盡管求解DLP的量子算法早在1994年Shor已給出，并且Shor在文章中指出素數(shù)域上的DLP可以推廣到其他域，但相關(guān)的研究直到近十年后才開始進(jìn)行。

量子算法攻擊ECC的方案最早可以追溯到2003年P(guān)roos和Zalka的工作[49]，文獻(xiàn)中主要考慮的有限域為素數(shù)域GF(p)，而沒有考慮諸如GF(2n)類有限域。在此基礎(chǔ)上，文獻(xiàn)給出了算法所需的邏輯量子比特數(shù)約為6n，其中n為密鑰長度，盡管這一數(shù)字大于Shor算法的各種改進(jìn)版本所需的邏輯比特數(shù)，但考慮到ECC加密算法的密鑰長度天然比RSA的密鑰長度短得多，攻擊相同安全級別的ECC較RSA所需的邏輯比特數(shù)仍然是降低的。

2017年，Roetteler等人[50]給出了攻擊素數(shù)域上ECDLP的精確估計。文中所需的邏輯比特數(shù)為9n+2[log2n]+10，線路所需的Toffoli門至多為448n3log2n+4090n3。并且他們同樣將上述估計與攻擊RSA的估計進(jìn)行比較，指出對于通用量子計算機，攻擊安全性能相當(dāng)?shù)耐劝踩墑eECC問題要比RSA問題更加簡單。

2020年，H?ner等人[51]通過平衡總量子比特數(shù)和線路深度以及T門數(shù)量，改進(jìn)了Shor算法求解ECDLP量子線路中的點加線路模塊，使之相較文獻(xiàn)[50]達(dá)到更短的線路深度和更少的T門數(shù)量。

然 后 在2021年，Wroński[52]通 過 分 析ECDLP經(jīng)典攻擊中的指標(biāo)積(Index Calculus)算法，其算法求解的關(guān)鍵是代數(shù)方程組的求解，他將其代數(shù)方程組的求解問題轉(zhuǎn)化為QUBO問題，從而可以發(fā)揮量子退火機的優(yōu)勢，不過這一步驟的復(fù)雜度仍然難以估計。此外，作者借助D-Wave Leap cloud攻擊了GF(p)(p=251)上的ECDLP。需要注意的是，經(jīng)典場景下的指標(biāo)積算法是一個亞指數(shù)級時間復(fù)雜度算法。該方案只是將量子退火理論與ECDLP相結(jié)合，目前還不能證明其優(yōu)越性。

2021年，Banegas[53]等人針對定義在GF(2n)域上ECDLP做了Shor算法攻擊實現(xiàn)的資源評估，需要7n+[log2n]+9個量子比特以及Toffoli門至多為，CNOT門的個數(shù)依然是O(n3)量級的。2022年，Liu等人[54]進(jìn)一步優(yōu)化Shor算法求解GF(2n)域上ECDLP的量子線路。利用節(jié)省空間的量子Karatsuba乘法器，可以實現(xiàn)較低CNOT門個數(shù)的模數(shù)求逆和模數(shù)除法線路，進(jìn)而達(dá)到整體線路中CNOT門個數(shù)降為O(n2)量級的效果。

綜上所述，量子算法攻擊ECDLP的進(jìn)展如表4所示。

表4 量子算法攻擊ECDLP的進(jìn)展

3 結(jié)論

本文較詳細(xì)地分析了量子算法攻擊公鑰密碼的研究現(xiàn)狀，重點介紹了Shor以及量子優(yōu)化算法攻擊RSA的發(fā)展進(jìn)程和Shor算法攻擊ECDLP的發(fā)展進(jìn)程，旨在幫助研究者們快速地了解國內(nèi)外的研究方法與最新進(jìn)展，為后續(xù)的工作起到借鑒作用。

由于通用量子計算機發(fā)展緩慢，在密碼攻擊領(lǐng)域，實現(xiàn)1 024比特的RSA攻擊和163比特的ECC攻擊還相當(dāng)遙遠(yuǎn)。目前，已公布的文獻(xiàn)中能夠通過Shor算法使用真實的量子計算機分解的最大數(shù)字仍然是21，而且每前進(jìn)1比特都相當(dāng)困難，盡管有很多文獻(xiàn)不斷向下調(diào)整目標(biāo)所需的邏輯比特或者物理比特，但Shor算法距離攻擊公鑰密碼的距離仍舊十分遙遠(yuǎn)。此外，盡管通用機上的分解算法進(jìn)展緩慢，但使用優(yōu)化算法量子專用機卻表現(xiàn)得出人意料，尤其是處理整數(shù)分解問題，通過經(jīng)典部分的預(yù)處理，退火機能夠分解的數(shù)字比通用機大幾十個量級。

除了量子硬件發(fā)展的限制，當(dāng)前量子算法攻擊公鑰密碼還存在一些技術(shù)上的約束和困難，有待后續(xù)解決，具體問題見表5。

表5 量子算法攻擊公鑰密碼的困難

由于量子計算對公鑰密碼的威脅，各國密碼管理部門對后量子密碼(Post-Quantum Cryptography，PQC)研究也開始重視和推進(jìn)，旨在能威脅現(xiàn)行公鑰密碼的通用量子計算機問世之前，完成公鑰密碼系統(tǒng)到后量子密碼系統(tǒng)的整體遷移。2022年7月5日晚，NIST公布其后量子密碼標(biāo)準(zhǔn)化項目第三輪篩選的結(jié)果。提前被選中并將進(jìn)行標(biāo)準(zhǔn)化的算法包括：CRYSTALS-Kyber、CRYSTALS-Dilithium、Falcon、SPHINCS+。其中CRYSTALS、Falcon是基于格的后量子密碼算法，SPHINCS+是基于哈希的后量子密碼算法。NIST正持續(xù)推進(jìn)PQC的標(biāo)準(zhǔn)化過程，歐盟和亞洲國家也高度關(guān)注。世界各國的數(shù)字空間也將面臨下一代公鑰密碼系統(tǒng)的遷移。這一趨勢必將引發(fā)新一輪的IT產(chǎn)業(yè)變革，促進(jìn)全球數(shù)字經(jīng)濟發(fā)展。

目前，國內(nèi)不少科研學(xué)術(shù)機構(gòu)和商業(yè)機構(gòu)一方面在持續(xù)研究量子算法對公鑰密碼的攻擊工作，另一方面也在高度關(guān)注后量子密碼的遷移工作。在公鑰密碼攻擊方面，上海大學(xué)的王潮團隊、中國科學(xué)技術(shù)大學(xué)的彭新華團隊一直致力于研究量子算法對RSA的攻擊工作；合肥本源量子計算科技有限責(zé)任公司致力于在真實的量子計算機上研究對RSA和ECC的量子攻擊算法實現(xiàn)。另一方面，很多科研團隊在后量子密碼的研究工作上也進(jìn)展頗豐，如國內(nèi)清華大學(xué)丁津泰教授參與設(shè)計的CRYSTALS-Kyber算法，順利入選NIST關(guān)于后量子密碼第四輪標(biāo)準(zhǔn)。

未來，密碼學(xué)與量子計算的結(jié)合將會越來越緊密，后續(xù)需研究與發(fā)展的方向可以關(guān)注下面幾個方面：

(1)不斷優(yōu)化Shor算法對公鑰密碼的攻擊實現(xiàn)。Shor算法在理論上已威脅到公鑰密碼體制的安全性，且實驗已經(jīng)驗證其正確性。在量子硬件條件受限的情況下，不斷優(yōu)化與改進(jìn)Shor算法攻擊RSA或ECC所需的量子比特數(shù)、量子門個數(shù)及其他性能指標(biāo)是未來必然的一項研究工作。

(2)發(fā)掘?qū)Ｓ眯土孔佑嬎阌糜诿艽a部件設(shè)計及公鑰密碼攻擊的潛能。量子設(shè)計密碼是一個新的領(lǐng)域，如何從傳統(tǒng)密碼的經(jīng)典線路過渡到量子線路實現(xiàn)，以及實現(xiàn)怎樣的密碼算法安全指標(biāo)。結(jié)合量子密碼設(shè)計，在量子環(huán)境下，分析公鑰密碼的攻擊實現(xiàn)以及可達(dá)到的安全級別。

(3)PQC遷移是必然趨勢，且宜早不宜遲。IBM可能在2030年之前實現(xiàn)1 000量子比特的大規(guī)模實用量子計算機；加拿大將在2030年規(guī)劃實現(xiàn)PQC的遷移；美國政府系統(tǒng)的后量子遷移工作將在10年后初步完成，并倡導(dǎo)工業(yè)界盡快完成后量子密碼遷移。當(dāng)前，部署后量子密碼的遷移工作是未來十年工作的重點，工程量浩大，需要全世界各行各業(yè)一起努力，一起面對與解決遷移過程中遇到的各種問題。

(4)拓展量子算法對后量子密碼的攻擊工作。未來后量子密碼面臨的挑戰(zhàn)主要是針對不同的困難問題分析它們的量子計算安全性。基于編碼的后量子密碼算法可以經(jīng)得起多年考驗，根本原因是其底層困難問題的歸約仍然處于未知狀態(tài)，因而缺乏針對性的高效算法。對于基于格的后量子密碼，其底層安全性是基于確切的數(shù)學(xué)困難問題，未來是否也有類似Shor算法的量子算法可以高效攻擊格密碼進(jìn)而帶來底層隱患尚不確定。

綜上所述，量子算法對公鑰密碼的威脅程度主要取決于量子計算硬件的發(fā)展，但對公鑰密碼的量子攻擊研究依然需要不斷優(yōu)化與改進(jìn)以提高其性能效率。未來十年，后量子密碼的遷移是大勢所趨，需要各行各業(yè)協(xié)同推進(jìn)。