现代密码学理论与实践 第13章 数字签名和认证协议 Fourth Edition by William Stallings Slides by 杨寿保 syang@ustc.edu.cn http://staff.ustc.edu.cn/~syang 2012年11月 2018/11/22 现代密码学理论与实践-13

本章要点 数字签名是一种认证机制，它使得消息的产生者可以添加一个起签名作用的码字。通过计算消息的散列值并用产生者的私钥加密散列值来生成签名。签名保证了消息的来源和完整性。 相互认证协议使得通信的各方对相互的身份感到放心, 并交换会话密钥。 单向认证时, 接收方想确信消息确实来自声称的发送方。 数字签名标准(DSS)是NIST标准，它使用安全散列算法(SHA)。 2018/11/22 现代密码学理论与实践-13

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

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

13.1.2 直接数字签名 直接数字签名仅涉及通信方(信源、信宿) 假定信宿知道信源的公开密钥 数字签名通过信源对整个报文用私有密钥加密，或对报文的摘要加密来实现 通常先签名，然后对消息和签名一起加密 安全性依赖于信源私有密钥的安全性 Direct Digital Signatures involve the direct application of public-key algs. But are dependent on security of the sender’s private-key. Have problems if lost/stolen and signatures forged. Need time-stamps and timely key revocation. 2018/11/22 现代密码学理论与实践-13

13.1.3 仲裁数字签名 涉及到一个仲裁方(arbiter A) 签名方的签名报文首先送给仲裁者 仲裁者对报文和签名进行测试以检验出处和内容，然后注上日期和仲裁说明后发给接收方 要求仲裁方在一定程度上是可以信任的 可以用对称密码或公开密钥密码实现 仲裁方可以知道消息，也可以不知道消息 See Stallings Table 13.1 for various alternatives 2018/11/22 现代密码学理论与实践-13

需要仲裁的数字签名技术 2018/11/22 现代密码学理论与实践-13

13.2 认证协议 认证服务和功能 认证是证实信息交换过程有效性和合法性的一种手段，包括对通信对象的认证(身份认证)和报文内容的认证(报文认证)，起到数据完整性的保护。这里有 信息的真实性 存储数据的真实性 接收方提供回执 发送方不可否认 时效性和公证可能性 认证的目的 防窃听、防假冒或拦截、防窃取等 2018/11/22 现代密码学理论与实践-13

基本认证方法 单向认证 双向认证 可信中继 群认证(Group Authentication) 使用对称加密方法，即一次一密方法的变形 使用公开密钥方法：A向B声称是A，B则向A送一随机数R，A用其私有密钥加密送B，B用A的公开密钥验证。 使用改进的口令方式 双向认证 对称密钥方式(三次握手) 公开密钥方式，A、B双向使用不同的R值 时标方式 可信中继 使用KDC密钥分发中心 通过DASS (Distributed Authentication Security Service) 群认证(Group Authentication) 2018/11/22 现代密码学理论与实践-13

13.2.1 双向认证 双向认证协议可以使通信双方达成一致并交换会话密钥 重放攻击：合法的签名消息被拷贝后重新送出 重放攻击的解决方法 简单重放 可检测的重放 不可检测的重放 不加修改的逆向重放 重放攻击的解决方法 使用序列号 使用时间戳(需要同步时钟) 挑战/应答(使用单独的nonce) 2018/11/22 现代密码学理论与实践-13

对称加密方法 使用两层传统加密密钥结构来保证分布环境中通信的保密性 通常需要可信密钥分发中心Key Distribution Center (KDC) 每一方与KDC共享主密钥 KDC产生双方通信要用的会话密钥 用主密钥来分发会话密钥 2018/11/22 现代密码学理论与实践-13

Needham-Schroeder Protocol 最初期的第三方密钥分发协议之一 KDC负责为用户A和B之间的通信产生会话密钥 协议如下: 1. A→KDC: IDA || IDB || N1 2. KDC→A: EKa[Ks || IDB || N1 || EKb[Ks||IDA] ] 3. A→B: EKb[Ks||IDA] 4. B→A: EKs[N2] 5. A→B: EKs[f(N2)] This is the original, basic key exchange protocol. Used by 2 parties who both trusted a common key server, it gives one party the info needed to establish a session key with the other. Note that since the key server chooses the session key, it is capable of reading/forging any messages between A&B, which is why they need to trust it absolutely! Note that all communications is between A&KDC and A&B, B&KDC don't talk directly (though indirectly a message passes from KDC via A to B, encrypted in B's key so that A is unable to read or alter it). Other variations of key distribution protocols can involve direct communications between B&KDC. 2018/11/22 现代密码学理论与实践-13

Needham-Schroeder Protocol 2018/11/22 现代密码学理论与实践-13

Needham-Schroeder Protocol 用于安全地分发A和B通信的新会话密钥 对于重放攻击是脆弱的，如果老会话密钥被破了的话 因此需要第三个消息来使得B相信是和A通信 有几种改进方法 增加时间戳(Denning 81) 使用一个额外的nonce (Neuman 93) There is a critical flaw in the protocol, as shown. This emphasises the need to be extremely careful in codifying assumptions, and tracking the timeliness of the flow of info in protocols. Designing secure protocols is not easy, and should not be done lightly. Great care and analysis is needed. 2018/11/22 现代密码学理论与实践-13

Denning方法 Denning 81 A and B verify timeliness by 1. A→KDC: IDA || IDB 2. KDC→A: EKa[Ks || IDB ||T|| EKb[Ks||IDA||T] ] 3. A→B: EKb[Ks ||IDA ||T] 4. B→A: EKs[N1] 5. A→B: EKs[f(N1)] A and B verify timeliness by |Clock – T| < Δt1 + Δt2 Δt1: time difference between KDC and local ones, Δt2: network delay 2018/11/22 现代密码学理论与实践-13

Neuman方法 Neuman 93 1. A→B: IDA ||NA 2. B→KDC: IDB || NB || EKb[IDA || NA ||Tb] 3. KDC→A: EKa[IDB||NA||Ks||Tb]||EKb[IDA||Ks||Tb]||NB 4. A→B: EKb[IDA || Ks ||Tb] ||EKs[NB] 在有效时限内，A与B建立新的会话： 1. A→B: EKb[IDA || Ks ||Tb], N’a 2. B→A: N’b , EKs[N’a] 3. A→B: EKs[N’b] 2018/11/22 现代密码学理论与实践-13

使用公开密钥密码实现双向认证 有很多使用公开密钥密码的双向认证方法 需要确保其他各方都拥有正确的公开密钥 使用一个集中式的认证服务器(AS) 现有很多不同的使用时间戳或nonce的方法 2018/11/22 现代密码学理论与实践-13

Denning AS Protocol Denning 81 presented the following: 1. A→AS: IDA || IDB 2. AS→A: EKRas[IDA||KUa||T] || EKRas[IDB||KUb||T] 3. A→B: EKRas[IDA||KUa||T] || EKRas[IDB||KUb||T] || EKUb[EKRa[Ks||T]] 会话密钥由A选择的, 因此AS不一定是可信的 时间戳可以防范重放攻击, 但是需要同步时钟 2018/11/22 现代密码学理论与实践-13

13.2.2 单向认证 当通信双方不同时在线时需要用到单向认证，比如发送电子邮件 消息头部必须是可读的以便在系统中传输 也可能希望消息的主体保密，发送者认证 2018/11/22 现代密码学理论与实践-13

使用对称密码实现单向认证 可以把KDC使用方法应用于此，不需要最终交换nonce 不能抗重放攻击 1. A→KDC: IDA || IDB || N1 2. KDC→A: EKa[Ks || IDB || N1 || EKb[Ks||IDA] ] 3. A→B: EKb[Ks||IDA] || EKs[M] 不能抗重放攻击 可以在消息中加入时间戳，由于电子邮件处理可能存在大量时延，加入时间戳的作用是有限的 2018/11/22 现代密码学理论与实践-13

公钥加密方法实现单向认证 已有一些适用的公钥方法 如果保密是主要关心的问题，可以使用 如果需要认证，则可基于数字证书使用数字签名的方法 A→B: EKUb[Ks] || EKs[M] 消息和会话密钥都加密了 如果需要认证，则可基于数字证书使用数字签名的方法 A→B: M || EKRa[H(M)] || EKRas[T||IDA||KUa] 这里有消息, 签名, 证书 2018/11/22 现代密码学理论与实践-13

13.3 数字签名标准(DSS) DSS是美国政府作为标准FIPS 186发布的 DSS使用SHA作为散列算法 由NIST和NSA在90年代早期设计 DSS是标准, DSA是其算法 DSS是ElGamal和Schnorr算法的变形 DSS产生320位数字签名, 但是具有512-1024位的安全性 DSS的安全依赖于DLP问题 DSA is the US Govt approved signature scheme - designed to provide strong signatures without allowing easy use for encryption. The signature scheme has advantages, being both smaller (320 vs 1024bit) and faster (much of the computation is done modulo a 160 bit number) than RSA. 2018/11/22 现代密码学理论与实践-13

2018/11/22 现代密码学理论与实践-13

DSA密钥产生 全局共享的公开密钥值为(p, q, g) 用户选择私钥，并计算其公开密钥 p是大素数 p = 2L 选择q, 是p-1的160位的素因子 选择g, 使得 g = h(p-1)/q where h<p-1, h(p-1)/q (mod p) > 1 用户选择私钥，并计算其公开密钥 选择 x<q 计算 y = gx (mod p) 2018/11/22 现代密码学理论与实践-13

DSA签名的产生 若要签名消息M, 签名方则 计算签名 把签名(r, s)和消息M一起发送给接收方 产生一个随机的签名密钥k, k<q r = (gk(mod p)) (mod q) s = k-1((SHA(M)+ x*r) (mod q) 把签名(r, s)和消息M一起发送给接收方 Signature creation is similar to ElGamal with the use of a per message temporary signature key k, but doing calculations first mod p, then mod q to reduce the size of the result. Note that the use of the hash function SHA is explicit. Note that only computing r involves calculation mod p and does not depend on message, hence can be done in advance. 2018/11/22 现代密码学理论与实践-13

DSA签名的验证 接收方收到消息M和签名(r, s) 接收方计算 如果v=r, 则签名通过验证 更多的证明细节可以参考有关资料 w = s-1(mod q) u1= (SHA(M) *w) (mod q) u2= (r*w) (mod q) v = (gu1 *yu2(mod p)) (mod q) 如果v=r, 则签名通过验证 更多的证明细节可以参考有关资料 Verification also consists of comparing two computations. Note that the difficulty of computing discrete logs is why it is infeasible for an opponent to recover k from r. Note that nearly all the calculations are mod q, and hence are much faster save for the last step. 2018/11/22 现代密码学理论与实践-13

DSS Signing and Verifying 2018/11/22 现代密码学理论与实践-13

2018/11/22 现代密码学理论与实践-13

基于非对称密码体制的数字签名 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 mod n = m 签名：s = md mod n 验证：m = se mod n = (md mod n )e mod n 2018/11/22 现代密码学理论与实践-13

用数字签名和加密同时实现报文的秘密和认证的传送 例：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 = 4829 mod 65 = 3 用数字签名和加密同时实现报文的秘密和认证的传送 设有用户A和B，A: nA, eA, dA, EA, DA, B: nB, eB, dB, EB, DB, 报文从A→B： 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 2018/11/22 现代密码学理论与实践-13

用数字签名和加密同时实现报文的秘密和认证的传送 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. nA<nB，则A：c = EB(DA(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，要求既保密又认证地传送。 2018/11/22 现代密码学理论与实践-13

重温：ElGamal的数据加密方法 假定A和B互相通信, 共享大素数p, 本原元素α 0<= m <= p-1, gcd(α, p) = 1, A和B各有自己的秘密xA和xB 加密 A选择k∈[0, p-1], k的作用即为xA, A访问公共区域找到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 2018/11/22 现代密码学理论与实践-13

ElGamal的数字签名方法 若A为B签署m，0≤m≤ p-1， A随机选择k∈[0, p-1]，gcd(k, p-1) = 1 计算r = αk mod p 计算αm = YArrs mod p, YA= αxA mod p 即αm = αxA rαk s mod p 则 m = (xAr + ks) mod p-1 根据此式求s，则对于m的数字签名即为(r, s)，0<= r, s<p-1. 2018/11/22 现代密码学理论与实践-13

ElGamal数字签名的验证 验证：给定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 = (10 + 5s) mod 16 5s mod 16 = 1, s = 13 所以，签名为(5, 13)。 验证: αm mod p = 311 mod 17 = 102x10x9 mod 17 = 7 YArrs mod p = (32)5 x 513 mod 17 = 7 2018/11/22 现代密码学理论与实践-13

密钥管理的内容 原则 密钥组织结构 密钥难以窃取 在一定条件下即使窃得密钥也无用，有使用时间和范围限制 密钥分配和更新对用户透明 密钥的层次化管理结构：最高层密钥为主密钥，构成密钥管理系统之核心。下层的密钥按照某种密钥协议来生成，掌握了主密钥，就有可能找出下层的各个密钥。 2018/11/22 现代密码学理论与实践-13

密钥的层次化管理结构 工作密钥(会话密钥 session key) 密钥的连通：密钥共享的范围 密钥的分割：适用范围和时间限制 重复使用同一密钥容易导致泄漏，应该经常更换； 使用相同密钥，攻击者可以实施重播攻击； 密钥丢失，仅影响本次会话； 更换密钥，防止对方以后窃取信息。 密钥的连通：密钥共享的范围 密钥的分割：适用范围和时间限制 按空间分割 按时间分割 分割实现：静态/动态 2018/11/22 现代密码学理论与实践-13

密钥的生成 ANSI的X9.17定义了一种线性密钥空间的密钥生成方法。 非线性密钥空间中的密钥生成算法 令k为主密钥，v0为64位的随机种子，T为时间戳，生成的密钥记为Ri，Ek为任意的加密算法，则 Ri = Ek(Ek(Ti)vi)；vi+1 = Ek(TiRi) 生成的Ri为64位, 去掉校验位, 则为标准的DES密钥。 非线性密钥空间中的密钥生成算法 将密钥分成两部分：k和Ek(Str)，Ek(Str)构成秘密预定义串；使用时先用k解密这个串，若正确，则正常使用k，否则强行启动另一个弱化了的加密算法。 2018/11/22 现代密码学理论与实践-13

密钥的管理机制 密钥的分配和传递 密钥的验证 密钥的保存 自动进行分配，集中传送和分散传送 在传递密钥时附带一个用该密钥加密的密文；接收者通过解密来验证密钥的正确性，同时可以结合接收者身份认证。 密钥的保存 可以分散保存，可以秘密分享secret sharing 2018/11/22 现代密码学理论与实践-13

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。 2018/11/22 现代密码学理论与实践-13

拉格朗日插值多项式法实现秘密分享 拉格朗日插值多项式法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可以从t个shadow中获得，少于t个shadow则不能重组h(x)和获得K。 2018/11/22 现代密码学理论与实践-13

拉格朗日插值多项式法的实现 h(x) = kis mod p 给定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 +10x +13) mod 17 k1 = h(1) = (2+10+13) mod 17 = 25 mod 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 2018/11/22 现代密码学理论与实践-13

拉格朗日插值多项式法实现 重组h(x)，t = 3，选k1, k3, k5： h(x) = [8 +10 +11 ] 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 +10x + 13) mod 17 K = h(0) = 13 2018/11/22 现代密码学理论与实践-13

离散对数的方法实现密钥共享 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 2018/11/22 现代密码学理论与实践-13

对假冒和桥接攻击的防范 Hughes对Diffie-Hellman方法的改进，目的是防假冒和桥接攻击 智能卡方式 双方密钥的生成是异步进行的，A可以事先生成密钥，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。全系统有一个通信各方均使用的公开密钥，对应的秘密密钥保留在发卡方。需要通信时由智能卡产生一个会话密钥。 2018/11/22 现代密码学理论与实践-13

加密的密钥交换技术EKE Steves Bellovin和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正确，则交换与鉴别成功。 前三步交换密钥，后三步双向身份认证。 2018/11/22 现代密码学理论与实践-13

13章习题 Due: Nov. 27, 2012 第四版，第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如何验证？ 2018/11/22 现代密码学理论与实践-13

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重组此二进制多项式 2018/11/22 现代密码学理论与实践-13