基于數(shù)論的RSA算法研究

余亞輝

【摘要】基于數(shù)論的公鑰密碼體制的RSA算法是最完善的加密算法. 通過(guò)RSA算法基本原理可以將大數(shù)的冪模運(yùn)算轉(zhuǎn)換為小數(shù)冪模運(yùn)算，并對(duì)一些模塊進(jìn)行適當(dāng)?shù)母倪M(jìn)，從而提出快速求解加密和解密的計(jì)算方法，提高RSA的運(yùn)算速度。

【關(guān)鍵詞】公鑰密碼算法RSA算法冪模運(yùn)算

【基金項(xiàng)目】河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目資助計(jì)劃（14A110016）。

【中圖分類號(hào)】O29 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】2095-3089（2014）05-0137-02

1.前言

RSA公鑰密碼算法是美國(guó)麻省理工學(xué)院的三位學(xué)者Rivest、Shamir和Adleman在1978年提出的[1]，既可以用于加密，又可用于數(shù)字簽名，它安全，易懂，易實(shí)現(xiàn)，是目前廣泛應(yīng)用的一種密碼算法。其理論基礎(chǔ)是數(shù)論中的大合數(shù)因子分解困難性，即求兩個(gè)大素?cái)?shù)之積，在計(jì)算機(jī)上很容易實(shí)現(xiàn)。但是要將一個(gè)大合數(shù)分解成兩個(gè)素?cái)?shù)的乘積，在計(jì)算機(jī)上很難實(shí)現(xiàn)。 由于RSA算法采用的冪模運(yùn)算耗時(shí)太多，大量的數(shù)據(jù)處理時(shí)速度很慢，所以提高RSA的運(yùn)算效率便成為非常重要的研究?jī)?nèi)容[4]。

2.基本定義與定理

定義1：若a,b,c都是整數(shù)，且a|b，a|c，那么a就是b和c的公因數(shù)。在所有公因數(shù)中最大一個(gè)，稱為最大公因數(shù)，并記為gcd(b,c)[3]。

定義2：若a和b的最大公因數(shù)是1，即gcd(b,c)=1，則稱a和b互素[2]。

定義3：設(shè)a，b∈Z,n≠0如果n|(a-b)，則稱a和b模n同余，記為a≡b(modn)，整數(shù)n稱為模數(shù)[3]。

定義4：元素x∈Zn有乘法逆元x-1，當(dāng)且僅當(dāng)x和n的最大公因子是1，即gcd(x,n=1)，即x和n互質(zhì)。如果x的逆元存在，必定滿足x×x-1modn=1[3]。

定理1：若a和n互素，則aφ(n)=1modn，稱為歐拉定理（簡(jiǎn)稱Euler定理）。

證明：設(shè)Zn={a1,a2,...aφ(n)}是模n的一個(gè)群集，由于gcd(a,n)=1，根據(jù)同余性質(zhì)ab=a1b1(modn)，故aZn={aa1,aa2,...aaφ(n)}也是模n的一個(gè)群集，即■a1≡■(aa1)(modn)。因此aφ(n)≡1modn。

定理2：若是p素?cái)?shù)，a是正整數(shù)且gcd(a,p)=1則ap-1≡1modp，稱為費(fèi)爾瑪定理。（簡(jiǎn)稱Fermat定理）[1]。

定理3：設(shè)n是一正整數(shù)，小于n且與n互質(zhì)的正整數(shù)的個(gè)數(shù)稱為n的歐拉函數(shù)，記為φ(n)，若n是素?cái)?shù)，則顯然有φ(n)=n-1[1]。

推論1：若n是兩個(gè)素?cái)?shù)p和q的乘積，則φ(n)=φ(p)×φ(q)=(p-1)×(q-1)

推論2：對(duì)任意非負(fù)整數(shù)a和正整數(shù)b有g(shù)cd(a,b)=gcd(b,amodb)。

證明：因?yàn)閎是正整數(shù)，所以可將a表示為a=kb+r≡rmodb，amodb=r，其中為k一整數(shù)，所以amodb=a-kb，設(shè)d是a，b的公因子，即d|a，d|b，所以d|kb，由d|a和d|kb得d|(amodb)，因此a是b和amodb的公因子。所以得出a，b的公因子集合與b，amodb的公因子集合相等，兩個(gè)集合的最大值也相等。

3.RSA公鑰算法描述

3.1密鑰選擇

RSA加密算法的密鑰選擇方法是該算法的核心，RSA密鑰的選擇和生成方法保證了RSA公鑰加密算法的安全性。先選擇兩個(gè)素?cái)?shù)p和q。這兩個(gè)素?cái)?shù)的乘積就是RSA密鑰中的正整數(shù)n，即n=p×q，如果p和q足夠大，那么乘積n也就足夠大，如再分解p和q困難性極大，這樣就可以滿足了公鑰密碼系統(tǒng)的要求，根據(jù)歐拉函數(shù)計(jì)算出φ(n)=(p-1)(q-1)。然后，隨機(jī)選取整數(shù)e，滿足1＜e＜φ(n)，并且gcd(e,φ(n))=1，作為加密密鑰。最后求出d=e-1modφ(n)，作為解密密鑰。則(e,n)為公鑰，d為私鑰，p和q為秘密參數(shù)，需要做保密處理。

3.2加密運(yùn)算

加密消息時(shí)，先將它分成比n小的數(shù)據(jù)分組，采用二進(jìn)制數(shù)，選取小于n的2的最大次冪，也就是說(shuō)，如果p和q為200位素?cái)?shù)，那么n將400有位，每個(gè)消息分組mi小于400位長(zhǎng),加密后的密文將由相同長(zhǎng)度的分組組成ci， 加密公式為c=memodn 如果需要對(duì)密文c進(jìn)行解密，則只需要c對(duì)進(jìn)行d次乘法運(yùn)算，然后再對(duì)乘積取n的模，得到明文m。

3.3解密運(yùn)算

解密公式為m=cdmodn，因?yàn)閐=e-1modφ(n)，等式兩邊同乘以e將等式轉(zhuǎn)化為d×e=1modφ(n)。根據(jù)模運(yùn)算性質(zhì)可知d×e=kφ(n)+1，其中k是一個(gè)大于等于的整數(shù)。根據(jù)加密公式和模運(yùn)算性質(zhì)可知cdmodn=(me)dmodn=mkφ(n)+1modn，利用指數(shù)運(yùn)算性質(zhì)m×mkφ(n)modn=m×1modn=m。

3.4 計(jì)算問(wèn)題

通過(guò)分析RSA算法的求解過(guò)程，可知RSA通過(guò)乘法與除法加以實(shí)現(xiàn)的。可想而知，RSA算法將執(zhí)行大量的乘除法運(yùn)算，從而導(dǎo)致RSA算法的加密與解密速度十分慢[6]。因此，大整數(shù)的乘除法成為影響RSA算法速度的重要因素。利用模運(yùn)算的性質(zhì)：(a×b)modn+[(amodn)×(bmodn)]modn可以大大減少中間運(yùn)算環(huán)節(jié)，提高運(yùn)算速度。例如求am，其中a和m是正整數(shù)， m表示為二進(jìn)制形式bk,bk-1,bk-2，…b0即m=bk2k+bk-12k-1+…+b12+b0。

4.RSA算法的安全性分析

4.1歐幾里得(Euclid)算法[2]

歐幾里得算法是基于推論2作為求兩個(gè)正整數(shù)的最大公因子的簡(jiǎn)化過(guò)程，是數(shù)論中的一個(gè)基本算法理論。當(dāng)兩個(gè)正整數(shù)互素時(shí)，可以求出其中一個(gè)數(shù)關(guān)于另一個(gè)數(shù)的乘法逆元。設(shè)輸入兩個(gè)正整數(shù)為b，a并設(shè)a＞b. ①x←b；y←a；②ifY=0then returnX=gcd(b,a)；③R=XmodY；④X=Y；⑤Y=R；⑥goto

4.2由n破譯p和q

RSA算法安全性是建立在大數(shù)的因數(shù)分解基礎(chǔ)上，下面解決大數(shù)的分解。若n=p×q被因子分解，則RSA便被攻破，因?yàn)樵趐和q已知的情況下，則利用歐拉函數(shù)可以解出φ(n)=(p-1)×(q-1），再利用歐幾里得算法求出以φ(n)為模的公鑰的e乘逆元d，就可以破譯出RSA的秘密私鑰。

若n無(wú)法分解時(shí)，如果破譯者知道φ(n)的值也能夠進(jìn)行破譯。已知n=p×q，φ(n)=(p-1)(q-1）=n-p-q+1，p+q=n-φ(n)+1，利用配方法得(p+q)2-4n=(p+q)2-4p×q=(p-q)2，即p-q=■聯(lián)立方程組(p+q)和(p-q)可得p=■，q=■ ,d也可以很容易地得到。也就是說(shuō)，如果能夠以一種可行的方法直接得到φ(n)，破譯者就可以對(duì)其進(jìn)行破譯。

4.3 合理選定參數(shù)

在設(shè)計(jì)RSA算法時(shí)，應(yīng)使分解n=p×q的上不可行，對(duì)p和q的主要限制是：第一，p和q足夠大，這樣可以基本保證不會(huì)在有效時(shí)間內(nèi)被破譯者破譯。 第二：差值|p-q|不宜太小，最好與p，q數(shù)位接近，如果p和q的數(shù)值相當(dāng)接近，則(p+q)≈2■，并且■(p-q)是一個(gè)相當(dāng)小的數(shù)，因此等式■■-n=■■等式右邊為平方數(shù)，因此可進(jìn)行因子分解。第三：d=gcd(p-1,q-1)應(yīng)盡量小，這樣可以減小將n因數(shù)分解的可能性。第四：p-1與q-1都應(yīng)該至少含有一個(gè)大素?cái)?shù)因子，p+1與q-1也至少含有一個(gè)大素?cái)?shù)因子，否則就可能利用重復(fù)加密攻擊的方法求出n的真因數(shù)。

4.4參數(shù)e和d選擇原則

在選好p和q后，要選取滿足gcd(e,φ(n))的e值是很容易的，因?yàn)閮蓚€(gè)隨機(jī)數(shù)互素的概率為0.6，若采用小的e，可加快加密的速度，但e太小時(shí)易遭加密指數(shù)的攻擊。 這是因?yàn)榈谝唬寒?dāng)e過(guò)小時(shí)，對(duì)小的m，可能出現(xiàn)的me＜n情況，此時(shí)c=memodn=me即未取模，由c直接開e次方就可求出明文m。 第二：加密指數(shù)的攻擊，令網(wǎng)中有3個(gè)用戶為加快速度，均選用e=3，而有不同的模n1,n2,n3，一般情況下其模n1,n2,n3是互素，否則可求出構(gòu)成n1,n2,n3的兩個(gè)因子p和q中的1個(gè)，進(jìn)而導(dǎo)致解密密鑰被破解。 若有1用戶要將明文n傳給這3個(gè)用戶，其密文分別為：c1=m3modn1，c2=m3modn2,c3=modn3 ，令設(shè)c=m3mod(n1×n2×n3)利用中國(guó)剩余定理可以求出c，故c=m3,m=■即失密。

5.結(jié)語(yǔ)

RSA公鑰密碼算法是迄今為止在求解密碼問(wèn)題中最為成熟理論之一，RSA的基礎(chǔ)是數(shù)論的歐拉定理，它的安全性依賴于大數(shù)的因數(shù)分解困難性。RSA算法不僅可用于加密/解密,還可以運(yùn)于數(shù)字簽名，密鑰交換等方面。本文通過(guò)對(duì)RSA公鑰密碼算法分析，在RSA公鑰密碼算法安全性上做出具體的分析并給出較為合理參數(shù)體系結(jié)構(gòu)，對(duì)進(jìn)行密鑰設(shè)計(jì)與求解私鑰具有一定的借鑒作用[7]。

參考文獻(xiàn):

[1]陳波,于泠,肖軍模.計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)[M]. 北京:機(jī)械工業(yè)出版社2006. 1

[2]凌捷,謝贊福.信息安全概論[M].廣州:華南理工大學(xué)出版社2005. 8

[3]楊波.現(xiàn)代密碼學(xué)[M].北京:清華大學(xué)出版社2003. 7

[4]殷彬,陶安等. RSA算法的一種高效軟件實(shí)現(xiàn)方法[J]. 微計(jì)算機(jī)信息. 2006(33):258-259

[5]鄢喜愛(ài),楊金民等.RSA公鑰密碼算法的分析[J].長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào). 2006(27):142-144

[6]滕濟(jì)凱. 基于RSA的公鑰叛逆追蹤方案[J].計(jì)算機(jī)工程. 2008(13):152-153

[7]宋曉莉,李敬兆等.RSA算法及其一種簡(jiǎn)單實(shí)現(xiàn)方法的設(shè)計(jì)[J].電子工程師.2004(30):35-37