廣義數(shù)域篩法對(duì)公鑰加密算法的攻擊

侯方天，張雅琨

(中國傳媒大學(xué)信息工程學(xué)院，北京市100024)

1 引言

RSA是一種非常流行的公鑰加密算法，如今被應(yīng)用在許多的電子商業(yè)系統(tǒng)中，如網(wǎng)站的瀏覽器和服務(wù)器系統(tǒng)、電子郵件系統(tǒng)、遠(yuǎn)程會(huì)議安全和電子信用卡支付系統(tǒng)等，它是建立在大整數(shù)很難因式分解的基礎(chǔ)之上的，所以對(duì)大整數(shù)做因數(shù)分解的難度決定了RSA算法的可靠性，隨著整數(shù)分解算法的不斷改進(jìn)和計(jì)算機(jī)運(yùn)算速度的加快，人們對(duì)RSA系統(tǒng)的安全性又產(chǎn)生了懷疑。本文將介紹大整數(shù)分解的一種重要的算法——廣義數(shù)域篩法(GNFS)。

廣義數(shù)域篩法(GNFS)是數(shù)域篩法(NFS)的一般形式，比較適于分解130位以上的大整數(shù)。NFS其還有一種特殊的形式，被稱為特殊數(shù)域篩法(SNFS)，SNFS分解的大整數(shù)w要滿足形式w=re±s，其中 r，e，s∈Z，并且 e＞0，在 07 年的春天就有科學(xué)家通過SNFS分解了1039bit的大整數(shù)，但由于SNFS對(duì)所要分解的大整數(shù)有著特殊的形式要求，它比用GNFS分解768bit的大整數(shù)在難度上要小得多。

廣義數(shù)域篩法(GNFS)是一種很好的因式分解的方法，到目前為止，有效的因式分解方法還有很多，譬如試除法，Pollard’s rho分解法，Pollard’s P-1分解法，橢圓曲線分解法，基于完全平方的分解算法［1］，各算法的特點(diǎn)如表1所示。

表1 因式分解各算法特點(diǎn)

GNFS是一種很好的基于完全平方的分解算法，它對(duì)分解大整數(shù)的效率相對(duì)較高，本文將結(jié)合RSA-768的破解過程［2］，對(duì)GNFS的相關(guān)理論和操作步驟做出相應(yīng)說明。

2 二次篩法(QS)

二次篩法與數(shù)域篩法有著相似的理論基礎(chǔ)，為了更好的理解數(shù)域篩法，我們首先來研究一下二次篩法。

從費(fèi)馬、歐拉、高斯開始，一直到現(xiàn)在，一般整數(shù)分解方法基本上都是在“同余式的平方組合”上做文章，同時(shí)也會(huì)再加上一些現(xiàn)代技巧，如因數(shù)基、平滑數(shù)、篩法、線性代數(shù)等［3］?，F(xiàn)在假定想分解的數(shù)n，如果能夠找到兩個(gè)正整數(shù) x和 y，滿足 x2=y2(mod n)并且0＜x＜y＜n，x≠y，x+y≠n則 gcd(x+y，n)和gcd(x-y，n)有可能就是n分解的兩個(gè)因數(shù)。

QS是一種很好的因式分解的方法，一般適合分解130位以下的整數(shù)，它的核心是Dixon的隨機(jī)二次理論，該理論的核心是要通過運(yùn)用因數(shù)基、平滑和二次剩余類中向量的相關(guān)性等概念計(jì)算出相應(yīng)的平方值。在QS中，因數(shù)基為非空的素?cái)?shù)集合，假設(shè)為F，如果一個(gè)整數(shù)k的所有分解的素?cái)?shù)都在集合F中，那就稱該整數(shù)k在因數(shù)基F上平滑。

現(xiàn)在固定一個(gè)因數(shù)基 F={p1，p2，…，pm}，選取一個(gè)等式f(x)=x2(mod n)，計(jì)算出合適的值ri，使得f(ri)在因數(shù)基F上平滑，當(dāng)有m個(gè)ri被找到后，

這就得到了我們所需要的配對(duì)(x，y)。

舉個(gè)簡單的例子，先假設(shè)因數(shù)基F為(-1，2，3，5，7)，f(ri)為一些隨機(jī)整數(shù)的平方，但要保證 f(ri)在因數(shù)基F上平滑，取n=33，隨機(jī)取f(ri)的值結(jié)果如表2所示。

表2 f(ri)的取值結(jié)果

從線性代數(shù)的角度上來看，只要能在質(zhì)因數(shù)模二值構(gòu)成的向量中找到一個(gè)線性相關(guān)組，就能找到所需要的配對(duì)組合(x，y)。從表中可以看到，當(dāng)f(ri)=72時(shí)，向量跟自身線性相關(guān)，于是可以得到72≡222≡42(mod 33)，從而可以計(jì)算出 gcd(7±4，33)=(3，11)，當(dāng)向量跟自身不相關(guān)時(shí)，可以通過和別的向量組合，一起組成一個(gè)線性相關(guān)組，當(dāng)把f(ri)等于52和62的質(zhì)因數(shù)的模二值相加后，向量為(1，1，1，0，0)，正好與 f(ri)等于 32的向量線性相關(guān)，于是可以得到32≡(5×6)2(mod 33)，gcd(30 ±3，33)=(3，11)。

從以上的分析可以看出，二次篩法最主要的步驟就是通過篩選獲取在因數(shù)基上平滑的數(shù)，然后通過計(jì)算找到線性相關(guān)的向量組，最后以一定概率分解大整數(shù)，廣義數(shù)域篩法的主要步驟也大體如此。當(dāng)然廣義數(shù)域篩法也有著其自身的特點(diǎn)，對(duì)于那些大于130位的整數(shù)，廣義數(shù)域篩法有著更高的分解效率，篩法中所選取的不可約多項(xiàng)式f(ri)的最高次數(shù)不再僅僅是二次，高次的多項(xiàng)式可以產(chǎn)生更多在因數(shù)基上平滑的數(shù)。在二次篩法中，f(ri)起到了一個(gè)橋梁的作用，他把整數(shù)Z映射到了n次剩余類，Z/n Z把一個(gè)在Z中的完全平方數(shù)映射到了一個(gè)在Z/n Z中的完全平方數(shù)，這種映射的方法在廣義數(shù)域篩中也有著重要的作用，兩者的不同點(diǎn)在于QS操作的數(shù)都是整數(shù)，映射是從Z到Z/n Z，而廣義數(shù)域篩操作的數(shù)除了整數(shù)，還有環(huán)Z［α］，映射包括了兩部分，一部分是從Z到Z/n Z，還有一部分是從Z［α］到Z/n Z，這部分映射用φ(β)來表示，這就使廣義數(shù)域篩法相比二次篩法顯得更加得復(fù)雜。

3 廣義的數(shù)域篩法(GNFS)

廣義的數(shù)域篩法的分解理論和技術(shù)包括多項(xiàng)式選擇、篩選、矩陣形成和線性相關(guān)以及平方根的求解，同二次篩法一樣，廣義的數(shù)域篩法也是基于“同余式的平方組合”，目的是找到更多的配對(duì)組合(x，y)，從而分解大整數(shù)，正如上文提到的，廣義的數(shù)域篩法的操作的數(shù)還包括環(huán)Z［α］，其中α是多項(xiàng)式f(x)的根，根的集合形成了集合ψ，在這個(gè)環(huán)Z［α］上能產(chǎn)生更多的平滑，于是廣義的數(shù)域篩法產(chǎn)生配對(duì)組合(x，y)的兩個(gè)基礎(chǔ)方程分別為:

其中 α∈ψ，z∈Z，β =f'(θ)·α∈Z［θ］y=f'(m)·z，x=φ(β)∈Z/n Z。

通過恒等式(5)可以看到，廣義的數(shù)域篩法要想找到合適的配對(duì)組合(x，y)，就得找到足夠的配對(duì)組合(a，b)，使得a+bθ在代數(shù)因數(shù)基Z上平滑，a+bm在有理數(shù)因數(shù)基Z上平滑，然后計(jì)算出(x，y)，以50%左右的可能性得到整數(shù)n的分解因式。

廣義的數(shù)域篩法的分解步驟如下所示。

3.1 多項(xiàng)式選擇

多項(xiàng)式的選擇是廣義數(shù)域篩法的第一步，它對(duì)整個(gè)篩法的耗時(shí)量和篩選的復(fù)雜程度有著重要的作用。

廣義數(shù)域篩法一般會(huì)選取一個(gè)不可約的d階多項(xiàng)式 f(x)，α為這多項(xiàng)式的一個(gè)復(fù)根，Z［α］?Z［x］/f(x)，然后選取一個(gè)參數(shù)m∈Z/n Z，通過 Murphy的多項(xiàng)式選取法，使得f(m)≡0(mod N)，N為所要分解的大整數(shù)，令m為N的一個(gè)分解基，則N，其中 ci∈Z 并且 0≤ci≤m-1，當(dāng)時(shí)，很容易得到，f(m)=N≡0(mod N)滿足等式的要求。由映射φ:Z［α］→Z/n Z，得到φ(α)=m，這樣就使Z［α］的值同整數(shù)有了對(duì)應(yīng)關(guān)系。

在實(shí)踐中，需要通過大量的實(shí)驗(yàn)，參數(shù)的細(xì)致調(diào)整，憑借經(jīng)驗(yàn)，有時(shí)再加上點(diǎn)運(yùn)氣，才能尋找到一個(gè)最合適的多項(xiàng)式。一般來說，首先會(huì)確定多項(xiàng)式的次數(shù)d，d的大小由所要分解的大整數(shù)N的位數(shù)有關(guān)［4］，當(dāng)分解50～80位的十進(jìn)制整數(shù)時(shí)，會(huì)取d值為3;80～110位的十進(jìn)制整數(shù)時(shí)，取d值為4;120～220為十進(jìn)制整數(shù)時(shí)，取d值為5;當(dāng)分解220～300位十進(jìn)制整數(shù)時(shí)，取d值為6。然后確定參數(shù)m的值，通常取m值為或其附近的某一整數(shù)，多項(xiàng)式的選擇有很多不確定因素，多項(xiàng)式的次數(shù)d的選取，參數(shù)m的取值都有很強(qiáng)的隨機(jī)性，即使確定了一組d和m，多項(xiàng)式的系數(shù)還可以有不同的選擇，只有通過實(shí)驗(yàn)，根據(jù)得到的合適的整數(shù)對(duì)(a，b)的數(shù)量才能確定多項(xiàng)式的好壞。

RSA-768的團(tuán)隊(duì)通過三個(gè)月的時(shí)間，從260個(gè)多項(xiàng)式中選出了3個(gè)符合要求的質(zhì)量很高的多項(xiàng)式，而他們最終決定采用的多項(xiàng)式為

RSA-768的團(tuán)隊(duì)同時(shí)也選取了一個(gè)一階的多項(xiàng)式用來在整數(shù)環(huán)上進(jìn)行計(jì)算，多項(xiàng)式為

3.2 平滑和因數(shù)基

從二次篩法中可以看出，平滑和因數(shù)基是篩法的基礎(chǔ)，通過找到足夠多的在因數(shù)基上平滑的數(shù)，才能順利分解大整數(shù)，廣義的數(shù)域篩法也是這樣，不過因?yàn)槠洳还庠谡麛?shù)域上操作，還要在環(huán)Z［α］上操作，所以在環(huán)Z［α］對(duì)于平滑和因數(shù)基就有了新的定義，因數(shù)基不再是Z［α］中的素?cái)?shù)，而是其理想。

α是多項(xiàng)式的根，定義 N(α)=σ1(α)σ2(α)σ3(α)…σd(α)，其中 σi是從 Q［θ］到 C 的映射，D 為一綽金環(huán)，P為D的一個(gè)素理想，p代表一些素?cái)?shù)，當(dāng)N(P)=p時(shí)，定義P為D的第一階素理想，當(dāng)r屬于 Z/p Z，并且 f(r)≡0(mod p)時(shí)，集合(r，p)同第一階素理想的集合一一映射，理想p決定了組合(r，p)，廣義數(shù)域篩法要找的因數(shù)基就是集合(r，p)。

廣義數(shù)域篩法中定義了三個(gè)因數(shù)基，為有理數(shù)因數(shù)基、代數(shù)因數(shù)基和二次特征基。

有理數(shù)因數(shù)基跟二次篩法中的因數(shù)基一樣，都是在整數(shù)域上操作，通過對(duì)(a，b)的取值，找到在a+bm上平滑的值，為了和代數(shù)因數(shù)基和二次特征基的形式保持一致，在實(shí)踐中一般選取因數(shù)基的形式為(m(mod p)，p)。

上文提到過不可約多項(xiàng)式f(x)根形成的集合為O，由數(shù)論的相關(guān)知識(shí)可知，環(huán)O是一個(gè)綽金環(huán)，它的一些理想可以被分解為素理想，從O的理想中選取一個(gè)集合I，這個(gè)集合I就被稱為代數(shù)因數(shù)基，然后找一對(duì)組合(a，b)，使得a+bθ有一個(gè)主理想，能完全分解成I上的素理想，這樣的元素a+bθ就被稱為在I上平滑。

二次特征基是用來確定a+bθ在Z［θ］上是否為一個(gè)完全平方數(shù)，廣義數(shù)域篩法的一個(gè)基礎(chǔ)方程為

給定一個(gè)第一階素理想Q，它決定了組合(s，q)，當(dāng)Q不能分解主理想〈a+bθ〉，并且f'(s)≠0(mod q)時(shí)，也就是說，如果a+bθ在Z［θ］上是一個(gè)完全平方數(shù)，那么當(dāng)然這是一個(gè)必要條件，不是說當(dāng)?shù)仁匠闪r(shí)，a+bθ就一定是完全平方數(shù)，通常在實(shí)際計(jì)算的時(shí)候，q會(huì)取比p大一點(diǎn)的值。

3.3 篩選

篩選是廣義數(shù)域篩法中最重要也是最耗時(shí)的步驟之一，可以通過并行處理的方式提高效率，篩選的目的是要得到足夠多的整數(shù)對(duì)(a，b)，使得a+bm在有理數(shù)因數(shù)基Z上平滑，a+bθ在代數(shù)因數(shù)基Z［θ］上平滑，而對(duì)兩者篩選的方法大體一致。

對(duì)于a+bm來說，m已經(jīng)在上文確定，還有兩個(gè)變量a和b，當(dāng)固定b的值(通常先取b=1)，再取-u＜a＜u(u是a的取值的范圍，可視情況而定)，a從-u開始一直取到u，通過計(jì)算得到能使a+bm在因數(shù)基上平滑的組合(a，b)，當(dāng)取完a的值發(fā)現(xiàn)組合還不夠時(shí)，增加b的值直到組合夠?yàn)橹梗@種方法需要計(jì)算每個(gè)a+bm的值是否平滑，很消耗時(shí)間。在實(shí)際中一般會(huì)固定一個(gè)因數(shù)基里的素?cái)?shù)p和一個(gè)正整數(shù)b，當(dāng)a+bm≡0(mod p)，也就是a≡-bm(mod p)的時(shí)候，p就能分解，a+bm那么在篩選的時(shí)候，在-u到u的范圍內(nèi)取滿足等式a=-bm+kp的a的值就可以了，這就大大提高了效率。

a+bθ的篩選是在代數(shù)因數(shù)基上進(jìn)行的，是要通過第一階素理想P來分解主理想〈a+bθ〉，而P可以由組合(r，p)決定，當(dāng)a≡-br(mod p)的時(shí)候，p能分解，N(a+bθ)而當(dāng) p能分解 N(a+bθ)的時(shí)候，第一階素理想P也就能分解主理想〈a+bθ〉，于是篩選的方法就是固定b的值和組合(r，p)，取a≡-br+kp，并且 -u ＜a＜ u，然后計(jì)算 N(a+bθ)的值，當(dāng)值能被p分解時(shí)，(a，b)就是篩選出來的可用的整數(shù)對(duì)。

通過篩選，RSA-768的團(tuán)隊(duì)總共獲取了64334489730對(duì)合適的組合，然后通過分布式篩選理論，其中有24.7%的組合是重復(fù)記錄的，然后通過一種判別算法，刪去那些包含素?cái)?shù)(小概率出現(xiàn))的組合，于是就只剩下2458248361對(duì)組合，只占原來的3.4%。

3.4 矩陣生成及過濾

通過篩選，得到了I對(duì)整數(shù)對(duì)(a，b)，接下來就要構(gòu)建一個(gè)矩陣，假設(shè)有理數(shù)因數(shù)基有k個(gè)素?cái)?shù)，代數(shù)因數(shù)基有l(wèi)個(gè)第一階素理想，二次特征基有m個(gè)第一階素理想，則矩陣應(yīng)該有k+l+m+1行，列數(shù)為I，矩陣的每一列都由一對(duì)整數(shù)對(duì)(a，b)決定，構(gòu)建矩陣的最終目的是尋找到矩陣列與列之間的線性相關(guān)性，從而找到不同的 a+bm，〈a+bθ〉和 a+bθ，使他們的乘積值為完全平方數(shù)。

每一列矩陣都是由四部分組成，第一部分就一位，它表示a+bm的正負(fù)性，正的話為0，負(fù)的話為1;第二部分有k位，有理數(shù)因數(shù)基中的素?cái)?shù)有k個(gè)，a+bm由這些素?cái)?shù)分解后素?cái)?shù)的指數(shù)模二的值就對(duì)應(yīng)了該k位，假設(shè)因數(shù)基為{2，3，5}，選定的整數(shù)對(duì)為(3，1)，m 為27，則 a+bm=30=2 ×3×5，前 k位就為(1，1，1);第三部分有l(wèi)位，代數(shù)因數(shù)基中有一對(duì)(r，p)，通過公式 N(a+bθ)=(-b)df(-a/b)計(jì)算出 N(a+bθ)的值，把 N(a+bθ)分解得到 p，當(dāng) a≡-br(mod p)時(shí)，記該位為1;第四部分有m位，由二次特征基決定，當(dāng)滿足公式時(shí)，值為0，否則為1.

以上生成的是一個(gè)原始矩陣，矩陣維數(shù)和重量會(huì)直接決定線性相關(guān)求解的時(shí)間，原始矩陣顯然不是最合適的矩陣，必須通過相應(yīng)的過濾方法，減小矩陣的維數(shù)，同時(shí)控制重量的增長，使兩者達(dá)到一個(gè)最佳平衡點(diǎn)，這樣能大大提高分解效率。

3.5 線性相關(guān)

當(dāng)最佳矩陣找到后，就得通過計(jì)算得到矩陣列向量之間的線性相關(guān)性了，這也可以理解為求解一個(gè)大規(guī)模稀疏線性方程組，用傳統(tǒng)的高斯消元法去處理一個(gè)維數(shù)很大的矩陣時(shí)會(huì)消耗很多時(shí)間，不能被采用，目前最常用的求解的方法為 Lanczos和Wiedemann算法［5］，尋找線性相關(guān)性的這一步是數(shù)域篩法中耗時(shí)最多的步驟之一，實(shí)際中通常會(huì)采用并行處理。

RSA-768的團(tuán)隊(duì)最后生成了一個(gè)192796550*192795550的矩陣，矩陣的重量為27797115920，也就是說每行平均有144個(gè)非0數(shù)，通過119天的計(jì)算，團(tuán)隊(duì)最終在2009年的十月八號(hào)完成了矩陣的計(jì)算，得到了能使矩陣列向量線性相關(guān)的組合。

3.6 平方根的求解

用廣義數(shù)域篩法分解大整數(shù)，利用的是“同余式的平方組合”，這就需要利用LLL算法或是Montgomery的算法［6］，來求解整數(shù)的平方根，同過大規(guī)模稀疏線性方程組的求解，就能找到對(duì)應(yīng)的平方關(guān)系，這些平方關(guān)系都是由幾對(duì)組合(a，b)確定的，通過組合(a，b)得到，而β2=f'(θ)2·α2，從而計(jì)算出 β 的含 θ的多項(xiàng)式 f2(θ)，于是 x=f2(m)≡φ(β)(mod N);通過組合(a，b)得，而 y2=f'(m)2·Z2，通過平方根的求解就能得到y(tǒng)的值。

4 結(jié)論

本文討論了數(shù)域篩法中廣義數(shù)域篩法的基本理論，從中可以看出，廣義數(shù)域篩法的分解步驟是相對(duì)固定的，首先要選擇一個(gè)合適的多項(xiàng)式，多項(xiàng)式質(zhì)量的好壞決定了篩選的效率，然后要確定三個(gè)因數(shù)基，以平滑為標(biāo)準(zhǔn)進(jìn)行篩選，篩選可以采取并行處理［7］，當(dāng)篩選出有效的組合后，就可以組成一個(gè)矩陣，并對(duì)其進(jìn)行處理，找到線性相關(guān)的列向量，這一步驟計(jì)算量很大，需進(jìn)行并行處理，通過平方根的求解，得到組合(x，y)，最終以50%左右的可能性完成對(duì)大整數(shù)的分解。

對(duì)于廣義數(shù)域篩法來說，雖然還存有很多問題需要解決，但作為目前對(duì)大整數(shù)分解最快的方法，通過硬件設(shè)備和算法的改良，其每一分解步驟都有改進(jìn)的空間，從而能夠更加高效的完成大整數(shù)的分解，從而完成對(duì)公鑰加密算法RSA的攻擊。

［1］ T Kleinjung，K Aoki，J Franke，A Lenstra.Factorization of a 768-bit rsa modulus［J］.Cryptology ePrint Archive，Report.2010/006，2010.

［2］ M E Briggs.An introduction to the general number field sieve［D］.Virginia Polytechnic Institute and State University，USA，1998.

［3］ J Hill.The Number Field Sieve:An Extended Abstract［D］.March 12，2010.

［4］ 王洪濤，劉春雷.數(shù)域篩法中多項(xiàng)式的選擇［J］.信息工程大學(xué)學(xué)報(bào)，2003，4(3).

［5］ L T Yang，Li X，J H Park.A Parallel GNFS Algorithm with the Improved Linbox Montgomery Block Lanczos Method for Integer Factorization［J］.International Conference on Information Se-curityandAssurance，2008.

［6］ AKLenstra，HWLenstra，MSManasse.The numberfieldsieve［D］.

［7］ 顏松遠(yuǎn).整數(shù)分解［M］.北京:科學(xué)出版社，2009.