第 3 部分： 非对称密码术
非对称密码体制提供的安全性取决于难以解决的数学问题，例如，将大整数因式分解成质数。公钥系统使用这样两个密钥，一个是公钥，用来加密文本，另一个是安全持有的私钥，只能用此私钥来解密。也可以使用私钥加密某些信息，然后用公钥来解密，而公钥是大家都可以知道的，这样拿此公钥能够解密的人就知道此消息是来自持有私钥的人，从而达到了认证作用。
简介
加密和解密都需要共享一个秘钥，这可能是使用密码术的对称密码体制的主要弱点。在非对称密码术或公钥密码术中没有这样的问题。使用在数学上相关的两个密钥，并通过用其中一个密钥加密的明文只能用另一个密钥进行解密的方法来使用它们。通常，其中一个密钥由个人秘密持有，因此几乎没有必要共享密钥，从而避免了对安全性的威胁。第二个密钥，即所谓的公钥，需要让尽可能多的人知道。
加密／解密过程可以双向进行。即，我可以使用您的公钥加密某个信息以确保只有您可以使用您的私钥来读取它。另外，还可以使用我的私钥来加密某个信息，尽管从信息隐藏的观点来看，这是没有意义的实践 ― 因为知道我公钥的任何人都可以解密该消息 ― 但这是认证系统的基础，其确保了消息确实来自知道我私钥的人那里，推测起来就是我。
以前，我提到过非对称密码是 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。但是，因为可能的消息数目是无限的，所以冲突一定是可能的（并且实际上，数量是无限的）。另外，在任何构造良好的密码散列算法中，两个不同消息产生同一散列值的可能性是极其微小的，对于所有实际用途，可以假设不会发生冲突。
散列函数只能单向工作，对于检索明文的目的，它毫无作用。然而，它提供了一种数字标识，这种数字标识仅特定于一个消息，如果纯消息文本有任何更改（甚至包括添加或除去一个空格）该标识也将更改，散列函数在这方面确实做得很好。前面段落中给出的告诫对它也适用，这意味着可以使用一个适当的散列函数来确认给定的消息未被更改。这个散列值称为消息摘要。消息摘要对于给定消息来说是
