有關(guān)中國剩余定理在多個(gè)素?cái)?shù)的RSA解密運(yùn)算中的加速公式的論證以及加速效率的估算

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

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

0 引 言

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

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

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

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

步驟1采用Montgomery算法優(yōu)化后的Miller Rabin算法[3]取2個(gè)互質(zhì)的素?cái)?shù)p和q,令N=pq;Φ(N)=(p-1)(q-1)。

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

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

1.2 使用中國剩余定理簡化n素?cái)?shù)RSA解密算法時(shí)素?cái)?shù)的選取原則

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

1.3 使用中國剩余定理對n素?cái)?shù)RSA解密算法的簡化

采用Montgomery算法優(yōu)化后的Miller Rabin算法,取n個(gè)互質(zhì)的素?cái)?shù)p1,p2,p3,…,pn,令N=p1p2p3…pn；Φ(N)=(p1-1)(p2-1)(p3-1)…(pn-1)。

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

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

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。

由費(fèi)馬小定理:令p為素?cái)?shù),對任何不能為p整除的數(shù)A,恒滿足Ap-1≡1modp,可得:Ap-2≡A-1modp,所以

modN。

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

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

Cdmodp1=Cdmod(p1-1)modp1

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

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

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

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

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

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

步驟2計(jì)算Cp1=Cmodp1,Cp2=Cmodp2,…,Cpn=Cmodpn；

步驟3計(jì)算Mp1=Cp1dp1modp1,Mp2=Cp2dp2modp2,…,Mpn=Cpndpnmodpn；

步驟4計(jì)算

modp1p2…pn

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

1.4 使用中國剩余定理對4素?cái)?shù)和更多素?cái)?shù)情況下的RSA解密算法的簡化程序驗(yàn)證

通過比較可以發(fā)現(xiàn),雖然計(jì)算的步驟增多,但是每一步需要的模冪運(yùn)算大量減少,從而大大降低運(yùn)算的復(fù)雜程度。

下面分別對4～6個(gè)素?cái)?shù)的情況通過計(jì)算機(jī)程序來驗(yàn)證該公式的正確性,如圖1～3所示。

圖1 4個(gè)素?cái)?shù)時(shí)基于中國剩余定理加速后采用C++實(shí)現(xiàn)的結(jié)果

圖2 5個(gè)素?cái)?shù)時(shí)基于中國剩余定理加速后采用C++實(shí)現(xiàn)的結(jié)果

圖3 6個(gè)素?cái)?shù)時(shí)基于中國剩余定理加速后采用C++實(shí)現(xiàn)的結(jié)果

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

2.1 使用中國剩余定理對n素?cái)?shù)RSA解密算法的簡化時(shí)的效率提升的公式推導(dǎo)

采用Montgomery算法優(yōu)化后的Miller Rabin算法取n個(gè)互質(zhì)的素?cái)?shù),假設(shè)每個(gè)素?cái)?shù)的二進(jìn)制長度均為k/nbp,則對于N和d的二進(jìn)制長度我們可認(rèn)為是kbp。

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

modp1p2…pn

其中主要的計(jì)算均集中在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進(jìn)制字節(jié)長度相差過大的數(shù)的計(jì)算)。若采用并行算法同時(shí)計(jì)算,則可得計(jì)算效率為原先n3/(n2-2n+2)倍。

2.2 使用中國剩余定理對多素?cái)?shù)時(shí)RSA解密算法的簡化時(shí)的效率的提升的驗(yàn)證

4個(gè)素?cái)?shù)時(shí)的效率提升:Mp(qrs)p-1的主要操作為10k3/64次位操作。采用并行算法后效率提升64/10倍,符合公式的計(jì)算。

5個(gè)素?cái)?shù)時(shí)的效率提升:Mp(qrst)p-1的主要操作為17k3/125次位操作。采用并行算法后效率提升125/17倍,符合公式的計(jì)算。

6個(gè)素?cái)?shù)時(shí)的效率提升:Mp(qrstu)p-1的主要操作為26k3/216次位操作。采用并行算法后效率提升216/26倍,符合公式的計(jì)算。

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

3 結(jié) 論

通過選擇多個(gè)素?cái)?shù)的RSA算法,首先可以在選擇大素?cái)?shù)時(shí)適當(dāng)減小素?cái)?shù)位數(shù),從而在根本上減少計(jì)算量。在解密過程中,采用中國剩余定理將私鑰d轉(zhuǎn)換成多個(gè)dx的運(yùn)算,進(jìn)一步減少d的位數(shù),再一次減少計(jì)算量。

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

[1] 饒進(jìn)平,馮國登. 一種高效率的RSA模冪算法的研究[J].計(jì)算機(jī)工程與應(yīng)用, 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加密中大素?cái)?shù)的生成方法及其改進(jìn)[J]. 廊坊師范學(xué)院學(xué)報(bào):自然科學(xué)版, 2010, 10(2):55-57.

[4] 徐進(jìn). 三素?cái)?shù)RSA算法的快速實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程與應(yīng)用, 2006, 42(11):57-58.

[5] 施月玲,夏濤,丁宏. 利用中國剩余定理改進(jìn)大數(shù)模平方計(jì)算研究[J]. 杭州電子科技大學(xué)學(xué)報(bào), 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.