密码协议结构模块协议介绍协议介绍密码学的用途是解决种种难题（实际上，这也是计算机的主要用途）。密码学解决的各种难题围绕机密性、鉴别、完整性和不诚实的人。协议是一系列步骤，它包括两方或多方，设计它的目的是要完成一项任务。这个定义很重要 ：“一系列步骤”意味着协议是从开始到结束的一个序列，每一步必须依次执行，在前一步完成前，后面的步骤都不能执行 ；“包括两方或多方”意味着完成这个协议至少需要两个人，单独的一个人不能构成协议，当然单独的一个人也可采取一系列步骤去完成一个任务（例如烤蛋糕），但这不是协议（另外一些人必须吃蛋糕才构成协议）；最后，“设计它的目的是要完成一项任务”意味着协议必须做一些事。有些东西看起来像协议，但不完成一个任务，那也不是协议，只是浪费时间而已。协议介绍协议介绍协议还有其他特点：（1）协议中的每人都必须了解协议，并且预先知道所要完成的所有步骤。（2）协议中的每人都必须同意遵循它。（3）协议必须是不模糊的，每一步必须明确定义，并且不会引起误解。（4）协议必须是完整的，对每种可能的情况必须规定具体的动作。协议介绍协议介绍密码协议是使用密码学的协议。参与该协议的伙伴可能是朋友和完全信任的人，或者也可能是敌人和互相完全不信任的人。密码协议包含某种密码算法，但通常，协议的目的不仅仅是为了简单的秘密性。参与协议的各方可能为了计算一个数值想共享它们的秘密部分、共同产生随机系列、确定互相的身份、或者同时签署合同。在协议中使用密码的目的是防止或发现偷听者和欺骗。如果你以前没有见过这些协议，它们会从根本上改变你的思想，相互之间不信任的各方也能够在网络上完成这些协议。一般地，这能够被陈述为：不可能完成或知道得比协议中规定的更多。这看起来很难。接下来的几节课中会讨论许多协议。在其中的一些协议中，参与者中的一个有可能欺骗其他人。偷听者也可能暗中破坏协议或获悉秘密信息。一些协议之所以失败，是因为设计者对需求不是定义得很完备。其它一些失败是因为协议的设计者分析得不够充分。就像算法一样，证明它不安全比证明它安全容易得多。协议的目的在日常生活中，几乎所有的事情都有非正式的协议：电话订货、玩扑克、选举中投票，没有人认真考虑过这些协议，这些协议随着时间的推移而发展，人们都知道怎样使用它们，而且它们也很有效。越来越多的人通过计算机网络交流，从而代替了面对面的交流。计算机需要正式的协议来完成人们不用考虑就能做的事情。如果你换了一个购物网站进行购物，可能会发现支付方式与你以前使用的完全不同，你会很容易去适应它。但计算机就不那么灵活了。协议的目的协议的目的许多面对面的协议依靠人的现场存在来保证公平和安全。你会交给陌生人一叠现金去为你买食品吗？如果你没有看到他洗牌和发牌，你愿意和他玩扑克吗？那种假设使用计算机网络的人都是诚实的想法，是天真的。天真的想法还有：假设计算机网络的管理员是诚实的，假设计算机网络的设计者是诚实的。当然，绝大多数人是诚实的，但是不诚实的少数人可能招致很多损害。通过规定协议，可以查出不诚实者企图欺骗的把戏，还可开发挫败这些欺骗者的协议。游戏角色为了帮助说明协议，我们设定一些角色。Alice和Bob是开始的两个人。他们将完成所有的两人协议。按规定，由Alice 发起所有协议，Bob响应。如果协议需要第三或第四人，Carol和Dave将扮演这些角色。由其他人扮演的专门配角，将在后面介绍。Alice所有协议中的第一个参加者Bob所有协议中的第二个参加者Carol在三、四方协议中的参加者Dave在四方协议中的参加者Eve窃听者Mallory恶意的主动攻击者Trent值得信赖的仲裁者Walter监察人：在某些协议中保护Alice和BobPeggy证明人Victor验证者仲裁协议仲裁协议仲裁者是在完成协议的过程中，值得信任的公正的第三方，仲裁者能帮助互不信任的双方完成协议。“公正”意味着仲裁者在协议中没有既得利益，对参与协议的任何人也没有特别的利害关系。“值得信任”表示协议中的所有人都接受这一事实，即仲裁者说的都是真实的，他做的是正确的，并且他将完成协议中涉及他的部分。仲裁者能帮助互不信任的双方完成协议。仲裁协议在现实社会中，律师经常作为仲裁者。例如，Alice要卖汽车给不认识的Bob。Bob想用支票付帐，但Alice不知道支票的真假。在Alice将车子转给Bob前，她必须查清支票的真伪。同样，Bob也并不相信Alice，就像Alice不相信Bob一样，在没有获得所有权前，也不愿将支票交与Alice。这时就需要双方都信任的律师。在律师的帮助下，Alice和Bob能够用下面的协议保证互不欺骗。（1）Alice将车的所有权交给律师。（2）Bob将支票交给Alice。（3）Alice在银行兑现支票。（4）在等到支票鉴别无误能够兑现的时间之后，律师将车的所有权交给Bob。如果在规定的时间内支票不能兑现，Alice将证据出示给律师，律师将车的所有权和钥匙交还给Alice。仲裁协议这种思想可以转化到计算机世界中，但计算机仲裁者有下面几个问题：（1）如果你知道对方是谁，并能见到他的面，就很容易找到和相信中立的第三方。互相怀疑的双方很可能也怀疑在网络别的什么地方并不露面的仲裁者。（2）计算机网络必须负担仲裁者的费用。就像我们知道的律师费用，谁想负担那种网络费用呢？（3）在任何仲裁协议中都有延迟的特性。（4）仲裁者必须处理每一笔交易。任何一个协议在大范围执行时，仲裁者是潜在的瓶颈。增加仲裁者的数目能缓解这个问题，但费用将会增加。（6）由于在网络中每人都必须相信仲裁者，对试图破坏网络的人来说，仲裁者便是一个易受攻击的弱点。尽管如此，仲裁者仍扮演一个角色。在使用可信任的仲裁协议中，这个角色将由Trent来扮演。裁决协议裁决协议由于雇用仲裁者代价高昂，仲裁协议可以分成两个低级的子协议。一个是非仲裁子协议，这个子协议是想要完成协议的各方每次都必须执行的；另一个是仲裁子协议，仅在例外的情况下执行的，即有争议的时候才执行，这种特殊的仲裁者叫做裁决人。裁决人也是公正的和可信的第三方。他不像仲裁者，并不直接参与每一个协议。只有为了要确定协议是否被公平地执行，才将他请来。裁决协议法官是职业的裁决者。法官不像公证人，仅仅在有争议时才需要他出场，Alice和Bob可以在没有法官的情况下订立合同。除非他们中有一个人把另一人拖到法院，否则法官决不会看到合同。合同签字协议可以归纳为下面形式：非仲裁子协议（每次都执行）：（1）Alice和Bob谈判合同的条款。（2）Alice签署合同。（3）Bob签署合同。裁决子协议（仅在有争议时执行）：（1）Alice和Bob出现在法官面前。（2）Alice提出她的证据。（3）Bob也提出他的证据。（4）法官根据证据裁决。裁决协议裁决者和仲裁之间的不同是裁决者并不总是必需的。如果有争议，法官被请来裁决。如果没有争议，就没有必要请法官。目前已有计算机裁决协议。这些协议依赖于与协议有关的各方都是诚实的；如果有人怀疑欺骗时，一个中立的第三方能够根据存在的数据正文文本判断是否有人在欺骗。在好的裁决协议中，裁决者还能确定欺骗人的身份。裁决协议是为了发现欺骗，而不是为了阻止欺骗。发现欺骗是起了防止和阻碍欺骗的作用。自动执行的协议自动执行的协议自动执行的协议是协议中最好的。协议本身就保证了公平性。不需要仲裁者来完成协议，也不需要裁决者来解决争端。协议的构成本身不可能发生如何争端。如果协议中的一方试图欺骗，其他各方马上就能发觉并且停止执行协议。无论欺骗方想通过欺骗来得到什么，他都不能如愿以偿。最好，让每个协议都能自动执行。不幸的是，在现实所有情形下，没有一个是自动执行的协议。对协议的攻击对协议的攻击密码攻击可以直接攻击协议中所用的密码算法、用来实现该算法和协议的密码技术、或者攻击协议本身。在此我们仅讨论协议。我们假设密码算法和密码技术是安全的，只关注对协议本身的攻击。 被动攻击被动攻击：与协议无关的人能够偷听协议的一部分或全部。因为攻击者不可能影响协议，所有他能做的事是观察协议并试图获取信息。由于被动攻击难于发现，因此协议应阻止被动攻击而不是发现这种攻击。在这种协议中，偷听者的角色将由Eve扮演。 主动攻击主动攻击：他可能假装是其它一些人，在协议中引入新的信息，删掉原有的信息，用另外的信息代替原来的信息，重放旧的信息，破坏通信信道，或者改变存贮在计算机中的信息等。对协议的攻击被动攻击试图获取协议中各方的信息。他们收集协议各方所传送的信息，并试图对它们进行密码分析。而主动攻击可能有更多的目的。攻击者可能对获取信息感兴趣，也可能降低系统性能，破坏已有的信息，或者获得非授权的资源存取。主动攻击严重得多，特别是在那些各方都不必彼此信任的协议中。攻击者不一定都是入侵者，他可能是合法的系统用户，他们可能是系统管理员。甚至有很多主动攻击者，他们都在一起工作，每人都是合法的系统用户。这个恶意的主动攻击者的角色将由Mallory扮演。对协议的攻击攻击者也可能是与协议有关的各方中的一方。他可能在协议期间撒谎，或者根本不遵守协议，这类攻击者叫做骗子骗子。被动骗子被动骗子遵守协议，但试图获取协议外的其他信息。主动骗子主动骗子在协议的执行中试图通过欺骗来破坏协议。如果与协议有关的各方中的大多数是主动骗子，就很难保持协议的安全性。但合法用户发觉是否有主动欺骗却是可能的。当然，协议对被动欺骗来说应该是安全的。使用对称密码术的通信通信双方怎样安全地通信呢？当然，他们可以对通信加密。完整的协议比它更复杂，让我们来看看Alice发送加密的信息给Bob会发生什么情况吧：（1）Alice和Bob协商用同一密码系统。（2）Alice和Bob协商同一密钥。（3）Alice用加密算法和选取的密钥加密她的明文信息，得到了密文信息。（4）Alice发送密文信息给Bob。（5）Bob用同样的算法和密钥解密密文，然后读它。使用对称密码术的通信位于Alice和Bob之间的窃听者Eve监听这个协议，她能做什么呢？如果她听到的是在第（4）步中发送的密文，她必须设法分析密文，这是唯密文的被动攻击法；有很多算法能够阻止Eve，使她不可能得到问题的解答。尽管如此，但Eve却不笨，她也想窃听步骤（1）和步骤（2），这样她就知道了算法和密钥，她就和Bob知道的一样多。当步骤（4）中的信息通过信道传送过来时，她所做的全部工作就是解密密文信息。好的密码系统的全部安全性只与密钥有关，和算法没有任何关系。这就是为什么密钥管理在密码学中如此重要的原因。有了对称算法，Alice和Bob能够公开地实现步骤（1），但他们必须秘密地完成步骤（2）。在协议执行前、执行过程上和执行后，只要信息必须保持秘密，密钥就必须保持秘密，否则，信息就将不再秘密了。使用对称密码术的通信主动攻击者Mallory可能做其他一些事情，他可能企图破坏在（4）中使用的通信信道，使Alice和Bob根本不可能通信。他也可能截取Alice的信息并用他自己的信息替代它。如果他也知道密钥（通过截取（2）的通信或者破译密码系统），他可能加密自己的信息，然后发送给Bob，用来代替截取的信息。Bob没有办法知道接收到的信息不是来自Alice。如果Mallory不知道密钥，他所产生的代替信息，被解密出来是无意义的，Bob就会认为从Alice那里来的信息是网络或者是Alice有严重的问题。Alice又怎么样呢？她能做什么来破坏这个协议吗？她可以把密钥的副本给Eve。现在Eve可以读Bob所发的信息，他还不知道Eve已经把他的话散播了出去。虽然问题很严重，但这并不是协议的问题。在协议过程的任何一点都不可能阻止Alice把明文的副本交给Eve。当然Bob也可能做Alice所做的事。协议假定Alice和Bob互相信任。使用对称密码术的通信总之，对称密码算法存在下面的问题：（1）密钥必须秘密地分配，它们比任何加密的信息更有价值，因为知道了密钥意味着知道了所有信息。对于遍及世界的加密系统，这可能是令人沮丧的任务，需经常派信使将密钥传递到目的地。（2）如果密钥被损害了（被偷窃，猜出来，被逼迫交出来，受贿等等），那么Eve就能用该密钥去解密所有传送的信息，也能够假装是几方中的一方，产生虚假信息去愚弄另一方。（3）假设网络中每对用户使用不同的密钥，那么密钥总数随着用户数的增加迅速增多。N个用户的网络需要n（n-1）/2个密钥。例如，10个用户互相通信需要45个不同的密钥，100个用户需要4950个不同的密钥，这个问题可以通过将用户数量控制在较小数目来减轻，但这并不总是可能的。单向函数单向函数的概念是计算起来相对容易，但求逆却非常困难。也就是说，已知x，我们很容易计算f（x）。但已知f（x），却难于计算出x。在这里，“难”定义成：即使世界上所有的计算机都用来计算，从f（x）计算出x也要花费数百万年的时间。打碎盘子就是一个很好的单向函数的例子。把盘子打碎成数千片碎片是很容易的事情，然而，要把所有这些碎片再拼成为一个完整的盘子，却是非常困难的事情。这听起来很好，但事实上却不能证实它的真实性。如果严格地按数学定义，我们不能证明单向函数的存在性，同时也还没有实际的证据能够构造出单向函数。即使这样，还是有很多函数看起来和感觉像单向函数：我们能够有效地计算它们，且至今还不知道有什么办法能容易地求出它们的逆。例如，在有限域中x2是很容易计算的，但计算x1/2却难得多。单向函数单向函数不能用作加密。用单向函数加密的信息是毫无用处的，无人能解开它。（在盘子上写上信息，然后砸成碎片，把这些碎片给你的朋友，要求你的朋友读这上面的信息，观察你的朋友对单向函数会有多么深刻的印象）。对公开密钥密码，我们还需要一些其它的东西。陷门单向函数是有一个秘密陷门的一类特殊单向函数。它在一个方向上易于计算而反方向却难于计算。但是，如果你知道那个秘密，你也能很容易在另一个方向计算这个函数。也就是说， 已知x，易于计算f（x），而已知f（x），却难于计算x。然而，有一些秘密信息y，一旦给出f（x）和y，就很容易计算x。拆开表是很好的单向陷门函数的例子。很容易把表拆成数百片小片，把这些小片组装成能够工作的表是非常困难的。然而，通过秘密信息（表的装配指令），就很容易把表还原。单向Hash函数Hash函数长期以来一直在计算机科学中使用，无论从数学上或别的角度看，Hash函数就是把可变输入长度串（叫做预映射）转换成固定长度（经常更短）输出串（叫做hash值）的一种函数。简单的Hash函数就是对预映射的处理，并且返回由所有输入字节异或组成的一字节。这儿的关键就是：产生一个值，这个值能够指出候选选预映射是否与真实的预映射有相同的值。因为Hash函数是典型的多到一的函数，我们不能用它们来确定两个串一定相同，但我们可用它的来得到准确性的合理保证。单向Hash函数是在一个方向上工作的Hash函数，从预映射的值很容易计算其Hash值，但要产生一个预映射的值使其Hash值等于一个特殊值却是很难的。前面提到的Hash函数不是单向函数：已知一个特殊的字节值，要产生一个字节串使它的异或结果等于那个值是很容易的事情。用单向Hash函数你不可能那样做。好的hash函数也是无冲突的：难于产生两个预映射的值，使他们的hash值相同。单向Hash函数Hash函数是公开的，对处理过程不用保密。单向hash函数的安全性是它的单向性。无论怎么看，输出不依赖于输入。预映射的值的单个比特的改变，平均而言，将引起hash值中一半的比特改变。已知一个hash值，要找到预映射的值，使它的hash值等于已知的hash值在计算上是不可行的。可把单向Hash函数看作是构成指纹文件的一种方法。如果你想验证某人持有一特定的文件（你同时也持有该文件），但你不想他将文件传给你，那么，就要求他将该文件的单向Hash值传送给你，如果他传送的Hash值是正确的，那么几乎可以肯定地说他持有那份文件一般情况下，你应使用不带密钥的单向Hash函数，以便任何人都能验证Hash值。使用公开密钥密码术的通信对称算法可看成保险柜，密钥就是保险柜的号码组合。知道号码组合的人能够打开保险柜，放入文件，再关闭它。持有号码组合的其他人可以打开保险柜，取出文件来，而不知道保险柜号码组合的人就必须去摸索打开保险柜的方法。公开密钥密码学使用两个不同的密钥：一个是公开的，另一个是秘密的。持有公钥的任何人都可加密信息，但却不能解密。只有持有私钥的人才能解密。就好像有人把密码保险柜变成一个信箱，把邮件投进邮箱相当于用公开密钥加密，任何人都可以做，只要打开窗口，把它投进去。取出邮件相当于用私钥解密。一般情况下，打开它是很难的，你需要焊接机和火把。然而，如果你拥有私钥（开信箱的钥匙），就很容易从邮箱中取出邮件。 使用公开密钥密码术的通信数学上，这个过程是基于前面讨论过的单向陷门函数。加密是容易的，加密指令就是公开密钥，任何人都能加密信息。解密是困难的，它做得非常困难，以致于不知道这个秘密，即使用计算机和几百万年的时间都不能解开这个信息。这个秘密或陷门就是私钥。持有这个秘密，解密就和加密一样容易。下面描述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想读他的信息时，他才与协议有牵连。混合密码系统混合密码系统在实际的世界中，公开密钥算法不会代替对称算法。公开密钥算法不用来加密消息，而用来加密密钥。这样做有两个理由：1.公钥算法比对称算法慢，对称算法一般比公钥算法快一千倍。2.公开密钥密码系统对选择明文攻击是脆弱的。如果C=E（P），当P是N个可能明文集中的一个明文，那么密码分析者只需要加密所有N个可能的明文，并能与C比较结果（记住，加密密钥是公开的）。用这种方法，他不可能恢复解密密钥，但他能够确定P。 混合密码系统混合密码系统如果持有少量几个可能加了密的明文消息，那么采用选择明文攻击可能特别有效。例如，如果P是比1百万美圆少的某个美圆值，密码分析家尝试所有1百万个可能的美圆值（可能的加密解决了这个问题），即使P不很明确，这种攻击也是非常有效的。单是知道密文与某个特殊的明文不相符，就可能是有用的信息。对称密码系统不易受这种攻击，因为密码分析家不可能用未知的密钥来完成加密的尝试。混合密码系统混合密码系统在大多数实际的实现中，公开密钥密码用来保护和分发会话密钥。这些会话密钥用在对称算法中，对通信消息进行保密。有时称这种系统为混合密码混合密码系统系统。1. Bob将他的公开密钥发给Alice。2. Alice产生随机会话密钥K，用Bob的公开密钥加密，并把加密的密钥EB（K）送给Bob。3.Bob用他的私钥解密Alice的消息，恢复出会话密钥。DB（EB（K）= K4.他们两人用同一会话密钥对他们的通信信息进行加密。混合密码系统混合密码系统把公开密钥密码用于密钥分配解决了很重要的密钥管理问题。对对称密码而言，数据加密密钥直到使用时才起作用。如果Eve得到了密钥，那么她就能够解密用这个密钥加密的消息。在前面的协议中，当需要对通信加密时，才产生会话密钥，不再需要时就销毁，这极大地减少了会话密钥遭到损害的风险。当然，私钥面对泄露是脆弱的，但风险较小，因为只有每次对通信的会话密钥加密时才用它。数字签名在文件上手写签名长期以来被用作作者身份的证明，或至少同意文件的内容。签名为什么会如此引人注目呢？（1）签名是可信的。签名使文件的接收者相信签名者是慎重地在文件上签字的。（2）签名不可伪造。签名证明是签字者而不是其他人慎重地在文件上签字。（3）签名不可重用。签名是文件的一部分，不法之徒不可能将签名移到不同的文件上。（4）签名的文件是不可改变的。在文件签名后，文件不能改变。（5）签名是不可抵赖的。签名和文件是物理的东西。签名者事后不能声称他没有签过名。数字签名在现实生活中，关于签名的这些陈述没有一个是完全真实的。签名能够被伪造，签名能够从文章中盗用移到另一篇文章中，文件在签名后能够被改变。然而，我们之所以愿意与这些问题纠缠在一起，因为欺骗是困难的，并且还要冒被发现的危险。在计算机上做这种事情，但还存在一些问题。首先计算机文件易于复制。即使某人的签名难以伪造（例如，手写签名的图形），但是从一个文件到另一个文件剪裁和粘贴有效的签名都是很容易的。这种签名并没有什么意义；其次文件在签名后也易于修改，并且不会留下任何修改的痕迹。使用对称密码系统和仲裁者的文件签名使用对称密码系统和仲裁者的文件签名Alice想对数字消息签名，并送给Bob。在Trent和对称密码系统的帮助下，她能做到。Trent是一个有权的、值得依赖的仲裁者。他能同时与Alice和Bob（也可以是其他想对数据文件签名的任何人）通信。他和Alice共享秘密密钥KA，和Bob共享另一个不同的秘密密钥KB。这些密钥在协议开始前就早已建好，并且为了多次签名可多次重复使用。（1）Alice用KA加密她准备发送给Bob的信息，并把它传送给Trent。（2）Trent用KA解密信息。（3）Trent把这个解密信息和他收到Alice信息的声明，一起用KB加密。（4）Trent把加密的信息包传给Bob。（5）Bob用KB解密信息包，他就能读Alice所发的信息和Trent的证书，证明信息来自Alice。使用对称密码系统和仲裁者的文件签名使用对称密码系统和仲裁者的文件签名Trent怎么知道信息是从Alice而不是从其他人冒名顶替者那里来的呢？从信息的加密推断出来。由于只有他和Alice共享他们两人的秘密密钥，所以只有Alice能用这个密钥加密信息。这和文件签名一样好吗？让我们看看我们需要的特点：（1）这个签名是可信的，Trent是可信的仲裁者，并且知道消息是从Alice那里来的，Trent的证书对Bob起着证明的作用。（2）这个签名是不可伪造的。只有Alice（和Trent，但每个人都相信他）知道KA，因此只有Alice才能把用KA加密的信息传给Trent。如果有人冒充Alice，Trent在第（2）步马上就会察觉，并且不会去证明它的可靠性。使用对称密码系统和仲裁者的文件签名使用对称密码系统和仲裁者的文件签名（3）这个签名是不能重新使用的。如果Bob想把Trent的证书附到另一个信息上，Alice可能就会大叫受骗了。仲裁者（可能是Trent或者可存取同一信息的完全不同的仲裁者）就会要求Bob同时提供信息和Alice加密后的信息，然后仲裁者就用KA加密信息，他马上就会发现它与Bob提供的加密信息不相同。很显然，Bob由于不知道KA，他不可能提供加密信息使它与用KA加密的信息相符。（4）签名文件是不能改变的。Bob想在接收后改变文件，Trent就可用刚才描述的同样办法证明Bob的愚蠢行为。（5）签名是不能抵赖的，即使Alice以后声称她没有发信息给Bob，Trent的证书会说明不是这样。记住：Trent是每个人都信任的，他说的都是正确的。使用对称密码系统和仲裁者的文件签名使用对称密码系统和仲裁者的文件签名如果Bob想把Alice签名的文件给Carol阅读，他不能把自己的秘密密钥交给她，他还得通过Trent：（1）Bob把信息和Trent关于信息是来自Alice的声明用KB加密，然后送回给Trent。（2）Trent用KB解密信息包。（3）Trent检查他的数据库，并确认原始信息是从Alice那里来的。（4）Trent用他和Carol共享的密钥KC重新加密信息包，把它送给Carol。（5）Carol 用KC解密信息包，她就能阅读信息和Trent证实信息来自Alice的证书。使用对称密码系统和仲裁者的文件签名使用对称密码系统和仲裁者的文件签名这些协议是可行的，但对Trent来说是非常耗时的。他不得不整天加密、解密信息，在彼此想发送签名文件的每一对人之间充当中间人。他必须备有数据库信息。在任何通信系统中，即使他是毫无思想的软件程序，他都是通信瓶颈。更困难的是产生和保持像Trent那样的网络用户都信任的人。Trent必须是完善无缺的，即使他在100万次签名中只犯了一个错误，也将不会有人再信任他。Trent必须是完全安全的，如果他的秘密密钥数据库泄漏了，或有人能修改他的程序代码，所有人的签名可能是完全无用的。理论上这种协议或许是可行的，但实际上不能很好运转。使用公钥密码对文件签名使用公钥密码对文件签名基本协议是简单的：（1）Alice用她的私钥对文件加密，从而对文件签名。（2）Alice将签名的文件传给Bob。（3）Bob用Alice的公钥解密文件，从而验证签名。这个协议比以前的算法更好。不需要Trent去签名和验证。他只需要证明Alice的公钥的确是她的。甚至协议的双方不需要Trent来解决争端；如果Bob不能完成第（3）步，那么他知道签名是无效的。使用公钥密码对文件签名使用公钥密码对文件签名这个协议也满足我们期待的特征：（1）签名是可信的。当Bob用Alice的公钥验证信息时，他知道是由Alice签名的。（2）签名是不可伪造的。只有Alice知道她的私钥。（3）签名是不可重用的。签名是文件的函数，并且不可能转换成另外的文件。（4）被签名的文件是不可改变的。如果文件有任何改变，文件就不可能用Alice的公钥验证。（5）签名是不可抵赖的。Bob不用Alice的帮助就能验证Alice的签名。文件签名和时间标记文件签名和时间标记实际上，Bob在某些情况下可以欺骗Alice。他可能把签名和文件一起重用。如果Alice在合同上签名，这种重用不会有什么问题。但如果Alice在一张数字支票上签名，那样做就令人兴奋了假若Alice交给Bob100的签名数字支票，Bob把支票拿到银行去验证签名，然后把钱从Alice的帐户上转到自己的帐上。Bob是一个无耻之徒，他保存了数字支票的副本。过了一星期，他又把数字支票拿到银行，银行验证数字支票并把钱转到他的帐上。只要Alice不去对支票本清帐，Bob就可以一直干下去。因此，数字签名经常包括时间标记。对日期和时间的签名附在信息中，并跟信息中的其他部分一起签名。银行将时间标记存贮在数据库中。现在，当Bob第二次想支取Alice的支票时，银行就要检查时间标记是否和数据库中的一样。由于银行已经从Alice的支票上支付了这一时间标记的支票，于是就叫警察。这样一来Bob就要在监狱中度过15个春秋去研读密码协议的书籍了。用公钥密码和单向用公钥密码和单向Hash函数对文件签名函数对文件签名在实际的实现过程中，采用公钥密码算法对长文件签名效率太低。为了节约时间，数字签名协议经常和单向Hash函数一起使用。Alice并不对整个文件签名，只对文件的Hash值签名。在这个协议中，单向Hash函数和数字签名算法是事先就协商好了的。（1）Alice产生文件的单向Hash值。（2）Alice用她的私钥对Hash加密，凭此表示对文件签名。（3）Alice将文件和Hash签名送给Bob。（4）Bob用Alice发送的文件产生文件的单向Hash值，然后用数字签名算法对hash值运算，同时用Alice的公钥对签名的Hash解密。如果签名的hash值与自己产生的Hash值匹配，签名就是有效的。用公钥密码和单向用公钥密码和单向Hash函数对文件签名函数对文件签名计算速度大大地提高了，并且两个不同的文件有相同的160比特Hash值的概率为1/2160。因此，使用Hash函数的签名和文件签名一样安全。如果使用非单向Hash函数，可能很容易产生多个文件使它们的hash值相同，这样对一特定的文件签名就可复制用于对大量的文件签名。这个协议还有其它好处。首先，签名和文件可以分开保存。其次，接收者对文件和签名的存贮量要求大大降低了。档案系统可用这类协议来验证文件的存在而不需保存它们的内容。中央数据库只存贮各个文件的Hash值，根本不需要看文件。用户将文件的Hash值传给数据库，然后数据库对提交的文件加上时间标记并保存。如果以后有人对某文件的存在发生争执，数据库可通过找到文件的Hash 值来解决争端。这里可能牵连到大量的隐秘：Alice可能有某文件的版权，但仍保持文件的秘密。只有当她想证明她的版权时，她才不得不把文件公开。算法和术语算法和术语有许多数字签名算法，它们都是公钥算法，用秘密信息对文件签名，用公开信息去验证。有时签名过程也叫“用私钥加密用私钥加密”，验证过程也叫“用公钥解密用公钥解密”，许多算法可用作数字签名，但不能用作加密。一般地，提到签名和验证过程通常不包括任何算法的细节。用私钥K签名信息表示为： SK（M）.用相应的公钥验证信息表示为： VK（M）.在签名时，附在文件上的比特串叫数字签名数字签名（在上面的例子中，用私钥对文件的单向Hash值加密）或者就叫签名签名。信息的接收者用以确认发送者的身份和信息的完整性的整个协议叫做鉴别鉴别。多重签名多重签名Alice和Bob怎么对同一数字文件签名呢？不用单向Hash函数，有两种选择。第一种选择是Alice和Bob分别对文件的副本签名，结果签名的信息是原文的两倍。第二种就是Alice首先签名，然后Bob对Alice的签名再进行签名，这是可行的，但是在不验证Bob的签名的情况下就验证Alice的签名是不可能的。采用单向Hash函数，多重签名是容易的：（1）Alice对文件的hash签名。（2）Bob对文件的hash签名。（3）Bob将他的签名交给Alice。（4）Alice把文件、她的签名和Bob的签名发给Carol。（5）Carol验证Alice和Bob的签名。Alice和Bob能同时或顺序地完成（1）和（2），在（5）Carol可以只验证其中一人的签名而不用验证另一人的签名。抗抵赖和数字签名抗抵赖和数字签名Alice有可能用数字签名作欺骗，并且无人能阻止她。她可能对文件签名，然后声称并没有那样做。首先，她按常规对文件签名，然后她以匿名的形式发布她的私钥，故意把私钥丢失在公共场所，或者只要假装做上面两者中的一个。这样，发现该私钥的任何人都可装成是Alice对文件签名，于是Alice就声明她的签名受到侵害，其他人正在假装她签名云云。她否认对文件的签名和任何其他的用她的私钥签名的文件，这叫做抵赖抵赖。采用时间标记可以限制这种欺骗的作用，但Alice总可以声称她的密钥在较早的时候就丢失了。如果Alice把事情做得好，她可以对文件签名，然后成功地声称并没有对文件签名。虽然没有办法阻止这种可能的乱用，但可以采取措施保证旧的签名不会失效（例如，Alice 可能有意丢失她的密钥，以便不用对昨天从Bob那里买的二手车付帐，在这个过程中，Alice使她的银行帐户无效）。抗抵赖和数字签名抗抵赖和数字签名数字签名文件的接收者持有签名的时间标记就能解决这个问题。一般在协议中给出：Alice对信息签名。Alice产生一个报头，报头中包含有些鉴别信息。她把报头和签名的信息连接起来，对连接的信息签名，然后把签名的信息发给Trent。Trent验证外面的签名，并确认鉴别信息。他在Alice签名信息中增加一个时间标记和鉴别信息。然后对所有的信息签名，并把它发给Bob和Alice。Bob验证Trent 的签名、鉴别信息和Alice的签名。Alice验证Trent发给Bob的信息。如果她没有发起这个信息，她很快就会大喊大叫了。数字签名的应用数字签名的应用数字签名最早的建议应用之一是用来对禁止核试验条约的验证。美国和前苏联互相允许把地震测试仪放入另一个国家中，以便对核试验进行监控。问题是每个国家需要确信东道国没有篡改从监控国家的地震仪传来的数据。同时，东道主国家需要确信监测器只发送规定的需要监测的信息。 传统的鉴别技术能解决第一个问题，但只有数字签名能同时解决两个问题。东道国一方只能读，但不能窜改从地震测试仪来的数据；而监督国确信数据没有被窜改。带加密的数字签名通过把公钥密码和数字签名结合起来，我们能够产生一个协议，可把数字签名的真实性和加密的安全性合起来。想象你妈妈写的一封信：签名提供了原作者的证明，而信封提供了秘密性 。（1）Ailce用她的私钥对信息签名。 SA（M）.（2）Alice用Bob的公钥对签名的信息加密，然后送给Bob。 EB（SA（M）.（3）Bob用他的私钥解密。 DB（EB（SA（M）=SA（M）.（4）Bob用Alice的公钥验证并且恢复出信息。 VA（SA（M）=M.带加密的数字签名加密前签名是很自然的。当Alice写一封信，她在信中签名，然后把信装入信封中。如果她把没签名的信放入信封，然后在信封上签名，那么Bob可能会担心是否这封信被替换了。如果Bob把Alice的信和信封给Carol看，Carol可能因信没装对信封而控告Bob说谎。在电子通信中也是这样，加密前签名是一种谨慎的习惯做法。这样做不仅是更安全（敌人不可能从加密信息中把签名移走，然后加上他自己的签名）。而且还有法律的考虑：当他附加他的签名时，如果签名者不能见到被签名的文本，那么签名没有多少法律强制作用。带加密的数字签名Alice没有理由必须把同一个公钥/私钥密钥对用作加密和签名。她可以有两个密钥对：一个用作加密，另一个用作解密。分开使用有它的好处：她能够把她的加密密钥交给警察而不泄露她的签名，一个密钥被托管而不会影响到其他密钥，并且密钥能够有不同的长度，能够在不同的时间终止使用。当然，这个协议应该用时间标记来阻止信息的重复使用。时间标记也能阻止其他潜在的危险，例如下面描述的这种情形。作为收据的重发信息作为收据的重发信息我们来考虑这个协议附带确认信息的实现情形：每当Bob接收到信息，他再把它传送回发方作为接收确认。（1）Alice用她的私钥对信息签名，再用Bob的公钥加密，然后传给Bob。 EB（SA（M）.（2）Bob用他的私钥对信息解密，并用Alice的公钥验证签名，由此验证确是Alice对信息签名，并恢复出信息。 VA（DB（EB（SA（M）=M.（3）Bob用他的私钥对信息签名，用Alice的公钥加密，再把它送回给Alice。 EA（SB（M）.（4）Alice用她的私钥对信息解密，并用Bob的公钥对验证Bob的签名。如果接收的信息与她传给Bob的相同，她就知道Bob准确地接收到她所发送的信息。作为收据的重发信息作为收据的重发信息如果同一算法既用作加密又用作数字签名，就有可能受到攻击。在这种情况中，数字签名操作是加密操作的逆过程：VX=EX，并且SX=DX。假设Mallory是持有自己公钥和私钥的系统合法用户。让我们看看他怎么读Bob的邮件。首先他将Alice在（1）中送给Bob的信息记录下来，在以后的某个时间，他将那个信息送给Bob，声称信息是从Mallory处来的。Bob认为是从Mallory来的合法信息，于是就用私钥解密，然后通过用Mallory的公钥解密来验证Mallory的签名，那么得到的信息纯粹是乱七八糟的信息： EM（DB（EB（DA（M）=EM（DA（M）.即使这样，Bob继续执行协议，并且将收据发给Mallory。 EM（DB（EM（DA（M）.现在Mallory所要做的就是用他的私钥对信息解密，用Bob的公钥加密，再用Mallory自己的私钥解密，并用Alice的公钥加密。哇！Mallory就获得了所要的信息M。作为收据的重发信息作为收据的重发信息认为Bob会自动回送给Mallory一个收据不是不合理的。例如：这个协议可能嵌入在通信软件中，并且在接收后自动发送收据。收到乱七八糟的东西也送出确认收据会导致不安全性。如果在发送收据前仔细地检查信息是否能理解，就能避免这个安全问题。还有一种更强的攻击，就是允许Mallory送给Bob一个与窃听的信息不同的信息。不要对从其他人那里来的信息随便签名并将结果交给其他人。阻止重发攻击阻止重发攻击安全的协议应该是加密和数字签名操作稍微不同，每次操作使用不同的密钥能做到这一点，每次操作使用不同的算法也能做到；采用时间标记也能做到，它使得输入的信息和输出信息不同。用单向Hash函数的数字签名也能解决这个问题；一般说来，下面这个协议是非常安全的，它使用的是公开密钥算法：（1）Alice对消息签名。（2）Alice用Bob的公钥对消息和签名加密（采用和签名算法不同的加密算法），然后将它传送给Bob。（3）Bob用他的私钥对消息解密。（4）Bob验证Alice的签名。 对公钥密码的攻击对公钥密码的攻击在所有公钥密码协议中，回避了Alice怎么得到Bob的公钥这件事。得到某人的公钥的最容易的方法是从某个地方的安全数据库中得到。这个数据库必须是公开的，以便任何人都可得到其他人的公钥。数字库也必须阻止Trent以外的其他人写入数据；否则Mallory可能用他选取的任意一个公钥代替Bob的，他那样做后，Bob就不能解读发给他的信息，但Mallory却能读。即使公钥存贮在安全数据库中，Mallory仍能在传送期间用另外的公钥来代替。为了防止这个问题，Trent可用他的私钥对每一公钥进行签名。当用这种方式时，Trent常被称为密钥鉴证机关密钥鉴证机关或密钥分配中心密钥分配中心（KDC）。在实际的实现中，KDC对由用户名、公钥和其他用户的重要信息组成的一组信息进行签名。被签名的这组信息存贮在KDC数据库中。当Alice得到Bob的密钥时，她验证KDC的签名以使自己确信密钥的有效性。在最后的分析中，对Mallory来说并不是不可能，只不过更困难了：Alice仍将KDC的公钥存贮在某个地方，Mallory只得用自己的公钥代替那个密钥，破坏数据库，然后用自己的密钥代替有效密钥（好像他就是KDC一样，用自己的私钥对所有密钥签名），再进行运算，如果Mallory要制造更多的麻烦，他甚至连文件签名都可以伪造。随机和伪随机序列的产生为什么我们不厌其烦地谈论随机数产生呢？随机数产生器已嵌入在大多数编译器中了，产生随机数仅仅是函数调用而已。为什么不用编译器的那种呢？ 不幸的是，那些随机数产生器对密码来说几乎肯定是不安全的，甚至可能不是很随机的。它们中的大多数都是非常差的随机数。随机序列产生器并不是随机的，因为它们不必要是完全随机的。像计算机游戏，大多数简单应用中只需几个随机数，几乎无人注意到它们，然而密码学对随机数产生器的性质是极其敏感的。用粗劣的随机数产生器，你会得到十分奇妙的相关和奇怪的结果。如果安全性依赖于你的随机数发生器，那么你得到的最后的东西就是这种奇妙的相关和结果。随机和伪随机序列的产生随机数产生器不能产生随机序列，它甚至可能产生不了乍看起来像随机序列的数。当然，在计算机上不可能产生真正的随机数。 “任何人考虑用数学的方法产生随机数肯定是不合情理的”。计算机确是怪兽：数据从一端进入，在内部经过完全可预测的操作，从另一端出来的却是不同的数据；把同一数据在不相干情况下输入进去，两次出来的数据是相同的；把同样的数据送入相同的两个计算机，它们的运算结果是相同的。计算机只能是一个有限的状态数（一个大数，但无论如何是有限的），并且输出状态总是过去的输入和计算机当前状态的确定的函数。这就是说计算机中的随机序列产生器（至少，在有限状态机中）是周期性的，周期性的任何东西都是可预测的。如果是可预测的，那么它就不可能是随机的。真正的随机序列产生器需要随机输入，计算机不可能提供这种随机输入。伪随机序列伪随机序列最好的计算机能产生的是伪随机序列产生器，什么意思呢？随机数序列是看起来是随机的序列，序列的周期应足够长，使得实际应用中相当长的有限序列都不是周期性的。就是说如果你需要十亿个随机比特，就不要选择仅在一万六千比特后就重复的序列产生器。这些相对短的非周期性的子序列应尽可能和随机序列没有多少区别。我们的意思是，如果一序列产生器是伪随机的，它应有下面的性质：看起来是随机的，这表明它通过了我们所能找到的所有随机性统计检验。人们在计算机上已经做了许多努力来产生好的伪随机序列，学术文献中有很多讨论伪随机序列产生器和各种随机性检验的，但所有这些产生器是周期的（都不可能例外）。然而周期大于2256比特的随机数序列，能够得到大量应用。这里的关键问题还是那些奇妙的相关性和奇怪的结果。如果你以某种方式使用它们，则每个随机数序列产生器都将产生这些结果。这正是为什么密码分析者用它来对系统进行攻击的原因密码学意义上安全的伪随机序列密码学意义上安全的伪随机序列密码的应用比其他大多数应用对伪随机序列的要求更严格。密码学的随机性并不仅仅意味着统计的随机性，虽然它也是其中的一部分。密码学意义上安全的伪随机数，还必须具有下面的性质：它是不可预测的。即使给出产生序列的算法或硬件和所有以前产生的比特流的全部知识，也不可能通过计算来预测下一个随机比特应是什么。密码学意义上安全的伪随机序列应该是不可压缩的除非你知道密钥。密钥通常是用来设置产生器的初始状态的种子。像任何密码算法一样，密码学意义上安全的伪随机序列产生器也会受到攻击，就好像加密算法有可能被破译一样，破译密码学意义上安全的伪随机序列产生器也是可能的。密码学讲的都是关于如何使产生器抵抗攻击。真正的随机序列真正的随机序列现在我们走进哲学家的领域，真有随机数这样的东西吗？随机序列是什么？你怎么知道序列是随机的？“101110100”比“101010101”更随机吗？量子力学告诉我们，在现实世界中有真正的随机性。但是在计算机芯片和有限状态机的确定世界中，这种随机性还能保持吗？暂且不说哲学。从我们的观点来说，如果一个随机序列产生器具有下面的第三条性质，它就是真正随机真正随机的：它不能可靠地重复产生。如果你用完全同样的输入对序列产生器操作两次（至少与人所能做到的最精确的一样），你将得到两个不相关的随机序列。满足这三条性质的产生器的输出对于一次一密乱码本、密钥的产生和任何其它需要真正随机数序列产生器的密码应用来说都是足够好的。难点在于确定真正的随机数。如果我用一个给定的密钥，用DES算法重复地对一个字符串加密，我将得到一个好的，看起来随机的输出。但你仍不可能知道它是否真的随机数，除非你租用美国国家安全局的DES破译专家。