公钥加密RSA算法在信息安全中的作用

本文介绍了当今社会对信息安全技术的需求，谈了自己对信息安全的看法。然后讨论目前流行的公钥加密算法RSA的技术要点及其安全性的几个问题，最后概括了RSA的使用情况，并且指出RSA方法发展方向。

一、引言

　　从古人挥舞着大刀长枪的战争开始，信息就是军队统帅战胜敌人的要决。但是，保密的需要不仅是战争的专利。互联网的出现，正在不可阻挡的改变着世界上的一切，如果没有制衡力量，在未来的几十年中，可能我们的一言一行都会被监视、被记录、并被分析——这些终于让人们认识到必须把“保密”作为一个独立的学科，再调用一批卓越的科学家和深奥的理论去研究。

　　现代密码术的划时代突破，是威特菲尔德·迪菲(WhitfieldDiffie)和马丁·海尔曼(MartinHellman)有关公开密钥加密系统的构想，这是在1976年发表的。但威特菲尔德·迪菲和马丁·海尔曼提供的MH背包算法于1984年被破译，因而失去了实际意义。真正有生命力的公开密钥加密系统算法是由隆·里维斯特()、阿迪·沙米尔(AdiShamir)和雷奥纳德·阿德尔曼(n)在威特菲尔德·迪菲和马丁·海尔曼的论文的启发下，在1977年发明的，这就是沿用至今的RSA算法。它是第一个既能用于数据加密也能用于数字签名的算法。

　　二、公钥加密算法RSA

　　传统的加密技术都是秘密密钥加密技术，也称单密钥加密技术。在公开密钥加密技术中，加密密钥与解密密钥是不一样的。加密者可以将加密密钥公开，成为公开密钥，而仍将解密密钥保密，作为秘密密钥。下面就要描述RSA加密算法的流程：

　　首先，找出三个数：p、q、r，其中p和q是两个相异的质数，r是与(p-1)(q-1)互质的数。

　　接着，找出e，使得re≡1mod(p-1)(q-1)。这个e一定存在，因为r与(p-1)(q-1)互质，用辗转相除法就可以得到了。

　　再来，计算n=pq。(n，e)便是publickey。(n，r)就是privatekey。

　　p和q应该被销毁掉(PGP为了用中国的同余理论加快加密运算保留了p和q，不过它们是用IDEA加密过再存放的)

　　加密的过程是，若待加密信息为a，将其看成是一个大整数，假设a=n的话，就将a表成s进位(s<=n，通常取s=2^t)，则每一位数均小于n，然後分段编码。

　　接下来，计算C≡aemodn，(0<=C　　解码的过程是，计算M≡brmodC(0<=c　　如果第三者进行窃听时，他会得到几个数：m，n(=pq)，b。他如果要解码的话，必须想办法得到r。所以，他必须先对n作质因数分解。如果他能够成功的分解n，得到这两个质数p和q，那么就表明此算法被攻破。一般说来，许多数学中的函数都有“单向性”，这就是说，有许多运算本身并不难，但如果你想把它倒回去，作逆运算，对于RSA来说，用公开密钥加密后，如果想再通过公开密钥解密是很困难的。这个困难性就表现在对n的因式分解上。若n=pq被因式分解，(p-1)(q-1)就可以算出，继而算出解密密钥m。所以RSA算法的基础就是一个假设：对n的因式分解是很困难的。

　　RSA算法在理论上的重大缺陷就是并不能证明分解因数绝对是如此之困难，也许我们日后可以找到一种能够快速分解大数的因数的算法，从而使RSA算法失效。如果有人偶然发现了快速将大数分解因数的方法，并将其保密，则他有可能在一段时间内获得极为巨大的力量。

　　目前RSA被广泛应用于各种安全或认证领域，如web服务器和浏览器信息安全、Email的安全和认证、对远程登录的安全保证和各种电子信用卡系统的核心。

　　与单钥加密方法比较，RSA的缺点就是运算较慢。用RSA方法加密、解密、签名和认证都是一系列求模幂运算组成的。在实际应用中，经常选择一个较小的公钥或者一个组织使用同一个公钥，而组织中不同的人使用不同的n。这些措施使得加密快于解密而认证快于签名。一些快速的算法比如基于快速傅立叶变换的方法可以有效减少计算步骤，但是在实际中这些算法由于太复杂而不能广泛的使用，而且对于一些典型的密钥长度它们可能会更慢。

　　三、RSA算法的安全性

　　若n被因式分解成功，则RSA便被攻破。还不能证明对RSA攻击的难度和分解n的难度相当，但也没有比因式分解n更好的攻击方法。已知n，求得Φ(n)(n的欧拉函数)，则p和q可以求得。因为根据欧拉定理，Φ(n)=(p-1)(q-1)=pq–(p+q)+1。和(p–q)2= (p+q)2-4pq;据此列出方程，求得p和q。

　　另一个攻击RSA的方法是根据C≡aemodn来计算C1/emodn。这种攻击方式没有一种普遍的实现方法，也不知道是否其难度与对n因式分解相当。但是在一些特殊的情况下，当多个相关的信息用同样的密钥加密时，可能很容易被攻破。

　　为安全起见，对p和q要求：p和q的相差不大;(p-1)和(q-1)有大素数因子;gcd(p-1，q-1)很小，满足这样条件的素数称做安全素数。RSA的出现使得大整数分解因式这一古老的问题再次被重视，近些年来出现的不少比较高级的因数分解方法使“安全素数”的概念也在不停的演化。所以，选择传统上认为是“安全素数”并不一定有效的增加安全性，比较保险的方法就是选择足够大的素数。因为数越大，对其分解因式的难度也就越大!对n和密钥长度的选择取决于用户保密的需要。密钥长度越大，安全性也就越高，但是相应的计算速度也就越慢。由于高速计算机的出现，以前认为已经很具安全性的512位密钥长度已经不再满足人们的需要。

　　RSA的安全性并不能仅靠密钥的长度来保证。在RSA算法中，还有一种值得注意的现象，那就是存在一些n=pq，使得待加密消息经过若干次RSA变换后就会恢复成原文。这不能不说是RSA本身具有的一个缺点，选择密钥时必须注意避免这种数。

　　四、结语

　　RSA方法即可用于保密，也能用于签名和认证，目前已经广泛应用于各种产品、平台等软件上。许多流行的操作系统上如微软、Apple、Sun 和Novell都在其产品上融入了RSA。在硬件上，如安全电话、以太网卡和智能卡都使用了RSA技术。而且几乎所有Internet安全协议如 S/MIME，SSL和S/WAN都引入了RSA加密方法。ISO9796标准把RSA列为一种兼容的加密算法。可以预见，在不远的几年内，RSA的应用将会越来越广泛。