王寶楠，陳宇航，尹寶，胡風(fēng)，張煥國，王潮

(1. 上海大學(xué)通信與信息工程學(xué)院特種光纖與光接入網(wǎng)省部共建教育部重點(diǎn)實(shí)驗(yàn)室，上海 200072；2. 武漢大學(xué)空天信息安全與可信計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430072)

第一寄存器小Qubit量子計(jì)算攻擊RSA研究

王寶楠1，陳宇航1，尹寶1，胡風(fēng)1，張煥國2，王潮1

(1. 上海大學(xué)通信與信息工程學(xué)院特種光纖與光接入網(wǎng)省部共建教育部重點(diǎn)實(shí)驗(yàn)室，上海 200072；2. 武漢大學(xué)空天信息安全與可信計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430072)

提出了針對(duì)RSA的小Qubit量子攻擊算法設(shè)計(jì)，量子攻擊的第一量子寄存器所需的Qubit數(shù)目由原先至少2L降低到L1，總體空間復(fù)雜度記為(L1, L)，其中2L1≥r，r為分解所得周期。由于第一寄存器量子比特?cái)?shù)的減少，降低了算法復(fù)雜度和成功率，且改進(jìn)原算法中模冪計(jì)算，提升運(yùn)算速率。改進(jìn)攻擊算法的量子電路的時(shí)間復(fù)雜度為T=O(2L2)。在時(shí)間復(fù)雜度和空間復(fù)雜度上都有明顯的進(jìn)步。改進(jìn)算法的成功率降低了，但實(shí)際成功求解時(shí)間，即每次分解時(shí)間/成功率，依然低于Shor算法目前的主要改進(jìn)算法。完成了仿真模擬實(shí)驗(yàn)，分別用11、10、9 Qubit成功分解119的量子電路。

Shor算法；RSA算法；量子電路；小比特；攻擊

1 引言

《Nature》[1]在調(diào)查歐洲、美國多個(gè)量子中心后，判斷破譯現(xiàn)有的1 024 bit RSA密碼所需要的千位Qubit以上的通用量子計(jì)算機(jī)，在未來5～10年內(nèi)仍難實(shí)現(xiàn)。

根據(jù)《Nature》[1]，Hanson和 Vandersypen等領(lǐng)導(dǎo)的荷蘭量子研究中心（QuTech Centre）的目標(biāo)是近期研究17 Qubit。

瑞士蘇黎世聯(lián)邦技術(shù)研究所的Matthias Troyer[1]認(rèn)為目前的通用量子計(jì)算機(jī)缺乏殺手級(jí)應(yīng)用，已知的2個(gè)應(yīng)用（密碼破譯和數(shù)據(jù)庫搜索）都不成功。Matthias Troyer還認(rèn)為，百位Qubit不容易實(shí)現(xiàn)或者無法很經(jīng)濟(jì)地實(shí)現(xiàn)。Matthias Troyer對(duì)目前量子計(jì)算機(jī)的情況非常熟悉，還參加了南加州大學(xué)的加拿大量子計(jì)算機(jī)測試。

事實(shí)上，根據(jù)《Nature》，目前已經(jīng)實(shí)現(xiàn)的通用量子計(jì)算機(jī)最大規(guī)模為9 Qubit，由加州大學(xué)圣巴巴拉分校（UCSB）的John Martinis團(tuán)隊(duì)實(shí)現(xiàn)，然而John Martinis認(rèn)為通用量子計(jì)算機(jī)還在二戰(zhàn)時(shí)期第一臺(tái)電子計(jì)算機(jī)的程度。

盡管John Martinis團(tuán)隊(duì)已經(jīng)在原理上驗(yàn)證了Shor計(jì)算攻擊RSA的可行性，并在2011年成功用量子電路實(shí)現(xiàn)了量子傅里葉變換[2]，這是破譯RSA的量子計(jì)算Shor算法的核心基礎(chǔ)，2012年，John Martinis團(tuán)隊(duì)還成功完成攻擊小規(guī)模RSA實(shí)驗(yàn)[3]，分解了15=3×5。但是，John Martinis團(tuán)隊(duì)不再繼續(xù)從事通用量子計(jì)算機(jī)的研究，2014年9月，John Martinis整個(gè)團(tuán)隊(duì)全部搬入谷歌總部“建造能解決實(shí)際問題的量子計(jì)算機(jī)”——基于量子退火的專用量子計(jì)算機(jī)，其原理并不適合運(yùn)用于公鑰密碼破譯的Shor算法。

因此需要考慮在通用量子計(jì)算機(jī)器件條件限制的情況下，研究公鑰密碼RSA的小Qubit量子計(jì)算攻擊方法，降低對(duì)通用量子計(jì)算機(jī)的器件要求[4]。

本文改進(jìn)了原始Shor算法，提出新的量子電路設(shè)計(jì)，降低了量子器件要求，探究性地提出了小規(guī)模Qubit實(shí)現(xiàn)Shor算法對(duì)公鑰密碼的攻擊，并進(jìn)行了仿真模擬。

本文介紹了Shor算法攻擊RSA的國內(nèi)外研究現(xiàn)狀，引出改進(jìn)Shor量子算法對(duì)公鑰密碼的攻擊；給出Shor算法分解實(shí)驗(yàn)。另外，本文分別給出Shor算法攻擊RSA的量子電路攻擊實(shí)驗(yàn)和改進(jìn)Shor量子攻擊算法實(shí)驗(yàn)及運(yùn)行結(jié)果；并進(jìn)行了實(shí)驗(yàn)分析；比較了目前主要的Shor改進(jìn)算法，并對(duì)改進(jìn)的Shor算法進(jìn)行分析。

2 Shor算法攻擊RSA國內(nèi)外研究現(xiàn)狀

Shor算法對(duì)RSA的攻擊體現(xiàn)在Shor算法對(duì)RSA安全基礎(chǔ)的大數(shù)N的分解，關(guān)于Shor算法對(duì)N分解的研究一直是國內(nèi)外專家學(xué)者的研究熱點(diǎn)。

1996年，美國科學(xué)家Juan Pablo Paz在一個(gè)有干擾和損耗的量子電路上展示分解了15，理論上需要27 Qubit才能成功分解。同時(shí)他更是指出對(duì)于大數(shù)N，所需要的量子比特?cái)?shù)是n=5L+7（其中L為不小于log2N的最小正整數(shù)）。這項(xiàng)工作的研究成果給實(shí)際操作中實(shí)現(xiàn) Shor量子算法提供了很好的借鑒。

2001年，斯坦福大學(xué)和美國IBM公司合作，利用核磁共振技術(shù)演示了Shor算法對(duì)整數(shù)15進(jìn)行分解的實(shí)驗(yàn)過程，但該實(shí)驗(yàn)不能顯示其量子屬性，也無法擴(kuò)展到更多的比特情況，限制了進(jìn)一步的研究。

2004年，美國赫爾辛基理工大學(xué)的Vartiainen[5]利用約瑟夫森電荷構(gòu)成的量子比特實(shí)現(xiàn)了 Shor算法。他把Shor算法的量子電路分成了一系列2 Qubit和3 Qubit的量子門，不僅加速了Shor算法的實(shí)現(xiàn)，而且在此基礎(chǔ)上通過數(shù)值優(yōu)化的方法成功完成對(duì) N=21分解的物理實(shí)現(xiàn)。但該實(shí)驗(yàn)要求很高的物理性，即必須在特定的物理?xiàng)l件下才能實(shí)現(xiàn)。

2007年，法國理論物理研究實(shí)驗(yàn)室在研究Shor算法的缺陷[8]（由量子比特間殘余耦合所造成）所產(chǎn)生的影響時(shí)，通過編寫Quantware庫并且調(diào)用該庫，用30個(gè)量子比特模擬實(shí)現(xiàn)了N=943的分解。該方法雖然很好理解，但是Quantware庫所用的限制性很多。2007年，中國科學(xué)院公布，中國科學(xué)技術(shù)大學(xué)潘建偉教授和楊濤教授等[9]與英國牛津大學(xué)的研究人員合作，在國際上首次利用光量子計(jì)算機(jī)實(shí)現(xiàn)了Shor量子分解算法，研究發(fā)表在2007年1月的物理評(píng)論快報(bào)上，并在該量子計(jì)算上成功操控 4個(gè)光子量子比特構(gòu)造一個(gè)簡單的線性光網(wǎng)絡(luò)，實(shí)現(xiàn) N=15的分解。

2010年，英國布里斯托大學(xué)電氣和電子工程物理實(shí)驗(yàn)室和量子光學(xué)中心的Thompson等[10]介紹了基本的Shor因式分解量子算法實(shí)現(xiàn)過程，主要是在由6個(gè)H門和2個(gè)可控的相位門組成的波導(dǎo)電路中建立一個(gè)可以實(shí)現(xiàn)Shor量子分解算法的電路，并且成功地用Shor算法分解N=15。

2010年，解放軍信息工程大學(xué)通過改進(jìn)量子傅里葉變換加速實(shí)現(xiàn)Shor算法對(duì)N的分解[11]，但該算法中改進(jìn)的量子傅里葉變換是以串行代替并行加快速度的。該算法的空間復(fù)雜度記為（4，L），時(shí)間復(fù)雜度T=O(L3)。

2012年，美國加州大學(xué)圣巴巴拉分校的John Martinis[3]，在實(shí)現(xiàn)量子傅里葉變換電路基礎(chǔ)上，完成了15=3×5的素?cái)?shù)分解實(shí)驗(yàn)，原理上驗(yàn)證了Shor計(jì)算攻擊RSA的可行性。

上述研究和最近的一些研究[12,13]都是 Shor算法分解N研究的代表，但基本上都需要在量子計(jì)算機(jī)器件[6,7]很高的要求下，包括需要千位量子比特的量子計(jì)算機(jī)和高精度的糾纏能力等。

3 改進(jìn)Shor算法

3.1 改進(jìn)Shor算法介紹

對(duì)大數(shù) N（N＞0）的素因子分解，也就是對(duì)大數(shù)N和整數(shù)x（x＜N）求出滿足同余式xr=1modN的階r。

改進(jìn)Shor算法步驟如下。

Step1準(zhǔn)備具有L1量子比特的第一寄存器和L量子比特的第二寄存器的態(tài)矢量其中，為周期。

Step2對(duì)第一寄存器實(shí)行 L1次 Hadamard變換得到到的個(gè)態(tài)的疊加，可給出

Step3將Ux,a算符應(yīng)用到寄存器，

Step4利用二進(jìn)制查表法計(jì)算xamod N的值。如下[14]。

③ 當(dāng)i≥0時(shí)，執(zhí)行④～⑩。

④ 如果ai=1，則執(zhí)行⑤～⑨。

⑤ 如果i≥k，則執(zhí)行⑥～⑧。

⑥ 把該位開始的 k個(gè)二進(jìn)制數(shù)作為一個(gè)整體進(jìn)行計(jì)算，進(jìn)行連續(xù)k次平方。

⑧ 令i=i-k，減少一個(gè)分組的長度。

⑨ 如果i＜k，則把該位開始的k個(gè)二進(jìn)制數(shù)作為一個(gè)整體，即令m=m×m×x mod N，且i=i-1。

⑩ 如果ai=0，則直接計(jì)算該位開始的k個(gè)二進(jìn)制的平方取模，且i=i-1，最后返回m值。

Step5進(jìn)行xamod N的階數(shù)搜索過程。

Step6對(duì)第一個(gè)量子寄存器進(jìn)行 QFT逆變換，并觀測概率。

Step7由周期性求得階數(shù)r。

Step8由階數(shù)r求得2個(gè)N的分解數(shù)。

3.1.1 原始Shor算法分解N=119量子電路

圖1是理論上Shor算法的完整實(shí)現(xiàn)，第一量子寄存器需要的量子比特?cái)?shù)第二量子寄存器需要的量子比特?cái)?shù)

圖1 原始Shor算法分解N=119的量子電路

3.1.2 改進(jìn)Shor量子算法分解N=119量子電路

基于改進(jìn)Shor量子算法實(shí)現(xiàn)對(duì)RSA的攻擊量子電路原理如圖2所示。

圖2 改進(jìn)的Shor小比特攻擊算法分解N=119的量子電路

對(duì)比圖1和圖2，改進(jìn)的地方在于把第一量子寄存器的量子比特?cái)?shù)1～14進(jìn)行了減少，由原來的14 Qubit修改成了1～2的2個(gè)量子比特，與理論上相比少用了12個(gè)量子比特，這大大減少了對(duì)量子計(jì)算機(jī)的器件要求。

3.2 改進(jìn)Shor量子算法分析

改進(jìn)Shor算法相比原始Shor算法分析如下。

參考Shor算法及相關(guān)文獻(xiàn)[15]對(duì)Shor算法分解大數(shù)的理論分析，本文設(shè)計(jì)的量子電路主要包括3個(gè)部分：一是用一系列的H變換替換傅里葉變換；二是控制模冪變換，并引入二進(jìn)制查表法計(jì)算模冪算法；三是量子傅里葉變換。

該改進(jìn) Shor量子算法主要是量子比特?cái)?shù)的減少，一般情況下空間復(fù)雜度和時(shí)間復(fù)雜度與成功率呈相反的關(guān)系，即成功率的提升是以復(fù)雜度的提升為代價(jià)的。由于第一量子寄存器比特?cái)?shù)的減少，所需通過H變換的次數(shù)也相應(yīng)地減少，引起了模冪中模乘次數(shù)的減少，促進(jìn)了整個(gè)算法運(yùn)行時(shí)間的減少，且并不影響后續(xù)的操作。第一量子寄存器執(zhí)行的是模冪操作的控制，是用于控制模冪運(yùn)算的模乘次數(shù)和量子傅里葉變換，縮小了量子比特?cái)?shù)，使所能進(jìn)行的模冪運(yùn)算次數(shù)也變少，并引發(fā)了后面操作次數(shù)的減少，在一定程度上降低了該Shor算法攻擊的成功率，但提高了成功求解速度。而引入二進(jìn)制查表法的目的是進(jìn)一步減少模乘的次數(shù)，該算法雖然增加了一點(diǎn)空間，但并不影響整體算法的空間復(fù)雜度，且引入該算法的主要目的是該算法能大幅度減少模冪中乘法的次數(shù)，使模冪的計(jì)算速度進(jìn)一步提高。

Shor原始算法量子電路空間復(fù)雜度需要至少S=(2L, L)，L=log2N Qubit（第一量子寄存器需要2L Qubit，第二量子寄存器需要L Qubit，S表示空間復(fù)雜度）。改進(jìn)Shor算法量子電路空間復(fù)雜度需要S=(L1, L)（第一量子寄存器需要L1 Qubit，第二量子寄存器需要L Qubit）。其中，L Qubit即進(jìn)行模冪運(yùn)算至少要有的量子比特?cái)?shù)（保存模冪運(yùn)算預(yù)運(yùn)算的值）。L1 Qubit即量子傅里葉變換需要的量子比特?cái)?shù)。例如，基于改進(jìn)Shor算法分解N的步驟分析，設(shè)計(jì)的量子電路的量子比特?cái)?shù)對(duì)于分解119的量子電路而言，從原來至少需要（14，7）量子比特降為僅用（2，7）量子比特。Shor原始算法量子電路計(jì)算復(fù)雜度，即時(shí)間復(fù)雜度為T=O(L3)，改進(jìn) Shor算法量子電路復(fù)雜度為T=O(L2)。

與 Shor算法相比，降低了至少 L規(guī)模的比特?cái)?shù)，即空間復(fù)雜度降低了O(L)規(guī)模。與目前主要的Shor改進(jìn)算法相比，改進(jìn)Shor算法的比特?cái)?shù)基本上與其他相近或更少，但是在成功求解時(shí)間上更小，且做法上更簡單，更易于理解。

由于現(xiàn)階段的通用量子計(jì)算機(jī)難以滿足破譯RSA公鑰密碼的實(shí)際需求，所以降低了成功率而使所需空間復(fù)雜度變低，能在一定程度內(nèi)解決量子計(jì)算機(jī)器件的難題，這樣做對(duì)目前更好地解決更大數(shù)的 RSA破譯有深遠(yuǎn)的影響，所以值得推廣。正是應(yīng)用這一特點(diǎn)，提出了改進(jìn)Shor量子攻擊方法。

3.3 改進(jìn)Shor算法分解N=119量子電路的實(shí)驗(yàn)

本實(shí)驗(yàn)在配置為Intel Core2 Duo CPU T6670 2.20 GHz、內(nèi)存2 G的聯(lián)想筆記本上，在數(shù)學(xué)工具M(jìn)athematics9.0軟件下調(diào)用 José Luis Gómez-Mu?oz 和 Francisco Delgado編寫的量子程序包進(jìn)行的量子電路上進(jìn)行仿真?；赟hor算法實(shí)現(xiàn)步驟的分析，實(shí)驗(yàn)成功分解了15、21、35、65、119、123、205等數(shù)，下面討論Shor算法量子電路[15]實(shí)現(xiàn)分解N=119的實(shí)驗(yàn)。

將改進(jìn)Shor量子攻擊算法與原Shor算法進(jìn)行對(duì)比實(shí)驗(yàn)，比較其攻擊結(jié)果。選用Shor算法分解 N=119的實(shí)驗(yàn)，選擇的隨機(jī)數(shù) x=13，在Mathematics 9.0軟件下進(jìn)行仿真實(shí)驗(yàn)。

運(yùn)行如圖2所示的量子電路，求解所得周期，結(jié)果如圖3所示。

圖3 量子傅里葉變換后第一寄存器|c＞的概率（第二寄存器的

由此得到N=119，可以分解為119=17×7。

這里要說明的是，在判斷周期r的時(shí)候，其實(shí)只要觀察圖3的波峰即可確定。在判斷時(shí)，直接觀察波峰數(shù)就是周期數(shù)的依據(jù)是：結(jié)合最后測量的概率公式，在觀察的概率分布時(shí)，s=1,…,r-1，c的取值為k，當(dāng)出現(xiàn)一個(gè)k滿足時(shí)，離散概率就出現(xiàn)一個(gè)波峰。

本次實(shí)驗(yàn)的其他結(jié)果統(tǒng)計(jì)如表1～表4所示。

表1 分解相同數(shù)、相同比特?cái)?shù)，不同隨機(jī)數(shù)下的實(shí)驗(yàn)結(jié)果

表2 分解相同數(shù)、相同隨機(jī)數(shù)13，不同比特?cái)?shù)下的實(shí)驗(yàn)結(jié)果

表3 分解相同數(shù)，相同隨機(jī)數(shù)83，不同比特?cái)?shù)下的實(shí)驗(yàn)結(jié)果

表4 分解相同數(shù)、相同隨機(jī)數(shù)97，不同比特?cái)?shù)下的實(shí)驗(yàn)結(jié)果

觀察表1可發(fā)現(xiàn)，不同隨機(jī)數(shù)會(huì)影響分解運(yùn)行時(shí)間。

由表2～表4可以發(fā)現(xiàn)，量子比特?cái)?shù)的多少對(duì)運(yùn)行時(shí)間是有影響的，且隨機(jī)數(shù)的選擇對(duì)量子比特?cái)?shù)的多少也是有影響的。

4 實(shí)驗(yàn)分析

4.1 成功率分析

分解 119，在設(shè)置不同量子比特?cái)?shù)、不同隨機(jī)數(shù)下，實(shí)驗(yàn)成功次數(shù)的統(tǒng)計(jì)如表5所示。

觀察表5可以發(fā)現(xiàn)，當(dāng)量子比特?cái)?shù)減少時(shí)，對(duì)于分解的成功率是有影響的，且可以定性地反映出當(dāng)量子比特?cái)?shù)減少時(shí)，成功率是下降的。

Shor原始算法給出，選定一個(gè)隨機(jī)數(shù)求得周期r的成功率為，其中r是階也可以說是周期，歐拉函數(shù)，p和q是N的2個(gè)因子。因?yàn)閿?shù)論上有，k是一個(gè)小于1的常數(shù)。所以，Shor認(rèn)為如果重復(fù)做O(loglogr)規(guī)模次，其成功率一定可以增加。由于本文的改進(jìn)Shor算法與Shor算法本質(zhì)上是一樣的，所以成功求得周期r的概率也是。如果知道周期 r，則可成功分解的概率至少是，即Shor算法成功分解的概率至少是。結(jié)合實(shí)驗(yàn)數(shù)據(jù)，給出成功率公式為

其中，φ(N)、φ(r)都是關(guān)于N和r的歐拉函數(shù)，N是要分解的數(shù)，r是求的階，即周期。所以在分解119的時(shí)候，當(dāng)L=2，r=4時(shí)，成功率為

1997年，Eicher J和Opoku Y的研究給出了一個(gè)在多項(xiàng)式時(shí)間內(nèi)以1/480≈0.002的成功率攻擊橢圓曲線離散對(duì)數(shù)問題的量子計(jì)算算法，證明低成功率也可以成功攻擊。而這里分解 119，成功率為0.001 3，所以也滿足條件。

4.2 復(fù)雜度分析

一個(gè)量子電路的復(fù)雜度分為空間復(fù)雜度和時(shí)間復(fù)雜度，具體反映在3個(gè)方面：量子電路比特?cái)?shù)[16]、量子電路需要的基本量子門規(guī)模（也稱量子電路尺寸）和量子電路深度。量子電路尺寸和量子電路深度對(duì)應(yīng)量子電路所需要的時(shí)間規(guī)模，即時(shí)間復(fù)雜度，量子比特?cái)?shù)目即空間復(fù)雜度。電路尺寸是指一個(gè)量子電路中所有基本量子門電路的總數(shù)，基本量子門指的是H門、CNOT門、控制-旋轉(zhuǎn)門、Toffli門等。一個(gè)量子電路的深度是指該量子電路所有量子門的深度之和，直觀上講就是這個(gè)量子電路有幾層，類似于程序的循環(huán)?？傊?，在計(jì)算量子電路復(fù)雜度時(shí)，一要計(jì)算該量子電路需要的量子比特?cái)?shù)，即空間復(fù)雜度；二是計(jì)算量子電路所需要的基本量子門規(guī)模和量子電路的深度，即量子電路的時(shí)間復(fù)雜度。

由于算法本質(zhì)上還是Shor算法的原型，下面給出改進(jìn)Shor算法的復(fù)雜度。因?yàn)镾hor算法主要由量子傅里葉變換和模冪運(yùn)算組成，故 Shor算法的復(fù)雜度也是指這兩部分的復(fù)雜度，如表6所示。

表6 Shor算法復(fù)雜度

表6中的L=log2N，N為要分解的數(shù)。

引入二進(jìn)制查表法加快了模冪算法的運(yùn)算速度。在改進(jìn)的Shor算法引入該算法后，其空間復(fù)雜度和時(shí)間復(fù)雜度依然為（L1，L）和T=O(2L2)。

4.3 算法比較

4.3.1 與原始Shor攻擊算法比較

通過分解119實(shí)驗(yàn)，總結(jié)改進(jìn)Shor量子算法屬性，并與原始Shor算法進(jìn)行比較，如表7所示。其中，L1為第一量子寄存器量子比特?cái)?shù)，L=log2N。

可以知道，改進(jìn)Shor算法成功求解時(shí)間相對(duì)于 Shor原始算法成功求解時(shí)間可簡化為Shor原始算法成功求解時(shí)間可簡化為，所以，改進(jìn)Shor算法成功求解時(shí)間小于原始算法，得到了一定的提升。

表7 改進(jìn)Shor量子算法與原始Shor算法的比較

雖然降低了成功率，但也成功降低了復(fù)雜度，在分解119的時(shí)候，成功地將所需空間復(fù)雜度從S=(2L，L)降低為S=(2，L)。這對(duì)于現(xiàn)階段還沒有通用的大量子比特計(jì)算機(jī)來說具有深刻的意義，復(fù)雜度降低，讓其可以在更少量子比特?cái)?shù)的量子計(jì)算機(jī)上運(yùn)行，能很好地解決現(xiàn)階段量子計(jì)算機(jī)器件要求高的難題。

4.3.2 與目前主要改進(jìn)Shor算法比較

2008年，英國倫敦帝國學(xué)院布萊克特實(shí)驗(yàn)室的Parker S等[17]給出了一個(gè)單一的純量子比特與log2N量子比特在任意混合態(tài)下的集合來有效實(shí)現(xiàn)Shor因式分解的算法。該算法大大減少了所需的量子比特?cái)?shù)。

2010年，解放軍信息工程大學(xué)[11]提出了2個(gè)新的改進(jìn)Shor算法：具有高概率的整數(shù)分解量子計(jì)算算法和 Shor整數(shù)分解量子算法的加速實(shí)現(xiàn)算法。

具有高概率的整數(shù)分解量子計(jì)算算法指出需要3個(gè)L bit的量子寄存器實(shí)現(xiàn)（該量子電路需要4次量子傅里葉變換和1次模冪運(yùn)算）。

Shor整數(shù)分解量子算法的加速實(shí)現(xiàn)算法指出需要S=(4, L)量子比特（每個(gè)量子傅里葉變換需要2個(gè)量子比特，第一量子寄存器對(duì)應(yīng)量子傅里葉變換需要4個(gè)量子比特，第二個(gè)量子寄存器需要L Qubit）。

2013年，美國的佐治亞大學(xué)[18]用8 Qubit實(shí)現(xiàn)了Shor算法分解51和85的實(shí)驗(yàn)，它是對(duì)量子輸入態(tài)的改進(jìn)，該算法指出第一量子寄存器和第二量子寄存器都只需要 S=(Lmax, Lmax) Qubit，其中，接近為

由表8可知，改進(jìn)Shor算法的復(fù)雜度比文獻(xiàn)[11]的2個(gè)改進(jìn)Shor整數(shù)分解算法要小。Shor整數(shù)分解量子算法的加速實(shí)現(xiàn)算法的第一量子寄存器量子比特?cái)?shù)雖然比較小，但所需的時(shí)間復(fù)雜度還是O(L3)，相對(duì)于改進(jìn)Shor算法，雖然減少了量子比特?cái)?shù)，但是時(shí)間復(fù)雜度多了L倍，所以第一量子比特?cái)?shù)降低為4沒有很大的意義。而具有高概率的整數(shù)分解量子計(jì)算算法增加了量子比特?cái)?shù)，且時(shí)間復(fù)雜度還是O(L3)。這里定義一個(gè)新的時(shí)間——成功求解時(shí)間，即每次求解時(shí)間與成功率之間的比值?？芍?，改進(jìn)Shor算法成功求解時(shí)間相對(duì)于文獻(xiàn)[11]的2個(gè)改進(jìn)Shor整數(shù)分解算法的成功求解時(shí)間可簡化為文獻(xiàn)[11]的 Shor整數(shù)分解算法成功求解時(shí)間可簡化為O(L3)4，文獻(xiàn)[11]的具有高概率的 Shor分解算法成功求解時(shí)間簡化為L越大，復(fù)雜度一個(gè)級(jí)別的差距不是與幾個(gè)簡單的自然數(shù)相乘就可以達(dá)到的，因此可知改進(jìn)Shor算法的成功求解時(shí)間小于文獻(xiàn)[11]的2個(gè)改進(jìn)Shor整數(shù)分解算法的成功求解時(shí)間。

表8 改進(jìn)Shor量子算法與目前主要的改進(jìn)Shor算法的比較

對(duì)比Michael[18]的改進(jìn)Shor算法，改進(jìn)Shor算法的復(fù)雜度比 Michael的復(fù)雜度要小，且成功求解時(shí)間比改進(jìn)Shor算法的成功求解時(shí)間大。對(duì)比Parker的改進(jìn)Shor算法，改進(jìn)Shor算法的時(shí)間復(fù)雜度較小，空間復(fù)雜度相近，最主要的是，成功求解時(shí)間比Parker改進(jìn)Shor算法的成功求解時(shí)間小。

5 結(jié)束語

本文的主要內(nèi)容在于犧牲成功率來換取空間復(fù)雜性的降低，并在一定范圍內(nèi)提高了算法的運(yùn)算速度，目的是為了在現(xiàn)有量子計(jì)算機(jī)器件允許的條件下開展研究，事實(shí)上并沒有降低實(shí)際上的成功求解時(shí)間。

雖然犧牲了成功率，需要數(shù)百次運(yùn)行才能得到成功的破譯結(jié)果，但降低了對(duì)通用量子計(jì)算機(jī)的器件要求，提高了通用量子計(jì)算機(jī)破譯公鑰密碼的現(xiàn)實(shí)性。改進(jìn)的模冪計(jì)算也提高了Shor算法的運(yùn)算速度。

由于實(shí)際成功求解時(shí)間等于每次分解時(shí)間除以成功率。本文提出的小Qubit改進(jìn)Shor算法，實(shí)際成功求解時(shí)間還是低于 Shor算法和目前主要的改進(jìn)Shor算法。

就算法本身而言，雖然Shor算法能夠?qū)崿F(xiàn)把指數(shù)級(jí)的運(yùn)算降為多項(xiàng)式時(shí)間內(nèi)來完成[19]，但其需要的資源卻隨著量子比特?cái)?shù)指數(shù)級(jí)增長。理論上講，當(dāng)量子比特?cái)?shù)增加時(shí)，量子算法的能力應(yīng)該是更強(qiáng)的，因?yàn)榱孔颖忍財(cái)?shù)增加了，并行計(jì)算的資源增加了，那么利用并行計(jì)算的量子算法自然增強(qiáng)了。但事實(shí)上，當(dāng)量子比特?cái)?shù)增加時(shí)，消耗資源的增長反而限制了量子算法的實(shí)現(xiàn)，使量子算法陷入一個(gè)無法掙脫最開始并行的境地。由此，本文也驗(yàn)證了在通用量子計(jì)算機(jī)還沒有達(dá)到千位量子比特之前，想要利用更多量子比特并行能力的想法目前還不能實(shí)現(xiàn)。

這就是說，盡管大家都認(rèn)為多量子比特可能比小量子比特實(shí)現(xiàn)量子算法解決實(shí)際問題更好，但是當(dāng)器件進(jìn)展尚無法控制千位量子比特時(shí)，不能達(dá)到預(yù)期的效果。所以本文改進(jìn)算法的研究有助于充分提高現(xiàn)有小通用量子計(jì)算機(jī)破譯公鑰密碼的可行性。

[1] GIBNEY E. Physics: quantum computer quest: after a 30-years struggle to harness quantum weirdness for computing, physicists finally have their goal reach[J]. Nature News Feature, 2014:24-26.

[2] MARIANTONI M, WANG H, YAMAMOTO T et al. Implementing the quantum von neumann architecture with superconducting circuits[J]. Science, 2011, 334(6052):61-5.

[3] ERIK L, BAREDNS R., CHEN Y, et al. Computing prime factors with a josephson phase Qubit quantum processor[J]. Nature Physical, 2012, 8: 719-723

[4] 王潮, 王云江, 胡風(fēng). 量子計(jì)算機(jī)的商業(yè)化進(jìn)展及對(duì)信息安全的挑戰(zhàn)[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 2016, 2(3):17-27.WANG C, WANG Y J, HU F. Shaping the future of commercial quantum computer and the challenge for information security[J]. Chinese Journal of Network and Information Security, 2016, 2(3):17-27.

[5] VARTIAINEN J J, NISKANEN A O, NAKAHARA M, et al. Implementing Shor's algorithm on Josephson charge Qubits[J]. Physical Review A, 2004, 70(1).

[6] GLENDINNING I, ?MER B. Parallelization of the QC-Lib quantum computer simulator library[J]. Lecture Notes in Computer Science, 2003, (3019):461-468.

[7] DE-RAEDT K, MICHIELSEN K, DE-RAEDT H ET AL. Massively parallel quantum computer simulator[J]. Computerphysicscommunications,2007,176:121-136.

[8] GARCíA-MATA I, FRAHM K M, SHEPELYANSKY D L. Effects of imperfections for Shor’s factorization algorithm[J]. Physical Review A, 2007,(75).

[9] YANG C, DANIEL L, BROWNE E, YANG T, et al. Demonstration of a compiled version of Shor’s quantum factoring algorithm using photonic Qubits[J]. Physical Review Letter, 2007, (99).

[10] THOMPSON M G, POLITI A, MATTHEWS J C F, et al. Integrated waveguide circuits for optical quantum computing[J]. Institution of Engineering and Technology, 2011, 5: 94-102

[11] 付向群, 鮑皖蘇. 具有高概率的量子計(jì)算算法研究[D]. 鄭州:解放軍信息工程大學(xué). 2011 FU X Q, BAO W S. Research on the quantum algorithm with high probability[D]. Zhengzhou: PLA Information Engineering University. 2011

[12] NAGAICH S, GOSWAMI Y C. Shor’s algorithm for quantum numbers using MATLAB simulator [C]//The fifth International Conference on Advanced Computing amp; Communication Technologies. 2015:165-168.

[13] DAVID S W, CHARIES D H, LLOYD C L, et al. Simulatiobs of shor’s algorithm using matrix product states[J]. 2015.

[14] 董付國, 厲玉蓉, 杜萍. 方冪?？焖儆?jì)算的二進(jìn)制分組查表法[J].計(jì)算機(jī)工程與應(yīng)用, 2009, 45(22): 71-73.DONG F G, LI Y R, DU P. Fast calculation of modular exponentiation binary group look-up table method[J]. Computer Engineering and Applications, 2009, 45(22): 71-73.

[15] 佐川弘幸, 吉田宣章, 著. 宋鶴山 譯. 量子信息論[M]. 大連:大連理工大學(xué)出版社, 2007.SONG H S. Quantum information theory[M]. Dalian: Dalian University of Technology Press, 2007.

[16] CHOI B S, METER R V. On the effect of quantum interaction distance on quantum addition circuits[J]. ACM Journal on Emerging Technologies in Computing Systems. 2010.

[17] PARKER S, PLENIO M B. Efficient factorization with a single pure Qubit and log N mixed qubits[J]. Physical Review Letter, 2000,(85): 3048-3052

[18] MICHAEL R.G, ZHOU Z Y. Factoring 51 and 85 with 8 Qubits[R].Scientific Reports, 2013.

[19] 孫國棟, 蘇盛輝, 徐茂智.求根問題的量子計(jì)算算法[J].北京工業(yè)大學(xué)學(xué)報(bào), 2015, (41): 366-371.SUN G D, SU S H, XU M Z. Quantum computing algorithms of find roots problems[J]. Journal of Beijing University of Technology,2015, (41): 366-371.

Research of the small Qubit quantum computing attack to the RSA public key cryptography

WANG Bao-nan1, CHEN Yu-hang1, YIN Bao1, HU Feng1, ZHANG Huan-guo2, WANG Chao1

(1. Key Laboratory of Special Fiber Optics and Optical Access Networks, School of Communication and Information Engineering, Shanghai University, Shanghai 200072, China;2. Key Laboratory of Aerospace Information Security and Trusted Computing, Wuhan University, Wuhan 430072, China)

The small Qubit quantum algorithm attack to RSA was proposed, the need Qubit of the first quantum register from 2L to L1, it can be reduced to 2 Qubit, the overall space complexity denoted (L1,L), where 2L1≥r, r is the period of decomposed. Because of the reduce of the first quantum register, it reduces the algorithm’s complexity and success rates, and use the binary look-up table method to compute the modular exponentiation, it enhances the computing speed. The improved algorithm’s quantum circuit complexity is T=O(2L2). It have a significant improvement on the time complexity and space complexity. Although the success rate is reduced, the overall success solution time is still lower than the Shor algorithm and the current major improvements Shor algorithm. Completed a simulation experiment. Respectively use the 11、10、9 Qubit decomposing the quantum circuit 119. The new algorithm explore the reality of using a universal quantum computer device to decipher the public key cryptography.

Shor algorithm, RSA algorithm, quantum circuits, small qubits, attack

s：The Key Program of National Natural Science Foundation of China (No.61332019), The National Natural Science Foundation of China (No.61572304, No.61272096, No.60970006)

TP309

A

10.11959/j.issn.2096-109x.2017.00206

2017-08-19；

2017-09-27。

王潮，wangchao@staff.shu.edu.cn

國家自然科學(xué)基金重點(diǎn)資助項(xiàng)目（No.61332019)；國家自然科學(xué)基金資助項(xiàng)目（No.61572304, No.61272096,No.60970006）

王寶楠（1989-），女，江蘇淮安人，上海大學(xué)博士生，主要研究方向?yàn)樾畔踩?、量子?jì)算密碼、社會(huì)網(wǎng)絡(luò)。

陳宇航（1991-），男，浙江杭州人，上海大學(xué)碩士生，主要研究方向?yàn)榱孔佑?jì)算與量子攻擊密碼分析。

尹寶（1991-），男，河南信陽人，上海大學(xué)碩士生，主要研究方向?yàn)榱孔佑?jì)算與量子攻擊密碼分析。

胡風(fēng)（1991-），男，浙江溫州人，上海大學(xué)博士生，主要研究方向?yàn)樾畔踩⒘孔佑?jì)算密碼、社會(huì)網(wǎng)絡(luò)。

張煥國（1945-），男，河北元氏人，武漢大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)樾畔踩?、密碼學(xué)和可信計(jì)算。

王潮（1971-），男，江蘇鎮(zhèn)江人，博士，上海大學(xué)教授，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、網(wǎng)絡(luò)信息安全與橢圓曲線密碼學(xué)、量子計(jì)算與量子攻擊密碼分析。