2.5 使用公开密钥密码术的通信

    对称算法可看成保险柜，密钥就是保险柜的号码组合。知道号码组合的人能够打开保险柜，放入文件，再关闭它。持有号码组合的其他人可以打开保险柜，取出文件来，而不知道保险柜号码组合的人就必须去摸索打开保险柜的方法。

    1976年，Whitfield Diffie和Martin Hellman永远改变了密码学的范例（NSA宣称早在1966年就有这种概念的知识，但没有提供证据）。他们提出了公开密钥密码学。他们使用两个不同的密钥：一个是公开的，另一个是秘密的。持有公钥的任何人都可加密信息，但却不能解密。只有持有私钥的人才能解密。就好像有人把密码保险柜变成一个信箱，把邮件投进邮箱相当于用公开密钥加密，任何人都可以做，只要打开窗口，把它投进去。取出邮件相当于用私钥解密。一般情况下，打开它是很难的，你需要焊接机和火把。然而，如果你拥有私钥（开信箱的钥匙），就很容易从邮箱中取出邮件。

    数学上，这个过程是基于前面讨论过的单向陷门函数。加密是容易的，加密指令就是公开密钥，任何人都能加密信息。解密是困难的，它做得非常困难，以致于不知道这个秘密，即使用Cray计算机和几百万年的时间都不能解开这个信息。这个秘密或陷门就是私钥。持有这个秘密，解密就和加密一样容易。

    下面描述Alice怎样使用公开密钥密码发送信息给Bob：

        （1）Alice和Bob选用一个公开密钥密码系统。

        （2）Bob将他的公钥传送给Alice。

        （3）Alice用Bob的公钥加密她的信息，然后传送给Bob。

        （4）Bob用他的私钥解密Alice的信息。

    注意公钥密码是怎样解决对称密码系统的密钥管理问题的。在对称密码系统中， Alice和Bob不得不选取同一密钥。Alice能够随机选取一个，但她不得不把选取的密钥传给Bob。她可能事先交给Bob，但那样做需要有先见之明。她也可以通过秘密信使把密钥送给Bob，但那样做太费时间。采用公钥密码，就很容易了，不用事先安排，Alice就能把信息安全地发送给Bob。整个交换过程一直都在窃听的Eve，有Bob的公钥和用公钥加密的信息，但却不能恢复Bob的私钥或者传送的信息。

    更一般地说，网络中的用户约定一公钥密码系统，每一用户有自己的公钥和私钥，并且公钥在某些地方的数据库中都是公开的，现在这个协议就更容易了：

    （1）Alice从数据库中得到Bob的公钥。

    （2）Alice用Bob的公钥加密信息，然后送给Bob。

    （3）Bob用自己的私钥解密Alice发送的信息。

    第一个协议中，在Alice给Bob发送信息前，Bob必须将他的公钥传送给Alice，第二个协议更像传统的邮件方式，直到Bob想读他的信息时，他才与协议有牵连。

混合密码系统

    在讨论把DES算法作为标准建议的同时，公开了第一个公开密钥算法。这导致了密码学团体中的政治党派之争。

    在实际的世界中，公开密钥算法不会代替对称算法。公开密钥算法不用来加密消息，而用来加密密钥。这样做有两个理由：

    1．公钥算法比对称算法慢，对称算法一般比公钥算法快一千倍。是的，计算机变得越来越快，在15年后计算机运行公开密钥密码算法的速度比得上现在计算机运行对称密码的速度。但是，带宽需求也在增加，总有比公开密钥密码处理更快的加密数据要求。

    2．公开密钥密码系统对选择明文攻击是脆弱的。如果C=E（P），当P是N个可能明文集中的一个明文，那么密码分析者只需要加密所有N个可能的明文，并能与C比较结果（记住，加密密钥是公开的）。用这种方法，他不可能恢复解密密钥，但他能够确定P。

    如果持有少量几个可能加了密的明文消息，那么采用选择明文攻击可能特别有效。例如，如果P是比1百万美圆少的某个美圆值，密码分析家尝试所有1百万个可能的美圆值（可能的加密解决了这个问题，见23.15节），即使P不很明确，这种攻击也是非常有效的。单是知道密文与某个特殊的明文不相符，就可能是有用的信息。对称密码系统不易受这种攻击，因为密码分析家不可能用未知的密钥来完成加密的尝试。

    在大多数实际的实现中，公开密钥密码用来保安全和分发会话密钥。这些会话密钥用在对称算法中，对通信消息进行保密[879]。有时称这种系统为混合密码系统。

    （1）Bob将他的公开密钥发给Alice。

    （2）Alice产生随机会话密钥K，用Bob的公开密钥加密，并把加密的密钥EB（K）送给Bob。

    （3）Bob用他的私钥解密Alice的消息，恢复出会话密钥。

        DB（EB（K））= K

    （4）他们两人用同一会话密钥对他们的通信信息进行加密。

    把公开密钥密码用于密钥分配解决了很重要的密钥管理问题。对对称密码而言，数据加密密钥直到使用时才起作用。如果Eve得到了密钥，那么她就能够解密用这个密钥加密的消息。在前面的协议中，当需要对通信加密时，才产生会话密钥，不再需要时就销毁，这极大地减少了会话密钥遭到损害的风险。当然，私钥面对泄露是脆弱的，但风险较小，因为只有每次对通信的会话密钥加密时才用它。这在3.1节进一步讨论。

Merkle的难题

    Ralph Merkle发明了第一个公开密钥密码的设计。1974年他在Berkeley的加利福尼亚大学注册了由Lance Hoffman教的计算机安全课程。在这个学期初，他的学期论文的题目是处理“不安全的信道上的安全通信”的问题[1064]。Hoffman不理解Merkle的建议，最终Merkle放弃了这门课程。尽管连遭失败让人们难以理解其结果，但他仍孜孜不倦地在这个问题上工作着。

    Merkle的技术基于：发送者和接收者解决难题(Puzzles)比窃听者更容易。下面谈谈Alice怎样不用首先和Bob交换密钥就能把加密消息发给Bob：

    （1）Bob产生220或大约1百万个这种形式的消息：“这是难题数x，这是秘密密钥数y”，其中x是随机数，y是随机的秘密密钥。每个消息的x和y都是不相同的。采用对称算法，他用不同的20比特密钥对每个消息加密，并都发给Alice。

    （2）Alice随机选择一个消息，通过穷举攻击恢复明文。这个工作量是很大的，但并不是不可能的。

    （3）Alice用她恢复的密钥和有些对称算法加密秘密消息，并把它和x一起发给Bob。

    （4）Bob知道他用哪个秘密密钥y对消息x加密的，这样他就能解密消息。

    Eve能够破译这个系统，但是她必须做比Alice和Bob多得多的工作。为了恢复第（3）步的消息，她必须完成对Bob在第（1）步中的所有220消息的穷举攻击。这个攻击的复杂性是240。X的值不会对Eve有什么帮助。他们在第（1）步中是随机指定的。一般情况下，Eve花费的努力大约是Alice花费的努力的平方。

    按照密码的标准，n到n2没有什么优势，但在某些情况下，这可能足够（复杂）了。如果Alice和Bob每秒可试1万个，这将要花他们每个人1分钟去完成他们的步骤，再花另外1分钟在1.544Mb/s链路上完成从Alice到Bob的通信难题。如果Eve有同样的计算设备，破译这个系统将花费她大约1年的时间，其它算法甚至更难破译。