广义数域筛法对公钥加密算法的攻击
2012-09-20侯方天张雅琨
中国传媒大学学报(自然科学版) 2012年3期
侯方天,张雅琨
(中国传媒大学信息工程学院,北京市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)
二次筛法与数域筛法有着相似的理论基础,为了更好的理解数域筛法,我们首先来研究一下二次筛法。……
登录APP查看全文
