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

0 引 言

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

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

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

1 EAMS1RSA算法

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

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

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

公鑰：和 私鑰：。

2) 加密算法：

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

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

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

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

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

根據(jù)文獻[4]，RSA算法的1 024位和1 536位的模長安全強度分別對應(yīng)于對稱密碼系統(tǒng)中密鑰強度為72位和80位[3-4]。所以，在本文以下的數(shù)據(jù)實驗中，從1 024位到3 072位的安全強度范圍內(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ù)：

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

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

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

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

(2)b個素數(shù)因子還需要滿足以下關(guān)系：

4

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

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

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

并且可進一步得到定理2。

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

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

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

2.2 EAMS1RSA算法格攻擊分析

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

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

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

定理3EAMS1RSA的d1和d2私鑰指數(shù)，對應(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)可進一步推出：

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

(2)

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

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

(3)

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

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

通過S、M以及m值，通過忽略較小的項，求出：

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

3 理論及驗測試結(jié)果

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

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

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

表1 改進RSA解密加速比

4 結(jié) 語

本文運用多素數(shù)以及解密轉(zhuǎn)移負(fù)載至加密端的方法提出了解密性能提升且可并行的改進RSA算法。同時本文使用連分?jǐn)?shù)和格歸約對改進算法進行分析，得到該算法相對于標(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]. 計算機應(yīng)用，2010，30(9): 2393- 2397.

[5] 李云飛.RSA密碼算法的研究與實現(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] 李云飛,柳青,李彤，等.對一種改進RSA算法的密碼分析[J]. 應(yīng)用科學(xué)學(xué)報，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].中國科學(xué)：信息科學(xué)，2011,41(2):173- 180.

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