對Shor算法破解RSA的探討

凃玲英， 胡一凡， 張洪濤， 代永濤， 熊紅梅

(1. 湖北工業(yè)大學 納米電子技術(shù)與微系統(tǒng)實驗室， 湖北 武漢 430068;2. 湖北工業(yè)大學 電氣與電子工程學院， 湖北 武漢 430068)

對Shor算法破解RSA的探討

凃玲英1,2， 胡一凡1,2， 張洪濤1,2， 代永濤1,2， 熊紅梅1,2

(1. 湖北工業(yè)大學 納米電子技術(shù)與微系統(tǒng)實驗室， 湖北 武漢 430068;2. 湖北工業(yè)大學 電氣與電子工程學院， 湖北 武漢 430068)

針對Shor算法具有隨機性，會導致破解RSA公鑰密碼體制成功率不高的問題，對Shor算法原理、RSA公鑰密碼體制特點和大量計算結(jié)果進行分析，提出量子函數(shù)式f(x)=axmodn對a值的隨機選取是有規(guī)律的.結(jié)合數(shù)論知識和蒙特卡洛法證明,結(jié)果表明：隨機數(shù)a取完全平方數(shù)，所求周期r很可能不滿足Shor算法要求；a取非完全平方數(shù)可以提高Shor算法破解RSA的成功率.

Shor算法； 非完全平方數(shù)； RSA算法； 公鑰密碼體制； 蒙特卡洛法.

迄今為止，RSA算法被認為是世界上最成熟完善的公鑰密碼體制.它能夠抵抗已知的絕大多數(shù)密碼攻擊，已被ISO推薦為公鑰數(shù)據(jù)加密標準.目前，世界上還沒有任何可靠的方法破解RSA.隨著Shor算法的提出和量子計算機的不斷發(fā)展，RSA的安全性也受到威脅.Shor算法利用量子計算的并行性，可以快速分解出大數(shù)的質(zhì)因子，它的提出在理論上破解了目前被公認為最安全的RSA公鑰密碼.Shor算法的基本原理是運用量子傅里葉變換，將大整數(shù)因子分解轉(zhuǎn)化為求某一個函數(shù)的周期[1].但是在求函數(shù)周期過程中，現(xiàn)有的Shor算法隨機性大，效率不高[2].鑒于此，本文通過對Shor算法和RSA算法原理的分析，并結(jié)合前人的研究成果，提出了一種可以提高Shor算法破解RSA成功率的方法.

1 RSA公鑰密碼

RSA使用公開的公鑰進行加密通信，密文只能被擁有與之匹配的私鑰的人解開.RSA算法的理論基礎(chǔ)[3]是可逆模指數(shù)運算，它的安全性基于數(shù)論中大整數(shù)分解的復雜性.數(shù)論中，大整數(shù)分解的問題可概述為：已知整數(shù)n=p·q，其中，p和q是2個素數(shù)，求出p和q的值.

在RSA公鑰密碼體制中，用戶擁有2個密鑰：公鑰PK={e,n}和私鑰SK={d,n}.公鑰用于加密，私鑰用于解密.用戶可將公鑰PK公開，而私鑰中的d必須嚴格保密.RSA公鑰密碼中相關(guān)參數(shù)的計算如下.1) 選取2個保密的素數(shù)p和q(p和q為100位以上的十進制數(shù)).2) 計算n=p·q的值.其中，n是RSA算法的模數(shù).3) 計算φ(n)=(p-1)(q-1)的值，φ(n)是n的歐拉函數(shù)值.4) 隨機選取1個整數(shù)e，使其滿足1

設(shè)m為需要加密的明文，c為加密后的密文.加密時,先將明文比特串進行分組，讓每個明文分組的十進制數(shù)mi小于n,記ci為對應(yīng)的mi加密后的密文，則加密算法為

式(1)中:0≤mi

解密時，先對密文c進行比特串分組，則解密算法為

因此，RSA公鑰密碼體制中，最關(guān)鍵的是公鑰PK中的e值和私鑰SK中的d值.

2 Shor算法

2.1 原理描述

故

3) 求A和B,表達式為

得出

式(7)中:為保證A,B為整數(shù)，周期r應(yīng)為非零偶數(shù)[5-6].

2.2 周期r的求取

由A和B的表達式可知：只要求出函數(shù)f(x)的周期r，大整數(shù)n的因子分解問題就得到了解決.Shor算法中，周期r的信息是通過量子傅里葉變換獲得的[7-8].

首先，對2個量子寄存器R1和R2進行初始化,再對R1依次作H變換和幺正變換，得到的結(jié)果分別存放到R1和R2中.R1和R2中的狀態(tài)為糾纏態(tài)，即

然后，對|R2〉進行測量.假設(shè)f(x)的周期為r.當|R2〉坍縮時，|R1〉也對應(yīng)地坍縮為

式(11)中:A為小于(q-1)/r的最大整數(shù).

最后，對|R1〉作量子傅里葉變換,并對其進行測量,求出函數(shù)f(x)的周期r，表達式為

量子傅里葉變換會使需要的結(jié)果增強，并使不需要的結(jié)果為0，這種現(xiàn)象稱為量子干涉[9].所以，當c=kq/r，則

|R1〉經(jīng)量子傅里葉變換后，周期從r變?yōu)閝/r.由于c=kq/r，c和q是已知的，如果k與r互質(zhì)，就能求出r[10].最大的非零偶數(shù)r，就是需要求的f(x)的周期.

3 Shor算法在破解RSA中的應(yīng)用

RSA的安全性取決于大整數(shù)n的分解，Shor算法的功能是分解大整數(shù)n，所以Shor算法在理論上破解了RSA公鑰密碼[11-12].破解過程具體如下6個步驟.

步驟1 通過量子傅里葉變換，求出函數(shù)f(x)的周期r,并保證r為非零偶數(shù).

步驟2 將r帶入式子(7),(8)中，結(jié)合待分解的大整數(shù)n，求出A和B的值.

步驟3 RSA中已銷毀的p,q值分別是A,B.

步驟4 將p,q帶入式子φ(n)=(p-1)(q-1)中，求出φ(n).

步驟5 將φ(n)和已知的e值帶入式子d×e≡1 modφ(n)中，求出d值.

步驟6 將d，n的值帶入式(2)中，完成了對RSA的破解.

4 對Shor算法破解RSA的優(yōu)化

4.1 優(yōu)化思路

Shor算法雖然在理論上破解了RSA，但還是存在一些微小的不足的地方.應(yīng)用Shor算法破解RSA，并不是大數(shù)n滿足了條件就一定能成功破解，只是能使破解的成功率盡量接近1.

例1 函數(shù)f(x)=axmod 33，選取a=4，求周期r.

f(0)=1,f(1)=4,f(2)=16,f(3)=31,f(4)=25,

f(5)=1,f(6)=4,f(7)=16,f(8)=31,f(9)=25, …

此時周期r=5，不是偶數(shù).

為了方便計算a取完全平方數(shù)時周期r的值，用C語言編寫了一段程序，程序的源代碼為

#include 〈stdio.h〉

#include 〈math.h〉

int gcd(int x,int y);

void main() {int a,c,x,n;

printf(″Please enter two int numbers:a=?,n=? ″);

scanf(″%d,%d″,&a,&n); if(gcd(a,n)!=1 ‖ a>n)

printf(″Please enter two correct int numbers b,n ″);

else { x=1; c=1%n;

while((int)(pow((double)a,(double)x))%n!=c)

x++; printf(″函數(shù)f(x)的周期r是：%d ″,x);

}

}

int gcd(int x,int y) {

int z; if(x

{ z=x; x=y; y=z;}

if(x%y = = 0) return y;

else return gcd(y, x%y); }

圖1 例1的驗算結(jié)果

在Visual C++中運行程序驗證例1的結(jié)果，驗算結(jié)果如圖1所示.由圖1可知：當a=4時，周期r為5，例1的結(jié)果得到了驗證.此程序方便求取r,為大量計算a取不同的完全平方數(shù)時對應(yīng)的周期r提供了便利.

4.2 優(yōu)化思路的證明

由例1可知：a取完全平方數(shù)算得的周期都不是偶數(shù).通過計算發(fā)現(xiàn)，這是Shor算法周期求解中的大概率事件.如果對隨機選取的a增加限制，不選取完全平方數(shù)，破解RSA的成功率會相應(yīng)地提高[5].

令p=2x+1，q=2y+1，且x≠y，則成功破解RSA的概率表示為

令d=gu,v為d的階，這就等同于uv=0 mod(p-1),v最小.

當x≠y時，只需考慮x

所以,成功破解RSA的概率是

在x=y的情況下，此時概率為1，表示(a/n)=-1中的a總是滿足條件1)和2).

從證明過程可看出，對a經(jīng)過一定的限定，應(yīng)用Shor算法破解RSA的成功率明顯得到提高，說明優(yōu)化思路是可行有效的.采用蒙特卡洛法作進一步分析.

列舉不同的整數(shù)N值，算出a在2個條件下,函數(shù)f(x)的周期r為偶數(shù)的概率P，如表1所示.Shor算法能否高效破解RSA，對應(yīng)函數(shù)式f(x)的周期r為偶數(shù)的概率P是重要指標.功能函數(shù)方程為

用蒙特卡洛法分析提高Shor算法破解RSA成功率的原理是：假設(shè)對大整數(shù)N進行M次隨機抽樣，求出每組P1,P2,并將其代入功能函數(shù)進行計算，得到M個T值.若T>0,則破解的成功率得到提升；若T≤0,則破解的成功率未得到提升.

圖2 P1和P2的部分曲線分布

表1 a在不同條件下函數(shù)周期為偶數(shù)的概率

由圖2可知：對于任意樣本N值，P1均大于P2.對隨機數(shù)a不做限定時，Shor算法成功破解RSA的概率P2不會超過50%；若限定隨機數(shù)a取非完全平方數(shù)，破解的成功率P1不會低于75%，即T>0，說明Shor算法破解RSA的成功率得到提升.

5 結(jié)束語

[1] HARDY G H,WRIGHT E M.An introduction to the theory of numbers[M].張曉堯,譯.5版.北京:人民郵電出版社,2009:58-102.

[2] 朱和貴.探析初等數(shù)論基本知識在密碼學中的應(yīng)用[J].山東工業(yè)技術(shù),2014(21):253.

[3] 李海峰,馬海云,徐燕文.現(xiàn)代密碼學原理及應(yīng)用[M].北京:國防工業(yè)出版社,2013:110-114.

[4] NAM Y S,BLUMEL R.Sealing laws for Shor′s alglorithm with a banded quantum fourier transform[J].Physica Review A,2013,87(3):032333.

[5] 彭衛(wèi)豐,孫力.SHOR量子算法的優(yōu)化及應(yīng)用研究[J].計算機應(yīng)用與軟件,2009,26(5):239-240,246.

[6] NIELSEN M A,CHUANG I L.量子計算和量子信息(一)[M].趙千川,譯.北京：清華大學出版社，2009：199-223.

[7] 王蘊,黃德才,俞攸紅.量子計算及量子算法研究進展[J].計算機系統(tǒng)應(yīng)用,2011，20(6)：228-231.

[8] 徐煒,肖智,楊道理.量子算法在大數(shù)據(jù)挖掘中的應(yīng)用前景淺析[C]∥中國信息經(jīng)濟學會學術(shù)年會暨博士生論壇論文集.廣東：中國信息經(jīng)濟學會，2013:2-7.

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

[10] GARCIA-MATA I,FRAHM K M,SPEPELYANSKY D L.Effects of imperfections for Shor′s factorization algorithm[J].Physical Review A,2007,75(5):2311.

[11] LUCERO E,BARENDS R,CHEN Y,et al.Computing prime factors with a Josephson phase qubit quantum processor[J].Nature Physics,2012,8:719-723.

[12] THOMPSON M G,POLITI A,MATTHEWS J C F,et al.Integrated waveguide circuits for optical quantum computing[J].Circuits, Device and System, IET,2010,5(2):94-102.

(責任編輯： 黃曉楠 英文審校： 吳逢鐵)

Discussion on Cracking RSA With Shor Algorithm

TU Lingying1,2， HU Yifan1,2， ZHANG Hongtao1,2， DAI Yongtao1,2， XIONG Hongmei1,2

(1. Nanoelectronics and Microsystems Technology Laboratory, Hubei University of Technology, Wuhan 430068, China; 2. School of Electrical and Electronic Engineering, Hubei University of Technology, Wuhan 430068, China)

Since the randomness of Shor algorithm could lead to low success rate in cracking RSA. By analyzing the principle of Shor algorithm, characteristics of RSA public key password system and lots of data, the view that the way for quantum functional in randomly selecting value is regular was putting forward .Verified by number theory and Monte Carlo method， the results showed that if takes a perfect square, the cycle probably can′t meet the requirements of Shor algorithm. It comes to a conclusion that take a non-perfect square can improve the success rate of Shor algorithm in cracking RSA.

Sahor algorithm; non-perfect squares; RSA algorithm; public key password system； Monte Carlo method

1000-5013(2015)06-0640-05

10.11830/ISSN.1000-5013.2015.06.0640

2015-05-24

凃玲英(1963-)，女，副教授，主要從事量子通信與量子計算、視頻監(jiān)控系統(tǒng)的研究.E-mail:947392311@qq.com.

湖北省武漢市科技局“十城千輛新動力汽車計劃”項目(2013011801010600)

TP 301.6

A