文章作者：Murdoch Mactaggart
Murdoch Mactaggart 是一名自由撰稿人和商业顾问，他撰写关于软件开发、因特网以及围绕这些领域的商业和管理问题的文章。尽管他尝试写得灵活些，但读者是否能准确理解他所写的内容还是个未知数，他通常坚持用英语，而不是引入自创的语言。可以通过
IBMDev@TextBiz.com 与他联系。
非对称密码体制提供的安全性取决于难以解决的数学问题，例如，将大整数因式分解成质数。公钥系统使用这样两个密钥，一个是公钥，用来加密文本，另一个是安全持有的私钥，只能用此私钥来解密。也可以使用私钥加密某些信息，然后用公钥来解密，而公钥是大家都可以知道的，这样拿此公钥能够解密的人就知道此消息是来自持有私钥的人，从而达到了认证作用。
简介
加密和解密都需要共享一个秘钥，这可能是使用密码术的对称密码体制的主要弱点。在非对称密码术或公钥密码术中没有这样的问题。使用在数学上相关的两个密钥，并通过用其中一个密钥加密的明文只能用另一个密钥进行解密的方法来使用它们。通常，其中一个密钥由个人秘密持有，因此几乎没有必要共享密钥，从而避免了对安全性的威胁。第二个密钥，即所谓的公钥，需要让尽可能多的人知道。
加密／解密过程可以双向进行。即，我可以使用您的公钥加密某个信息以确保只有您可以使用您的私钥来读取它。另外，还可以使用我的私钥来加密某个信息，尽管从信息隐藏的观点来看，这是没有意义的实践 — 因为知道我公钥的任何人都可以解密该消息 — 但这是认证系统的基础，其确保了消息确实来自知道我私钥的人那里，推测起来就是我。
以前，我提到过非对称密码是 1976 年由 Whitfield Diffie 和 Martin Hellman（后来去了斯坦福大学）在其 New Directions in Cryptography 一文中提出的。但是，正如来自英国密码术权威的报告所显示的（J.H. Ellis，The Possibility of Secure Non-Secret Digital Encryption，CESG Report，1970 年 1 月），早先可能已经提出并检验了一种很相似的机制，但是却被英国当局保密着。无论事实源自什么（这种开发总是构建在以前开展的工作上），非对称密码体制概念的引入以及后来在各种特定系统中的改进都是非常重要的发展。
对称密码体制和非对称密码体制各有利弊。特别是，非对称密码体制在几方面易受攻击（例如，通过伪装），并且加密／解密过程比对称密码体制慢得多。但是，它们有突出的优点，尤其是可以与对称密码体制一起创建完美和有效的密码机制，并且可以提供非常高级别的安全性。在后继文章中将更充分地讨论这两种常见方法的互补特性；本文更侧重于与公钥系统相关的技术以及其它方面。
虽然散列函数与公钥密码体制不同，但因为散列函数通常用于消息摘要，因此在这里将它们视为认证和数字签名的整个系统的一部分也是适宜的。
非对称密码的示例
Diffie-Hellman
在前面提到的论文中对 Diffie-Hellman 协议作了充分描述。它允许两个用户通过某个不安全的交换机制来共享密钥，而不需要首先就某些秘密值达成协议。它有两个系统参数，每个参数都是公开的，其中一个质数 p，另一个通常称为生成元，是比 p 小的整数；这一生成元经过一定次数幂运算之后再对 p 取模，可以生成从 1 到 p-1 之间任何一个数。
在实际情况下，可能涉及以下过程。首先，每个人生成一个随机的私有值，即 a 和 b。然后，每个人使用公共参数 p 和 g 以及它们特定私有值 a 或 b 通过一般公式 g n mod p（其中 n 是相应的 a 或 b）来派生公共值。然后，他们交换这些公共值。最后，一个人计算 kab = (g b ) a mod p，另一个人计算 kba = (g a ) b mod p。当 kab = kba = k 时，即是共享的秘钥。
这一密钥交换协议容易受到伪装攻击，即，所谓中间人（middle-person）攻击。如果 A 和 B 正在寻求交换密钥，则第三个人 C 可能介入每次交换。A 认为初始的公共值正在发送到 B，但事实上，它被 C 拦截，然后向 B 传送了一个别人的公共值，然后 B 给 A 的消息也遭受同样的攻击，而 B 以为它给 A 的消息直接送到了 A。这导致 A 与 C 就一个共享秘钥达成协议而 B 与 C 就另一个共享秘钥达成协议。然后，C 可以在中间拦截从 A 到 B 的消息，然后使用 A/C 密钥解密，修改它们，再使用 B/C 密钥转发到 B，B 到 A 的过程与此相反，而 A 和 B 都没有意识到发生了什么。
为了防止这种情况，1992 年 Diffie 和其他人一起开发了经认证的 Diffie-Hellman 密钥协议。在这个协议中，必须使用现有的私钥／公钥对以及与公钥元素的相关数字证书，由数字证书验证交换的初始公共值。
RSA
1977 年，即，Diffie-Hellman 的论文发表一年后，MIT 的三名研究人员根据这一想法开发了一种实用方法。这就是 RSA，它是以三位开发人员 — Ron Rivest、Adi Shamir 和 Leonard Adelman — 姓的首字母大写命名的，而且 RSA 可能是使用最广泛的公钥密码体制。1983 年给 RSA 在美国申请了专利，并正式地被采用为标准，虽然到目前为止，它的出口仍受到限制，但在美国以外还是一直广泛地用于本地开发的实现。
与其它此类系统一样，RSA 使用很大的质数来构造密钥对。每个密钥对共享两个质数的乘积，即模数，但是每个密钥对还具有特定的指数。RSA 实验室对 RSA 密码体制的原理做了如下说明：
“用两个很大的质数，p 和 q，计算它们的乘积 n = pq；n 是模数。选择一个比 n 小的数 e，它与 (p - 1)(q - 1) 互为质数，即，除了 1 以外，e 和 (p - 1)(q - 1) 没有其它的公因数。找到另一个数 d，使 (ed - 1) 能被 (p - 1)(q - 1) 整除。值 e 和 d 分别称为公共指数和私有指数。公钥是这一对数 (n, e)；私钥是这一对数 (n, d)。”
知道公钥可以得到获取私钥的途径，但是这取决于将模数因式分解成组成它的质数。这很困难，通过选择足够长的密钥，可以使其基本上不可能实现。需要考虑的是模数的长度；RSA 实验室目前建议：对于普通公司使用的密钥大小为 1024 位，对于极其重要的资料，使用双倍大小，即 2048 位。对于日常使用，768 位的密钥长度已足够，因为使用当前技术无法容易地破解它。保护资料的成本总是需要和资料的价值以及攻破保护的成本是否过高结合起来考虑。RSA 实验室提到了最近对 RSA 密钥长度安全性的研究，这种安全性是基于在 1995 年可用的因式分解技术。这个研究表明用 8 个月的努力花费少于一百万美元可能对 512 位的密钥进行因式分解。事实上，在 1999 年，作为常规 RSA 安全性挑战的一部分，用了 7 个月时间完成了对特定 RSA 512 位数（称为 RSA-155）的因式分解。
记住：对于提供的安全性范围，这里给出的各种数字都是平均值，有时识别一个特定的私钥可能会快得多，这一点也很重要。同样，提供的安全性假设是基于对质数进行因式分解是很困难的。如果发现了能使因式分解变得简单的新数学技术，这种假设就会发生变化，那时 RSA 提供的安全性和类似的算法就可能立即变得毫无价值。
还请注意，密钥长度增加时会影响加密／解密的速度，所以这里有一个权衡。将模数加倍将使得使用公钥的操作时间大致增加为原来的 4 倍，而用私钥加密／解密所需的时间增加为原来的 8 倍。进一步说，当模数加倍时，生成密钥的时间平均将增加为原来的 16 倍。如果计算能力持续快速地提高，并且事实上非对称密码术通常用于简短文本，因此在实践运用中这不是问题。
其它非对称密码体制
以其开发人员的名字命名的 ElGamal 系统基于离散对数问题，并有加密和签名变体，而数字签名算法（DSA）部分基于 ElGamal。该系统看来与 RSA 一样安全，但是通常更慢，在加密期间扩展消息的时间是 RSA 的两倍。这些限制不太影响该算法在签名中的使用。
其它体制包括 1978 年第一次发布的 Merkle-Hellman 背包（knapsack）密码体制、1984 年第一次发布的 Chor-Rivest 背包密码体制及其 1988 年的修订版。还有在澳大利亚和新西兰开发的 LUC 公钥系统。McEliece 公钥加密算法基于代数编码理论，并使用一类称为 Goppa 代码的纠错码。这些代码提供快速译码，但使用的密钥大小约有半兆，并且加密时对消息文本的扩展也很大。
一组更先进的公钥密码体制是在八十年代中期提出称为椭圆曲线的密码体制，现在引起了人们的兴趣。这些体制基于数字理论和代数几何学中的数学构造，并通常定义在有限域上。这些体制尽管使用较短的密钥长度，但似乎有可能提供与现有系统类似的安全性，有些则可能在移动计算或基于智能卡的系统中特别有用。RSA 实验室提出使用 160 位密钥长度的椭圆曲线密码体制可能提供与使用 1024 位密钥的 RSA 几乎相同的安全性。然而，问题是：对于某些尚未完全开发的专门攻击来说，椭圆曲线密码体制可能是脆弱的。
散列函数
散列涉及将任意的数据字符串转换成定长结果。原始的长度可能变化很大，但结果将总是相同长度，在密码使用中通常为 128 或 160 位。散列广泛用于填充用来快速精确匹配搜索的索引；在技术上有各种散列函数，但概念上从密码编码角度是完全相同的。当使用散列来构造索引项时，需要在工作系统中预计索引项的密度和可能的冲突（即，不同的项返回同一散列值）之间寻求平衡。除非索引很大且填充得很疏松，否则将一定会有冲突，但在创建索引中这些问题很容易解决，比方说，与空值链接，然后在返回结果前检查那些具有相同散列值的原始项。但是，当在密码体制中使用散列时，这种做法是不现实的，相应的算法需要尽可能地消除冲突。比方说，128 位散列值的极限是 3.4 x 1038。但是，因为可能的消息数目是无限的，所以冲突一定是可能的（并且实际上，数量是无限的）。另外，在任何构造良好的密码散列算法中，两个不同消息产生同一散列值的可能性是极其微小的，对于所有实际用途，可以假设不会发生冲突。
散列函数只能单向工作，对于检索明文的目的，它毫无作用。然而，它提供了一种数字标识，这种数字标识仅特定于一个消息，如果纯消息文本有任何更改（甚至包括添加或除去一个空格）该标识也将更改，散列函数在这方面确实做得很好。前面段落中给出的告诫对它也适用，这意味着可以使用一个适当的散列函数来确认给定的消息未被更改。这个散列值称为消息摘要。消息摘要对于给定消息来说是很小的并且实际上是唯一的，它通常用作数字签名和数字时间戳记中的元素，将在后面的系列文章中讨论每一种用法。
如果可能生成冲突，则可能伪造摘要，然后发送欺诈的消息。这样做的一种方法是使用称为“生日攻击”的一类蛮力攻击，“生日攻击”这个名称的由来是根据这样一个事实：23 个人的一组中有两个或多个人的生日在同一天的概率大于 1/2 这一惊人的结果。
想伪造消息的人首先创建一条欺诈消息并拿取一条被攻击对象要签名的消息。然后，他使用任意秘钥及适当散列算法来生成被攻击消息的 2 n/2 个变体以及相同数量的欺诈消息的变体，n 是消息摘要的位数。假设最微小的更改也会产生不同的消息摘要，至少在理论上可能创建仅在较小细节上不同的消息。根据生日理论，被攻击消息的一个变体与欺诈消息的一个变体的散列值相匹配的概率大于 1/2。伪造者让没有产生怀疑的目标对象对所选的被攻击消息签名，然后适时地将其换成欺诈消息，该欺诈消息的摘要与被攻击消息的签名者创建的新摘要完全相同。使用这种方法，在生成消息摘要时不必知道目标对象所使用的秘钥。
MD4 和 MD5
MD2、MD4 和 MD5 是由 Ron Rivest 开发的用于数字签名应用程序的消息-摘要算法，在数字签名应用程序中将消息压缩成摘要，然后由私钥加密。MD2 是为 8 位计算机系统设计的，而 MD4 和 MD5 是为 32 位计算机系统开发的。MD4 是在 1990 开发的，现在它被认为是不安全的。
RSA 实验室将 MD5 描述为“系有安全带的 MD4”，它虽然比 MD4 慢，但却被认为是安全的。与使用 MD4 时相同，会填补明文消息以确保其位的长度加上 448 可以被 512 整除。然后添加表示原始消息长度的 64 位二进数，然后使用循环压缩函数在 512 位块中处理该消息，每块都要经过四轮各不相同的处理。
SHA 和 SHA-1
安全散列算法（SHA）是由美国国家标准和技术协会（National Institute of Standards and Technology）开发的，该协会隶属于美国商务部，负责发放密码规程的标准。然而，该算法的安全性要比其名称所暗示的低，1994 年适时发布了原始算法的修订版，称为 SHA-1。
与 MD5 相比，SHA-1 生成 160 位的消息摘要，虽然执行更慢，却被认为更安全。明文消息的最大长度可达到 264 位。
结束语
公钥密码术是特别用于认证技术的重要部分。虽然公钥体制可能只用于加密明文，但其实际价值可能更多地取决于和其它元素的结合使用，包括消息摘要和对称密码体制，从而支持复合信息包的认证和安全传输。
诸如 RSA 这样的公钥体制使用很长的密钥长度 — 现在，建议至少使用 768 位的密钥。因式分解成质数是攻击许多此类系统的基本方法，而这样做非常困难。因为计算机系统的处理能力不断增强，在蛮力攻击下，以前安全的密钥也可能变得脆弱，因此确保使用足够长的密钥以提供保护应付将来可能存在的威胁，这一点很重要。虽然计算机能力的提高使攻击旧的密钥变得更容易，但通过更方便地在合理的时间里使用在可预见的将来不可能被破解的较长密钥，实际上许多人获得了更多的好处。
