基于數論的RSA算法研究

余亞輝

【摘要】基于數論的公鑰密碼體制的RSA算法是最完善的加密算法. 通過RSA算法基本原理可以將大數的冪模運算轉換為小數冪模運算，并對一些模塊進行適當的改進，從而提出快速求解加密和解密的計算方法，提高RSA的運算速度。

【關鍵詞】公鑰密碼算法RSA算法冪模運算

【基金項目】河南省教育廳科學技術研究重點項目資助計劃（14A110016）。

【中圖分類號】O29 【文獻標識碼】A 【文章編號】2095-3089（2014）05-0137-02

1.前言

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

2.基本定義與定理

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

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

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

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

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

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

定理2：若是p素數，a是正整數且gcd(a,p)=1則ap-1≡1modp，稱為費爾瑪定理。（簡稱Fermat定理）[1]。

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

推論1：若n是兩個素數p和q的乘積，則φ(n)=φ(p)×φ(q)=(p-1)×(q-1)

推論2：對任意非負整數a和正整數b有gcd(a,b)=gcd(b,amodb)。

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

3.RSA公鑰算法描述

3.1密鑰選擇

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

3.2加密運算

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

3.3解密運算

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

3.4 計算問題

通過分析RSA算法的求解過程，可知RSA通過乘法與除法加以實現的?？上攵琑SA算法將執行大量的乘除法運算，從而導致RSA算法的加密與解密速度十分慢[6]。因此，大整數的乘除法成為影響RSA算法速度的重要因素。利用模運算的性質：(a×b)modn+[(amodn)×(bmodn)]modn可以大大減少中間運算環節，提高運算速度。例如求am，其中a和m是正整數， m表示為二進制形式bk,bk-1,bk-2，…b0即m=bk2k+bk-12k-1+…+b12+b0。

4.RSA算法的安全性分析

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

歐幾里得算法是基于推論2作為求兩個正整數的最大公因子的簡化過程，是數論中的一個基本算法理論。當兩個正整數互素時，可以求出其中一個數關于另一個數的乘法逆元。設輸入兩個正整數為b，a并設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算法安全性是建立在大數的因數分解基礎上，下面解決大數的分解。若n=p×q被因子分解，則RSA便被攻破，因為在p和q已知的情況下，則利用歐拉函數可以解出φ(n)=(p-1)×(q-1），再利用歐幾里得算法求出以φ(n)為模的公鑰的e乘逆元d，就可以破譯出RSA的秘密私鑰。

若n無法分解時，如果破譯者知道φ(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=■聯立方程組(p+q)和(p-q)可得p=■，q=■ ,d也可以很容易地得到。也就是說，如果能夠以一種可行的方法直接得到φ(n)，破譯者就可以對其進行破譯。

4.3 合理選定參數

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

4.4參數e和d選擇原則

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

5.結語

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

參考文獻:

[1]陳波,于泠,肖軍模.計算機系統安全原理與技術[M]. 北京:機械工業出版社2006. 1

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

[3]楊波.現代密碼學[M].北京:清華大學出版社2003. 7

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

[5]鄢喜愛,楊金民等.RSA公鑰密碼算法的分析[J].長春工業大學學報. 2006(27):142-144

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

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