有關中國剩余定理在多個素數的RSA解密運算中的加速公式的論證以及加速效率的估算

劉 承 彬, 耿 也, 舒 奎, 高 真 香 子

( 大連工業大學 信息科學與工程學院, 遼寧 大連 116034 )

0 引 言

RSA加密算法是第一個既能用于數據加密也能用于數字簽名的算法。RSA算法基于單向陷門函數原理,依賴于大數因數分解的困難性。因此,基于大整數分解問題的RSA算法是目前實際應用最廣泛的公鑰密碼算法。

隨著科學技術的發展,為保證RSA算法有足夠的安全性,RSA算法需要的密鑰長度不斷增加,明顯降低了加密/解密的效率。出于安全性考慮,一般要求密鑰長度在1 024～2 048 bp[1]。因為運用RSA算法對數據進行加解密運算需要進行大量模冪運算,密鑰越復雜,RSA處理數據的速度越低,由于中國剩余定理對于提高模冪運算效率有顯著提升,因而與RSA一起使用。

1 使用中國剩余定理對RSA解密算法的加速公式推論

1.1 RSA算法的基本闡述[2]

步驟1采用Montgomery算法優化后的Miller Rabin算法[3]取2個互質的素數p和q,令N=pq;Φ(N)=(p-1)(q-1)。

步驟2取與Φ(N)互質的整數e,且1

步驟3加密過程:C=MemodN；解密過程:M=CdmodN。

1.2 使用中國剩余定理簡化n素數RSA解密算法時素數的選取原則

(1)每個素數都要足夠大；(2)每個素數均為強素數；(3)各個素數之差要大,差多個位以上；(4)各個素數與1求差之后新形成的各個數的最大公因子要小。

1.3 使用中國剩余定理對n素數RSA解密算法的簡化

采用Montgomery算法優化后的Miller Rabin算法,取n個互質的素數p1,p2,p3,…,pn,令N=p1p2p3…pn；Φ(N)=(p1-1)(p2-1)(p3-1)…(pn-1)。

加密過程采用原始的加密方式:取與Φ(N)互質的整數e,且1

對任意給定的數M,加密后的數C=MemodN。解密過程采用中國剩余定理優化的解密方式。對于同余方程組:

M≡Mp1modp1,M≡Mp2modp2,M≡Mp3modp3,…,M≡Mpnmodpn,模N有唯一解,解為M≡(Mp1M1y1+Mp2M2y2+Mp3M3y3+…+MpnMnyn)modN。式中,

M1=p2p3p4…pn,

M2=p1p3p4…pn,

M3=p1p2p4…pn,

?

Mk=p1p2p3…pk-1pk+1…pn,…,

Mn=p1p2p3…pn-1,

M1y1≡1modp1,M2y2≡1modp2,

M3y3≡1modp3,…,Mnyn≡1modpn。

由費馬小定理:令p為素數,對任何不能為p整除的數A,恒滿足Ap-1≡1modp,可得:Ap-2≡A-1modp,所以

modN。

由于M≡Mp1modp1,M≡Mp2modp2,…,M≡Mpnmodpn[4],所以Mp1≡Mmodp1≡(CdmodN)modp1≡Cdmodp1。

由費馬小定理推論:令p為素數,對任何不能為p整除的數A,且有n=mmod(p-1),則An≡Ammodp,可得:

Cdmodp1=Cdmod(p1-1)modp1

令dp1=dmod(p1-1),則Mp1=Cdp1modp1；其中dp1可看作采用中國剩余定理簡化后新的n個私鑰中的1個。

同理,Mp2=Cdp2modp2,…,Mpn=Cdpnmodpn；且產生新的私鑰dp2,dp3,…,dpn。

又由Cdp1modp1=(Cmodp1)dp1modp1,令Cp1=Cmodp1,即Mp1=Cp1dp1modp1；

同理可得Mp2=Cp2dp2modp2,…,Mpn=Cpndpnmodpn。

對于采用中國剩余定理簡化的RSA解密算法可分解為4個步驟執行:

步驟1計算dp1=dmod(p1-1),dp2=dmod(p2-1),…,dpn=dmod(pn-1)；

步驟2計算Cp1=Cmodp1,Cp2=Cmodp2,…,Cpn=Cmodpn；

步驟3計算Mp1=Cp1dp1modp1,Mp2=Cp2dp2modp2,…,Mpn=Cpndpnmodpn；

步驟4計算

modp1p2…pn

注:此公式僅適用于解密算法。

1.4 使用中國剩余定理對4素數和更多素數情況下的RSA解密算法的簡化程序驗證

通過比較可以發現,雖然計算的步驟增多,但是每一步需要的模冪運算大量減少,從而大大降低運算的復雜程度。

下面分別對4～6個素數的情況通過計算機程序來驗證該公式的正確性,如圖1～3所示。

圖1 4個素數時基于中國剩余定理加速后采用C++實現的結果

圖2 5個素數時基于中國剩余定理加速后采用C++實現的結果

圖3 6個素數時基于中國剩余定理加速后采用C++實現的結果

2 采用中國剩余定理對RSA解密算法加速時的效率估算

2.1 使用中國剩余定理對n素數RSA解密算法的簡化時的效率提升的公式推導

采用Montgomery算法優化后的Miller Rabin算法取n個互質的素數,假設每個素數的二進制長度均為k/nbp,則對于N和d的二進制長度我們可認為是kbp。

沒有采用中國剩余定理加速的RSA解密算法M=CdmodN,實際操作可估算為k3次位操作(其中忽略2進制字節長度相差過大的數的計算)。

modp1p2…pn

其中主要的計算均集中在Mp1,Mp2,Mp3,…,Mpn,以及(p2p3p4…pn)p1-1,(p1p3p4…pn)p2-1,(p1p2p4…pn)p3-1,…,(p1p2p3…pn-1)pn-1中,由Mp1=Cp1dp1modp1,Cp1=Cmodp1,dp1=dmod(p1-1)可估算Mp1(p2p3p4…pn)p1-1共采用(n-1)2k3/n3+k3/n3次位操作[5],即(n2-2n+2)k3/n3次位操作(其中忽略2進制字節長度相差過大的數的計算)。若采用并行算法同時計算,則可得計算效率為原先n3/(n2-2n+2)倍。

2.2 使用中國剩余定理對多素數時RSA解密算法的簡化時的效率的提升的驗證

4個素數時的效率提升:Mp(qrs)p-1的主要操作為10k3/64次位操作。采用并行算法后效率提升64/10倍,符合公式的計算。

5個素數時的效率提升:Mp(qrst)p-1的主要操作為17k3/125次位操作。采用并行算法后效率提升125/17倍,符合公式的計算。

6個素數時的效率提升:Mp(qrstu)p-1的主要操作為26k3/216次位操作。采用并行算法后效率提升216/26倍,符合公式的計算。

由式n3/n2-2n+2可知,隨著n的增加,采用中國剩余定理的加速效果越明顯。

3 結 論

通過選擇多個素數的RSA算法,首先可以在選擇大素數時適當減小素數位數,從而在根本上減少計算量。在解密過程中,采用中國剩余定理將私鑰d轉換成多個dx的運算,進一步減少d的位數,再一次減少計算量。

通過分析中國剩余定理, 提出了適合于計算多素數RSA算法中數據解密部分的計算公式,并采用并行方式來處理, 簡化了模冪運算復雜的解密過程,顯著提高了數據處理速度。由于“組成各種長度的模究竟多少個素數才合適”[6]這個論題仍在研究中,所以同時給出了采用中國剩余定理加速后的效率提升的估算公式。結合素數個數增加時的計算復雜度和采用中國剩余定理加速后的效率提升可確定出素數個數的范圍。本文的不足之處在于只針對了解密算法的研究,沒有從理論上證實破譯RSA的難度和大數分解難度相等價,在以后的研究中將作為主要研究方向。

[1] 饒進平,馮國登. 一種高效率的RSA模冪算法的研究[J].計算機工程與應用, 2003(9):76-77, 121.

[2] ABOUD S J, AL-FAYOUMI M A, Al-FAYOUMI M. An efficient RSA public key encryption scheme[C]. Washington DC:Fifth International Conference on Information Technology: New Generations, 2008:127-130.

[3] 葉建龍. RSA加密中大素數的生成方法及其改進[J]. 廊坊師范學院學報:自然科學版, 2010, 10(2):55-57.

[4] 徐進. 三素數RSA算法的快速實現[J]. 計算機工程與應用, 2006, 42(11):57-58.

[5] 施月玲,夏濤,丁宏. 利用中國剩余定理改進大數模平方計算研究[J]. 杭州電子科技大學學報, 2007, 27(1):42-45.

[6] BURNETT S, PAINE S. RSA security′s official guide to cryptography[M]. New York: McGraw-Hill Education, 2001:89-96.