安全技术—RSA公钥密码体制安全性分析

引言

 RSA密码系统是较早提出的一种公开钥密码系统。1978年，美国麻省理工学院（MIT）的Rivest,Shamir和Adleman在题为《获得数字签名和公开钥密码系统的方法》的论文中提出了基于数论的非对称(公开钥)密码体制，称为RSA密码体制。RSA是建立在“大整数的素因子分解是困难问题”基础上的，是一种分组密码体制。

 介绍公钥密码体制（背景）

 1、对称密码体制

 对称密码体制是一种传统密码体制，也称为私钥密码体制。在对称加密系统中，加密和解密采用相同的密钥。因为加解密密钥相同，需要通信的双方必须选择和保存他们共同的密钥，各方必须信任对方不会将密钥泄密出去，这样就可以实现数据的机密性和完整性。对于具有n个用户的网络，需要n(n-1)/2个密钥，在用户群不是很大的情况下，对称加密系统是有效的。但是对于大型网络，当用户群很大，分布很广时，密钥的分配和保存就成了问题。对机密信息进行加密和验证随报文一起发送报文摘要(或散列值)来实现。比较典型的算法有DES(Data Encryption Standard数据加密标准)算法及其变形Triple DES(三重DES)，GDES(广义DES)；欧洲的IDEA；日本的FEAL N、RC5等。DES标准由美国国家标准局提出,主要应用于银行业的电子资金转帐(EFT)领域。DES的密钥长度为56bit。Triple DES使用两个独立的56bit密钥对交换的信息进行3次加密，从而使其有效长度达到112bit。RC2和RC4方法是RSA数据安全公司的对称加密专利算法，它们采用可变密钥长度的算法。通过规定不同的密钥长度,，C2和RC4能够提高或降低安全的程度。对称密码算法的优点是计算开销小，加密速度快，是目前用于信息加密的主要算法。它的局限性在于它存在着通信的贸易双方之间确保密钥安全交换的问题。此外，某一贸易方有几个贸易关系，他就要维护几个专用密钥。它也没法鉴别贸易发起方或贸易最终方，因为贸易的双方的密钥相同。另外，由于对称加密系统仅能用于对数据进行加解密处理，提供数据的机密性，不能用于数字签名。因而人们迫切需要寻找新的密码体制。

 2、非对称密码体制

 非对称密码体制也叫公钥加密技术，该技术就是针对私钥密码体制的缺陷被提出来的。在公钥加密系统中，加密和解密是相对独立的，加密和解密会使用两把不同的密钥，加密密钥(公开密钥)向公众公开，谁都可以使用，解密密钥(秘密密钥)只有解密人自己知道，非法使用者根据公开的加密密钥无法推算出解密密钥，顾其可称为公钥密码体制。如果一个人选择并公布了他的公钥，另外任何人都可以用这一公钥来加密传送给那个人的消息。私钥是秘密保存的，只有私钥的所有者才能利用私钥对密文进行解密。公钥密码体制的算法中最著名的代表是RSA系统，此外还有:背包密码、McEliece密码、Diffe_Hellman、Rabin、零知识证明、椭圆曲线、EIGamal算法等。公钥密钥的密钥管理比较简单,并且可以方便的实现数字签名和验证。但算法复杂,加密数据的速率较低。公钥加密系统不存在对称加密系统中密钥的分配和保存问题，对于具有n个用户的网络，仅需要2n个密钥。公钥加密系统除了用于数据加密外，还可用于数字签名。公钥加密系统可提供以下功能：A、机密性（Confidentiality）：保证非授权人员不能非法获取信息，通过数据加密来实现；B、确认（Authentication）：保证对方属于所声称的实体，通过数字签名来实现；C、数据完整性（Data integrity）：保证信息内容不被篡改，入侵者不可能用假消息代替合法消息，通过数字签名来实现；D、不可抵赖性（Nonrepudiation）：发送者不可能事后否认他发送过消息，消息的接受者可以向中立的第三方证实所指的发送者确实发出了消息，通过数字签名来实现。可见公钥加密系统满足信息安全的所有主要目标。

 RSA公钥密码体制的优势（意义）

1 解决大规模网络应用中密钥的分发和管理问题

 采用分组密码、序列密码等对称密码体制时，加解密双方所用的密钥都是秘密的，而且需要定期更换，新的密钥总是要通过某种秘密渠道分配给使用方，在传递的过程中，稍有不慎，就容易泄露。

 公钥密码加密密钥通常是公开的，而解密密钥是秘密的，由用户自己保存，不需要往返交换和传递，大大减少了密钥泄露的危险性。同时，在网络通信中使用对称密码体制时，网络内任何两个用户都需要使用互不相同的密钥，只有这样，才能保证不被第三方窃听，因而N个用户就要使用N（N–1）/2个密钥。在大型网络中，如果有100万个用户，则要使用4950万个密钥，密钥量太大，难以管理，而且使用起来非常麻烦。采用公钥密码体制，N个用户只需要产生N对密钥。仍以100万个用户为例，只需100万对密钥，需要秘密保存的仅100万个私钥，二者相差近50倍，数量大大减少，而且分发简单，安全性好。由此可见，只有公钥密码才能方便、可靠地解决大规模网络应用中密钥的分发和管理问题。

 2 实现网络中的数字签名机制

 对称密钥技术由于其自身的局限性，无法提供网络中的数字签名。这是因为数字签名是网络中表征人或机构的真实性的重要手段，数字签名的数据需要有惟一性、私有性，而对称密钥技术中的密钥至少需要在交互双方之间共享，因此，不满足惟一性、私有性，无法用做网络中的数字签名。相比之下，公钥密码技术由于存在一对公钥和私钥，私钥可以表征惟一性和私有性，而且经私钥加密的数据只能用与之对应的公钥来验证，其他人无法仿冒，所以，可以用做网络中的数字签名服务。

 具体而言，一段消息以发送方的私钥加密之后，任何拥有与该私钥相对应的公钥的人均可将它解密。由于该私钥只有发送方拥有，且该私钥是密藏不公开的，所以，以该私钥加密的信息可看做发送方对该信息的签名，其作用和现实中的手工签名一样有效而且具有不可抵赖性。

 一种具体的做法是：认证服务器和用户各持有自己的证书，用户端将一个随机数用自己的私钥签名后和证书一起用服务器的公钥加密后传输到服务器；使用服务器的公钥加密保证了只有认证服务器才能进行解密，使用用户的密钥签名保证了数据是由该用户发出；服务器收到用户端数据后，首先用自己的私钥解密，取出用户的证书后，使用用户的公钥进行解密，若成功，则到用户数据库中检索该用户及其权限信息，将认证成功的信息和用户端传来的随机数用服务器的私钥签名后，使用用户的公钥进行加密，然后，传回给用户端，用户端解密后即可得到认证成功的信息。

 介绍RSA公钥密码体制

 RSA是Rivest,Shamir,Adleman提出基于数论的非对称密钥体制。RSA是建立在大整数分解的困难上的,是一种分组密码体制。它是以推广的欧拉定理为基础的（见下）：

 定理1 若(a,n)=1, 则 ＝(mod n) ,其中φ(n) 表示不超过n与n互素的正整数个数。

 定理2 若(m1,m2)=1，则φ(m1 • m2)=φ(m1) • φ(m2)。

 定理3 若p为素数，则φ(p)=p-1。

 RSA建立方法如下:

 •首先随机选两个大素数p,q , 计算n=p • q；

 •计算欧拉函数 φ(n)=(p-1)(q-1)；

 •任选一个整数e为公开加密密钥，由e求出秘密解密密钥d：d • e＝ 1 mod φ(n)＝ k

 'φ(n) +1

 •加密/解密：

 将明文分成长度小于 位的明文块m，

 加密过程是：c = E(m，e) = mod n

 解密过程是：m = D(c，d) = mod n

 在RSA体制下： D(d, E(m，e)) o = o m mod n

 E(e, D(d,m)) o = o m mod n

 e,d可以互换。在用于数字签名时,发送方只须用己方的解密密钥d先 "加密"即可, 因为只有发送方自己知道自己的d, 收方只有用对应的e "解密"

 才能知道明文, 同时也验证了发方的身份。

 RSA公钥密码体制的安全性分析

 RSA的安全性依赖于大整数的因式分解问题。实际上，人们推测RSA的安全性依赖于大整数的因式分解问题，但谁也没有在数学上证明从c和e计算m需要对n进行因式分解。可以想象可能会有完全不同的方式去分析RSA。然而，如果这种方法能让密码解析员推导出d，则它也可以用作大整数因式分解的新方法。最难以令人置信的是，有些RSA变体已经被证明与因式分解同样困难。甚至从RSA加密的密文中恢复出某些特定的位也与解密整个消息同样困难。另外，对RSA的具体实现存在一些针对协议而不是针对基本算法的攻击方法。

 攻击者对RSA系统攻击的目标可以分为三类：

 设计RSA系统的注意事项

 1经过对RSA安全性的分析，可以得出使用RSA时应该注意的事项：

 •随机选择足够大素数（目前应在512位以上）；

 •在使用RSA的通信网络协议中，不应该使用公共模（使用者知道f(n)）；

 •不要让攻击者得到原始的解密结果；

 •解密密钥d相对模数n来说不应过小；

 •应该或者加密密钥大；或者被加密的信息m总是大而且m不能是一些已知值的乘积，后面一种情况可以在加密前对m填充随机值实现。

 •相关的消息不能用同样的密钥加密，加密前对消息进行随机值填充破坏消息之间的代数联系及相关性，但是要注意填充算法的选择；

 •应该使获得对任意值的原始签名不可能。

 •被签名的消息应该与模数差不多大，而且不是一些已知值的乘积；

 •使用平均解密时间和混乱(blinding)等方法使时间攻击中使用的统计手段失效；

 •如果有条件，采用规模差别比较大的质因子p,q来提高系统的安全性；

 2 RSA系统的参数选择

 RSA系统是第一个将安全性植基于因子分解的系统。很明显地，在公开密钥（e,N）中，若N能被因子分解，则在模N中所有元素价的最小公倍数（即所谓陷门）T=φ(N)=(p-1)(q-1)即无从隐藏。使得解密密钥d不再是秘密，进而整个RSA系统即不安全。虽然迄今人们尚无法“证明”，破解RSA系统等于因子分解。但一般“相信”RSA系统的安全性，等价于因子分解。即：若能分解因子N，即攻破RSA系统；

 若能攻破RSA系统，即分解因子N（相信，但未证明）

 因此，在使用RSA系统时，对于公开密钥N的选择非常重要。必须使得公开N后，任何人无法从N得到T。此外，对于公开密钥e与解密密钥d，亦需有所限制。否则在使用上可能会导致RSA系统被攻破，或应用在密码协议上不安全。

 经过分析，我们知道RSA系统安全性与系统的参数有很大关系，X.931标准对此提出以下几点：

 •如果公钥e是奇数，e应与p-1，q-1互质；

 •如果公钥e是偶数，e必须与(p-1)/2,(q-1)/2互质，且poq mod 8不成立；

 •模数的长应该为1024+256x，x=0,1• • • • • • ；

 •质数p，q应通过质数检测，使出错的概率小于 ；

 •p-1,q-1,p+1,q+1应有大质数因子；

 •gcd(p-1,q-1)应该小；

 •p/q不应靠近两个小整数比值，且 ；

 •|p-q|应有大质数因子。

 RSA公钥密码体制的应用

 1数字签名

 长期以来的日常生活中，对于重要的文件，为了防止对文件的否认，伪造，篡改等等的破坏，传统的方法是在文件上手写签名。但是在计算机系统中无法使用手写签名，而代之对应的数字签名机制。数字签名应该能实现手写签名的作用，其本质特征就是仅能利用签名者的私有信息产生签名。因此，当它被验证时，它也能被信任的第三方（如法官）在任一时刻证明只有私有信息的唯一掌握者才能产生此签名。

 数字签名具有以下特点：

 •签名是可信的；

 •签名是不能伪造的；

 •签名是不可重用的；

 •签名后的文件是不能更改的；

 •签名是不能否认的。

 由于非对称密码体制的特点，对于数字签名的实现比在对称密码体制下要有效和简单的多。

 2 RSA公钥签名技术

 数字签名可以用秘密密钥利，也可用公开密钥。但采用秘密密钥是建立在有一个众人信任的中间机构的基础上，而采用公钥加密法进行数字签名则不受此限制，收发两方之间不需要任何可信赖机构。假定公开密钥加密和解密算法除了满足D（E（P））=P外，还能满足E（D（P））=P（RSA满足这两个条件，所以这个假定并不是不现实的）。那么发方A就可以通过EB（DA（P））的转换，将一条签名的明文信息P发给收方B。注意，A知道自己的私有解密密钥DA，还知道B的公开密钥EB，所以建立这条信息的工作应由A来做。

 当B收到这条消息后，他象往常一样用自己的私有密钥将它解密，得到DA（P），如图所示。他将这条信息放在一个安全的地方，然后用EA解密，得到初始的明文。

 要了解这种签名是如何工作的，现在假设A后来否认曾经发送消息P给B。当案子上了法庭，B能够出示P和 DA(P)。法官只要使用一下EA，就能轻易地证明B确实有一条用DA加密的有效信息。由于B不知道A的私有密钥，B能得到用它加密的唯一途径就是A发送过来的。

 需要说明的是，虽然使用公开密钥加密法进行数字签名的是一个很好的方法，但仍有一些问题存在于它们所应用的环境而不是算法。只有当

DA保密时，B才能证明某条信息是A发送来的。如果A公开了它的私有密钥，那么证据就不成立了，因为任何人包括B都可以发送这条消息。

 网络技术的发展使得，电子商务正在广泛开展，电子邮件也被普遍使用，数字签名技术越来越重要。RSA虽然有算法复杂，速度慢的缺点，但目前还是被广泛的应用于数字签名中。随着计算机技术的发展及对RSA的深入研究，目前RSA正在走向实用化，商业化,可以预见在网络安全中，基于RSA的网络安全系统的设计将会广泛使用。