广义数域筛法对公钥加密算法的攻击

侯方天，张雅琨

(中国传媒大学信息工程学院，北京市100024)

1 引言

RSA是一种非常流行的公钥加密算法，如今被应用在许多的电子商业系统中，如网站的浏览器和服务器系统、电子邮件系统、远程会议安全和电子信用卡支付系统等，它是建立在大整数很难因式分解的基础之上的，所以对大整数做因数分解的难度决定了RSA算法的可靠性，随着整数分解算法的不断改进和计算机运算速度的加快，人们对RSA系统的安全性又产生了怀疑。本文将介绍大整数分解的一种重要的算法——广义数域筛法(GNFS)。

广义数域筛法(GNFS)是数域筛法(NFS)的一般形式，比较适于分解130位以上的大整数。NFS其还有一种特殊的形式，被称为特殊数域筛法(SNFS)，SNFS分解的大整数w要满足形式w=re±s，其中 r，e，s∈Z，并且 e＞0，在 07 年的春天就有科学家通过SNFS分解了1039bit的大整数，但由于SNFS对所要分解的大整数有着特殊的形式要求，它比用GNFS分解768bit的大整数在难度上要小得多。

广义数域筛法(GNFS)是一种很好的因式分解的方法，到目前为止，有效的因式分解方法还有很多，譬如试除法，Pollard’s rho分解法，Pollard’s P-1分解法，椭圆曲线分解法，基于完全平方的分解算法［1］，各算法的特点如表1所示。

表1 因式分解各算法特点

GNFS是一种很好的基于完全平方的分解算法，它对分解大整数的效率相对较高，本文将结合RSA-768的破解过程［2］，对GNFS的相关理论和操作步骤做出相应说明。

2 二次筛法(QS)

二次筛法与数域筛法有着相似的理论基础，为了更好的理解数域筛法，我们首先来研究一下二次筛法。

从费马、欧拉、高斯开始，一直到现在，一般整数分解方法基本上都是在“同余式的平方组合”上做文章，同时也会再加上一些现代技巧，如因数基、平滑数、筛法、线性代数等［3］。现在假定想分解的数n，如果能够找到两个正整数 x和 y，满足 x2=y2(mod n)并且0＜x＜y＜n，x≠y，x+y≠n则 gcd(x+y，n)和gcd(x-y，n)有可能就是n分解的两个因数。

QS是一种很好的因式分解的方法，一般适合分解130位以下的整数，它的核心是Dixon的随机二次理论，该理论的核心是要通过运用因数基、平滑和二次剩余类中向量的相关性等概念计算出相应的平方值。在QS中，因数基为非空的素数集合，假设为F，如果一个整数k的所有分解的素数都在集合F中，那就称该整数k在因数基F上平滑。

现在固定一个因数基 F={p1，p2，…，pm}，选取一个等式f(x)=x2(mod n)，计算出合适的值ri，使得f(ri)在因数基F上平滑，当有m个ri被找到后，

这就得到了我们所需要的配对(x，y)。

举个简单的例子，先假设因数基F为(-1，2，3，5，7)，f(ri)为一些随机整数的平方，但要保证 f(ri)在因数基F上平滑，取n=33，随机取f(ri)的值结果如表2所示。

表2 f(ri)的取值结果

从线性代数的角度上来看，只要能在质因数模二值构成的向量中找到一个线性相关组，就能找到所需要的配对组合(x，y)。从表中可以看到，当f(ri)=72时，向量跟自身线性相关，于是可以得到72≡222≡42(mod 33)，从而可以计算出 gcd(7±4，33)=(3，11)，当向量跟自身不相关时，可以通过和别的向量组合，一起组成一个线性相关组，当把f(ri)等于52和62的质因数的模二值相加后，向量为(1，1，1，0，0)，正好与 f(ri)等于 32的向量线性相关，于是可以得到32≡(5×6)2(mod 33)，gcd(30 ±3，33)=(3，11)。

从以上的分析可以看出，二次筛法最主要的步骤就是通过筛选获取在因数基上平滑的数，然后通过计算找到线性相关的向量组，最后以一定概率分解大整数，广义数域筛法的主要步骤也大体如此。当然广义数域筛法也有着其自身的特点，对于那些大于130位的整数，广义数域筛法有着更高的分解效率，筛法中所选取的不可约多项式f(ri)的最高次数不再仅仅是二次，高次的多项式可以产生更多在因数基上平滑的数。在二次筛法中，f(ri)起到了一个桥梁的作用，他把整数Z映射到了n次剩余类，Z/n Z把一个在Z中的完全平方数映射到了一个在Z/n Z中的完全平方数，这种映射的方法在广义数域筛中也有着重要的作用，两者的不同点在于QS操作的数都是整数，映射是从Z到Z/n Z，而广义数域筛操作的数除了整数，还有环Z［α］，映射包括了两部分，一部分是从Z到Z/n Z，还有一部分是从Z［α］到Z/n Z，这部分映射用φ(β)来表示，这就使广义数域筛法相比二次筛法显得更加得复杂。

3 广义的数域筛法(GNFS)

广义的数域筛法的分解理论和技术包括多项式选择、筛选、矩阵形成和线性相关以及平方根的求解，同二次筛法一样，广义的数域筛法也是基于“同余式的平方组合”，目的是找到更多的配对组合(x，y)，从而分解大整数，正如上文提到的，广义的数域筛法的操作的数还包括环Z［α］，其中α是多项式f(x)的根，根的集合形成了集合ψ，在这个环Z［α］上能产生更多的平滑，于是广义的数域筛法产生配对组合(x，y)的两个基础方程分别为:

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

通过恒等式(5)可以看到，广义的数域筛法要想找到合适的配对组合(x，y)，就得找到足够的配对组合(a，b)，使得a+bθ在代数因数基Z上平滑，a+bm在有理数因数基Z上平滑，然后计算出(x，y)，以50%左右的可能性得到整数n的分解因式。

广义的数域筛法的分解步骤如下所示。

3.1 多项式选择

多项式的选择是广义数域筛法的第一步，它对整个筛法的耗时量和筛选的复杂程度有着重要的作用。

广义数域筛法一般会选取一个不可约的d阶多项式 f(x)，α为这多项式的一个复根，Z［α］≅Z［x］/f(x)，然后选取一个参数m∈Z/n Z，通过 Murphy的多项式选取法，使得f(m)≡0(mod N)，N为所要分解的大整数，令m为N的一个分解基，则N，其中 ci∈Z 并且 0≤ci≤m-1，当时，很容易得到，f(m)=N≡0(mod N)满足等式的要求。由映射φ:Z［α］→Z/n Z，得到φ(α)=m，这样就使Z［α］的值同整数有了对应关系。

在实践中，需要通过大量的实验，参数的细致调整，凭借经验，有时再加上点运气，才能寻找到一个最合适的多项式。一般来说，首先会确定多项式的次数d，d的大小由所要分解的大整数N的位数有关［4］，当分解50～80位的十进制整数时，会取d值为3;80～110位的十进制整数时，取d值为4;120～220为十进制整数时，取d值为5;当分解220～300位十进制整数时，取d值为6。然后确定参数m的值，通常取m值为或其附近的某一整数，多项式的选择有很多不确定因素，多项式的次数d的选取，参数m的取值都有很强的随机性，即使确定了一组d和m，多项式的系数还可以有不同的选择，只有通过实验，根据得到的合适的整数对(a，b)的数量才能确定多项式的好坏。

RSA-768的团队通过三个月的时间，从260个多项式中选出了3个符合要求的质量很高的多项式，而他们最终决定采用的多项式为

RSA-768的团队同时也选取了一个一阶的多项式用来在整数环上进行计算，多项式为

3.2 平滑和因数基

从二次筛法中可以看出，平滑和因数基是筛法的基础，通过找到足够多的在因数基上平滑的数，才能顺利分解大整数，广义的数域筛法也是这样，不过因为其不光在整数域上操作，还要在环Z［α］上操作，所以在环Z［α］对于平滑和因数基就有了新的定义，因数基不再是Z［α］中的素数，而是其理想。

α是多项式的根，定义 N(α)=σ1(α)σ2(α)σ3(α)…σd(α)，其中 σi是从 Q［θ］到 C 的映射，D 为一绰金环，P为D的一个素理想，p代表一些素数，当N(P)=p时，定义P为D的第一阶素理想，当r属于 Z/p Z，并且 f(r)≡0(mod p)时，集合(r，p)同第一阶素理想的集合一一映射，理想p决定了组合(r，p)，广义数域筛法要找的因数基就是集合(r，p)。

广义数域筛法中定义了三个因数基，为有理数因数基、代数因数基和二次特征基。

有理数因数基跟二次筛法中的因数基一样，都是在整数域上操作，通过对(a，b)的取值，找到在a+bm上平滑的值，为了和代数因数基和二次特征基的形式保持一致，在实践中一般选取因数基的形式为(m(mod p)，p)。

上文提到过不可约多项式f(x)根形成的集合为O，由数论的相关知识可知，环O是一个绰金环，它的一些理想可以被分解为素理想，从O的理想中选取一个集合I，这个集合I就被称为代数因数基，然后找一对组合(a，b)，使得a+bθ有一个主理想，能完全分解成I上的素理想，这样的元素a+bθ就被称为在I上平滑。

二次特征基是用来确定a+bθ在Z［θ］上是否为一个完全平方数，广义数域筛法的一个基础方程为

给定一个第一阶素理想Q，它决定了组合(s，q)，当Q不能分解主理想〈a+bθ〉，并且f'(s)≠0(mod q)时，也就是说，如果a+bθ在Z［θ］上是一个完全平方数，那么当然这是一个必要条件，不是说当等式成立时，a+bθ就一定是完全平方数，通常在实际计算的时候，q会取比p大一点的值。

3.3 筛选

筛选是广义数域筛法中最重要也是最耗时的步骤之一，可以通过并行处理的方式提高效率，筛选的目的是要得到足够多的整数对(a，b)，使得a+bm在有理数因数基Z上平滑，a+bθ在代数因数基Z［θ］上平滑，而对两者筛选的方法大体一致。

对于a+bm来说，m已经在上文确定，还有两个变量a和b，当固定b的值(通常先取b=1)，再取-u＜a＜u(u是a的取值的范围，可视情况而定)，a从-u开始一直取到u，通过计算得到能使a+bm在因数基上平滑的组合(a，b)，当取完a的值发现组合还不够时，增加b的值直到组合够为止，这种方法需要计算每个a+bm的值是否平滑，很消耗时间。在实际中一般会固定一个因数基里的素数p和一个正整数b，当a+bm≡0(mod p)，也就是a≡-bm(mod p)的时候，p就能分解，a+bm那么在筛选的时候，在-u到u的范围内取满足等式a=-bm+kp的a的值就可以了，这就大大提高了效率。

a+bθ的筛选是在代数因数基上进行的，是要通过第一阶素理想P来分解主理想〈a+bθ〉，而P可以由组合(r，p)决定，当a≡-br(mod p)的时候，p能分解，N(a+bθ)而当 p能分解 N(a+bθ)的时候，第一阶素理想P也就能分解主理想〈a+bθ〉，于是筛选的方法就是固定b的值和组合(r，p)，取a≡-br+kp，并且 -u ＜a＜ u，然后计算 N(a+bθ)的值，当值能被p分解时，(a，b)就是筛选出来的可用的整数对。

通过筛选，RSA-768的团队总共获取了64334489730对合适的组合，然后通过分布式筛选理论，其中有24.7%的组合是重复记录的，然后通过一种判别算法，删去那些包含素数(小概率出现)的组合，于是就只剩下2458248361对组合，只占原来的3.4%。

3.4 矩阵生成及过滤

通过筛选，得到了I对整数对(a，b)，接下来就要构建一个矩阵，假设有理数因数基有k个素数，代数因数基有l个第一阶素理想，二次特征基有m个第一阶素理想，则矩阵应该有k+l+m+1行，列数为I，矩阵的每一列都由一对整数对(a，b)决定，构建矩阵的最终目的是寻找到矩阵列与列之间的线性相关性，从而找到不同的 a+bm，〈a+bθ〉和 a+bθ，使他们的乘积值为完全平方数。

每一列矩阵都是由四部分组成，第一部分就一位，它表示a+bm的正负性，正的话为0，负的话为1;第二部分有k位，有理数因数基中的素数有k个，a+bm由这些素数分解后素数的指数模二的值就对应了该k位，假设因数基为{2，3，5}，选定的整数对为(3，1)，m 为27，则 a+bm=30=2 ×3×5，前 k位就为(1，1，1);第三部分有l位，代数因数基中有一对(r，p)，通过公式 N(a+bθ)=(-b)df(-a/b)计算出 N(a+bθ)的值，把 N(a+bθ)分解得到 p，当 a≡-br(mod p)时，记该位为1;第四部分有m位，由二次特征基决定，当满足公式时，值为0，否则为1.

以上生成的是一个原始矩阵，矩阵维数和重量会直接决定线性相关求解的时间，原始矩阵显然不是最合适的矩阵，必须通过相应的过滤方法，减小矩阵的维数，同时控制重量的增长，使两者达到一个最佳平衡点，这样能大大提高分解效率。

3.5 线性相关

当最佳矩阵找到后，就得通过计算得到矩阵列向量之间的线性相关性了，这也可以理解为求解一个大规模稀疏线性方程组，用传统的高斯消元法去处理一个维数很大的矩阵时会消耗很多时间，不能被采用，目前最常用的求解的方法为 Lanczos和Wiedemann算法［5］，寻找线性相关性的这一步是数域筛法中耗时最多的步骤之一，实际中通常会采用并行处理。

RSA-768的团队最后生成了一个192796550*192795550的矩阵，矩阵的重量为27797115920，也就是说每行平均有144个非0数，通过119天的计算，团队最终在2009年的十月八号完成了矩阵的计算，得到了能使矩阵列向量线性相关的组合。

3.6 平方根的求解

用广义数域筛法分解大整数，利用的是“同余式的平方组合”，这就需要利用LLL算法或是Montgomery的算法［6］，来求解整数的平方根，同过大规模稀疏线性方程组的求解，就能找到对应的平方关系，这些平方关系都是由几对组合(a，b)确定的，通过组合(a，b)得到，而β2=f'(θ)2·α2，从而计算出 β 的含 θ的多项式 f2(θ)，于是 x=f2(m)≡φ(β)(mod N);通过组合(a，b)得，而 y2=f'(m)2·Z2，通过平方根的求解就能得到y的值。

4 结论

本文讨论了数域筛法中广义数域筛法的基本理论，从中可以看出，广义数域筛法的分解步骤是相对固定的，首先要选择一个合适的多项式，多项式质量的好坏决定了筛选的效率，然后要确定三个因数基，以平滑为标准进行筛选，筛选可以采取并行处理［7］，当筛选出有效的组合后，就可以组成一个矩阵，并对其进行处理，找到线性相关的列向量，这一步骤计算量很大，需进行并行处理，通过平方根的求解，得到组合(x，y)，最终以50%左右的可能性完成对大整数的分解。

对于广义数域筛法来说，虽然还存有很多问题需要解决，但作为目前对大整数分解最快的方法，通过硬件设备和算法的改良，其每一分解步骤都有改进的空间，从而能够更加高效的完成大整数的分解，从而完成对公钥加密算法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］ 王洪涛，刘春雷.数域筛法中多项式的选择［J］.信息工程大学学报，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］ 颜松远.整数分解［M］.北京:科学出版社，2009.