现代密码学理论与实践第13章数字签名和认证协议.ppt-得力文库

资源描述

《现代密码学理论与实践第13章数字签名和认证协议.ppt》由会员分享，可在线阅读，更多相关《现代密码学理论与实践第13章数字签名和认证协议.ppt（47页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、2021/8/5,现代密码学理论与实践-13,1/47,现代密码学理论与实践第13章数字签名和认证协议,Fourth Edition by William Stallings Slides by 杨寿保 2012年11月,2021/8/5,现代密码学理论与实践-13,2/47,本章要点,数字签名是一种认证机制，它使得消息的产生者可以添加一个起签名作用的码字。通过计算消息的散列值并用产生者的私钥加密散列值来生成签名。签名保证了消息的来源和完整性。相互认证协议使得通信的各方对相互的身份感到放心, 并交换会话密钥。单向认证时, 接收方想确信消息确实来自声称的发送方。数字签名标准(DSS)是N

2、IST标准，它使用安全散列算法(SHA)。,2021/8/5,现代密码学理论与实践-13,3/47,13.1 数字签名Digital Signature,数字签名的简单定义数字签名是使以数字形式存储的明文信息经过特定密码变换生成密文，作为相应明文的签名，使明文信息的接收者能够验证信息确实来自合法用户，以及确认信息发送者身份。对数字签名的基本要求在收发双方不能完全信任的情况下，需要除认证之外的其他方法来解决假冒和否认的问题，数字签名则是解决办法；签名接收者能容易地验证签字者对消息所做的数字签名，包括日期和时间；任何人，包括签名接收者，都不能伪造签名者的签字；发生争议时，可由第三方解决

3、。,2021/8/5,现代密码学理论与实践-13,4/47,数字签名与消息认证的区别消息认证是使消息接收方验证消息发送者发送的内容有无被修改过，对防止第三者破坏足够，但收发双方有利害冲突时就无法解决纷争，需要更严格的手段，即数字签名。数字签名的基本形式对消息签名的两种方法对消息整体的签字，将被签消息整体经过密码变换得到签字；对消息摘要的签字，附在被签消息之后，或嵌在某一特定位置上作一段签字图样。两类数字签名确定性数字签名，明文与签名一一对应；概率性数字签名，一个明文可以有多个合法签名，每次都不一样。,数字签名的基本形式,2021/8/5,现代密码学理论与实践-13,5/47,1

4、3.1.2 直接数字签名,直接数字签名仅涉及通信方(信源、信宿) 假定信宿知道信源的公开密钥数字签名通过信源对整个报文用私有密钥加密，或对报文的摘要加密来实现通常先签名，然后对消息和签名一起加密安全性依赖于信源私有密钥的安全性,2021/8/5,现代密码学理论与实践-13,6/47,13.1.3 仲裁数字签名,涉及到一个仲裁方(arbiter A) 签名方的签名报文首先送给仲裁者仲裁者对报文和签名进行测试以检验出处和内容，然后注上日期和仲裁说明后发给接收方要求仲裁方在一定程度上是可以信任的可以用对称密码或公开密钥密码实现仲裁方可以知道消息，也可以不知道消息,2021/8/5,现代

5、密码学理论与实践-13,7/47,需要仲裁的数字签名技术,2021/8/5,现代密码学理论与实践-13,8/47,13.2 认证协议,认证服务和功能认证是证实信息交换过程有效性和合法性的一种手段，包括对通信对象的认证(身份认证)和报文内容的认证(报文认证)，起到数据完整性的保护。这里有信息的真实性存储数据的真实性接收方提供回执发送方不可否认时效性和公证可能性认证的目的防窃听、防假冒或拦截、防窃取等,2021/8/5,现代密码学理论与实践-13,9/47,单向认证使用对称加密方法，即一次一密方法的变形使用公开密钥方法：A向B声称是A，B则向A送一随机数R，A用其私有密钥加密送

6、B，B用A的公开密钥验证。使用改进的口令方式双向认证对称密钥方式(三次握手) 公开密钥方式，A、B双向使用不同的R值时标方式可信中继使用KDC密钥分发中心通过DASS (Distributed Authentication Security Service) 群认证(Group Authentication),基本认证方法,2021/8/5,现代密码学理论与实践-13,10/47,13.2.1 双向认证,双向认证协议可以使通信双方达成一致并交换会话密钥重放攻击：合法的签名消息被拷贝后重新送出简单重放可检测的重放不可检测的重放不加修改的逆向重放重放攻击的解决方法使用序

7、列号使用时间戳(需要同步时钟) 挑战/应答(使用单独的nonce),2021/8/5,现代密码学理论与实践-13,11/47,对称加密方法,使用两层传统加密密钥结构来保证分布环境中通信的保密性通常需要可信密钥分发中心Key Distribution Center (KDC) 每一方与KDC共享主密钥 KDC产生双方通信要用的会话密钥用主密钥来分发会话密钥,2021/8/5,现代密码学理论与实践-13,12/47,Needham-Schroeder Protocol,最初期的第三方密钥分发协议之一 KDC负责为用户A和B之间的通信产生会话密钥协议如下: 1. AKDC: IDA | ID

8、B | N1 2. KDCA: EKaKs | IDB | N1 | EKbKs|IDA 3. AB: EKbKs|IDA 4. BA: EKsN2 5. AB: EKsf(N2),2021/8/5,现代密码学理论与实践-13,13/47,Needham-Schroeder Protocol,2021/8/5,现代密码学理论与实践-13,14/47,Needham-Schroeder Protocol,用于安全地分发A和B通信的新会话密钥对于重放攻击是脆弱的，如果老会话密钥被破了的话因此需要第三个消息来使得B相信是和A通信有几种改进方法增加时间戳(Denning 81) 使用一个额外的

10、学理论与实践-13,16/47,Neuman方法,Neuman 93 1. AB: IDA |NA 2. BKDC: IDB | NB | EKbIDA | NA |Tb 3. KDCA: EKaIDB|NA|Ks|Tb|EKbIDA|Ks|Tb|NB 4. AB: EKbIDA | Ks |Tb |EKsNB 在有效时限内，A与B建立新的会话： 1. AB: EKbIDA | Ks |Tb, Na 2. BA: Nb , EKsNa 3. AB: EKsNb,2021/8/5,现代密码学理论与实践-13,17/47,使用公开密钥密码实现双向认证,有很多使用公开密钥密码的双向认证方法需要确保

11、其他各方都拥有正确的公开密钥使用一个集中式的认证服务器(AS) 现有很多不同的使用时间戳或nonce的方法,2021/8/5,现代密码学理论与实践-13,18/47,Denning AS Protocol,Denning 81 presented the following: 1. AAS: IDA | IDB 2. ASA: EKRasIDA|KUa|T | EKRasIDB|KUb|T 3. AB: EKRasIDA|KUa|T | EKRasIDB|KUb|T | EKUbEKRaKs|T 会话密钥由A选择的, 因此AS不一定是可信的时间戳可以防范重放攻击, 但是需要同步时钟,202

12、1/8/5,现代密码学理论与实践-13,19/47,13.2.2 单向认证,当通信双方不同时在线时需要用到单向认证，比如发送电子邮件消息头部必须是可读的以便在系统中传输也可能希望消息的主体保密，发送者认证,2021/8/5,现代密码学理论与实践-13,20/47,使用对称密码实现单向认证,可以把KDC使用方法应用于此，不需要最终交换nonce 1. AKDC: IDA | IDB | N1 2. KDCA: EKaKs | IDB | N1 | EKbKs|IDA 3. AB: EKbKs|IDA | EKsM 不能抗重放攻击可以在消息中加入时间戳，由于电子邮件处理可能存在大量时延，加入

13、时间戳的作用是有限的,2021/8/5,现代密码学理论与实践-13,21/47,公钥加密方法实现单向认证,已有一些适用的公钥方法如果保密是主要关心的问题，可以使用 AB: EKUbKs | EKsM 消息和会话密钥都加密了如果需要认证，则可基于数字证书使用数字签名的方法 AB: M | EKRaH(M) | EKRasT|IDA|KUa 这里有消息, 签名, 证书,2021/8/5,现代密码学理论与实践-13,22/47,13.3 数字签名标准(DSS),DSS是美国政府作为标准FIPS 186发布的 DSS使用SHA作为散列算法由NIST和NSA在90年代早期设计 DSS是标准, DS

14、A是其算法 DSS是ElGamal和Schnorr算法的变形 DSS产生320位数字签名, 但是具有512-1024位的安全性 DSS的安全依赖于DLP问题,2021/8/5,现代密码学理论与实践-13,23/47,2021/8/5,现代密码学理论与实践-13,24/47,DSA密钥产生,全局共享的公开密钥值为(p, q, g) p是大素数 p = 2L L为512到1024位并且是64的倍数选择q, 是p-1的160位的素因子选择g, 使得 g = h(p-1)/q where h 1 用户选择私钥，并计算其公开密钥选择 xq 计算 y = gx (mod p),2021/8/5,现代

15、密码学理论与实践-13,25/47,DSA签名的产生,若要签名消息M, 签名方则产生一个随机的签名密钥k, kq k 必须是随机的，并且不能重复使用计算签名 r = (gk(mod p) (mod q) s = k-1(SHA(M)+ x*r) (mod q) 把签名(r, s)和消息M一起发送给接收方,2021/8/5,现代密码学理论与实践-13,26/47,DSA签名的验证,接收方收到消息M和签名(r, s) 接收方计算 w = s-1(mod q) u1= (SHA(M) *w) (mod q) u2= (r*w) (mod q) v = (gu1 *yu2(mod p) (mod

16、q) 如果v=r, 则签名通过验证更多的证明细节可以参考有关资料,2021/8/5,现代密码学理论与实践-13,27/47,DSS Signing and Verifying,2021/8/5,现代密码学理论与实践-13,28/47,2021/8/5,现代密码学理论与实践-13,29/47,RSA方法的数字签名给定n = pq，p和q是大素数，ed mod(n) = 1，公开密钥为(n, e)，秘密密钥为(p, q, d) 加密：m 0, n-1，gcd(m, n) = 1, 则c = me mod n 解密：m = cd mod n = (me mod n )d mod n = med

17、 mod n = m 签名：s = md mod n 验证：m = se mod n = (md mod n )e mod n = med mod n = m,基于非对称密码体制的数字签名,2021/8/5,现代密码学理论与实践-13,30/47,例：n = 55 = 11x5, (n) = 40, 选d = 11, 则e = 11 m = 3, 签名s = 311 mod 55 =47 验证：m = s11 mod 55 = 4711 mod 55 = 3 例：n = 65, (n) = 48, 选d = 5, 则e = 29, m = 3 s = 35 mod 65 = 48, 验证：m

18、= 4829 mod 65 = 3 用数字签名和加密同时实现报文的秘密和认证的传送设有用户A和B，A: nA, eA, dA, EA, DA, B: nB, eB, dB, EB, DB, 报文从AB： Secrecy: c = EB(m) = meB mod nB m = DB(c) = cdB mod nB = meBdB mod nB Authenticity: c = DA(m) = mdA mod nA m = EA(c) = ceA mod nA = meAdA mod nA = m,用数字签名和加密同时实现报文的秘密和认证的传送,2021/8/5,现代密码学理论与实践-13,3

19、1/47,Both secrecy and authenticity: c = EB(DA(m) = (mdA mod nA)eB mod nB or: c = DA(EB(m) = (meB mod nB)dA mod nA m = EA(DB(c) = EA(DB(EB(DA(m) = (mdA mod nA)eB mod nB)dB mod nB )eA mod nA = m or: m = DB(EA(c) = DB(EA(DA(EB(m) = (meB mod nB)dA mod nA)eA mod nA )dB mod nB = m 注意：1. nAnB，则A：c = EB(DA(

20、m)， B：m = EA(DB(c) = EA(DB(EB(DA(m) 2. nB nA，则A：c = DA(EB(m)， B：m = DB(EA(c) = DB(EA(DA(EB(m) 例：(nA, eA)=(15, 3)，(nB, eB)=(35, 5)，A发送m = 11给B，要求既保密又认证地传送。,用数字签名和加密同时实现报文的秘密和认证的传送,2021/8/5,现代密码学理论与实践-13,32/47,假定A和B互相通信, 共享大素数p, 本原元素 0= m = p-1, gcd(, p) = 1, A和B各有自己的秘密xA和xB 加密 A选择k0, p-1, k的作用即为xA, A

21、访问公共区域找到B的公开密钥YB = xB mod p, 计算： K = (YB)k mod p，即K = xBk mod p c1 = k mod p c2 = mK mod p 密文即为 (c1, c2) 解密 B首先恢复K：K = c1xB mod p = kxB mod p 然后恢复m：m = c2/K mod p = c2K-1 mod p,重温：ElGamal的数据加密方法,2021/8/5,现代密码学理论与实践-13,33/47,若A为B签署m，0m p-1， A随机选择k0, p-1，gcd(k, p-1) = 1 计算r = k mod p 计算m = YArrs mod p

22、, YA= xA mod p 即m = xA rk s mod p 则 m = (xAr + ks) mod p-1 根据此式求s，则对于m的数字签名即为(r, s)，0= r, sp-1.,ElGamal的数字签名方法,2021/8/5,现代密码学理论与实践-13,34/47,验证：给定m, r, 和s，容易计算 m mod p = YArrs mod p, 看其是否一致, k不能重复使用。例：p =17, =3, xA=2, xB=5, m =11, k =5, 求签名及验证。签名：r = k mod p = 35 mod 17 = 5 11 = (2x5 + 5s) mod 16 =

23、 (10 + 5s) mod 16 5s mod 16 = 1, s = 13 所以，签名为(5, 13)。验证: m mod p = 311 mod 17 = 102x10 x9 mod 17 = 7 YArrs mod p = (32)5 x 513 mod 17 = 7,ElGamal数字签名的验证,2021/8/5,现代密码学理论与实践-13,35/47,密钥管理的内容,原则密钥难以窃取在一定条件下即使窃得密钥也无用，有使用时间和范围限制密钥分配和更新对用户透明密钥组织结构密钥的层次化管理结构：最高层密钥为主密钥，构成密钥管理系统之核心。下层的密钥按照某种密钥协议来生成，掌

24、握了主密钥，就有可能找出下层的各个密钥。,2021/8/5,现代密码学理论与实践-13,36/47,工作密钥(会话密钥 session key) 重复使用同一密钥容易导致泄漏，应该经常更换；使用相同密钥，攻击者可以实施重播攻击；密钥丢失，仅影响本次会话；更换密钥，防止对方以后窃取信息。密钥的连通：密钥共享的范围密钥的分割：适用范围和时间限制按空间分割按时间分割分割实现：静态/动态,密钥的层次化管理结构,2021/8/5,现代密码学理论与实践-13,37/47,ANSI的X9.17定义了一种线性密钥空间的密钥生成方法。令k为主密钥，v0为64位的随机种子，T为时间戳，生成的密钥

25、记为Ri，Ek为任意的加密算法，则 Ri = Ek(Ek(Ti)vi)；vi+1 = Ek(TiRi) 生成的Ri为64位, 去掉校验位, 则为标准的DES密钥。非线性密钥空间中的密钥生成算法将密钥分成两部分：k和Ek(Str)，Ek(Str)构成秘密预定义串；使用时先用k解密这个串，若正确，则正常使用k，否则强行启动另一个弱化了的加密算法。,密钥的生成,2021/8/5,现代密码学理论与实践-13,38/47,密钥的分配和传递自动进行分配，集中传送和分散传送密钥的验证在传递密钥时附带一个用该密钥加密的密文；接收者通过解密来验证密钥的正确性，同时可以结合接收者身份认证。密钥的保存

26、可以分散保存，可以秘密分享secret sharing,密钥的管理机制,2021/8/5,现代密码学理论与实践-13,39/47,Threshold Scheme: Secret Sharing,(t, w) Threshold Scheme 依据下列原则将一个秘密K分解成w个shadows (pieces) k1, k2, , kw 只要有t个ki，计算K是容易的；从任何少于t个ki，计算K是不可能的；丢失或损坏了一个shadow，只要还剩t个shadows，都可以恢复K。这就是Shamir于1979年提出的(t, w) threshold scheme。,2021/8/5,现代密码学理

27、论与实践-13,40/47,拉格朗日插值多项式法Lagrange Interpolating Polynomial Scheme(1979, Shamir) 每个shadow由下列t-1次方的随机多项式导出: h(x) = (at-1xt-1 + + a1x1+ a0) mod p a0即为秘密K, a0=K, 是常数项, K p, w p, GF(p) 给定h(x)，则K = h(0)，ki= h(xi)，i =1, , w 每一对(xi, ki)就是h(x)函数曲线上的一个点，x1, x2, , xw无需保密，只是普通数字。重组t-1次的多项式，只需要t个点就可以唯一地重组。这样，K可以

28、从t个shadow中获得，少于t个shadow则不能重组h(x)和获得K。,拉格朗日插值多项式法实现秘密分享,2021/8/5,现代密码学理论与实践-13,41/47,给定t个shadow，ki1, ki2, , kit，h(x)可由下面的Lagrange Interpolating Polynomial给出： h(x) = kis mod p 所有运算在GF(p)里进行，除是由乘模p的逆实现的。例：Let t = 3，w = 5，p = 17，K = 13， h(x) = (2x2 +10 x +13) mod 17 k1 = h(1) = (2+10+13) mod 17 = 25 mo

29、d 17 = 8 k2 = h(2) = (8+20+13) mod 17 = 41 mod 17 = 7 k3 = h(3) = (18+30+13) mod 17 = 61 mod 17 = 10 k4 = h(4) = (32+40+13) mod 17 = 85 mod 17 = 0 k5 = h(5) = (50+50+13) mod 17 = 113 mod 17 = 11,拉格朗日插值多项式法的实现,2021/8/5,现代密码学理论与实践-13,42/47,重组h(x)，t = 3，选k1, k3, k5： h(x) = 8 +10 +11 mod 17 = 8 +10 +11

30、mod 17 = 8*inv(8,17)(x-3)(x-5)+10*inv(-4,17)(x-1)(x-5)+11*inv(8,17) (x-1)(x-3) mod 17 = 8*15(x-3)(x-5)+10*4(x-1)(x-5)+11*15(x-1)(x-3) mod 17 = 1(x-3)(x-5)+6(x-1)(x-5)+12(x-1)(x-3) mod 17 = (19x2 92x + 81) mod 17 = (2x2 7x + 13) mod 17 = (2x2 +10 x + 13) mod 17 K = h(0) = 13,拉格朗日插值多项式法实现,2021/8/5,现代密

31、码学理论与实践-13,43/47,Diffie-Hellman方法设用户A和B, 共享和P, 是本原元素, P是大素数。 A、B各有一私有密钥, xA和xB, 公布他们的公开密钥： YA = xA mod P YB = xB mod P 双方共享的会话密钥为 A：KAB = (YB)xA mod P = xAxB mod P B：KBA = (YA)xB mod P = xBxA mod P,离散对数的方法实现密钥共享,2021/8/5,现代密码学理论与实践-13,44/47,Hughes对Diffie-Hellman方法的改进，目的是防假冒和桥接攻击双方密钥的生成是异步进行的，A可以事先

32、生成密钥，B在解密时才获得。 A: K = k mod P B: Y = xB mod P A A: X = Yk mod P = kxB mod P B B: K = XxB-1 mod P = kxBxB-1 mod P = k mod P = K 智能卡方式将RSA与Diffie-Hellman协议相结合，通过KDC分配可进行密钥管理的智能卡，平时使用密钥时不需要KDC。全系统有一个通信各方均使用的公开密钥，对应的秘密密钥保留在发卡方。需要通信时由智能卡产生一个会话密钥。,对假冒和桥接攻击的防范,2021/8/5,现代密码学理论与实践-13,45/47,Steves Bellovin和

33、Michael Merit提出Encrypted Key Exchange，用共享的对称密钥P来保护随机产生的公开密钥K： A 随机产生一对公开/隐蔽密钥，使用对称密钥算法时将公开密钥K加密，将标识符A和Ep(K)发给B B产生随机会话密钥K，向A发送Ep(EK(K) A解出K，产生随机数RA，向B发送EK(RA) B产生RB，向A发送EK(RA, RB) A收到后，向B发送EK(RB) A收到后确认RB正确，则交换与鉴别成功。前三步交换密钥，后三步双向身份认证。,加密的密钥交换技术EKE,2021/8/5,现代密码学理论与实践-13,46/47,13章习题 Due: Nov. 27, 20

34、12,第四版，第13章，第5、10、14 补充四道题如下： 1. 假定A和B要用RSA方法进行一次保密又认证的通信。A的公钥是(nA, eA)=(33, 7), B的公钥是(nB, eB)=(15, 3) (a) A和B的秘密密钥dA和dB各是什么? (b) A送消息m=2给B, 要求保密又认证, 密文C是什么? (c) B如何从C解得m？ 2. 在Elgamal系统中, =7, p=13, xa=5, xb=3. (a).假定A加密传送m=3给B, 随机选择k=8, 密文是什么? (b).如果A要签名m=7, 随机选择k=5, 签名是什么? B如何验证？,2021/8/5,现代密码学理论与实

35、践-13,47/47,13章习题(续),3. 假定拉各朗日插值多项式为h(x)=3x3+5x+2 mod 7, 用来实现 (t, w)的密钥共享，w=5. (a) t和K的值是多少? (b) 如果k1=h(2), k2=h(4), k3=h(3), k4=h(5), k5=h(7). 如何从k1, k2, k4, k5重组K？ 4. 现有p(x)=x3+x2+1=1101和二进制多项式h(x)=(001x2+101x+011) mod 1101, 运算在GF(23)中进行 (a) t是多少？k是什么？ (b) 对于x1=001, x2=011, x3=100, x4=110, 分别计算相应的shadows。 (c) 从x1, x2和x4的shadow重组此二进制多项式,

展开阅读全文

现代密码学理论与实践第13章 数字签名和认证协议.ppt

现代密码学理论与实践第13章数字签名和认证协议.ppt