分解大整數(shù)為兩個(gè)素因子乘積的析出算法

孫克泉

(南開社區(qū)學(xué)院計(jì)算機(jī)系,天津市 300100)

分解大整數(shù)為兩個(gè)素因子乘積的析出算法

孫克泉

(南開社區(qū)學(xué)院計(jì)算機(jī)系,天津市 300100)

RSA的算法是基于數(shù)論中兩個(gè)大素?cái)?shù)乘積所得整數(shù)n和選取滿足一定條件的整數(shù)e組成公開鑰(e,n),RSA的安全性是依據(jù)大數(shù)整數(shù)n分解困難性的。根據(jù)RSA公鑰加密體制的公開密鑰n為兩個(gè)素?cái)?shù)乘積的特性,以及Euclid算法的特點(diǎn),給出了一種分解n的算法—析出算法,并進(jìn)行了算法的數(shù)學(xué)證明、算法設(shè)計(jì)和相關(guān)分析。同時(shí),通過也證明了,在RSA密碼體制中構(gòu)造模n時(shí),其素因子的倍數(shù)與n1/2距離過近是不安全的結(jié)論。

析出算法;RSA;Euclid算法;密碼分析算法;算法數(shù)論

一、引言

RSA算法[1]是1978年由R.Rivest,A.Shamir和L.A dleman提出的一種用數(shù)論方法構(gòu)造的非對(duì)稱加密方法,它被認(rèn)為是目前相當(dāng)成熟、完善的公鑰密碼體制,并廣泛地應(yīng)用于密鑰管理、數(shù)字簽名等方面。

RSA的算法是基于數(shù)論中兩個(gè)大素?cái)?shù)乘積所得整數(shù)n和選取滿足一定條件的整數(shù)e組成公開密鑰(e,n),并選取特定私鑰d組成私有密鑰對(duì)(d,n)。對(duì)于RSA加密體制攻擊是來自多方面的,同時(shí)對(duì)加密算法的密碼分析是檢驗(yàn)算法安全性的標(biāo)志。因?yàn)樵诮o定e和n和情況下,確定d的計(jì)算量至少等價(jià)于整數(shù)分解問題[2],所以RSA算法的安全性就是基于數(shù)論中大整數(shù)分解困難性的,一旦成功分解n,就很容易地得到了私鑰d,也就破解了用RSA加密的內(nèi)容。因此,在對(duì)RSA的密碼分析方法中,大多數(shù)都集中在對(duì)公鑰n的因式分解方法上,比如數(shù)域分解法、二次篩選法、橢圓曲線法和試除法等。

本文是利用RSA密鑰加密中的公開鑰n是兩相大素?cái)?shù)乘積的特性和Euclid算法的特點(diǎn),給出了一種新的分解n的算法,這里稱為析出算法(Analysis A lgorithm),并進(jìn)行相關(guān)的理論證明和該算法設(shè)計(jì),以及相關(guān)分析。同時(shí)得出在RSA密碼體制中構(gòu)造模n時(shí),其素因子的倍數(shù)與n1/2距離過近是不安全的結(jié)論。

二、RSA算法的基本描述與安全性分析

1.RSA的公鑰加密體制

由Rivest、Sham ir和A dleman開發(fā)的RSA方案利用了指數(shù)運(yùn)算,明文以分組的方式被加密,其中每個(gè)分組是一個(gè)小于某一整數(shù)n的二進(jìn)數(shù),即分組的長度必須小于或等于log2n;實(shí)際上,分組長度k滿足2k

發(fā)送者和接收者都必須知道整數(shù)n,發(fā)送者e,而只有接收者知道d的值。因此這是一個(gè)公鑰加密算法,其中公開密鑰 KU=(e,n),而私有密鑰 KR=(d,n),RSA算法須滿足以下要求:

(1)對(duì)于所有m

(2)對(duì)于m

(3)給定e和n,求d是計(jì)算上不可行的。

2.RSA密鑰的產(chǎn)生

(1)選兩個(gè)保密的大素?cái)?shù)p和q。

(2)計(jì)算n=pq,φ(n)=(p-1)(q-1),其中φ(n)是n的歐拉函數(shù)值。

(3) 選一整數(shù) e,滿足 1

(4)計(jì)算d,滿足d·e≡1 modφ(n),即d是e在模φ(n)下的乘法逆元,因e與φ(n)互素,由模運(yùn)算可知,它的乘法逆元一定存在。(5)以{e,n}為公開密鑰,{d,n}為私有密鑰。

3.RSA加密/解密運(yùn)算

加密時(shí)首先將明文比特串分組,使得每個(gè)分組對(duì)應(yīng)的十進(jìn)制數(shù)小于n,即分組長度小于log2n。然后對(duì)每個(gè)明文分組m,作加密運(yùn)算:memod n=c,其中c為明文m的e次冪與n的模運(yùn)算。對(duì)密文分組的解密運(yùn)算為:m=cdmod n,并且可以根據(jù)Euler定理證明解密的正確性[3]。

4.分解n的算法及RSA安全性分析

RSA的安全性是基于分解大整數(shù)的困難性假定,這種假定是因?yàn)橹两襁€未能證明分解大整數(shù)n的問題。如果RSA的模數(shù)n被成功地分解為兩相素?cái)?shù)乘積n=pq,則立即獲得φ(n)=(p-1)(q-1),從而能夠確定e模φ(n)的乘法逆元 d,即d≡e-1modφ(n),因此攻擊成功。如果給定 n,φ(n)等價(jià)于對(duì)n的分解[3];在給定e和 n的情況下,確定d的計(jì)算量至少等價(jià)于整數(shù)分解問題[2]。因此,只有分解n才能從c和e中計(jì)算出明文m。對(duì)n的因式分解方法中,通常的方法是采用數(shù)論中的因式分解方法。針對(duì)公鑰n比較常用的因式分解方法有試除法、Fermat分解法、Pollard’s rho分解法、Pollard’s P-1分解法、Dixon分解法、連分?jǐn)?shù)分解法、二次篩法、多多項(xiàng)式二次篩法、數(shù)域篩法和橢圓曲線法等。Pollard’s rho分解法、Pollard’s P-1分解法和橢圓曲線法都是概率分解的方法,都是要求被分解的模數(shù)有特殊的條件[4][5]。為了增強(qiáng)RSA的安全性,通常采用選擇強(qiáng)素?cái)?shù)的方法,以預(yù)防這類算法的攻擊[6]。Fermat分解法、Dixon分解法、二次篩法、多多項(xiàng)式二次篩法、數(shù)域篩法等都是基于求同余式為x2≡y2(mod n)且x≠±y(mod n)所構(gòu)成完全平方數(shù)x和y。只要求出x和y,即通過gcd(x+y,n)和gcd(x-y,n)達(dá)到分解n的目的。但求出這樣的x和y通常是很困難的,必須構(gòu)造有效的算法,利用一些數(shù)論技巧才能完成它。這些基于構(gòu)造完全平方數(shù)的算法就是利用各用數(shù)論理論和技巧,如同余式、二次剩余、多項(xiàng)式等以及代數(shù)運(yùn)算,通過比較復(fù)雜的算法構(gòu)造,盡量縮減運(yùn)算量,降低運(yùn)算復(fù)雜度,以搞高分解n的效率。數(shù)域篩法被認(rèn)為是當(dāng)前最有效的算法[4][5]。

根據(jù)目前的研究,提高分解n的有效性和效率只是在這些算法的基礎(chǔ)上,進(jìn)行改進(jìn),如更好地構(gòu)造多項(xiàng)式等[7],或給出分解特殊形式的n的方法[8],以提高分解效率。因此,當(dāng)n的二進(jìn)制位數(shù)在1024位以上時(shí)被認(rèn)為是安全的。

本文根據(jù)n為兩個(gè)素因子乘積的特性,以及求最大公約數(shù)的 Euclid算法,給出一種新的分解n的算法,不妨將它叫做析出算法。下面就給出該算法的相關(guān)定理及證明、算法設(shè)計(jì),以及相關(guān)分析。

三、析出算法的相關(guān)定理

定義1設(shè)a,b為任意整數(shù),如果存在整數(shù)c,使得a=bc,則稱a是b的倍數(shù),b是a的因數(shù)或約數(shù),即a被 b整除,或 b整除a,記為 b|a。

定義2能夠整除a,b,…l的每一個(gè)整數(shù)叫做它們的公約數(shù),公約數(shù)中最大的一個(gè)叫做最大公約數(shù) ,記作(a,b,…l)或 gcd(a,b,…l)。

定義3對(duì)于任意實(shí)數(shù)x,用[x]表示不超過x的最大整數(shù)。

定理1設(shè)n為兩個(gè)素?cái)?shù)乘積的正整數(shù),n=pq,p和q為素?cái)?shù),且p

引理1(因子分解的唯一性):如果n=pq,p和q為素?cái)?shù),且p

引理2如果 n=pq,p和 q為素?cái)?shù),且p[n1/2]。

證明:用反證法,如果p=[n1/2],由于 n=pq,所以 q=p=[n1/2],與p

如果p>[n1/2],由于 n1/2不是整數(shù),則p>n1/2,得p2>n。由 q>p,得pq>n,與 n=pq矛盾。

因此p<[n1/2],同理可以證明q>[n1/2]。

定理1的證明:由p為素?cái)?shù),和引理1得知,必定存在一個(gè)正整數(shù)k(k≥1),使得 kp≤[n1/2]≤(k+1)p

引理3設(shè)a,b為正整數(shù)且b≤a,則唯一存在正整數(shù)d和r,使得

a=bd+r;0≤r

數(shù)d稱為帶余除法的不完全商數(shù),數(shù)r稱為b除a的余數(shù)。

特別地,如果r=0,則a=bd,由此得b和d是a的因數(shù)。

證明:假設(shè)還可以表示成:a=bd1+r1,0≤r1

引理4設(shè)a,b為正整數(shù),且b≤a,不妨表示為a=bd+r。如果(a,b)=1,且m為a和r的公因子,則 m|(d,r);否則 m|(b,r)。

證明:如果 m=(a,b),即 m|a,m|b,由 a=bd+r和 m|bd+r,得 m|r,所以 m|(b,r)。因此有 m|(b,r)。設(shè)(a,b)=1,如果存在 m|r,m|a,則由a=bd+r,得 m|d,即 m|(d,r)。

定理2(Euclid算法(輾轉(zhuǎn)相除法))

設(shè)a,b為正整數(shù),由于引理3,我們求得一串等式:

這串等式直到余數(shù)等0為止。而且

(b,r1)=(r1,r2)=(r2,r3)=…=(rn-1,rn)= rn.

(證明略)

因?yàn)閎,r1,r2,…,rn是是遞減的正整數(shù)數(shù)列,不能包括多于b個(gè)的正整數(shù),所以上述一串等式成立。

由引理4得(b,r1)=(r1,r2)=(r2,r3)=…=(rn-1,rn)= rn.

定理3設(shè)a,b為正整數(shù)且b≤a,表示為a=bd+r;0≤rb,(a,d)=(d,r)。

證明:因?yàn)閐>b,所以在a=bd+r式中有0≤r

定理4設(shè)n為兩個(gè)素?cái)?shù)乘積的正整數(shù),不妨設(shè)n=pq,p和q為素?cái)?shù),且p

證明:首先證明d>b>[n1/2]。假定 d<[n1/2],則 n=bd+r≥bd>[n1/2][n1/2]。因?yàn)閇n1/2][n1/2]b>[n1/2]。

由于引理3和引理4,有(n,b)= (b,r)或(n,d)= (d,r)。由引理2得知,p<[n1/2],q>[n1/2],以及n只有兩個(gè)素因子p和q,因此,如果n與小于[n1/2]的數(shù)的最大公約數(shù)存在,則必為p。即(n,b)=p或(n,d)=p。

四、析出算法原理與分析

1.采用 Euclid算法分解n的方法

可以采用 Euclid算法分解n。由定理1,如果存在一個(gè)整數(shù)k≥1,使得kp≤[n1/2]≤(k+1)p,發(fā)現(xiàn)小于[n1/2]的正整數(shù)中含有n的素因子p的整數(shù)為p,2p,3p…kp =[[n1/2]/p]p。要從小于[n1/2]的數(shù)中篩選出含有n的素因子p,可以采用 Euclid算法進(jìn)行。也就是說,依次取小[n1/2]的整數(shù),然后用 Euclid算法求該數(shù)與的最大公約數(shù),如果不存在,將該數(shù)減1,再重復(fù)使用 Euclid算法,直至求出n的素因子p,用具體設(shè)計(jì)方法是:

(1)設(shè)一變量i的初始值為[n1/2]

(2)根據(jù)定理2提供的 Euclid算法求n和i的最大公約數(shù)p(由定理4得知)。

(3)如果n與i互素,則進(jìn)行i-1運(yùn)算,然后返回(2),如果n與i存在公約數(shù),必得到公約數(shù)p,進(jìn)而求出n的另一個(gè)因子q。

2.Euclid算法分解n的方法分析

如果采用Euclid算法分解n,在設(shè)計(jì)一個(gè)程序運(yùn)行的情況下,該方法的計(jì)算量與n的素因子p有關(guān),進(jìn)而與[[n1/2]/p]p有關(guān)。只有變量i遞減到等于[[n1/2]/p]p時(shí)才能分解出n的素因子p,因?yàn)樵诖笥赱[n1/2]/p]p的數(shù)到[n1/2]都與是互素的。該方法的計(jì)算量取決于([n1/2]- [[n1/2]/p]p)3(最高一次輾轉(zhuǎn)相除的執(zhí)行次數(shù))。它存在的的缺陷是:

(1)對(duì)于求n與小于[n1/2]的數(shù)的公約數(shù),一旦該數(shù)與n互素,則此次輾轉(zhuǎn)相除的運(yùn)算是徒勞的。由于在[n1/2]-[[n1/2]/p]p([[n1/2]/p]p除外)之間的數(shù)都與n互素,因此,在該區(qū)間上每次輾轉(zhuǎn)相除都不能分解出素因子p。只有當(dāng)分解的數(shù)為[[n1/2]/p]p時(shí)才能找到素?cái)?shù)p。

(2)由定理1,kp≤[n1/2]≤(k+1)p(k≥1),即 k=[[n1/2]/p]。如果[n1/2]-[[n1/2]/p]p大于([[n1/2]/p]+1)p-[n1/2]時(shí),也就是說,當(dāng)大于[n1/2],而且距離[n1/2]與含有素因數(shù)p的數(shù)相對(duì)很近時(shí),不能由此程序分解出該素?cái)?shù),從而降低了分解效率。

3.析出算法的原理、設(shè)計(jì)與分析

1)析出算法的設(shè)計(jì)

對(duì)于上述用Euclid算法分解n的方法,從效率上是可以進(jìn)一步的改進(jìn)的。為了彌補(bǔ)上述缺陷,構(gòu)造出一種新算法,把它稱之為析出法,算法設(shè)計(jì)如下:

(1)設(shè)一變量i,它的初始值為[n1/2]

(2)根據(jù)定理3和定理4,采用下列的相除法:

將n mod i的值賦給變量r,這樣得到一個(gè)余數(shù)r。然后再求n mod r,依次類推,一直計(jì)算到預(yù)先設(shè)定的一個(gè)數(shù)s為止,s設(shè)定的依據(jù)是:被認(rèn)為在小于s的整數(shù)中不可能存在素因子p。

實(shí)際上是求下列一串等式:

(不妨設(shè)b=i)

在這里要對(duì)其中的rn是否小于s進(jìn)行判斷,一旦rn+1

(3)如果rn+1小于一個(gè)特定s且rn+1≠0,則進(jìn)行i-1運(yùn)算,然后返回(2),如果n與i存在公約數(shù),必得到公約數(shù)p,進(jìn)而求出n的另一個(gè)因子q。

2)析出算法的分析

該算法的原理是依據(jù) Euclid算法效率較高的特點(diǎn),主要是采用取余運(yùn)算,相對(duì)減少了運(yùn)算量。下面就該算法進(jìn)行如下分析。

(1)由于是從小于或等于[n1/2]的數(shù)開始,依次遞減操作,對(duì)于其中的任意一個(gè)整數(shù)b,根據(jù)引理4,都存在n=bd+r。由定理2,如果b≤[n1/2]中含有素因子p,則r中必包含素因子p,但是如果b不含有素因子p,也就是說n和b是互素的。如果按照 Euclid算法,最后只能得到gcd(n,b)=1。但是,此時(shí)r中并不一定不含有素因子p(通過實(shí)驗(yàn)驗(yàn)證是肯定的)。因此,該算法可以求r中含有n的素因子p。

(2)因?yàn)閎是依次遞減,所以d是遞增的。雖然在每次運(yùn)算中d的遞增可能不是1,但很明顯,在運(yùn)算中,與上一次相比,如果d不是增1,是由于該數(shù)除n的余數(shù)大于[n1/2],經(jīng)測(cè)試該算法仍能找到大于[n1/2]且與之最近的含素因子p的數(shù),進(jìn)而求得p。因此,該算法在計(jì)算了n=bd+r式中小于或等于[n1/2]的數(shù)b可能存在素因子p的同時(shí),也計(jì)算大于[n1/2]商數(shù)d與r可能存在素因子的問題(由定理3)。

(3)關(guān)于算法中給定一個(gè)假定的數(shù)s,是為了減少算法中第2步的運(yùn)算量,這個(gè)數(shù)的確定是根據(jù)RSA密碼體制中,n取較大素因子的情況。例如,假設(shè)n的兩個(gè)素因子為相同位數(shù),且十進(jìn)制位數(shù)為k,則s確定為10k-1。因?yàn)楫?dāng)小于s的所有整數(shù)不可能存在n的素因子。

(4)從概率角度分析,由于每次運(yùn)算所得的余數(shù)r大部分是不同的,很可能在其中的某個(gè)余數(shù)中存在n的素因子。因此,該法存在求出n的素因子的隨機(jī)性。

(5)為了增加求出n的素因子概率和提高分解速度,在算法中可以采用在一定范圍內(nèi)隨機(jī)抽取小于[n1/2]的數(shù)進(jìn)行第2步的運(yùn)算。或采用多臺(tái)機(jī)器分布運(yùn)算的方法。

(6)由定理3,該算法的單一程序的最大運(yùn)算量這min([n1/2]-[[n1/2]/p]p,([[n1/2]/p]+1)p-[n1/2])3(算法第2步的最大運(yùn)算量)。

(7)不難看出,如果在[n1/2]附近存在含有n的素因子的數(shù),那么,采用該算法會(huì)很快得到n的素因子,進(jìn)而求出RSA加密的明文。因此,該算法能很容易分離出與[n1/2]較近的含有n的素因子的數(shù),進(jìn)行破解RSA的密鑰;也就是說,如果n的素因子的倍數(shù)與n1/2距離較近時(shí),RSA密鑰體制是不安全的。

(8)雖然,大數(shù)取余的算法效率不是很高,但在還可以進(jìn)一步改進(jìn)該算法的設(shè)計(jì)方法,具體的算法設(shè)計(jì)的改進(jìn)有待進(jìn)一步研究。

(9)以上結(jié)果,在計(jì)算機(jī)上對(duì)小于64位的n進(jìn)行了有效驗(yàn)證。

五、總結(jié)

本文構(gòu)造了RSA密碼體制中分解公鑰n的析出算法。它是通過改進(jìn)Euclid算法,創(chuàng)造出的一種新算法。該算法利用了Euclid算法中求最大公約數(shù)效率高的特點(diǎn),并充分利用了n是兩個(gè)素?cái)?shù)乘積的特性,試圖提高分解n的效率,證明了如果一個(gè)數(shù)在n1/2附近含有n的素因子,使用該算法能比較容易地析出這個(gè)數(shù)所包含的n的素因子。由此也得出了一個(gè)結(jié)論:在RSA密碼體制中構(gòu)造模n時(shí),其素因子的倍數(shù)與n1/2距離過近是不安全的。今后,對(duì)于該算法的計(jì)算方式,以及大數(shù)模n的分解還需進(jìn)一步的研究。

研究背景:

依據(jù)對(duì)于算法數(shù)論和信息安全中RSA公鑰體制中研究。盡量查找目前資料中所能查到的各種算法,并對(duì)其進(jìn)行分析研究。在此基礎(chǔ)上提出一種新的密碼分析算法-析出算法,它是根據(jù)公鑰n是兩個(gè)素乘積的特性,在對(duì)Euclid算法的改進(jìn)后得出一種新算法,它從理論上不同于其它算法。并給出了該算法的相關(guān)數(shù)學(xué)證明、算法設(shè)計(jì)和算法分析。

[1]L Rivest,A Shamir,L Adleman.A Method for Obtaining Digital Signatures and Public Key Cryp tosystems[J].Communications of the ACM,1978,21(2):120-126.

[2]Ribenboin,P.The New Book of Prime Number Reco rds.New York:Sp ringer-Verlag,1996.

[3]Kslidki,B.;and Robshaw;M.“The secure Use of RSA”Cryp toBytes,Autumn 1995.

R L Rivest,A Shamir,L Adleman,“On Digital Signatures and Public Key Cryp tosystems”,Communications of the ACM,vol 21 no 2,pp120-126,Feb 1978.

[4]顏松遠(yuǎn),楊思熳等譯.計(jì)算數(shù)論[M].第2版.北京:清華大學(xué)出版社,2008.

[5]董青,吳楠.整數(shù)質(zhì)因子分解算法新進(jìn)展與傳統(tǒng)密碼學(xué)面臨的挑戰(zhàn)[J].計(jì)算機(jī)科學(xué),2008,(08).

[6]謝建全,陽春華.RSA算法中幾種可能泄密的參數(shù)選擇[J].計(jì)算機(jī)工程,2006,(16).

[7]裴定一,祝躍飛.算法數(shù)論[M].北京:科學(xué)出版社,2002.

[8]張鵬,李超.數(shù)域篩法分解re±s型大整數(shù)時(shí)多項(xiàng)式的選取[J].計(jì)算機(jī)應(yīng)用與軟件,2009,(04).

[9]N,M.維諾格拉陀夫.數(shù)論基礎(chǔ).北京:高等教育出版社,1956.

The Separation A lgorithm of D ividing Large Integer into Tw o Prim e D ivisor Product

SUN Ke-quan
(N ankai Comm unity College,Tianjin 300100 China)

RSA calculation is based on tw o divisors p roduct n and 1,w hich forms the conditional public key(e,n).The safety of RSA depends on the difficulty of dividing the large integer n.Accord2 ing to the characteristic of public key RSA and Euclid Calculations,this essay p resents a decomposing n’s calculation--Separation Algorithm,and undergoesmathematical p roof,design and analysis.At the same time,during the design of module n,it p roves unsafe if the integer multip le is too close to n1/2.

separation algorithm;RSA;Euclid Calculations;code analytical calculation;Theo2 retic Algorithms

TP309.7

A

1673-582X(2011)08-0037-06

2010-11-10

孫克泉(1961-),男,天津武清人,南開社區(qū)學(xué)院教師,碩士,副教授,CCF高級(jí)會(huì)員,主要研究領(lǐng)域?yàn)橛?jì)算機(jī)應(yīng)用,信息安全。