Shor量子計算對公鑰密碼的攻擊分析

尹寶，王克達，王嘯，王潮

Shor量子計算對公鑰密碼的攻擊分析

尹寶，王克達，王嘯，王潮

當前電子政務和電子商務CA中心采用的公鑰密碼主要是RSA和ECC，其安全基礎分別是大數分解和橢圓曲線離散對數的數學難題。1994年，Peter W.Shor提出了Shor算法，指出Shor算法可以用于在多項式時間內求解大數質因子和離散對數數學難題，開啟了Shor量子計算對公鑰密碼的攻擊研究。在參閱大量國內外相關研究文獻后，對目前Shor量子計算對公鑰密碼攻擊的研究概況和量子計算機物理硬件上的實現做了綜述性分析。

公鑰密碼；Shor算法；RSA算法；ECC算法；攻擊

0 引言

Diffie和Hellman于1976年首次提出公鑰密碼學（public key cryptography簡稱PKC）的概念。這一新的思想，引起了密碼學歷史上的一次巨大的歷史變革，開創了密碼學和信息安全發展的新紀元。相對于以前的DES、AES等對稱加密算法，公鑰密碼算法也被稱為非對稱加密算法。公鑰密碼學能夠很好的解決經典對稱密碼體制所固有的密鑰管理困難及不能進行數字簽名等問題，而且公鑰密碼方便密鑰的管理，這不僅使得對稱密碼體制的使用變得方便和可靠，而且使密碼學在網絡和信息安全中發揮的作用更加廣泛和突出。目前，公鑰密碼理論與技術的發展正在為各種各樣的信息系統的安全性發揮著不可或缺的保障作用。至今，公鑰算法的發展已經經歷了20多年，也出現了很多種類的公鑰密碼算法。

1 有代表性的公鑰密碼算法

目前有3種公鑰密碼具有代表性：

（1）基于大整數分解難題（IFP）的算法體制；

（2）基于離散對數難題（DLP）的算法體制；

（3）基于橢圓曲線離散對數難題（ECDLP）的算法體制。

應用比較廣泛的是第一種和第三種密碼體制對應下的密碼算法：RSA和 ECC公鑰密碼算法。對于 IFP 問題和ECDLP問題，在數論上被認為是難解的NP問題即在現有的經典計算機上暫時還不能找到有效的多項式算法來成功求解的。這種數學上的難解特性使得RSA和ECC加密算法具有很高的安全性。

RSA加密體制是由麻省理工大學的Rivest、Shamir和Adleman在1978年提出的，橢圓曲線密碼體制是Miller和Koblitz于1985首次提出的。這兩種加密算法在非對稱加密體制中占有重要地位，不僅能用來加密數據，還能用來進行數字簽名。RSA加密算法主要應用在網上交易加密連接、網上銀行身份驗證、各種信用卡的數字證書、智能移動電話和存儲卡的驗證的功能芯片等商業方面。ECC的應用目前還沒有統一的標準，且成本相對更高，使其應用不像 RSA那樣廣泛。但是由于其單位比特比RSA更高的安全性，在國家戰略層面上更受親睞，如其在二代身份證上的加密和數字簽名應用。

隨著計算機技術和量子力學的結合發展，一種全新的計算機概念被提出：量子計算機。量子計算機（quantum computer，簡稱QC），是一類遵循量子力學規律進行高速數學和邏輯運算、存儲及處理量子信息的物理裝置。當某個裝置處理和計算的是量子信息，運行的是量子算法時，它就是量子計算。雖然現在還沒有一臺真正意義上的通用量子計算機，但是已經有了量子計算：在經典計算機上運行量子算法。這種量子計算使得傳統計算機有了更高的運算效率，也使得當運行某種量子算法時，可以讓傳統計算機解決某些數學難題的不可能成為了可能。

1994年，美國AT&T公司的Shor提出了可在多項式時間內完成分解大整數質因子的量子算法，稱其為Shor算法。在1997年的時候，Shor又對這種量子算法做了進一步詳細的解釋和闡述?；赟hor算法的思想，Shor算法被用來求解大數 N的兩個質因子問題和求解橢圓曲線離散對數問題的研究開始出現。

這樣，Shor算法的提出就使得正被廣泛應用的RSA和ECC加密算法的安全性受到了極大的挑戰。這一挑戰也直接關系到我國使用公鑰密碼的電子商務和電子政務的信息安全，更關系到我國戰略層面上的如二代身份證的信息安全。所以，作為本課題Shor量子計算對公鑰密碼攻擊就具有了重要的科研價值和實際意義。

Shor算法是一種運行在量子計算機上的量子算法。人們已經付出了很多努力直接去構建量子計算機，但目前為止仍然難以實現控制成百上千個量子比特的量子計算機。令人遺憾的是，物理學界、密碼學界、計算機學界和數學界等的科學家認為：要研究出能夠控制成百上千個比特的量子計算機在未來很長一段時間內依然是極其困難的。本文參閱大量國內外相關研究文獻，對目前Shor量子計算對公鑰密碼攻擊的研究概況和物理硬件上的實現做綜述性分析。

2 國內外研究的最新進展

目前應用最廣泛的公鑰密碼是RSA和ECC，所以可以說量子算法（這里就是Shor算法）對公鑰密碼的攻擊就是量子算法對RSA和ECC加密算法的攻擊。由于RSA和ECC加密體制的安全基礎分別是IFP和ECDLP問題，所以量子算法攻擊RSA和ECC加密算法就是要使其能夠求解IFP（大數質因子分解問題）和 ECDLP（橢圓曲線離散對數問題）問題。圍繞著這兩個問題，目前國內外專家學者做了大量的研究。

2.1 Shor算法攻擊RSA研究概況

（1）國外研究概況

1996年，美國科學家Juan Pablo Paz在一個有干擾和損耗的量子電路上用了27量子比特成功分解了15。同時他指出對于分解大數N，需要的量子比特數應是n=5L+7（其中L取大于等于log2N的最小正整數）。這項工作的開展給實際操作中實現Shor量子算法提供了很好的借鑒。

2001年，美國IBM公司和斯坦福大學合作，利用核磁共振技術演示了Shor算法對15進行分解的實驗，但該實驗不能顯示其量子屬性，也無法擴展到更多的比特，限制了進一步的研究。

2003年，加拿大蒙特利爾大學的 Stephane Beauregard介紹了一個使用2n+3量子比特的Shor分解的電路[1]，還用量子電路的11個量子比特分解了15。該電路的部分靈感來自于1996年的英國牛津大學克拉倫登實驗室[2]。

2004年，美國赫爾辛基理工大學材料物理實驗室的Jula J.Vartiainen利用約瑟夫森電荷量子比特實現了Shor算法[3]。他把Shor算法的量子電路分成了一系列兩量子比特和三量子比特的量子門不僅加速了Shor算法的實現，而且在此基礎上通過數值優化的方法成功完成了對N=21分解的物理實現。

2007年，法國理論物理研究實驗室在研究Shor算法的缺陷[4]（量子比特間殘余耦合造成）所產生的影響時，通過編寫 Quantware庫并調用該庫，用 30個量子比特實現了N=943的分解。

2010年，英國布里斯托大學電氣和電子工程的物理實驗室和部門的量子光學中心的M.G. Thompson 等介紹了基本的Shor因式分解量子算法的實現[5]，主要是在由6個H門和 2個可控的相位門組成的波導電路中建立了一個可以實現Shor量子分解算法的電路，并成功的用Shor算法分解N=15。

2012年，美國加州大學圣巴巴拉分校的Erik Lucero等人[6]，在之前一些量子控制和硬件的技術下，展示了一個九量子元件的固態量子處理器來分解15的過程。該文首先用光譜描述設備，最后執行一個3量子比特模型來分解15，當超導量子態相干時間和更復雜的電腦被提供時可以分解更大的數。

2013年，美國衛斯理大學的 Y.S.Nan等，在一個 128核的傳統計算機集群上構建了一個虛擬的運行Shor算法的量子計算機[7]，該虛擬量子計算機被分為在兩種模式下實現Shor算法。Shor算法的核心部分包括模冪運算部分ME和求周期運算部分PF。這兩種模式也就是基于Shor算法劃分的：第一種模式稱之為 PF（周期查找）模式即只有周期查找部分沒有Shor算法的模冪運算部分（這部分用傳統模冪運算結果來代替），第二種模式稱之為滿Shor算法模式包括模冪運算和周期查找兩部分。在第一種模式下運行的虛擬量子計算機可以最多控制39量子比特來實現N=55793的分解，在第二種模式下，可以最多實現N=57的分解。

（2）國內研究概況

國內的研究起步比較晚，這其中主要以中國科技大學的研究者為代表。

2007年，中國科學院公布，中國科技大學教授潘建偉和他的同事楊濤等[8]與英國牛津大學的研究人員合作，在國際上首次利用光量子計算機實現了Shor量子分解算法，研究發表在當年1月的物理評論快報上。并在該量子計算上成功操控了 4個光子量子比特構造一個簡單的線性光網絡實現N=15的分解。

2.2 Shor算法攻擊ECC研究概況

關于量子算法Shor算法對ECC的攻擊相對于Shor算法攻擊RSA來說很少。原因主要有兩方面：（1）Shor算法是建立在有限域的乘法群上來求解問題的，而ECC加密算法的橢圓曲線密碼是基于有限域下的加法群。雖然有限域下乘法群和加法群都可以歸納為阿貝爾隱含子群，但它們之間還是有很大區別的。（2）ECC加密算法相對RSA算法具有更難理解、運算更復雜的特征。這就使得研究Shor算法攻擊ECC加密算法變得更加困難。截止2014年12月份，經對《Nature》、《Science》、《PhyReview》等國內外相關文獻的搜尋，針對Shor算法攻擊ECC的研究主要有以下幾家為代表：

首先是Shor本人。1994年，Shor提出了量子算法Shor算法，他指出Shor算法可以很容易破解大素數質因子分解，而且Shor算法可以去求解離散對數問題。至此開創了量子算法對公鑰密碼攻擊的研究，也給后來基于Shor算法求解橢圓曲線離散對數問題提供了很重要的思路。

其次，是以美國里奇蒙大學的Jodie Eicher和YawOpoku為代表的研究[9]。在 1997年，他們在首先介紹了橢圓曲線加密系統和量子計算的基礎之上，假設一個量子可以運行Shor算法的量子計算機已經存在，詳細的分析了Shor算法求解離散對數問題的過程并給出理論上的實現操作步驟。因為，橢圓曲線離散對數問題與離散對數問題具有一定的相關性，他們做了類似于Shor算法求解離散對數問題的用Shor算法求解橢圓曲線離散對數問題的研究。令人欣喜的是，按著他們的思想和方法，他們在理論上成功分析了一個具體的用Shor算法求解橢圓曲線離散對數問題的例子。但是該舉例實現起來相當困難。

另外一個具有代表性的是在2003年加拿大的滑鐵盧大學做的關于用Shor算法求解橢圓曲線離散對數問題的研究。滑鐵盧大學最開始是從數學和Shor算法兩個方面進行著手分析：首先，分析有限域下各種橢圓曲線的特性并選擇了一條特殊的橢圓曲線進行分析；然后，從實現Shor算法的模冪運算與量子傅里葉變換的兩個模塊本身出發，進行對Shor算法進行優化。在此基礎上，逐步分析Shor算法求解IFP、DLP、ECDLP問題，理論上做了一個很完整的Shor算法求解橢圓曲線離散對數問題的研究，并指出對于Shor算法攻擊n位比特的ECC，需要的量子比特數為6n Qubits。但是，僅限于理論分析沒有給出實驗模擬的過程。

此外，國內有關Shor算法求解橢圓曲線離散對數問題的研究也在逐步開展，這里面例如解放軍信息工程大學等[9][10]都有這方面的研究。

3 物理硬件上的實現

量子計算機上的物理硬件的實現能力決定著Shor算法分解攻擊的能力，對量子計算機上的物理硬件實現情況做相關分析總結。

在較新研究中，2012年，美國斯坦福大學愛德華.L.金茲頓實驗室的N.Cody Jones等人提出了一個基于光控量子點的量子計算機分層結構[11]，通過將功能劃分為層，可以獨立設計和分析子系統，并在該硬件平臺上執行分析了分解算法。

3.1 實現量子計算機的幾種物理方法

（1）光子法（原子和光腔相互作用）：如用光子法進行量子密鑰的分發。光晶格中的中性原子和光學級聯腔中的原子進行量子模擬，光學腔可以任意的幾何方式排列，每個腔和一個原子系統相互作用，同時可以加入外光場來驅動原子系統，腔中的原子和腔場一起構成了極化子，這個系統可以用于模擬Bose-Hubbard模型。

（2）捕獲原子法（離子阱）：光腔（介質波導）中相干光子做Qubit；微波腔中相干電磁波做Qubit。例如利用Pauli電磁勢阱來束縛離子，離子在勢阱中呈軸向排布，量子比特編碼在離子的內態上。優勢在于存在高精度的門操作和量子探測方案，但是集成性不是特別好，離子較多時，為使庫倫勢能最低，離子不在呈現規則的軸向排布，而是會形成“之”字型或者其他更復雜的圖樣。

（3）核磁共振實驗較簡單，可在室溫下進行，缺點：需做re-focds等，需要一定花費，使信號隨量子比特數增加而指數下降，要找具備很多有效量子比特的特定分子也不容易，所以NMR的QC最高只達到10Qubit左右。有實驗執行了基于7個量子位元的液態磁振量子電腦的Shor算法，對15做因式分解為3和5的示范，有寫到對7個量子比特算法分解15為3和5有實現了99.94%的性能改進。

（4）量子點和滲雜物固體，在二維電子氣中通過疊加兩維的網格門，實現了一個半導體量子點鏈，只有量子點和超導約瑟夫森結方案更適合集成化和小型化。

（5）超導量子計算機，Qubits-SQUID中的庫伯對或磁通量子，Access與操作—定位德爾電容，電感耦合（約瑟夫森結量子系統）。

（6）硅固態量子計算機，優勢在于：有希望大規模擴展；固態；與硅技術可兼容。

3.2 FPGA模擬

王伶俐的FPGA模擬方法可以分解任意n量子比特門為m量子比特門和各種對角線門，即數學上n量子比特門U(2n) =U(2m)矩陣和對角矩陣。跟FPGA的結構類似，該量子結構由量子路由通道（QRC，用來量子路由資源和實現幺正變換，控制量子邏輯輸入輸出）和量子邏輯塊（QLB，執行一個通用兩量子比特門）組成。

4 總結

本文分析Shor量子計算對公鑰密碼的攻擊的國內外研究及物理實現現狀，得出：

Shor量子計算對公鑰密碼的攻擊目前的研究還處于起步階段，能分解的大數和求解橢圓曲線離散對數的能力還很有限。

采用傳統方法來實現量子Shor量子計算攻擊更具有可行性。這也有助于降低對通用量子計算機的要求，實現Shor量子計算破譯公鑰密碼攻擊現實性。

目前的物理實現還只能控制小規模的量子比特實現量子算法Shor的運行，尚不能實現對現今使用的1024位RSA和163位的ECC的完全攻擊。所以要想能夠在多項式時間規模內實現Shor算法對公鑰密碼的攻擊，則必須依賴于千位以上的通用量子計算機。

[1]Juha J. Vartiainen, Antti O. Niskanen, Mikio Nakahara, and Martti M. Salomaa. Implementing Shor’s algorithm on Josephson charge qubits[J]. Phys. Rev. A 70, 012319, 2004.

[2]Ignacio Garcia-Mata, Klaus M. Frahm, and Dima L. Shepelyansky. Effects of imperfections for Shor’s factorization algorithm[J]. Phys. Rev. A 75, 052311, 2007.

[3]Chao-Yang Lu, Daniel E. Browne, Tao Yang, and Jian-Wei Pan. Demonstration of aCompiled Version of Shor’s Quantum Factoring Algorithm Using Photonic Qubits. Phys. [J]Rev. Lett. 99, 250504, 2007.

[4]M.G. Thompson, A. Politi, J.C.F. Matthews, J.L. O’Brien. Integrated Waveguide Circuits for Optical Quantum Computing[J]. Circuits, Device & System, IET. 2010, 5(2): 94-102.

[5]付向群, 鮑皖蘇. 具有高概率的量子計算算法研究[D].解放軍信息工程大學. 2010.

[6]Erik Lucero,R. Barends, Y. Chen, et al. Computing prime factors with a Josephson phase qubit quantum processor[J]. Nature physics. 2012, 8: 719-723.

[7]Nama Y. S., Blumel R..Streamlining Shor’s algorithm for potential hardware savings[J]. Phys. Rev. A ,87, 060304(R) (2013).

[8]Chao-Yang Lu, Daniel E. Browne, TaoYang, Jian-Wei Pan. Demonstration of a Compiled Version of Shor’s Quantum Factoring Algorithm Using Photonic Qubits[J]. Phys. Rev. Lett. 99, 250504, 2007.

[9]彭衛豐, 孫力. Shor量子算法的優化及應用研究. 計算機應用與軟件[J]. 2009, 26(5): 239-247.

[10]付向群, 鮑皖蘇, 王帥. ZN上離散對數量子計算算法[J].計算機學報, 2014, 37(5): 1058-1062.

[11]Jones, N. C., et al. A layered architecture for quantum computing using quantum dots[J]. Phys. Rev. X. 2, 031007 (2012).

Analysis of Shor quantum computer algorithm attacks to public key cryptography

Yin Bao1, Wang Keda2, Wang Xiao2, Wang Chao1
(1.Shanghai University Key Lab of Specialty Fiber Optics and Optical Access Network, Shanghai 200072, China; 2.China research institute of information security, Beijing 102200, China)

At present, e-government and e-commerce CA center use public key cryptography mainly containing RSA and ECC the security infrastructures of which are large integer factorization (IFP) and the elliptic curve discrete logarithm (ECDLP). In 1994，Peter W.Shor proposed Shor algorithm which could solvethe problems the of prime factorsof large numbers and elliptic curve discrete logarithm in polynomial time. It takes up the research of attackingpublic key cryptographywith Shor quantum algorithm. Referring to a lot of related research literatures, this paper makes analysis of the currently research on attacking public with key cryptography with Shor quantum algorithm and the realization of it in the physical hardware.

PublicKeyCryptography; Shor Algorithm; RSAAlgorithm; ECC Algorithm; Attacking

TN915

A

2015.04.01）

1007-757X(2015)05-0009-03

國家自然科學基金重點項目（61332019）；國家自然科學基金項目（61272096，60970006）；上海市教委創新基金重點項目（14ZZ089）

尹 寶（1990-），男，河南信陽人，上海大學，碩士研究生，研究方向：量子計算與量子攻擊密碼分析，上海，200072王克達（1976-），男，中國信息安全研究院，高級工程師，本科，研究方向：信息安全，北京，102200王 嘯（1985-），男，中國信息安全研究院，工程師，本科，研究方向：信息技術標準化和信息安全北京，102200王 潮（1971-），男，江蘇鎮江人，上海大學，教授，博士生導師，博士，研究方向：無線傳感器網絡、網絡信息安全與橢圓曲線密碼學，量子計算與量子攻擊密碼分析，上海，200072