改進RSA算法的安全性分析

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

0 引 言

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

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

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

1 EAMS1RSA算法

1) 密鑰產生算法:算法輸入參數為n、b、k、c，公鑰和私鑰將在該算法中求出，計算步驟如下：

(2) 求出和φ(N)彼此互素的公鑰指數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位隨機生成數和|pi-1|位隨機生成數。得到公鑰和私鑰分別是：

公鑰：和 私鑰：。

2) 加密算法：

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

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

3) 解密算法：解密端輸入向量數據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。

根據文獻[4]，RSA算法的1 024位和1 536位的模長安全強度分別對應于對稱密碼系統中密鑰強度為72位和80位[3-4]。所以，在本文以下的數據實驗中，從1 024位到3 072位的安全強度范圍內，參數k和c分別取值為2和128，參數b取值上限值為3。以上參數值的選取，確保了k×c數值的窮舉空較大，確保了EAMS1RSA算法的小位數私鑰的安全性。

2 EAMS1RSA算法格安全性分析

2.1 EAMS1RSA算法連分數攻擊分析

連分數是初等數論中的基本內容。α的連分數是形式如下的表達式[13]，為方便起見，記作α=[a0,a1,a2,…，aN]，其中a0是非負整數，a1,a2,…，aN是正整數：

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

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

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

(1) 設大數模N的b個素數因子滿足關系:pi

(2)b個素數因子還需要滿足以下關系：

4

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

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

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

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

證明：大數模N的b個素數因子滿足關系pi

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

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

2.2 EAMS1RSA算法格攻擊分析

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

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

引理2[11]設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)。攻擊的成功是假設1成立的前提下：

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

定理3EAMS1RSA的d1和d2私鑰指數，對應公鑰指數e、e1、e2，大數模N=pqr。令d1，d2

證明：根據EAMS1RSA密碼算法存在關系式：

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 理論及驗測試結果

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

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

表1顯示了RSA改進算法不同位數范圍內相對于標準RSA算法的解密加速比情況。從表1中可以看出EA1M3SRSA算法解密時獲得的加速比最高。

表1 改進RSA解密加速比

4 結 語

本文運用多素數以及解密轉移負載至加密端的方法提出了解密性能提升且可并行的改進RSA算法。同時本文使用連分數和格歸約對改進算法進行分析，得到該算法相對于標準RSA算法，也具有較好的安全性。接下來研究的內容是將該算法應用到云安全中。

[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]. 計算機應用，2010，30(9): 2393- 2397.

[5] 李云飛.RSA密碼算法的研究與實現[D].云南：云南大學信息學院，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]. 應用科學學報，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密碼系統小CRT解密指數的攻擊分析[J].中國科學：信息科學，2011,41(2):173- 180.

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