RSA算法研究及其抗攻击风险量化分析

王 昆 廖竞

摘要：网络安全是网络建设研究的一个重要方面。本文重点分析了广泛用于数字签名的RSA算法的原理和安全性。同时做了RSA算法的抗攻击风险量化分析。 关键词：数字签名 RSA算法 密钥

公开密钥算法是在1976年由当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)两人首先发明的（论文\"New Direction in Cryptography\"）。但目前最流行的RSA是由分别取自三位发明此算法的数学家（Ronald Rivest, Adi Shamir 和Len Adleman）的名字的第一个字母来构成的。它既能用于加密也能用于数字签名。

——RSA算法研制的最初理念与目标是旨在解决DES算法秘密密钥利用公开信道传输分发困难的难题。而实际结果不但很好地解决了这个难题；还可利用RSA来完成对电文的数字签名以对抗电文的否认与抵赖；同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完整性。 一、RSA算法的原理

首先,找出三个数,其中p,q是两个相异的质数,r是与(p-1)(q-1)互质的数，这三个数便是私钥。接着,找出m,使得rm==1MOD(p-1)*(q-1)这个m一定存在,因为r与(p-1)(q-1)互质,用辗转相除法就可以得到。再来,计算n=p*q,m,n这两个数便是公钥。编码过程是:若资料为a,将其看成是一个大整数,假设a=n的话,就将a表成s进位(s<=n,通常取s=2^t),则每一位数均小于n,然后分段编码接下来,计算

b==a^mMODn,(0<=b如果第三者进行窃听时,他会得到几个数:m,n(=p*q),b他如果要解码的话,必须想办法得到r所以,他必须先对n作质因数分解,要防止他分解,最有效的方法是找两个非常的大质数p,q,使第三者作因数分解时发生困难。 <定理>

若p,q是相异质数,rm==1MOD(p-1)(q-1),a是任意一个正整数b==a^mMODp*q,c==b^rMODp*q, 则c==aMODp*q

证明的过程,会用到费尔马小定理,叙述如下：

m是任一质数,n是任一整数,则n^m==nMODm 换另一句话说,如果n和m互质,则n^(m-1)==1MODm)。运用一些基本的群论的知识,就可以很容易地证出费尔马小定理； <证明>

因为rm==1MOD(p-1)(q-1)

所以rm=k(p-1)(q-1)+1,其中k是整数,因为在modulo中是preserve乘法的x==yMODz and u==vMODz =>xu==yvMODz),

所以,c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1)+1)MODp*q 1、 如果a不是p的倍数,也不是q的倍数时,

则a^(p-1)==1MODp(费尔马小定理)==>a^(k(p-1)(q-1))==1MODp a^(q-1)==1MODq(费尔马小定理)=>a^(k(p-1)(q-1))==1MODq 所以p,q均能整除a^(k(p-1)(q-1))-1=>pq|a^(k(p-1)(q-1))-1, 即a^(k(p-1)(q-1))==1MODp*q ==>c==a^(k(p-1)(q-1)+1)==aMODp*q 2、 如果a是p的倍数,但不是q的倍数时 则a^(q-1)==1MODq(费尔马小定理)

=>a^(k(p-1)(q-1))==1MODq=>c==a^(k(p-1)(q-1)+1)==aMODq=>q|c-a 因p|a=>c==a^(k(p-1)(q-1)+1)==0MODp=>p|c-a 所以,p*q|c-a=>c==aMODp*q

3、 如果a是q的倍数,但不是p的倍数时,证明同上。 4、 如果a同时是p和q的倍数时,则

p*q|a=>c==a^(k(p-1)(q-1)+1)==0MODp*q>p*q|c-a=>c==aMODp*q

这个定理说明a经过编码为b再经过解码为c时,a==cMODn(n=p*q)但我们在做编码解码时,限制0<=aRSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数n必须选得大一些，因具体适用情况而定。 当然也可以通过猜测(p-1)(q-1)的值来攻击RSA。但这种攻击没有分解n容易

有些攻击专门针对RSA的实现。他们不攻击基本的算法，而是攻击协议。仅会使用RSA而不重视它的实现是不够的。实现细节也很重要。这就是对RSA的选择密文攻击。RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装(Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构： (XM)^d = X^d *M^d mod n

前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-Way HashFunction 对文档作HASH处理，或同时使用不同的签名算法。

还有一种就是对RSA的公共模数攻击。若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那末该信息无需私钥就可得到恢复。设P为信息明文，两个加密密钥为e1和e2，公共模数是n，则： C1 = P^e1 mod n7 C2 = P^e2 mod n

密码分析者知道n、e1、e2、C1和C2，就能得到P。

因为e1和e2互质，故用Euclidean算法能找到r和s，满足： r * e1 + s * e2 = 1

假设r为负数，需再用Euclidean算法计算C1^(-1)，则 ( C1^(-1) )^(-r) * C2^s = P mod n

另外，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对e和d，一是有利于攻击者分解模数，一是有利于攻击者计算出其它成对的e和d，而无需分解模数。解决办法只有一个，那就是不要共享模数n。

三、RSA算法的抗攻击风险量化分析

我们知道RSA的安全性依赖于大数的因子分解。以下列出美国麻省理工学院RSA129（

N=10

129

素因子分

解攻击研究小组Hal Abelson, Jeff Schiller, Brian lamacchia和Derek Atkins. 根据他们对PGP RSA（MPQS）算法攻击研究的结果如下；

——RSA-129 (429-bit key) 4600 MIPS-YEARS

——即相当于要4600台VAX11/780联合运行一年的时间或一台Pentium100运行46年时间才能将一个N*10129的大数分解找到其P.Q.

1994年前人们常用二次筛选算法进行分解。但是到了今天数学家用一种新的因子分解算法取代了二次筛选法：一般数域筛选法。表一给出了应用该算法对一系列不同大小的数进行因子分解所需的MIPS-YEARS

[5]

位 512 768 1024 1280 1536 2048 进行因子分解所需的mips-year 30000 2*108 3*1011 1*1014 3*1016 3*1020 表 一 利用一般数域筛选法进行因子分解

一般数域分解法的速度仍在加快，其中与其相关的一个算法：特殊数域筛选法，它的速度比一般数域筛选法还要快。表二给出了用该算法对一系列不同大小的数进行因子分解所需的MIPS-YEARS

[5]

位 512 768 1024 1280 1536 2048 进行因子分解所需的mips-year <200 100000 3*107 3*109 2*1011 4*1014 表二 利用特殊数域筛选法进行因子分解

在选择公开密钥长度时，你必须考虑想要的安全性和密钥的生命周期，以及了解当前因子分解的发展水平。今天使用1024位的数仅能获得80年代初期512位的安全性。当然，我们也必须考虑密钥变长所付出的计算时间的代价，通常是想密钥足够长所需时间足够短。同时，在不同的应用场合密钥要求的长度也不同。通过我的大量实验，分别针对个人，大公司和政府的安全要求，就近20年RSA算法密钥长度应该多长提出我的预测。表三给出了RSA算法密钥长度的推荐值（位）。

年度 1995 2000 2005 2010 2015 对于个人 768 1024 1280 1280 1536 对于公司 1280 1280 1536 1536 2048 对于政府 1536 1536 2048 2048 2048 表三 RSA算法密钥长度的推荐值（位）

——从以上的分析结果表明，选取RSA密钥长度大于500bits时是安全的。考虑到算法的发展和计算机的计算能力的提高。我提出一些个人的看法：对于个人一般可取1024bits，对于公司和政府最好取2048bits。 四、RSA算法的安全管理：

——1)要严格管理、保存好自已的PIN IC卡。如PIN的物理保护失败，或私钥丢失与用户的口令被窃同时发生时，用户应及时挂失。 ——2)密钥的更换周期

——现代密码学的特征是算法可以公开。保密的关键是如何保护好自己的密钥，而破密的关键则是如何能破解得到密钥。

——系统的安全主管者，要根据本系统实际所使用的密钥长度与其所保护的信息的敏感程度、重要程度以及系统实际所处安全环境的恶劣程度，参照以上的分析数据，在留有足够的安全系数的条件下来确定其密钥和证书更换周期的长短。同时，将已废弃的密钥和证书放入黑库归档，以备可能后用。密钥更换周期的正确安全策略是系统能够安全运行的有力保障，是系统的安全管理者最重要、最核心的日常工作任务。 结束语：

RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。但RSA也有它的缺点，主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。 参考文献：

[1]黄叔武,杨一平主编.计算机网络工程教程[Ｍ].北京:清化大学出版社,2000.3. [2]美·Don Slice著.专业ＩＰ网络规划与设计[Ｍ].北京:希望电子出版社,2000.2.

[3]意·SilvanoGai著.ＩＰｖ6网络互连与Ｃｉｓｃｏ路由器[Ｍ].北京:机械工业出版社,1999.11. [4]美·Bruce Schneier 著.应用密码学 协议、算法与C源程序[Ｍ] 北京机械工业出版社 2001 3 [5]A.Odlyzko,\"Progress in Integer Faxtorization and Discrete Logarithms,\" unpublished manuscript, Feb 1995