第5章〓密钥分配与管理








密钥的分配与管理技术所解决的是网络环境中需要进行安全通信的端实体之间建立共享的密钥的问题，最简单的解决办法就是预先约定一个对称密钥序列并通过安全的渠道送达对方，以后按约定使用。如果密钥用量较大，且更换频繁，则密钥的传递就会成为严重的负担，而多数用户之间可能并没有安全的传输渠道，因此就需要研究在不安全的通信信道中传递密钥的方法。本章首先介绍单钥和公钥加密体制的密钥分配技术，然后介绍密钥托管及秘密分割技术，最后介绍常用的消息认证技术。


5.1
5.1〓单钥加密体制的密钥分配

5.1.1密钥分配的基本方法

两个用户在用单钥密码体制进行保密通信时，必须有一个共享的秘密密钥，而且为防止攻击者得到密钥，还必须经常更新密钥。因此，密码系统的强度也依赖于密钥分配技术。用户A和B获得共享密钥的方法基本上有以下几种。 

（1） 密钥由A选取并通过物理手段发送给B，如图51所示。

（2） 密钥由第三方选取并通过物理手段发送给A和B，如图52所示。



图51第一种方法




图52第二种方法



（3）  如果A、B事先已有一密钥，则其中一方选取新密钥后，用已有的密钥加密新密钥并发送给另一方，如图53所示。

（4） 如果A和B与第三方C分别有一保密信道，则C为A、B选取密钥后，分别在两个保密信道上发送给A、B，如图54所示。



图53第三种方法




图54第四种方法




前两种方法称为人工发送，密钥的人工发送在网络的链路加密时还是可行的，因为只有该链路上的两端交换数据。而密钥的人工发送在网络的端端加密方式中将不再可行，因为若加密是在网络层，则网络中任一对主机都必须有一共享密钥。如果有n台主机，则密钥数目为n(n-1)/2。当n很大时，密钥分配的代价非常大。

第三种方法对链路加密和端端加密方式都是可行的，但是攻击者一旦获得一个密钥就可获取以后的所有密钥。其初始密钥的分配代价仍然很大。

第四种方法广泛用于端端加密方式时的密钥分配，其中的第三方通常是一个负责为用户分配密钥的密钥中心(Key Distribution Center，KDC)。每个用户必须和KDC有一个共享密钥，称为主密钥。通过主密钥分配给一对用户的密钥称为会话密钥，用于这一对用户之间的保密通信。通信完成后，会话密钥即刻被销毁。若用户数为n个，则会话密钥数为n(n-1)/2。但主密钥数却只需n个，则可通过物理手段发送主密钥。

5.1.2密钥分配的一个实例

如图55所示，假定两个用户A、B分别与密钥分配中心有一个共享的主密钥kA和kB，A希望与B建立一个共享的一次性会话密钥，可通过以下几步来完成。




图55密钥分配实例


（1） A向KDC发出会话密钥请求。



表示请求的消息由两个数据项组成： 第一项Request是A和B的身份，第二项是这次业务的唯一识别符N1，称N1为一次性随机数，可以是时间戳、计数器或随机数。每次的N1都应不同，且为防止假冒，应使敌方对N1难以猜测。因此用随机数作为这个识别符最为合适。

（2） KDC为A的请求发出应答。

应答由kA加密，只有A能成功解密，且A可相信这一消息的确是由KDC发出的。

消息中包括A希望得到的两项内容： 

① 一次性会话密钥KS。

② A在（1）中发出的请求，包括一次性随机数N1，目的是使A将收到的应答与发出的请求相比较，确定是否匹配。

 A能验证自己发出的请求在被KDC收到之前，是否被他人篡改。

 A还能根据一次性随机数相信收到的应答不是重放的过去的应答。

消息中还有B希望得到的两项内容： 

① 一次性会话密钥kS。

② A的身份(例如A的网络地址)IDA。

 这两项由kB加密，将由A转发给B，以建立A、B之间的连接。

 并用于向B证明A的身份。

(3) A存储会话密钥kS，并向B转发EkB［kS‖IDA］。

① 因为转发的是由kB加密后的密文，所以转发过程不会被窃听。

② B收到后，可得到会话密钥kS，并由IDA可知另一方是A，而且还从EkB知道kS的确来自KDC。

③ 这一步完成后，会话密钥就安全地分配给了A、B。

(4) B用会话密钥kS加密另一个一次性随机数N2，并将加密结果发送给A。

(5) A以f(N2)作为对B的应答，其中f是对N2进行某种变换(例如加1)的函数，并将应答用会话密钥加密后发送给B。

这两步可使B相信第(3)步收到的消息不是一个重放。



注意： 
第(3)步就已完成密钥分配，第(4)、(5)两步结合第(3)步执行的是认证功能。






5.2
5.2〓公钥加密体制的密钥管理


接下来，从两个方面介绍公钥加密体制下的密钥分配： ①公钥加密体制所使用的公开密钥的分配； ②用公钥体制来分配单钥加密体制所需的密钥。

5.2.1公钥的分配

公钥加密的一个主要用途是分配单钥密码体制使用的密钥。公钥密码体制所用的公开密钥的分配方法如下： 

1. 公开发布

用户将自己的公钥发给每一个其他用户或向某一团体广播。这种方法虽简单却使任何人都可伪造这种公开发布。假冒者可解读发向被伪造方的加密消息，还可用伪造的密钥获得认证。

2. 公用目录表

公用目录表是指建立一个公用的公钥动态目录表，由某个可信的实体或组织承担目录表的建立、维护以及公钥的分布。这种方法比前一种安全性更高，但仍然容易受到攻击。

3. 公钥管理机构

公钥管理机构是在公钥目录表中对公钥的分配施加更严密的控制，使其安全性更强。公钥管理机构为各用户建立、维护动态公钥目录。同时每个用户都可靠地知道管理机构的公钥，而只有管理机构自己知道相应的秘密钥。公钥的分配如图56所示。



图56公钥管理机构分配公钥




(1) 用户A向公钥管理机构发送一带有时间戳的消息，请求获取用户B当前的公钥。

(2) 管理机构用自己的秘密钥SKAU加密对A的请求做出应答。A可以用管理机构的公开钥解密，并使A相信这个消息的确是来源于管理机构。其应答的消息有以下作用。 

① B的公钥PKB，A可用其对将要发往B的消息加密。

② A验证自己最初发出的请求在被管理机构收到以前未被篡改。

③ 时间戳使A相信管理机构发来的消息是B当前的公钥。

(3) A用B的公开钥对一个消息加密后发送给B，其中一项是A的身份IDA，另一项是一个一次性随机数N1，用于唯一地标识本次业务。

(4)、(5) B以相同的方式从管理机构获取A的公开钥。此时，A和B都已安全地得到了对方的公钥，但仍需要进一步的相互认证。

(6) B用PKA对一个消息加密后发送给A，其消息有A的一次性随机数N1和B产生的一个新的一次性随机数N2。因为只有B能解密(3)的消息，所以A收到的消息中的N1可使其相信通信的另一方的确是B。

(7) A用B的公钥对N2加密后返回给B，可使B相信通信的另一方的确是A。

以上7个消息中的前4个消息是用于获取对方的公钥。当用户得到对方的公钥后保存，使之以后使用时只发送(6)、(7)确认消息即可。但还必须定期地通过密钥管理机构中心获取通信对方的公钥，以免对方的公钥更新后无法保证当前的通信。

公钥管理机构方式的优缺点： 

(1) 每次密钥的获得由公钥管理机构查询并认证发送，用户不需要查表，提高了安全性。

(2) 公钥管理机构必须一直在线，由于每一用户要想和他人联系都需求助于管理机构，所以管理机构有可能成为系统的瓶颈。

(3) 由管理机构维护的公钥目录表易被敌手通过一定方式窜扰。

4. 公钥证书

公钥分配的另一种方法是公钥证书，用户通过公钥证书相互交换自己的公钥而无须与公钥管理机构联系。公钥证书由证书管理机构(Certificate Authority，CA)为用户建立，其证书的数据项有用户的公钥、身份和时间戳等，这些数据项经CA用自己的秘密钥签字后形成证书，其形式为CA=ESKCA［T，IDA，PKA］，其中IDA是用户A的身份，PKA是A的公钥，T是当前时间戳，SKCA是证书管理机构的秘密钥，CA即为用户A产生的证书，如图57所示。



图57公钥证书的产生过程


用户可将自己的公开钥通过公钥证书发给另一用户，接收方可用证书管理机构的公钥PKCA对证书加以验证，即DPKCA［CA］=DPKCA［ESKCA［T,IDA,PKA］］=(T,IDA,PKA)，因为只有用证书管理机构的公钥才能解读证书，同时获得了发送方的IDA和公开钥PKA。时间戳用于鉴定收到的证书是否是当前的或有效的。

5.2.2用公钥加密分配单钥密码体制的密钥

公开钥分配完成后，用户就可用公钥加密体制进行保密通信。然而由于公钥加密的速度过慢，以此进行保密通信不太合适，但用于分配单钥密码体制的密钥却非常合适。

1. 简单分配

图58简单描述了使用公钥加密算法建立会话密钥的过程，如果A希望与B通信，可通过以下几步建立会话密钥。



图58简单使用公钥加密算法建立会话密钥


（1）  A产生自己的一对密钥{PKA,SKA}，并向B发送PKA‖IDA，其中IDA表示A的身份。

（2）  B产生会话密钥kS，并用A的公开钥PKA对kS加密后发往A。

（3）  A由DSKA［EPKA［kS］］恢复会话密钥。因为只有A能解读kS，所以仅A、B知道这一共享密钥。

（4） A销毁{PKA,SKA}，B销毁PKA。

经过以上的步骤后，A、B就可以用单钥加密算法以kS作为会话密钥进行保密通信，通信完成后，又都将kS销毁。这种分配法虽然简单，但却由于A、B双方在通信前和完成通信后都没有存储密钥，因此密钥泄露的危险性最小，还可以防止双方的通信被攻击者监听。用公钥加密算法建立会话密钥这种协议容易受到攻击，若攻击者E已接入A、B双方的通信信道，就可通过以下不被察觉的方式截获双方的通信： 

（1） 与上面的步骤（1）相同。

（2）  E截获A的发送后，建立自己的一对密钥{PKE，SKE}，并将PKE‖IDA发送给B。

（3）  B产生会话密钥kS后，将EPKE［kS］发送出去。 

（4） E截获B发送的消息后，由DPKE［EPKE［kS］］解读kS。

（5） E再将EPKA［kS］发往A。

现在A和B知道kS，但并未意识到kS已被E截获。A、B在用kS通信时，E就可以实施监听。

2. 具有保密性和认证性的密钥分配

此种密钥分配过程具有保密性和认证性，因此既可防止被动攻击，又可防止主动攻击，如图59所示。假定A、B双方已完成公钥交换，可按以下步骤建立共享会话密钥： 



图59具有保密性和认证性的密钥分配


（1） A用PKB的公开钥加密A的身份IDA和一个一次性随机数N1后发往B，其中N1用于唯一地标识这一业务。

（2） B用PKA加密N1和B新产生的一次性随机数N2后发往A。B发来的消息中N1的存在可使A相信对方的确是B。

（3） A用PKB对N2加密后返回给B，使B相信对方的确是A。

（4） A选一会话密钥kS，然后将M=EPKB［ESKA［kS］］发给B，其中用B的公开钥加密是为保证只有B能解读加密结果，用A的秘密钥加密是保证该加密结果只有A能发送。

（5） B以DPKA［DSKB［M］］恢复会话密钥。


注意： 
这个方案其实是有漏洞的，即第4条消息容易被重放，假设敌方知道上次通话时协商的会话密钥kS，以及A对kS的签名和加密，则通过简单的重放即可实现对B的欺骗，解决的方法是将第3和第4条消息合并发送。




方案修改后的过程如图510所示。



图510具有保密性和认证性的密钥分配



5.2.3密钥管理的一个实例

DH密钥交换算法是W.Diffie和M. Hellman于1976年提出的第一个公钥密码算法，已在很多商业产品中得以应用。

（1） 算法的唯一目的是使得两个用户能够安全地交换密钥，得到一个共享的会话密钥，算法本身不能用于加、解密。

（2） 算法的安全性基于求离散对数的困难性。

算法过程如图511所示，其中p是大素数，a是p的本原根，p和a作为公开的全程元素。



图511DH密钥交换过程



用户A选择一保密的随机整数XA，并将YA=aXA mod p发送给用户B。类似地，用户B选择一保密的随机整数XB，并将YB=aXB mod p发送给用户A。然后A和B分别由k=YXAB mod p和k=YXBA mod p计算出共享密钥，这是因为： 


YXAB mod p=(aXB mod p)XA mod p=(aXB)XA mod p
=aXBXA mod p=aXAXB mod p
=(aXA mod p)XB mod p
=YXBA mod p




因XA、XB是保密的，敌方只能得到p、a、YA、YB，要想得到k，则必须得到XA、XB中的一个，这意味着需求离散对数。因此敌方求k是不可行的。

例51DH密钥交换算法示例。p＝97，a＝5，A和B分别秘密地选XA=36，XB=58，并分别计算

YA=536 mod 97=50，YB=558 mod 97=44

在交换YA、YB后，分别计算


k=YXAB mod p=4436 mod 97=75
k=YXBA mod p=5058 mod 97=75




5.3
5.3〓密钥托管

5.3.1密钥托管的背景

加密技术的快速发展对保密通信和电子商务起到了良好的推动作用。但是，也使得政府法律职能部门难以跟踪、截获犯罪嫌疑人员的通信，特别是在广泛采用公开密钥技术后，随之而来的是公开密钥的管理问题。对于中央政府来说，为了加强对贸易活动的监管，客观上也需要银行、海关、税务、工商等管理部门紧密协作。为了打击犯罪，还要涉及公安和国家安全部门。这样，交易方与密钥管理机构就不可避免地产生联系。为了监视和防止计算机犯罪活动，人们提出了密钥托管的概念。密钥托管与CA相结合，既能保证个人通信与电子交易的安全性，又能实现政法职能部门的管理介入，是今后信息安全策略的发展方向。

密钥托管(Key Escrow，KE)提供了一种密钥备份与恢复的途径，也称托管加密(Key Encryption)。从字面上理解，密钥托管就是指把通信双方的会话密钥交由合法的第三方，以便让合法的第三方利用得到的会话密钥解密双方通信的内容，从而监视双方的通信。这里所说的合法的第三方就是密钥托管的机构，一般是指政府保密部门和法律执行部门。其目的是保证对个人没有绝对的隐私和绝对不可跟踪的匿名性，即在强加密中结合对突发事件的解密能力。更确切地说，密钥托管是指为公众和用户提供更好的安全通信的同时，也允许授权者(包括政府保密部门、法律执行部门或有契约的私人组织等)为了国家、集团和个人隐私等安全利益，监听某些通信内容和解密有关密文。同时，这种技术还可以为用户提供一个备用的解密途径。所以，密钥托管也有“密钥恢复”(Key Recovery)、“数据恢复”和“特殊获取”等含义。这种技术产生的出发点是政府机构希望在需要时可通过密钥托管技术解密用户的一些特定的信息，此外当用户的密钥丢失或损坏时也可通过密钥托管技术恢复出自己的密钥。所以这个备用的手段不仅对政府部门有用，对用户自己也有用，为此，许多国家都制定了相关的法律法规。美国政府1993年4月颁布了EES(Escrowed Encryption Standard，托管加密标准)，该标准体现了一种新思想，即对密钥实行法定托管代理的机制。该标准使用的托管加密技术不仅提供了加密功能，同时也使政府可以在实施法律许可下的监听(如果向法院提供的证据表明，密码使用者是利用密码在进行危及国家安全和违反法律规定的事，经过法院许可，政府可以从托管代理机构取来密钥参数，经过合成运算，就可以直接监听通信)。美国政府希望用这种办法加强政府对密码使用的调控管理。

目前，在美国有许多组织都参加了密钥托管标准(KES)和EES的开发工作，系统的开发者是司法部门(DOJ)，NIST和基金自动化系统分部对初始的托管(Escrow)代理都进行了研究，国家安全局(NSA)负责KES产品的生产，联邦调查局(FBI)被指定为最初的合法性强制用户。

自从密钥托管出现以来，特别是美国政府的EES公布之后，在社会上引起了极大的反响，很多人对此项技术颇有争议。有关密钥托管争论的主要焦点在于以下两方： 一方认为，政府对密钥管理控制的重要性是出于安全考虑，这样可以允许合法的机构依据适当的法律授权访问该托管密钥，不但政府通过法律授权可以访问加密过的文件和通信，用户在紧急情况时，也可以对解密数据的密钥恢复访问； 另一方认为，密钥托管技术侵犯个人隐私，在他们看来密钥托管政策把公民的个人隐私置于政府情报部门手中，一方面违反了美国宪法和个人隐私法，另一方面也使美国公司的密码产品出口受到极大的限制和影响。

从技术角度来看，赞成和反对的意见也都有。赞成意见认为，应宣扬和推动这种技术的研究与开发； 反对意见认为，该系统的技术还不成熟，基于密钥托管的加密系统的基础设施会导致安全性能下降，投资成本增高。

本书对这种争议不做过多评论，重点讨论这种技术本身。

5.3.2密钥托管的定义和功能

密钥托管的实现手段通常是把加密的数据和数据恢复密钥联系起来，数据恢复密钥不必是直接解密的密钥，但由它可以得到解密密钥。理论上数据恢复密钥由所信任的委托人持有，委托人可以是政府保密部门、法院或有契约的私人组织。一个密钥也可能在数个这样的委托人中被拆分成多个分量，分别由多个委托人持有。授权机构(如调查机构或情报机构)可通过适当的程序(如获得法院的许可)，从数个委托人手中恢复密钥。

从技术实现角度，可以将密码托管定义为： 密钥托管是指用户向CA在申请数据加密证书之前，必须把自己的密钥分成t份交给可信赖的t个托管人。任何一个托管人都无法通过自己存储的部分用户密钥恢复完整的用户密码。只有这t个人存储的密钥合在一起才能得到用户的完整密钥。因此，密钥托管有如下重要功能。 

（1） 防止抵赖。在商务活动中，通过数字签名即可验证自己的身份以防抵赖。但当用户改变了自己的密码，他就可抵赖没有进行过此商务活动。为了防止这种抵赖，有几种办法： 一种是用户在改密码时必须向CA说明，不能私自改变； 另一种是密钥托管，当用户抵赖时，这t个托管人就可出示他们存储的密钥合成用户的密钥，使用户无法抵赖。

（2） 政府监听。政府、法律职能部门或合法的第三者为了跟踪、截获犯罪嫌疑人员的通信，需要获得通信双方的密钥。这时合法的监听者可通过用户的委托人收集密钥片后得到用户密钥，进而进行监听。

（3）  用户密钥恢复。用户遗忘了密钥想恢复密钥时，可从委托人那里收集密钥片恢复密钥。

5.3.3美国托管加密标准简介

1993年4月，美国政府为了满足其电信安全、公众安全和国家安全，提出了托管加密标准EES，该标准所使用的托管加密技术不仅提供了强加密功能，同时也为政府机构提供了实施法律授权下的监听功能。这一技术是通过一个防窜扰的芯片(称为Clipper芯片)来实现的。

它有两个特性： 

（1）  一个加密算法——Skipjack算法，该算法是由NSA设计的，用于加(解)密用户间通信的消息。该算法已于1998年3月公布。

（2） 为法律实施提供“后门”的部分——法律实施存取域(Law Enforcement Access Field，LEAF)。通过这个域，法律实施部门可在法律授权下，实现对用户通信的解密。

1. Skipjack算法

Skipjack算法是一个单钥分组加密算法，密钥长80b，输入和输出的分组长均为64b。

可使用4种工作模式： 电码本模式，密码分组链接模式，64b输出反馈模式，1b、8b、16b、32b或64b密码反馈模式。

算法的内部细节在向公众公开以前，政府邀请了一些局外人士对算法做出评价，并公布了评价结果。评价结果认为算法的强度高于DES，并且未发现陷门。

Skipjack的密钥长是80b，比DES的密钥长24b，因此通过穷举搜索的蛮力攻击比DES多224倍的搜索。所以若假定处理能力的费用每18个月减少一半，那么破译它所需的代价要1.5×24=36年才能减少到今天破译DES的代价。

2. 托管加密芯片

Skipjack算法以及在法律授权下对加密结果的存取是通过防窜扰的托管加密芯片来实现的。芯片装有以下部分： 

（1） Skipjack算法。

（2） 80b的族密钥KF(Family Key)，同一批芯片的族密钥都相同。

（3） 芯片单元识别符UID(Unique IDentifier)。

（4） 80b的芯片单元密钥KU(Unique Key)，它是两个80b的芯片单元密钥分量(KU1,KU2)的异或。

（5） 控制软件。

这些部分被固化在芯片上。编程过程是在由两个托管机构的代表监控下的安全工厂中进行的，一段时间一批。编程过程如图512所示。



图512芯片编程过程


首先，托管机构的代表通过向编程设备输入两个参数r1、r2(随机数)对芯片编程处理器初始化。芯片编程处理器对每个芯片，分别计算以上两个初始参数r1、r2和UID的函数，作为单元密钥的两个分量KU1和KU2。求KU1 XOR KU2，作为芯片单元密钥KU。UID和KU放在芯片中。

然后，用分配给托管机构1的密钥k1加密KU1得Ek1(KU1)。类似地，用分配给托管机构2的加密密钥k2加密KU2得Ek2(KU2)。(UID，Ek1(KU1))和(UID，Ek2(KU2))分别给托管机构1和托管机构2，并以托管形式保存。以加密方式保存单元密钥分量是为了防止密钥分量被窃或泄露。

编程过程结束后，编程处理器被清除，以使芯片的单元密钥不能被他人获得或被他人计算，只能从两个托管机构获得加密的单元密钥分量，并且使用特定的政府解密设备来解密。

3. 用托管加密芯片加密

通信双方为了使用Skipjack算法加密他们的通信，都必须有一个装有托管加密芯片的安全的防窜扰设备。该设备负责实现建立安全信道所需的协议，包括协商或分布用于加密通信的80b秘密会话密钥kS。

例如，会话密钥可使用DH密钥交换算法，该算法执行过程中，两个设备仅交换公共值即可获得公共的秘密会话密钥。

80b的会话密钥kS建立后，被传送给加密芯片，用于与初始量IV(由芯片产生)一起产生LEAF。

控制软件使用芯片单元密钥KU加密kS，然后将加密后的结果和芯片识别符UID、认证符A链接，再使用公共的族密钥KF加密以上链接的结果而产生LEAF。其过程如图513所示。



图513LEAF过程


最后将IV和LEAF传递给接收芯片，用于建立同步。同步建立后，会话密钥就可用于通信双方的加解密。对于语音通信，消息串(语音)首先应被数字化。

图514显示的是在发送者的安全设备和接收者的安全设备之间传送LEAF以及用会话密钥kS加密明文消息hello的过程。图中未显示初始量。



图514传送LEAF以及用会话密钥kS加密明文消息“hello”的过程


在双向通信(如电话)中，通信每一方的安全设备都需传送一个IV和由其设备芯片计算出的LEAF。然后，两个设备使用同一会话密钥kS来加密传送给通信对方的消息，并解密由对方传回的消息。

4. 密钥托管的一个应用

政府机构在进行犯罪调查时，为了监听被调查者的通信，首先必须取得法院的许可证书，并将许可证书出示给通信服务的提供者(电信部门)，然后从电信部门租用线路用来截取被监听者的通信。

如果被监听者的通信是经过加密的，则被截获的通信首先通过一个政府控制的解密设备。解密设备可识别由托管芯片加密的通信，取出LEAF和IV，并使用族密钥KF解密LEAF以取出芯片识别符UID和加密的会话密钥EKU(kS)。

政府机构将芯片识别符UID、法院许可监听的许可证书、解密设备的顺序号以及政府机构对该芯片的单元密钥分量的要求一起给托管机构。

托管机构在收到并验证政府机构传送的内容后，将被加密的单元密钥分量Ek1(KU1)和Ek2(KU2)传送给政府机构的解密设备。

解密设备分别使用加密密钥k1和k2解密Ek1(KU1)和Ek2(KU2)以得到KU1、KU2，求它们的异或KU1 XOR KU2，即为单元密钥KU。

由单元密钥KU解密EKU(kS)，得到被调查者的会话密钥kS。最后解密设备使用kS解密被调查者的通信。

为了实现解密，解密设备在初始化阶段，应安装族密钥KF和密钥加密密钥k1、k2。

托管机构在传送加密的密钥分量时，也传送监听的截止时间。因此解密设备的设计应使得它到截止时间后，可自动销毁芯片单元密钥及用于得到单元密钥的所有信息。

同时，因为每一次新的会话用一新的会话密钥加密，所以解密设备在监听的截止时间之前，在截获调查者新的会话时，可不经过托管机构而直接从LEAF中提取并解密会话密钥。

因此，除在得到密钥时可有一个时间延迟外，对被截获通信的解密也可在监听的有效期内有一个时间延迟。这种时间延迟对有些案情极为重要，如监听进行绑架的犯罪分子或监听有计划的恐怖活动。


5.4
5.4〓秘密分割



秘密分割是将某一密码信息k分成n片(ki,i=1,2,…,n)给n个人，只有当这n个人同时给出自己的秘密分片时，才能恢复信息。它与秘密共享具有相似性，但是没有秘密共享的要求高，也很容易实现。在很多场合，为了避免权力过于集中，必须将秘密分割开来由多人掌管。只有达到一定数量的人同时合作，才能恢复这个秘密。这就是密码学中的门限方案。

门限方案： 秘密s被分割成n个部分信息，每一部分信息称为一个子密钥，每个子密钥都由不同的参与者掌握，使得只有k个或k个以上的参与者共同努力才能重构信息s； 否则无法重构消息s。这种方案就称为(k,n)门限方案，k称为方案的门限值。

5.4.1秘密分割门限方案

在导弹控制发射、重要场所通行检验等情况下，通常必须由两人或多人同时参与才能生效，这时都需要将秘密分给多人掌管，而且必须有一定数量的掌管秘密的人同时到场才能恢复这一秘密。由此，引入门限方案(Threshold Schemes)的一般概念。

定义51设秘密s被分成n个部分信息，每一部分信息称为一个子密钥或影子(Share or Shadow)，由一个参与者持有，使得： 

（1） 由k个或多于k个参与者所持有的部分信息可重构s。

（2） 由少于k个参与者所持有的部分信息无法重构s。

则称这种方案为(k,n)秘密分割门限方案，k称为方案的门限值。

如果一个参与者或一组未经授权的参与者在猜测秘密s时，并不比局外人猜秘密时有优势，即由少于k个参与者所持有的部分秘密信息得不到秘密s的任何信息，则称这个方案是完善的，即(k,n)秘密分割门限方案是完善的。

为了可靠性也要适当控制n-k的值，以免该值太小而使得秘密的恢复由于有大于n-k个人员不能到场而无法恢复。所以(k,n)门限的安全性在于既要防止少于k个人合作恢复秘密，又要防止对t个人的攻击而阻碍秘密的恢复。

下面介绍最具代表性的秘密分割门限方案。

5.4.2Shamir门限方案

Shamir门限方案是典型的秘密分割门限方案。下面详细论述该方案的原理。

Shamir门限方案基于多项式的Lagrange插值公式。
插值是数学分析中的一个基本问题。

已知一个函数φ(x)在k个互不相同的点的函数值φ(xi)(i=1,2,…,k)，寻求一个满足f(xi)=φ(xi)(i=1,2,…,k)的函数f(x)来逼近φ(x)，f(x)称为φ(x)的插值函数，也称插值多项式。

已知φ(x)在k个互不相同的点的函数值φ(xi)(i=1,2,…,k)，可构造k-1次Lagrange插值多项式： 


f(x)=∑kj=1φ(xj)∏kl=1l≠jx-x1xj-x1




也可认为是已知k-1次多项式f(x)的k个互不相同的点的函数值f(xi)(i=1,2,…,k)，构造多项式f(x)。

若把密钥s取作f(0)，n个子密钥取作f(xi)(i=1,2,…,n)，那么利用其中的任意k个子密钥可重构f(x)，从而可得密钥s。

这种门限方案也可按如下更一般的方式来构造： 

（1） 设GF(q)是一有限域，其中q是一个大素数，满足q≥n+1。

（2） 秘密s是在GF(q)＼{0}上均匀选取的一个随机数，表示为s∈RGF(q)＼{0}。

（3） k-1个系数a1,a2,…，ai,…,ak-1的选取也满足ai∈RGF(q)＼{0} (i=1,2,…,k-1)。

（4） 在GF(q)上构造一个k-1次多项式f(x)=a0+a1x+…+ak-1xk-1。

（5） n个参与者记为P1,P2,…,Pi,…,Pn，Pi分配到的子密钥为f(i)。

（6） 如果任意k个参与者Pi1,Pi2,…,Pil,…,Pik(1≤i1<i2<…il<…<ik≤n)要想得到秘密s，可使用{(il,f(il))|l=1,2,…,k}构成如下的线性方程组： 


a0+a1(i1)+…+ak-1(i1)k-1=f(i1)
a0+a1(i2)+…+ak-1(i2)k-1=f(i2)
︙
a0+a1(ik)+…+ak-1(ik)k-1=f(ik)




因为il(l=1,2，…,k)均不相同，所以可由Lagrange插值公式构成如下多项式： 


f(x)=∑kj=1f(ij)∏kl=1l≠jx-i1ij-i1(mod q)




从而可得秘密s＝f(0)。

然而参与者仅需知道f(x)的常数项f(0)而无须知道整个多项式f(x)，所以令x＝0，仅需以下表达式就可以求出s： 


s=(-1)k-1∑kj=1f(ij)∏kl=1l≠ji1ij-i1(mod q)




如果k-1个参与者想获得秘密s，他们可构造出由k-1个方程构成的线性方程组，其中有k个未知量。对GF(q)中的任一值s0，可设f(0)＝s0，这样可得第k个方程，并由Lagrange插值公式得出f(x)。因此对每一s0∈GF(q)都有唯一的一个多项式满足方程组。所以已知k-1个子密钥得不到关于秘密s的任何信息，因此这个方案是完善的。

例52Shamir门限方案示例。设k=3，n=5，q=19，s=11，随机选取a1=2，a2=7，得多项式为： 


f(x)=(7x2+2x+11) mod 19




分别计算


f(1)=（7×12+2×1+11） mod 19=1
f(2)=（7×22+2×2+11） mod 19=5
f(3)=（7×32+2×3+11） mod 19=4
f（4）=（7×42+2×4+11） mod 19=17
f（5）=（7×52+2×5+11） mod 19=6




得5个子密钥。

如果知道其中的3个子密钥f(2)=5,f(3)=4,f(5)=6，就可重构出f(x)： 


5×(x-3)(x-5)(2-3)(2-5) mod 19=5×(3-1 mod 19)(x-3)(x-5)
=5×13×(x-3)(x-5)
4×(x-2)(x-5)(3-2)(3-5) mod 19=4×((-2)-1 mod 19)(x-2)(x-5)
=4×9×(x-2)(x-5)
6×(x-2)(x-3)(5-2)(5-3) mod 19=6×(6-1 mod 19)(x-2)(x-3)
=6×16×(x-2)(x-3)




所以

f(x)=［65(x-3)(x-5)+36(x-2)(x-5)+96(x-2)(x-3)］ mod 19
=7x2+2x+11


从而得秘密为s＝11。

5.4.3基于中国剩余定理的门限方案

设m1<m2<…<mn是n个大于1的整数，满足(mi,mj)=1 (对任意的i,j,i≠j)和m1m2…mk>mnmn-1…mn-k+2(注意这里的条件m1<m2<…<mn是必需的，在此条件下，m1m2…mk>mnmn-1…mn-k+2表明最小的k个数的乘积也比最大的k-1个数的乘积大，从而使得m1,m2,…,mn中任意k个数的乘积都不比m1m2…mk小)。

又设s是秘密数据，满足： 


mnmn-1…mn-k+2<s<m1m2…mk




这意味着对任意k个数的乘积T，s=s mod T,而任意的k-1个数的乘积R，则s mod R在数值上不等于s。

计算M=m1m2…mk，si=s(mod mi)(i=1,2,…,n)，以(si,mi,M)作为一个子密钥，集合{(si,mi,M)}i=1~n即构成了一个(k,n)门限方案。

这是因为，在k个参与者中，每个i、j计算： 


Mij=M/mij，Nij=M-1ij(mod mij)，yij=sijMijNij




结合起来根据中国剩余定理可求得： 


s=∑kj=1yijmod ∏kj=1mij




由于任意k个或k个以上的模数相乘都比s大，它们恢复出来的s必然相同，而少于k个参与者则不行。


5.5
5.5〓消息认证

5.5.1消息认证的基本概念

消息认证就是验证所收到的消息确实来自真正的发送方且是未被修改的消息，也可以验证消息的顺序和及时性，即消息认证是使接收者能够检验收到的消息是否真实的方法。因此，消息认证具有三层含义： 一是检验消息来源的真实性，即对消息的发送者进行身份认证，确定信息的发送者是真的而不是冒充的； 二是检验消息的完整性，即验证消息在传送或存储过程中是否被篡改、删除或插入等； 三是检验消息的时效性，即验证消息在传送过程中是否被重传或延迟等。

消息认证实际上是对消息本身产生一个冗余的信息——消息认证码(Message Authentication Code，MAC)。消息认证码是利用密钥对要认证的变长消息和收发双方共享的密钥的一个函数值产生的带密钥的消息摘要函数，它对于要保护的信息来说是唯一的和一一对应的，可以有效地保护消息的完整性以及实现发送方消息的不可抵赖性和不能伪造性。消息认证码的安全性取决于两方面： ①采用的加密算法，即利用公钥加密算法对块加密，以保证消息的不可抵赖性和完整性； ②待加密数据块的生成方法。

当需要进行消息认证时，仅有消息作为输入是不够的，需要加入密钥k，消息认证码MAC是与这个密钥k相关的单向杂凑函数。消息认证码通常表示为： 


MAC=Ck(M)



其中，M是长度可变的消息，k是收、发双方共享的密钥，函数值Ck(M)是定长的认证码，即密码校验和。


5.5.2消息加密认证
1. 在对称加密体制下

在对称加密体制下的消息加密认证如图515和图516所示。由于攻击者不知道密钥k，他也就不知道如何改变密文中的信息位才能在明文中产生预期的改变。



图515在对称加密体制下的消息加密认证方式1





图516在对称加密体制下的消息加密认证方式2


接收方可以根据解密后的明文是否具有合理的语法结构来进行消息认证。但有时发送的明文本身并没有明显的语法结构或特征，例如二进制文件，因此很难确定解密后的消息就是明文本身。

2. 在公钥加密体制下

在公钥加密体制下的消息加密认证如图517所示。由于只有A有用于产生ESKA(M)的密钥，所以此方法提供认证。



图517在公钥加密体制下的消息加密认证



5.5.3Hash函数

密码学上的Hash函数也称杂凑函数或报文摘要函数等，是一种将任意长度的消息m压缩(或映射)到某一固定长度的消息摘要H(m)的函数。H(m)也称消息m的指纹。一个Hash函数是一个多对一的映射。

1. Hash函数的分类

Hash函数按是否需要密钥可分为以下两类。 

（1） 不带密钥的Hash函数，它只有一个被通常称为消息的输入参数。

（2） 带密钥的Hash函数，它有两个不同的输入，分别称为消息和密钥。

按设计结构，散列算法可以分为三大类： 标准Hash、基于分组加密Hash和基于模数运算Hash。

标准Hash函数有两大类： MD系列的MD4、MD5、HAVAI、RIPEMD、RIPEMD160等； SHA系列的SHA1、SHA256、SHA384、SHA512等，这些Hash函数体现了目前主要的Hash函数设计技术。

2. Hash函数的性质

从应用需求上来说，Hash函数H必须满足以下性质。 

（1） H能够应用到任何大小的数据块上。

（2） H能够生成大小固定的输出。

（3） 对任意给定的x，H(x)的计算相对简单，使得硬件和软件的实现可行。

从安全意义上来说，Hash函数H应满足以下性质。



（1） 对任意给定的散列值h，找到满足H(x)=h的x在计算上是不可行的。

（2） 对任意给定的找到满足H(x)=H(y)而x≠y的对(x,y)在计算上是不可行的。

（3） 要发现满足H(x)=H(y)而x≠y的对(x,y)是计算上不可行的。

满足以上前两个性质的杂凑函数称为弱Hash函数，或称杂凑函数H(x)为弱无碰撞的； 如果还满足第（3）个性质，就称为强Hash函数，或称杂凑函数H(x)为强无碰撞的。

第（1）个性质是单向性的要求，通常也称抗原像性。第（2）个性质是弱无碰撞性，也称抗第二原像性，目的是防止伪造，即将一份报文的指纹伪造成另一份报文的指纹在计算上是不可行的。第（3）个性质是强无碰撞性，也称抗碰撞性，它防止对杂凑函数实施自由起始碰撞攻击或称生日攻击。

杂凑函数各性质之间的关系如下。 

性质51杂凑函数的强无碰撞性(抗碰撞性)隐含弱无碰撞性(抗第二原像性)。

证明51假设杂凑函数H(x)不具有弱无碰撞性，则对于一个x，就可以找到一个y(≠x)，使得H(x)=H(y)，这时(x，y)是不同输入杂凑为同一输出，而这与强无碰撞性矛盾。


3. 常用Hash算法

1) MD5 Hash算法

MD4是MD5杂凑算法的前身，由Ronald Rivest于1990年10月作为RFC提出，1992年4月公布的MD4的改进(RFC 1320，1321)称为MD5。

MD5算法的输入消息可任意长，压缩后输出为128b。MD5算法框图如图518所示。



图518MD5算法框图



MD5算法的步骤如下。 

（1） 分组填充，如图519所示。




图519MD5算法分组填充


如果消息长度大于264，则取其对264的模。

执行完后，消息的长度为512的倍数(设为L倍)，则可将消息表示为分组长为512的一系列分组Y0,Y1,…,YL-1，而每一分组又可表示为16个32b长的字，这样消息中的总字数为N=L×16，因此消息又可按字表示为M［0,…,N-1］。

（2） 缓冲区初始化。
Hash函数的中间结果和最终结果保存于128位的缓冲区中，缓冲区用32位的寄存器表示。可用4个32b字表示： A、B、C、D。初始存数以十六进制表示为： 


A=01234567
B=89ABCDEF
C=FEDCBA98
D=76543210




（3） HMD5运算。
以分组为单位对消息进行处理每一分组Yq(q=0,…,L-1)都经一压缩函数HMD5处理。HMD5是算法的核心，如图520所示，其中又有4轮处理过程。



图520HMD5运算示意图


HMD5的4轮处理过程结构一样，但所用的逻辑函数不同，分别表示为F、G、H、I。每轮的输入为当前处理的消息分组Yq和缓冲区的当前值A、B、C、D，输出仍放在缓冲区中以产生新的A、B、C、D。

每轮又要进行16步迭代运算，4轮共需64步完成。

第四轮的输出与第一轮的输入相加得到最后的输出。

压缩函数中的一步迭代过程如图521所示。





图521压缩函数中的一步迭代过程


其中基本逻辑函数g定义如表51所示。


表51基本逻辑函数g定义



轮
基本逻辑函数
g(b,c,d)
1
F(b,c,d)
(b∧c)∨(b-∧d)
2
G(b,c,d)
(b∧d)∨(c∧d-)
3
H(b,c,d)
bcd
4
I(b,c,d)
c(b∨d-)



MD5的输出为128b，若采用纯强力攻击寻找一个消息具有给定Hash值的计算困难性为2128，用每秒可试验1 000 000 000个消息的计算机需时1.07×1022年。

采用生日攻击法，找出具有相同杂凑值的两个消息需执行264次运算。

如果两个输入串的Hash函数的值一样，则称这两个串是一个碰撞(Collision)。既然是把任意长度的字符串变成固定长度的字符串，所以，必有一个输出串对应无穷多个输入串，碰撞是必然存在的。

2004年8月17日，在美国加利福尼亚州圣巴巴拉召开的国际密码学会议上，山东大学王小云教授公布了快速寻求MD5算法碰撞的算法。

2) SHA算法

（1） 算法简介。 

① 由NIST设计。

② 1993年成为联邦信息处理标准(FIPS PUB 180)。

③ 基于MD4算法，与之非常类似。

④ 输入为小于264b的任意消息。

⑤ 分组512b。

⑥ 输出160b。

(2) 算法描述。 

① 消息填充： 与MD5完全相同。

② 附加消息长度： 64b。

③ 缓冲区初始化。 


A＝67452301
B＝EFCDAB89
C＝98BADCFB
D＝10325476
E＝C3D2E1F0




(3) 分组处理，如图522所示。

(4) SHA1压缩函数(单步)，如图523所示。

(5) SHA1的基本逻辑函数ft如表52所示，其中∧、∨、-、分别表示与、或、非、异或4个逻辑运算。



图522分组处理示意图




图523SHA1压缩函数示意图




表52SHA中基本逻辑函数的定义



轮
基本函数
函数值
1
f1(B,C,D)
(B∧C)∨(∧D)
2
f2(B,C,D)
BCD
3
f3(B,C,D)
(B∧C)∨(B∧D)∨(C∧D)
4
f4(B,C,D)
BCD


(6) Wt： 从当前512位输入分组导出的32位字。

如图524所示，下面说明如何由当前的输入分组(512b)导出Wt(32b)。前16个值(即W0,W1,…,W15)直接取为输入分组的16个相应的字，其余值(即W16,W17,…,W79)取为： 


Wt=CLS1(Wt-16Wt-14Wt-8Wt-3)




图524Wt： 从当前512位输入分组导出的32位字示意图




与MD5比较，MD5直接用一个消息分组的16个字作为每步迭代的输入，而SHA则将输入分组的16个字扩展成80个字以供压缩函数使用，从而使得寻找具有相同压缩值的不同的消息分组更为困难。

(7) kt： 加法常量，如表53所示。


表53加法常量



步骤
十六进制
0≤t≤19
kt=5A827999
20≤t≤39
kt=6ED9EBA1
40≤t≤59
kt=8F1BBCDC
60≤t≤79
kt=CA62C1D6



3) SHA与MD5的比较

(1) 抗穷举搜索能力。 

① 寻找指定Hash值，SHA为O(2160)，MD5为O(2128)。

② 生日攻击，SHA为O(280)，MD5为O(264)。

(2) 抗密码分析攻击的强度，SHA似乎高于MD5。

(3) 速度。SHA较MD5慢。

(4) 简捷与紧致性。描述都比较简单，都不需要大的程序和代换表。

4) 其他Hash算法

(1) MD4。

① MD4使用3轮运算，每轮16步； MD5使用4轮运算，每轮16步。

② MD4的第一轮运算没有使用加法常量，第二轮运算中每步迭代使用的加法常量相同，第三轮运算中每步迭代使用的加法常量相同，但不同于第二轮运算使用的加法常量； MD5的64部使用的加法常量T［i］均不同。

③ MD4使用3个基本逻辑函数，MD5使用4个。

④ MD5中每步迭代的结果都与前一步的结果相加，MD4则没有。

⑤ MD5比MD4更复杂，所以其执行速度也更慢，Rivest认为增加复杂性可以增加安全性。

(2)  RIPEMD160。

① 欧共体RIPE项目组提出。

② 输入可以是任意长的报文，输出160位摘要。

③ 对输入按512位分组。以分组为单位处理。

④ 算法的核心是具有10轮运算的模块，10轮运算分成两组，每组5轮，每轮16步迭代。



〓〓习题5

1. 密钥管理的原则是什么?

2. 对称密码体制的密钥管理策略是什么?

3. 对称密钥体制下密钥分配的方法有哪些?

4. 公钥密码体制的秘密密钥的分配方法有哪些?

5. 公钥密码体制的公钥管理策略是什么?

6. 公钥密钥体制如何实施公开密钥的分配?

7. 随机数在密码算法中的使用有哪些?简述DES的输出反馈模式产生随机数的工作原理。

8. 密钥托管的目的是什么?简述密钥托管的工作原理。

9. 在公钥体制中，每一用户U都有自己的公开钥PKU和秘密钥SKU。如果任意两个用户A、B按以下方式通信，A发给B消息(EPKB(m),A)，B收到后，自动向A返回消息(EPKA(m),B)以通知A、B确实收到报文m。

(1) 问用户C怎样通过攻击手段获取报文m?

(2) 若通信格式变为： 

A发给B消息： EPKB(ESKA(m),m,A)

B向A返回消息： EPKA(ESKB(m),m,B)

这时的安全性如何?分析A、B这时如何相互认证并传递消息m。

10.  DH密钥交换算法在实施时易受中间人攻击，即攻击者截获通信双方通信的内容后可分别冒充通信双方，以获得通信双方协商的密钥。详细分析攻击者如何实施攻击。

11. 在DH密钥交换过程中，设大素数p=11，a=2是p的本原根。

(1) 用户A的公开钥YA=9，求其秘密钥XA。

(2) 设用户B的公开钥YB=3，求A和B的共享密钥k。

12. 线性同余算法Xn+1=(aXn) mod 24，问： 

(1) 该算法产生的数列的最大周期是多少?

(2) a的值是多少?

(3) 对种子有何限制?

13. 在Shamir门限方案中，设k=3，n=5，q=17，5个子密钥分别是8、7、10、0、11，从中任选3个，构造插值多项式并求秘密数据s。