_现代密码学与应用09_密钥建立协议

1、现代密码学与应用 密钥建立协议主讲人：余艳玮主讲人：余艳玮E-mail: 2021-11-202021-11-202 22021-11-202021-11-203 3参考书籍参考书籍 Handbook of Applied CryptographyHandbook of Applied Cryptography: : Chapter 12Chapter 12 Applied Cryptography: Protocols, Applied Cryptography: Protocols, algorithms, and source code in Calgorithms, and sourc

2、e code in C：Chapter 22Chapter 222021-11-202021-11-204 4大纲大纲一、一、基本概念基本概念二、基于对称加密的密钥传输二、基于对称加密的密钥传输三、基于对称技术的密钥协商三、基于对称技术的密钥协商四、基于公钥加密的密钥传输四、基于公钥加密的密钥传输五、基于非对称技术的密钥协商五、基于非对称技术的密钥协商六、秘密共享六、秘密共享七、会议密钥生成七、会议密钥生成八、密钥建立协议的分析八、密钥建立协议的分析一、基本概念一、基本概念2021-11-202021-11-206 6密钥建立协议密钥建立协议 是这样的一个协议，它能够为两个或多个参与方是这样的

3、一个协议，它能够为两个或多个参与方生成生成共享共享密钥密钥，供随后的密码方案使用。，供随后的密码方案使用。生成的共享密钥，常称为或用于推导生成的共享密钥，常称为或用于推导会话密钥会话密钥 协议：是协议：是一系列步骤一系列步骤，它，它包括两方和多方包括两方和多方，设，设计它的目的是计它的目的是要完成一项任务要完成一项任务。协议是从开始到结束的一个序列序列，每步必须依次执行完成协议至少需要两个人至少需要两个人协议的目的目的是为了做一些事情2021-11-202021-11-207 7分类分类密钥建立协议可分为：密钥建立协议可分为： 密钥传输协议：密钥传输协议： 它使得它使得一个参与方一个参与方可以

4、可以建立或获得建立或获得一个秘密一个秘密值，并将它值，并将它安全地传输安全地传输给其他参与方给其他参与方 密钥协商协议：密钥协商协议： 两个两个( (或更多的或更多的) )参与方参与方共同共同提供消息，提供消息，推导推导出一个共享密钥，（理想状态下）任何一方出一个共享密钥，（理想状态下）任何一方不能预先确定结果值不能预先确定结果值2021-11-202021-11-208 8可信服务器的使用可信服务器的使用 有多种名称：有多种名称：可信第三方可信第三方(TTP)(TTP)可信服务器可信服务器 (TS)(TS)认证服务器认证服务器 (AS)(AS)密钥分发中心密钥分发中心(KDC)(KDC)密钥

5、变换中心密钥变换中心(KTC)(KTC)证书颁发机构证书颁发机构(CA)(CA) 用于初始化系统设置和用于初始化系统设置和( (或或) )在线活动在线活动( (即包即包括实时参与）括实时参与）2021-11-202021-11-209 9实体认证、密钥认证和密钥确认实体认证、密钥认证和密钥确认 实体认证：实体认证：通过对秘密的拥有来证明身份身份 (实时性) 数据源认证数据源认证( (消息认证消息认证) )：MAC、数字签名、加密和hash函数 密钥确认：密钥确认：一个参与方能确认第二方(该方身份可能未识别)实际已经拥有拥有一个特定的密钥密钥认证焦点认证焦点为一些参与方是否可提供拥有给定密钥的证

6、据拥有给定密钥的证据 密钥认证：密钥认证： (认证焦点是身份)隐式密钥认证：隐式密钥认证：认证焦点是可能共享一个密钥的参与方的身份身份显式密钥认证：显式密钥认证：可确定一个身份已识别身份已识别的参与方实际拥有实际拥有一个给定密钥密钥 同时具有隐式密钥认证和密钥确认的特性 密钥建立协议通常附加单方的密钥确认密钥建立协议通常附加单方的密钥确认( (如，在最后的消如，在最后的消息中附加会话密钥的单向杂凑值息中附加会话密钥的单向杂凑值) )一个实体可能拥有多个秘密一个实体可能拥有多个秘密一个秘密也可能被多个实体拥有一个秘密也可能被多个实体拥有当一个秘密只能被两方拥有时，该秘密可作为身份的表征当一个秘密

7、只能被两方拥有时，该秘密可作为身份的表征2021-11-202021-11-2010102021-11-202021-11-201111会话密钥的使用动机会话密钥的使用动机 会话密钥：临时秘密会话密钥：临时秘密被严格限制在一小段时间内使用，如一次单独的通信会话 动机：动机：针对密码分析攻击，限制可用的密文(在一个规定的密钥下)在会话密钥暴露的事件中，限制暴露的时间周期以及数据量仅仅当实际需要时才建立密钥，从而避免长期存储大量不同的密钥(如，当一个终端需要与众多的参与方进行通信的情况下)在通信会话或应用过程中建立独立性2021-11-202021-11-201212密钥建立技术的特性密钥建立技术

8、的特性 认证的种类：认证的种类：实体认证?密钥认证？密钥确认? 认证的相互性：认证的相互性：单方面？相互？ 密钥的新鲜度密钥的新鲜度 密钥控制：密钥控制：密钥传输：密钥传输：某一参与方选择密钥值密钥协商：密钥协商：共同决定，任一参与方不能控制、也不能预知密钥值 效率：效率：消息数目、带宽、计算复杂度、需预计算? 第三方的需要第三方的需要 证书：证书：初始密钥的分发方式 不可抵赖性：不可抵赖性：能提供密钥已被交换的收据2021-11-202021-11-201313密钥建立协议中的假定和敌手密钥建立协议中的假定和敌手 假定：假定：使用的使用的底层密码机制底层密码机制( (如加密方案和签名方案如加

9、密方案和签名方案) )都是都是安全安全的的敌手是一个不能直接攻击底层机制的密码分析敌手是一个不能直接攻击底层机制的密码分析家家敌手只能敌手只能攻击协议攻击协议本身，即攻击底层机制的组本身，即攻击底层机制的组合，以达到击破协议的目标合，以达到击破协议的目标协议中的消息是通过协议中的消息是通过未受保护未受保护( (开放式开放式) )的网的网络络来传输的，敌手可以能完全控制数据来传输的，敌手可以能完全控制数据敌手能伪造成一个合法参与方敌手能伪造成一个合法参与方2021-11-202021-11-201414 敌手敌手外部敌手外部敌手内部敌手：能通过一些特权方法内部敌手：能通过一些特权方法( (如实际

10、获取如实际获取私人计算机上的资源或其他一些阴谋等私人计算机上的资源或其他一些阴谋等) )获取获取额外信息额外信息( (如会话密钥或部分秘密信息如会话密钥或部分秘密信息) ) 一次内部敌手一次内部敌手: :能及时获取某些信息并在随后时间能及时获取某些信息并在随后时间应用应用 持久内部敌手持久内部敌手: :能不断获取特权信息能不断获取特权信息2021-11-202021-11-201515 敌手的活动：敌手的活动：利用窃听到的消息推导会话密钥利用窃听到的消息推导会话密钥 （被动（被动) )伪装成合法的参与者，从而共享密钥伪装成合法的参与者，从而共享密钥 ( (主动主动) )2021-11-2020

11、21-11-201616完善前向保密和已知密钥攻击完善前向保密和已知密钥攻击 长期长期( (对称或非对称的对称或非对称的) )密钥的泄密密钥的泄密完善前向保密：完善前向保密：长期密钥的泄密不能使得过去的会话密钥泄密 （通信安全的锁定在过去） 过去的会话密钥的泄密过去的会话密钥的泄密 ( (可能性大可能性大) )已知密钥攻击：已知密钥攻击：若过去的会话密钥泄密，则可能会泄露将来的会话密钥，或将来可能被敌手用于伪装成合法参与者二、基于对称加密的密钥传输二、基于对称加密的密钥传输(Key transport based on symmetric encryption)2021-11-202021-1

12、1-201818 无服务器无服务器的对称密钥传输和导出的对称密钥传输和导出 使用对称加密的点对点密钥更新使用对称加密的点对点密钥更新 使用密钥导出和不可逆函数的点对点密钥更新使用密钥导出和不可逆函数的点对点密钥更新 无预先共享密钥的密钥传输无预先共享密钥的密钥传输 Kerberos协议和相关的协议和相关的基于服务器基于服务器的协议的协议 Needham-Schroeder共享密钥协议共享密钥协议 Kerberos认证协议认证协议2021-11-202021-11-2019192.1 使用对称加密的点对点密钥更新使用对称加密的点对点密钥更新 参与双方参与双方A和和B须预先共享须预先共享长期对称密

13、钥长期对称密钥K 可通过安全信道分发 也可从一个密钥预分发方案(如带固定指数的Diffie-Hellman协议)中得到 会话密钥会话密钥W：通过重复使用长期对称密钥：通过重复使用长期对称密钥K建立建立2021-11-202021-11-202020 单步密钥传输单步密钥传输 具有挑战具有挑战-响应的密钥传输响应的密钥传输W=rAW=f(rA, rB)W=rA2021-11-202021-11-202121分析分析 不能提供完善前向保密不能提供完善前向保密 （不实用）（不实用） 长期密钥长期密钥K不能泄露不能泄露 需要使用时变参数，否则会遭受重放攻击需要使用时变参数，否则会遭受重放攻击 有时需要

14、在加密函数中内置一个数据完整有时需要在加密函数中内置一个数据完整性机制性机制 （安全考虑）（安全考虑）2021-11-202021-11-2022222.2 使用密钥导出和不可逆函数的点使用密钥导出和不可逆函数的点对点密钥更新对点密钥更新 A和和B共享共享长期对称密钥长期对称密钥K和和K(KK) W：会话密钥 hK：用于实体认证的MAC hK：用于密钥导出的伪随机置换或带密钥的单向函数 可提供可提供相互的实体认证相互的实体认证和和W的隐式密钥认证的隐式密钥认证2021-11-202021-11-2023232.3 无预先共享密钥的密钥传输无预先共享密钥的密钥传输 不要求共享密钥，也不要求公钥不

15、要求共享密钥，也不要求公钥 每个参与方只有它自己的本地对称密钥每个参与方只有它自己的本地对称密钥 a,b分别是分别是A和和B分别分别随机选择随机选择的秘密数的秘密数 不提供认证不提供认证 K：共享密钥：共享密钥2021-11-202021-11-202424 Shamir 协议中对称密钥均由自己秘密保管。协议具体协议中对称密钥均由自己秘密保管。协议具体如下：如下： AB随机产生随机产生一个会话一个会话密钥密钥 k)(kEA)(kEEAB)()(kEkEEDBABA)(kEBkkEDBB)(Shamir协议要求加密算法是可交换的，即协议要求加密算法是可交换的，即)()(kEEkEEijji一次一

16、密密码系统是可交换的，一次一密密码系统是可交换的，RSA 密码体制也是可交换的。密码体制也是可交换的。无身份认证，无身份认证，易遭受中间人易遭受中间人攻击！攻击！2021-11-202021-11-202525 协议中协议中Alice和和Bob各与密钥分配中心各与密钥分配中心KDC共共享一个秘密密钥享一个秘密密钥KDCAliceBob。BAkk ,1、请求、请求2、产生一个、产生一个随机会话密钥随机会话密钥ABk)(),(2ABkABkkEkEBA、ABABkkAkkEDA)(3、)(4ABkkEB、ABABkkBkkEDB)(5、(1)该协议要求该协议要求KDC绝对可信；绝对可信；(2)KD

17、C可能会成为可能会成为瓶颈瓶颈。基于服务器的协议基于服务器的协议 协议中协议中Alice和和Bob各与密钥分配中心各与密钥分配中心KDC共共享一个秘密密钥享一个秘密密钥。BAkk ,2021-11-202021-11-2026262.4 Needham-Schroeder共享密钥协议共享密钥协议2. 4. )|(|1AsKBsKIDKERIDKEBAKDCAB1. IDA| IDB |R13. |AsKIDKEB5. )(2RfESK如果敌手获得了旧会话如果敌手获得了旧会话密钥，则可以冒充密钥，则可以冒充A重放重放3，并且可回答，并且可回答5，成功，成功的欺骗的欺骗BKs为随机会话密钥为随机会

18、话密钥2RESK2021-11-202021-11-202727Needham-Schroeder改进协议改进协议（1）2. 4. )|(|TIDKETIDKEAsKBsKBAKDCAB1. IDA| IDB3. |TIDKEAsKB1NESK5. )(1NfESK以时戳替代随机数，用以向A，B保证Ks的新鲜性|ClockT|t1+t2 Clock:本地时钟t1：本地时钟与KDC时钟误差估计值t2 ：网络延迟时间要求各方时钟同步要求各方时钟同步如果发方时钟超前如果发方时钟超前B方时钟，可能方时钟，可能导致等待重放攻击导致等待重放攻击2021-11-202021-11-202828Needham

19、-Schroeder改进协议改进协议（2）KDCAB3. 1. AANID |4. |BKBSAKNETKIDESB2. |BAAKBBTNIDENIDBBBSAKBSABKNTKIDETKNIDEBA|会话密钥的截止时间2021-11-202021-11-202929Needham-Schroeder改进协议改进协议（2）AB1.,|ABSAKNTKIDEB2.,AKBNENS3.BKNES有效期内可不通过KDC直接认证2021-11-202021-11-203030 这个协议这个协议中中Alice和和Bob两人各与两人各与KDC共享一个秘密密共享一个秘密密钥钥。(A, RA)EB(A, R

20、A, RB)EA(B, k, RA, RB), EB(A, k)解密得解密得k和和RA并并确认确认RA的有效性的有效性EB(A, k), Ek(RB)解密得解密得k,再解密得再解密得RB，确认确认RA的有效性的有效性A、B分别为分别为Alice和和Bob的名字；的名字；RA, RB为随机数为随机数通过该协议，通过该协议，Alice、Bob互相确信是正在同对方谈话，而不是跟第三方互相确信是正在同对方谈话，而不是跟第三方Yahalom协议协议AliceKDCBob2021-11-202021-11-203131Kerberos认证协议认证协议 主要目标：实体认证主要目标：实体认证 次要结果：共享密

21、钥的建立次要结果：共享密钥的建立KDCAliceBobA, BEA(T,L,K,B), EB(T,L,K,A)EK(A,T), EB(T,L,K,A)EK(T+1)A、B分别为分别为Alice和和Bob的名字；的名字；RA, RB为随机数为随机数这个协议中这个协议中Alice和和Bob两人各与两人各与KDC共享一个秘密密钥共享一个秘密密钥。 Alice想产生一会话密钥用于与想产生一会话密钥用于与Bob通信。协议如下：通信。协议如下：2021-11-202021-11-203232登录登录2021-11-202021-11-203333 Step1：与AS交互，获得TG ticket和一个与TG

22、S通信的会话密钥 Step2：与TGS交互，获得与所期盼的服务器通信的会话密钥和ticket Step3 ：访问所期盼的服务器2021-11-202021-11-203434Kerberos Kerberos 总结总结每业务请求需要一个 ticket.Tickets 来源于TGS (除了访问TGS的ticket).工作站不能解密用服务器密钥加密的tickets.每个 ticket有个相应的session key.Tickets 不能重用. .2021-11-202021-11-203535Kerberos Kerberos 总结（续）总结（续）Tickets有有限的生命期.信任状只能使用一次.

23、信任状失效得更快 !服务器维护一个信任状列表2021-11-202021-11-203636KerberosKerberos区域和多区域的区域和多区域的KerberosKerberosASTGSASTGS服务器Client区域AKerberosKerberos12435672021-11-202021-11-203737Kerberos协议的缺点协议的缺点 网络中的所有用户都是网络中的所有用户都是同步时钟同步时钟，因为目，因为目前目前的时间被用来确定是否一个给定的前目前的时间被用来确定是否一个给定的会话密钥会话密钥K是合法的。是合法的。 Kerberos的的口令口令没有进行额外的特殊处理，没有

24、进行额外的特殊处理，使用穷举攻击法的时间复杂性仅和口令长使用穷举攻击法的时间复杂性仅和口令长度成比例。度成比例。 Kerberos认证中心要求保存认证中心要求保存大量的共享私大量的共享私钥钥，无论管理还是更新都有很大的困难，无论管理还是更新都有很大的困难，需要特别细致的安全保护措施，将付出极需要特别细致的安全保护措施，将付出极大的系统代价。大的系统代价。2021-11-202021-11-203838小结小结三、基于对称技术的密钥协商三、基于对称技术的密钥协商 (Key agreement based on symmetric techniques)2021-11-202021-11-2040

25、40Blom方案方案 公开公开一个素数p，每个用户U对应的元素rUZp也是公开的公开的且互不相同 可信中心选择三个随机数a,b,c Zp，并且f(x,y)=(a+b(x+y)+cxy) mod p 对每个用户U,可信中心计算多项式gU(x)=f(x,rU) mod p，并将gU(x)通过一个安全信道上传给U 用户U和V想通信，他们之间的共享密钥KU,V=KV ,U=f(rU,rV)=(a+b(rU+rV)+crUrV) mod p=gU(rV)=gV(rU)仅仅TS知道知道该方案是一种密钥预分发方案！该方案是一种密钥预分发方案！四、基于公钥加密的密钥传输四、基于公钥加密的密钥传输 (Key t

26、ransport based on public-key encryption)2021-11-202021-11-204242 仅使用公钥加密技术的密钥传输仅使用公钥加密技术的密钥传输 组合组合PKPK加密技术和签名技术的协议加密技术和签名技术的协议 混合密钥传输协议混合密钥传输协议使用了使用了PKPK加密技术、签名技术和对称加密技加密技术、签名技术和对称加密技术术2021-11-202021-11-2043434.1 4.1 仅使用公钥加密技术仅使用公钥加密技术 通过公钥加密的单步密钥传输通过公钥加密的单步密钥传输基本的基本的PKPK加密加密 Needham-Schroeder公钥协议公钥

27、协议2021-11-202021-11-204444基本的基本的PK加密加密AliceBob),(. 1AkEBp会话密钥会话密钥W=kPA,PB分别为分别为Alice 和和Bob的公钥的公钥点评：可实现密钥传输点评：可实现密钥传输2021-11-202021-11-204545Needham-Schroeder公钥协议公钥协议AliceBob),(. 11AkEBp),(. 221kkEAp)(. 32kEBp会话密钥会话密钥W=f(k1,k2)PA,PB分别为分别为Alice 和和Bob的公钥的公钥可实现相互的实体认证、密钥认证和密钥传输可实现相互的实体认证、密钥认证和密钥传输2021-1

28、1-202021-11-204646Needham-Schroeder公钥协议的修改公钥协议的修改AliceBob),(. 111rAkEBp),(. 2212rrkEAp2. 3 r会话密钥会话密钥W=f(k1,k2)PA,PB分别为分别为Alice 和和Bob的公钥的公钥协议消息中利用随机数来抵抗重放攻击协议消息中利用随机数来抵抗重放攻击2021-11-202021-11-2047474.2 4.2 组合组合PKPK加密技术和签名技术的加密技术和签名技术的协议协议 加密已签名密钥加密已签名密钥 加密和签名分离加密和签名分离 签名已加密的密钥签名已加密的密钥X.509X.509强认证协议强认

29、证协议2021-11-202021-11-204848X.509强双向协议（两步）强双向协议（两步）AliceBob)(,(),(,( ,. 111kEBrtEkEBrtcertBABpAASpAAA)(,(),(,( ,. 222kErArtEkErArtcertABApABBSpABBBPA,SA分别为分别为Alice 的公钥和私钥；的公钥和私钥；PB,SB分别为分别为Bob的公钥和私钥；的公钥和私钥；certA和和certB分别为分别为Alice和和Bob的公钥证书的公钥证书可实现相互的实体认证、密钥认证和密钥传输可实现相互的实体认证、密钥认证和密钥传输共享密钥共享密钥为为k1和和k2使

30、用时戳和随使用时戳和随机数的挑战机数的挑战-响应技术响应技术2021-11-202021-11-204949X.509强双向协议（三步）强双向协议（三步）AliceBob),(),(. 3BrEBrBSBA)(,(),(,( ,. 222kErArEkErArcertABApABSpABB)(,(),(,( ,. 111kEBrEkEBrcertBABpASpAAPA,SA分别为分别为Alice 的公钥和私钥；的公钥和私钥；PB,SB分别为分别为Bob的公钥和私钥；的公钥和私钥；certA和和certB分别为分别为Alice和和Bob的公钥证书的公钥证书可实现相互的实体认证、密钥认证和密钥传输

31、可实现相互的实体认证、密钥认证和密钥传输共享密钥共享密钥为为k1和和k2基于随机数的基于随机数的挑战挑战-响应技术响应技术五、基于非对称技术五、基于非对称技术的密钥协商的密钥协商 (Key agreement based on asymmetric techniques)2021-11-202021-11-205151Diffie-Hellman密钥协商密钥协商 算法的安全性基于求离散对数的困难性算法的安全性基于求离散对数的困难性系统参数：系统参数：p是一个大素数，是一个大素数，g是是Z*p的一个生成元的一个生成元AliceBobpgXAxmod. 1pgYBxmod. 2pgpYkBAAxx

32、xmodmodpgpXkBABxxxmodmodxA和和xB分别为分别为Alice和和Bob的随的随机秘密机秘密2021-11-202021-11-205252Diffie-Hellman密钥预分配方案密钥预分配方案 Alice的私钥和公钥分别为的私钥和公钥分别为xA和和gxA Bob的私钥和公钥分别为的私钥和公钥分别为xB和和gxB Alice和和Bob之间的会话密钥为之间的会话密钥为gxAxB =(gxA)xB =(gxB)xA2021-11-202021-11-205353 对对Diffie-Hellman密钥协商协议的密钥协商协议的中间人攻击中间人攻击AliceBobk1:Alice和

33、敌手间通信的共享密钥和敌手间通信的共享密钥k2:Bob和敌手间通信的共享密钥和敌手间通信的共享密钥AdversarypgpZkBAdvBxxxmodmod2pgpZkAAdvAxxxmodmod1pgXAxmod. 1pgZAdvxmod. 2pgYBxmod. 3pgZAdvxmod. 42021-11-202021-11-205454端对端协议端对端协议(STS)AliceBobpgpYkBAAxxxmodmodpgpXkBABxxxmodmod),(. 3BAxxAkggSE),(,mod. 2ABBxxBkxggSEpgpgAxmod. 1PKA,SKA分别为分别为Alice 的公钥和

34、私钥；的公钥和私钥；PKB,SKB分别为分别为Bob的公钥和私钥；的公钥和私钥；SA(m)=ESKA(H(m)xA,xB分别为分别为Alice和和Bob的随机秘密的随机秘密计算计算Alice和和Bob的共享密钥的共享密钥k可实现：可实现：相互实体认证相互实体认证显式密钥认证显式密钥认证密钥协商密钥协商六、秘密共享六、秘密共享2021-11-202021-11-205656秘密共享的提出秘密共享的提出 在导弹控制发射、重要场所通行检验等情在导弹控制发射、重要场所通行检验等情况下，通常必须由两人或多人同时参加才况下，通常必须由两人或多人同时参加才能生效，这时都需要能生效，这时都需要将秘密分给多人将

35、秘密分给多人掌管，掌管，并且必须有一定人数的掌管秘密的人同时并且必须有一定人数的掌管秘密的人同时到场才能恢复这一秘密。由此，引入到场才能恢复这一秘密。由此，引入门限门限方案方案的一般概念。的一般概念。 利用利用n个用户中的至少个用户中的至少t个用户之间的相互个用户之间的相互协作，以控制某些重要任务的完成协作，以控制某些重要任务的完成(t,n)门限方案门限方案2021-11-202021-11-205757秘密共享的定义秘密共享的定义 定义定义:设秘密设秘密s被分成被分成n个部分信息，每一部个部分信息，每一部分信息称为一个子密钥或影子，由一个参分信息称为一个子密钥或影子，由一个参与者持有，使得：

36、与者持有，使得： 1.由由t个或多于个或多于t个参与者所持有的部分信息个参与者所持有的部分信息可重构可重构s。 2.由少于由少于t个参与者所持有的部分信息则无个参与者所持有的部分信息则无法重构法重构s。 则称这种方案为则称这种方案为(t,n)门限方案门限方案，t称为方案称为方案的的门限值门限值2021-11-202021-11-205858Shamir的的(t,n)门限方案门限方案 基于多项式基于多项式Lagrange插值公式插值公式 t-1次多项式次多项式 ：能通过：能通过t个不同的点个不同的点(xi,yi)唯一确定唯一确定 秘密秘密s=f(0)10)(tiiixaxfy2021-11-20

37、2021-11-205959举例举例 f(1)=1,f(2)=5,f(3)=4,f(4)=17,f(5)=6 已知已知f(2),f(3),f(5),如何求秘密如何求秘密s？ 分析：分析：是一个是一个(3,5)门限方案门限方案,f(x)的最高次数为的最高次数为21127)35)(25()3)(2(6)53)(23()5)(2(4)52)(32()5)(3(5)(2xxxxxxxxxf共享密钥为共享密钥为s=f(0)=112021-11-202021-11-206060Shamir的的(t,n)门限方案门限方案假设共享密钥为假设共享密钥为s 选择一个素数选择一个素数q 定义定义a0=s，随机选择，

38、随机选择t-1个独立系数个独立系数a1, , at-1, 并并构造构造t-1次多项式次多项式f(x)=a0+a1x+ak-1xt-1 计算计算Si=f(i) mod q，并将，并将(i,Si)传送给用户传送给用户Pi)()()()()()(111011t11110ntnkkkifiaiaaifiaiaa2021-11-202021-11-206161 任意任意t个或更多用户可以联合生成共享密钥个或更多用户可以联合生成共享密钥s=f(0)(mod)()()(11qiiixifxfkjkjllljlj)(mod)() 1()0(111qiiiiffskjkjllljljk共享秘密为：共享秘密为：重构的多项式为：重构的多项式为：七、会议密钥生成七、会议密钥生成2021-11-202021-11-206363会议密钥生成会议密钥生成 是双方密钥建议的一个推广，能为三方或是双方密钥建议的一个推广，能为三方或更多方提供一个共享密钥更多方提供一个共享密钥 要求：要求：不用的用户组重构不同的会话密钥不用的用户组重构不同的会话密钥会话密钥是动态的会话密钥是动态的参与方交换的信息是公开传输的参与方交换的信息是公开传输的每个参与方分别计算会