李云飛 劉菊琨 柳 青(云南財(cái)經(jīng)大學(xué)研究生部 云南 昆明 650)(云南中醫(yī)學(xué)院國(guó)際交流中心 云南 昆明 650500)(云南大學(xué)軟件學(xué)院 云南 昆明 65009)

0 引 言

由于RSA密碼算法[1]解密過程的大數(shù)模冪操作計(jì)算會(huì)使用大量計(jì)算資源，RSA密碼算法的性能受到了一定程度的影響。所以多種加快RSA算法解密速度的算法被提出。其中有通過減小模數(shù)及模冪指數(shù)位數(shù)提升運(yùn)算性能的多素?cái)?shù)RSA[2]算法。也有通過在加密過程中完成解密運(yùn)算轉(zhuǎn)移的負(fù)載來加快RSA算法解密速度的算法：RSA-S1系統(tǒng)[3]和RSA-S2[3]等。文獻(xiàn)[4-5]中的EAMRSA算法通過結(jié)合Multi-Prime和RSA-S2技術(shù)加快了算法的解密速度，但文章僅從密鑰搜索域?qū)λ惴ㄟM(jìn)行安全性分析，并未使用連分?jǐn)?shù)和格規(guī)約分析方法。

但以上改進(jìn)算法均通過減小指數(shù)d和大數(shù)模的位數(shù)來提升算法解密操作的速度。1999 年, Boneh 和Durfee[6]在Coppersmith[7]的基礎(chǔ)上把位數(shù)較少的密鑰d的邊界值提高到d

本文使用Multi-Prime和RSA-S1負(fù)載轉(zhuǎn)移技術(shù)使得RSA密碼算法解密過程的速度得到了較快提高。為了確保算法的安全性，本文使用May等求取小根的辦法，對(duì)算法進(jìn)行格規(guī)約分析。經(jīng)分析當(dāng)私鑰指數(shù)個(gè)數(shù)為2，大數(shù)模N素?cái)?shù)個(gè)數(shù)為3時(shí)，該改進(jìn)算法能抵擋格攻擊。通過分析及實(shí)驗(yàn)測(cè)試，得到改進(jìn)算法在輸入高安全參數(shù)值時(shí)，RSA算法解密性能提升較大。實(shí)驗(yàn)測(cè)試數(shù)據(jù)顯示與標(biāo)準(zhǔn)RSA算法(解密過程使用中國(guó)剩余定理)對(duì)比，該算法解密時(shí)平均加速比是5.68。

1 EAMS1RSA算法

1) 密鑰產(chǎn)生算法:算法輸入?yún)?shù)為n、b、k、c，公鑰和私鑰將在該算法中求出，計(jì)算步驟如下：

(2) 求出和φ(N)彼此互素的公鑰指數(shù)e，并運(yùn)算得到d=e-1modφ(N)。

(3) 求出d=d1·e1+…+di·ei+…+dk·ekmodφ(N)，1≤i≤k。變量di和ei(1≤i≤k)都是二進(jìn)制向量，其中每一個(gè)di和ei分別是c位隨機(jī)生成數(shù)和|pi-1|位隨機(jī)生成數(shù)。得到公鑰和私鑰分別是：

公鑰：和 私鑰：。

2) 加密算法：

(1) 明文數(shù)據(jù)M(M∈ZN)和加密指數(shù)e作為輸入，通過計(jì)算C=MemodN得到密文數(shù)據(jù)C。

(2) 密文數(shù)據(jù)C作為輸入，求出密文向量Z=(z1,…,zk)，zi值(1≤i≤k)通過計(jì)算zi=CeimodN得到，將向量發(fā)送到解密端。

3) 解密算法：解密端輸入向量數(shù)據(jù)Z。解密求解出明文m，具體過程如下：

(1) 通過Cj=zimodpj,求出Cj，1≤j≤b，1≤i≤k,zi包含在密文向量Z中。

(4) 獲取明文m通過以下計(jì)算：m=m1×…×mk=Ce1·d1+…+ek·dkmodN，1≤i≤k，mi=(zi)di=Cei·dimodN。

根據(jù)文獻(xiàn)[4]，RSA算法的1 024位和1 536位的模長(zhǎng)安全強(qiáng)度分別對(duì)應(yīng)于對(duì)稱密碼系統(tǒng)中密鑰強(qiáng)度為72位和80位[3-4]。所以，在本文以下的數(shù)據(jù)實(shí)驗(yàn)中，從1 024位到3 072位的安全強(qiáng)度范圍內(nèi)，參數(shù)k和c分別取值為2和128，參數(shù)b取值上限值為3。以上參數(shù)值的選取，確保了k×c數(shù)值的窮舉空較大，確保了EAMS1RSA算法的小位數(shù)私鑰的安全性。

2 EAMS1RSA算法格安全性分析

2.1 EAMS1RSA算法連分?jǐn)?shù)攻擊分析

連分?jǐn)?shù)是初等數(shù)論中的基本內(nèi)容。α的連分?jǐn)?shù)是形式如下的表達(dá)式[13]，為方便起見，記作α=[a0,a1,a2,…，aN]，其中a0是非負(fù)整數(shù)，a1,a2,…，aN是正整數(shù)：

對(duì)任意有理數(shù)α=b/a，求α的有限連分?jǐn)?shù)展開的計(jì)算復(fù)雜度實(shí)際上與求a和b的最大公因數(shù)的歐幾里德算法一致，可以在多項(xiàng)式時(shí)間內(nèi)求解。求α的N階漸近分?jǐn)?shù)的計(jì)算復(fù)雜度實(shí)際上與廣義歐幾里德算法一致，因而也是一個(gè)多項(xiàng)式時(shí)間算法[12]。事實(shí)上，求α的漸近分?jǐn)?shù)的過程實(shí)質(zhì)上就是求解分母逐漸增大的能夠很好地逼近α的一組分?jǐn)?shù)的過程。

定理1[13]令p、q是整數(shù)，α是一個(gè)實(shí)數(shù)。如果|p/q-α|<1/(2q2)，那么p/q是α的漸近連分?jǐn)?shù)。

EAMS1RSA算法中公鑰e和私鑰d滿足關(guān)系：e·d=1 modφ(N)，則必存在某個(gè)整數(shù)k使得ed-k·φ(N)=1。EAMS1RSA算法的大數(shù)模N和素?cái)?shù)pi，1≤i≤b，需要滿足以下兩個(gè)假設(shè)[14]：

(1) 設(shè)大數(shù)模N的b個(gè)素?cái)?shù)因子滿足關(guān)系:pi

(2)b個(gè)素?cái)?shù)因子還需要滿足以下關(guān)系：

4

以上兩個(gè)假設(shè)確保算法得到的素?cái)?shù)因子是平衡素?cái)?shù)因子，從而來抵御橢圓曲線方法[2]的快速因式分解方法的攻擊。

針對(duì)擁有b個(gè)素?cái)?shù)因子的大數(shù)模N，可以推出歐拉函數(shù)φ(N)的值為[14]：

N-φ(N)<(2b-1)N1-1/b

并且可進(jìn)一步得到定理2。

證明：大數(shù)模N的b個(gè)素?cái)?shù)因子滿足關(guān)系pi

N-φ(N)<(2b-1)N1-1/b

設(shè)ed=1+kφ(N)對(duì)某個(gè)整數(shù)k≥1，可推出kN-ed=k(N-φ(N))-1。

2.2 EAMS1RSA算法格攻擊分析

在RSA算法中存在某個(gè)未知整數(shù)k使得公鑰和私鑰滿足等式ed-1=k(N-(p+q-1))?？梢允褂肅oppersmith技術(shù)來求解多項(xiàng)式f(x,y,z)=ex-yN+yz-1的整數(shù)根(d,k,p+q-1)，從而得到大數(shù)模N的因子。與此同時(shí)，也可以通過求解多項(xiàng)式fe(y,z)=y(N-z)+1mode的模數(shù)根(k,p+q-1)來得到N的因子。所以有許多工具被用來解決尋找多項(xiàng)式模數(shù)根和整數(shù)小根的問題。

引理1[8，11]LLL算法將格L作為輸入，其中令格L通過(u1,u2,…,uw)得到，LLL算法產(chǎn)歸約向量集合(b1,b2,…,bw)滿足。

引理2[11]設(shè)L是向量集(u1,u2,…,uw)所生成的格，(b1,b2,…,bw)是格L的LLL歸約基，那么‖b1‖≤‖b2‖≤…≤‖bi≤2w(w-1)/4(w+1-i)det(L)1/w+1-i。

本部分將對(duì)EAMS1RSA(k=2和b=3，2個(gè)小私鑰)進(jìn)行安全性分析，此時(shí)EAMS1RSA算法的私鑰d可表示為：d=d1e1+d2e2modφ(N)。攻擊的成功是假設(shè)1成立的前提下：

假設(shè)1假設(shè)一個(gè)包含n個(gè)變?cè)亩囗?xiàng)式集合{f1,f2,…,fi}的在整數(shù)域上的根為(x1,0,x2,0,…,xn,0),其中i≥n。則以結(jié)式方式對(duì)以上多項(xiàng)式進(jìn)行求解，能計(jì)算得到相應(yīng)的整數(shù)根。

定理3EAMS1RSA的d1和d2私鑰指數(shù)，對(duì)應(yīng)公鑰指數(shù)e、e1、e2，大數(shù)模N=pqr。令d1，d2

證明：根據(jù)EAMS1RSA密碼算法存在關(guān)系式：

d=d1e1+d2e2modφ(N)和ed=1modφ(N)

由以上兩式可以推出：

e×e1×d1+e×e2×d2=1modφ(N)

(1)

由式(1)可進(jìn)一步推出：

ee1d1+ee2d2=1+k(N+r)

(2)

式中：r=φ(N)-N。由式(2)可得：

ee1d1+ee2d2-1-k(N+r)=0

(3)

安全分析的目的是得到解為k、r、d1、d2的多項(xiàng)式(已知d1

f(x1,x2,x3,x4)=-x1N-x1x2+ee1x3+ee2x4-1

通過S、M以及m值，通過忽略較小的項(xiàng)，求出：

代入X1、X2、X3、X4的值，可得到以下不等式：

3 理論及驗(yàn)測(cè)試結(jié)果

EAMS1RSA算法相對(duì)于標(biāo)準(zhǔn)RSA的理論解密過程的加速比約為：(b·n)/(4·k·c)。

改進(jìn)算法和相應(yīng)測(cè)試算法是基于OpenSSL實(shí)現(xiàn)。平臺(tái)為：Windows XP操作系統(tǒng)，Intel Pentium雙核1.73 GHz處理器，內(nèi)存1 GB。為了便于描述EAMRSA算法，本文將參數(shù)取值b等于3、k等于2和c等于128位的EAMS1RSA改進(jìn)算法稱為EA1M3SRSA算法。

表1顯示了RSA改進(jìn)算法不同位數(shù)范圍內(nèi)相對(duì)于標(biāo)準(zhǔn)RSA算法的解密加速比情況。從表1中可以看出EA1M3SRSA算法解密時(shí)獲得的加速比最高。

表1 改進(jìn)RSA解密加速比

4 結(jié) 語

本文運(yùn)用多素?cái)?shù)以及解密轉(zhuǎn)移負(fù)載至加密端的方法提出了解密性能提升且可并行的改進(jìn)RSA算法。同時(shí)本文使用連分?jǐn)?shù)和格歸約對(duì)改進(jìn)算法進(jìn)行分析，得到該算法相對(duì)于標(biāo)準(zhǔn)RSA算法，也具有較好的安全性。接下來研究的內(nèi)容是將該算法應(yīng)用到云安全中。

[1] Rivest R, Shamir A, Adleman L M. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the Acm, 1978, 26(2):96- 99.

[2] Dan B, Shacham H. Fast variants of RSA[J]. Cryptobytes, 2002, 5:1- 9.

[3] Castelluccia C,Mykletun E,Tsudik G.Improving secure server performance by re-balancing SSL/TLS handshakes[C]// ACM Symposium on Information, Computer and Communications Security. ACM, 2006:26- 34.

[4] 李云飛,柳青,郝林,等.一種有效的RSA 算法改進(jìn)方案的研究[J]. 計(jì)算機(jī)應(yīng)用，2010，30(9): 2393- 2397.

[5] 李云飛.RSA密碼算法的研究與實(shí)現(xiàn)[D].云南：云南大學(xué)信息學(xué)院，2011.

[6] Boneh D, Durfee G. Cryptanalysis of RSA with private key d less than N 0.292[J]. Information Theory IEEE Transactions on, 1999, 46(4):1339- 1349.

[7] Coppersmith D. Small solutions to polynomial equations and low exponent RSA vulnerabilities [J].Journal of Cryptology, 1997, 10(4):233- 260.

[8] Zheng M, Honggang H U, Wang Z. Generalized cryptanalysis of RSA with small public exponent[J]. Science China(Information Sciences), 2016, 59(3): 97- 106.

[9] Sarkar S, Maitra S. Cryptanalysis of RSA with two decryption exponents[J]. Information Processing Letters, 2010, 110(5):178- 181.

[10] 李云飛,柳青,李彤，等.對(duì)一種改進(jìn)RSA算法的密碼分析[J]. 應(yīng)用科學(xué)學(xué)報(bào)，2013，31(6): 655- 660.

[11] Howgrave-Graham N. Finding Small Roots of Univariate Modular Equations Revisited[C]// IMA International Conference on Cryptography and Coding. Springer, Berlin, Heidelberg, 1997:131- 142.

[12] Wiener M J.Cryptanalysis of short RSA secret exponents[J].Information Theory IEEE Transactions on,1990,36(3):553- 558.

[13] 韓立東, 王小云, 許光午, 等. RSA密碼系統(tǒng)小CRT解密指數(shù)的攻擊分析[J].中國(guó)科學(xué)：信息科學(xué)，2011,41(2):173- 180.

[14] Hinek M J. Cryptanalysis of RSA and Its Variants[M]. Chapman & Hall, 2009.