摘要

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

引论

    “秘密是一种力量。保护一个秘密，保留一个人的隐私的能力是一种力量。刺探秘密、了解秘密、利用秘密的能力也是一种力量。秘密给予人力量，秘密保护人，秘密损害人。在一个人不知情的情况下了解他的秘密——秘密地刺探另一个人的秘密——的能力，是一种更为强大的力量。”

从古人挥舞着大刀长枪的战争开始，信息就是军队统帅战胜敌人的要决。但是，保密的需要不仅是战争的专利。尤其在现代，从一个庞大的国家或者国家集团到走在大街上的一个寻常的人，都有其不希望任何别人知道的秘密。随着科技的发达，信息技术正在改变着世界上的一切。尤其是互联网的出现，正在不可阻挡的改变着世界上的一切。按照一些人的说法，如果没有制衡力量，在未来的几十年中，可能我们的一言一行都会被监视、被记录、并被分析——这些终于让人们认识到必须把“保密”作为一个独立的学科，再调用一批卓越的科学家和许许多多深奥的数学理论去研究。

另一方面，信息技术包括保密技术的发展也使得在极大规模上的信息交流可以秘密进行。这些交流包括正常的有利于社会的活动，也有罪恶的计划。它们可以在更大规模上秘密地策划、组织、实施。而在过去，只要计划的规模一大，通讯的规模也自然会大，因而就很难保住秘密。

密码术有很长的历史。古代人在没有高速运算设备的条件下想尽了各种方法，也包含了许多巧妙的构思。早在公元前1900年，一个古埃及书写员就在一个铭文中使用了非标准的象形文字，这是人类最早的有记录的密码术。其后，古代人使用的密码术有如把字母表的顺序颠倒过来、进行字母替代，或者用错后一定数目的位置的字母替代前面的字母（凯撒就将这个方法用于政府通讯，因此这个方法叫做“凯撒替代”）。其中有些密码术的构思也是十分巧妙的。

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

公钥加密算法RSA

传统的加密技术都是秘密密钥加密技术，也称单密钥加密技术。也就是说，消息发送者使用一把密钥将消息加密，而消息接收者须使用同一密钥将其解密。比如数据加密标准DES。这就产生了一个重要的密钥管理问题，如何告诉对方这个密钥。除非是在耳边小声告诉或者寄一封挂号信，如果在网路上传输，无论如何也不能保证这个宝贵的密钥不被一直肆机的敌人截获。这是一件很麻烦，有时甚至是做不到的事，特别是，如果你想和许许多多你根本不认识的人实现秘密通讯，用这种秘密密钥加密技术就根本不可能。公开密钥加密技术解决了这个难题。在公开密钥加密技术中，加密密钥与解密密钥是不一样的。加密者可以将加密密钥公开，成为公开密钥，而仍将解密密钥保密，作为秘密密钥。任何人如果想向其发送加密消息，都可以找到公开密钥，然而，以其加密的消息却必须用加密者自己保留的秘密密钥才能解密，别人只知道公开密钥，因而无法阅读该消息。如果想向另一个人发送加密消息，则可以先去找他的公开密钥（既然是公开的，因而往往不用与他本人作事先联系，甚至不必认识他），然后用此密钥加密我想发送的消息给他，除了他本人之外，别人是无法阅读这个消息的。

下面就要描述RSA加密算法的流程了：

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

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

    再来, 计算 n = pq。（n，e）便是 public key。（n，r）就是private key。

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

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

接下来, 计算 C ºa^e mod n, (0 <= C < n)。b 就是编码后的信息。

解码的过程是, 计算 M º b^r mod C (0 <= c < pq)，可以证明 M 和 a 其实是相等的。也就是需要得到的没有加密的信息。

如果第三者进行窃听时, 他会得到几个数: m，n(=pq)，b。他如果要解码的话, 必须想办法得到 r。所以, 他必须先对 n 作质因数分解。如果他能够成功的分解n，得到这两个质数p和q，那么就表明此算法被攻破。

RSA算法是利用了数学中存在的一种单向性。一般说来，许多数学中的函数都有“单向性”，这就是说，有许多运算本身并不难，但如果你想把它倒回去，作逆运算，那就难了。最简单的例子：除法比乘法难，开方比乘方难，这是谁都知道的。对于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，求得F(n)（n的欧拉函数），则p和q可以求得。因为根据欧拉定理，F(n) = (p-1)(q-1) = pq – (p + q) + 1。和(p – q )² = (p + q)² – 4pq；据此列出方程，求得p和q。

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

当然也有其他一些方法，不是面向完全攻破 RSA，而只是希望得到一部分信息或者针对RSA的实现用非一般性的手段来攻击——即使买通某些人得到保密密钥也是一种方法！

为安全起见，对p和q要求：p和q的相差不大；(p-1)和(q-1)有大素数因子；gcd(p-1,q-1)很小，满足这样条件的素数称做安全素数。RSA的出现使得大整数分解因式这一古老的问题再次被重视，近些年来出现的不少比较高级的因数分解方法使“安全素数”的概念也在不停的演化。所以，选择传统上认为是“安全素数”并不一定有效的增加安全性，比较保险的方法就是选择足够大的素数。因为数越大，对其分解因式的难度也就越大！对n和密钥长度的选择取决于用户保密的需要。密钥长度越大，安全性也就越高，但是相应的计算速度也就越慢。由于高速计算机的出现，以前认为已经很具安全性的512位密钥长度已经不再满足人们的需要。1997年，RSA组织公布当时密钥长度的标准：个人使用768位密钥，公司使用1024位密钥，而一些非常重要的机构使用2048位密钥。当时的人们预计到个人使用的768位密钥将在两年后就会生存期满，那么也就是指今年！所以密钥长度的选取也要考虑到这个长度不再具效力的预计时间。

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

RSA的现状和前景

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

    但是，任何一种事物有其出现、繁荣，也不可避免它的灭亡。在没有找到快速进行大整数分解因式方法的时候，RSA显示了它不可比拟的优点。而当到了分解因式不再是难题的时候，也就到了RSA生命结束的时刻。现在在国外正在实验的量子电脑就可能成为RSA的克星。1993年, P. W. Shor 指出：量子电脑可以做因式分解，而且，它所需要的计算时间，只与该数的对数成多项式关系。也就是说，如果 RSA 演算法的 public key 的大小为 n bits 的话，用量子电脑来做因式分解，只要 P(n) 的时间就够了，其中 P 是一个多项式。而用我们现在使用的以图灵机为架构的电脑来解，必须花上 2ⁿ的时间才能分解！而且，量子电脑所使用的算法，一定在这几年内会大大改进！所以不久的将来，多项式 P 的阶数一定会降得很可观，届时 RSA 在量子电脑之下将毫无招架之力！