现代密码学理论与实践第13章 数字签名和认证协议Fourth Edition by William StallingsSlides by 杨寿保syangustc.edu.cnhttp:/staff.ustc.edu.cn/syang2012年11月2024/7/211/47现代密码学理论与实践-13本章要点l数字签名是一种认证机制，它使得消息的产生者可以添加一个起签名作用的码字。通过计算消息的散列值并用产生者的私钥加密散列值来生成签名。签名保证了消息的来源和完整性。l相互认证协议使得通信的各方对相互的身份感到放心, 并交换会话密钥。l单向认证时, 接收方想确信消息确实来自声称的发送方。l数字签名标准(DSS)是NIST标准，它使用安全散列算法(SHA)。2024/7/212现代密码学理论与实践-1313.1 数字签名Digital Signaturel数字签名的简单定义l数字签名是使以数字形式存储的明文信息经过特定密码变换生成密文，作为相应明文的签名，使明文信息的接收者能够验证信息确实来自合法用户，以及确认信息发送者身份。l对数字签名的基本要求 l在收发双方不能完全信任的情况下，需要除认证之外的其他方法来解决假冒和否认的问题，数字签名则是解决办法；l签名接收者能容易地验证签字者对消息所做的数字签名，包括日期和时间；l任何人，包括签名接收者，都不能伪造签名者的签字；l发生争议时，可由第三方解决。2024/7/213现代密码学理论与实践-13l数字签名与消息认证的区别 l消息认证是使消息接收方验证消息发送者发送的内容有无被修改过，对防止第三者破坏足够，但收发双方有利害冲突时就无法解决纷争，需要更严格的手段，即数字签名。l数字签名的基本形式 l对消息签名的两种方法l对消息整体的签字，将被签消息整体经过密码变换得到签字；l对消息摘要的签字，附在被签消息之后，或嵌在某一特定位置上作一段签字图样。l两类数字签名l确定性数字签名，明文与签名一一对应；l概率性数字签名，一个明文可以有多个合法签名，每次都不一样。数字签名的基本形式2024/7/214现代密码学理论与实践-1313.1.2 直接数字签名l直接数字签名仅涉及通信方(信源、信宿) l假定信宿知道信源的公开密钥l数字签名通过信源对整个报文用私有密钥加密，或对报文的摘要加密来实现l通常先签名，然后对消息和签名一起加密l安全性依赖于信源私有密钥的安全性2024/7/215现代密码学理论与实践-1313.1.3 仲裁数字签名l涉及到一个仲裁方(arbiter A)l签名方的签名报文首先送给仲裁者l仲裁者对报文和签名进行测试以检验出处和内容，然后注上日期和仲裁说明后发给接收方l要求仲裁方在一定程度上是可以信任的l可以用对称密码或公开密钥密码实现l仲裁方可以知道消息，也可以不知道消息2024/7/216现代密码学理论与实践-13需要仲裁的数字签名技术2024/7/217现代密码学理论与实践-1313.2 认证协议l认证服务和功能l认证是证实信息交换过程有效性和合法性的一种手段，包括对通信对象的认证(身份认证)和报文内容的认证(报文认证)，起到数据完整性的保护。这里有l信息的真实性l存储数据的真实性l接收方提供回执l发送方不可否认l时效性和公证可能性l认证的目的l防窃听、防假冒或拦截、防窃取等2024/7/218现代密码学理论与实践-13l单向认证l使用对称加密方法，即一次一密方法的变形l使用公开密钥方法：A向B声称是A，B则向A送一随机数R，A用其私有密钥加密送B，B用A的公开密钥验证。l使用改进的口令方式l双向认证l对称密钥方式(三次握手)l公开密钥方式，A、B双向使用不同的R值l时标方式l可信中继l使用KDC密钥分发中心l通过DASS (Distributed Authentication Security Service)l群认证(Group Authentication)基本认证方法2024/7/219现代密码学理论与实践-1313.2.1 双向认证l双向认证协议可以使通信双方达成一致并交换会话密钥l重放攻击：合法的签名消息被拷贝后重新送出l简单重放l可检测的重放l不可检测的重放l不加修改的逆向重放l重放攻击的解决方法l使用序列号l使用时间戳(需要同步时钟)l挑战/应答(使用单独的nonce)2024/7/2110现代密码学理论与实践-13对称加密方法l使用两层传统加密密钥结构来保证分布环境中通信的保密性l通常需要可信密钥分发中心Key Distribution Center (KDC)l每一方与KDC共享主密钥lKDC产生双方通信要用的会话密钥l用主密钥来分发会话密钥2024/7/2111现代密码学理论与实践-13Needham-Schroeder Protocoll最初期的第三方密钥分发协议之一lKDC负责为用户A和B之间的通信产生会话密钥l协议如下:1. AKDC: IDA | IDB | N12. KDCA: EKaKs | IDB | N1 | EKbKs|IDA 3. AB: EKbKs|IDA4. BA: EKsN25. AB: EKsf(N2)2024/7/2112现代密码学理论与实践-13Needham-Schroeder Protocol2024/7/2113现代密码学理论与实践-13Needham-Schroeder Protocoll用于安全地分发A和B通信的新会话密钥l对于重放攻击是脆弱的，如果老会话密钥被破了的话l因此需要第三个消息来使得B相信是和A通信l有几种改进方法l增加时间戳(Denning 81)l使用一个额外的nonce (Neuman 93)2024/7/2114现代密码学理论与实践-13Denning方法lDenning 811. AKDC: IDA | IDB2. KDCA: EKaKs | IDB |T| EKbKs|IDA|T 3. AB: EKbKs |IDA |T4. BA: EKsN15. AB: EKsf(N1) A and B verify timeliness by|Clock T| t1 + t2 t1: time difference between KDC and local ones, t2: network delay2024/7/2115现代密码学理论与实践-13Neuman方法lNeuman 931. AB: IDA |NA2. BKDC: IDB | NB | EKbIDA | NA |Tb3. KDCA: EKaIDB|NA|Ks|Tb|EKbIDA|Ks|Tb|NB 4. AB: EKbIDA | Ks |Tb |EKsNB在有效时限内，A与B建立新的会话：1. AB: EKbIDA | Ks |Tb, Na2. BA: Nb , EKsNa3. AB: EKsNb2024/7/2116现代密码学理论与实践-13使用公开密钥密码实现双向认证l有很多使用公开密钥密码的双向认证方法l需要确保其他各方都拥有正确的公开密钥l使用一个集中式的认证服务器(AS)l现有很多不同的使用时间戳或nonce的方法2024/7/2117现代密码学理论与实践-13Denning AS ProtocollDenning 81 presented the following:1. AAS: IDA | IDB2. ASA: EKRasIDA|KUa|T | EKRasIDB|KUb|T 3. AB: EKRasIDA|KUa|T | EKRasIDB|KUb|T | EKUbEKRaKs|T l会话密钥由A选择的, 因此AS不一定是可信的l时间戳可以防范重放攻击, 但是需要同步时钟2024/7/2118现代密码学理论与实践-1313.2.2 单向认证l当通信双方不同时在线时需要用到单向认证，比如发送电子邮件l消息头部必须是可读的以便在系统中传输l也可能希望消息的主体保密，发送者认证2024/7/2119现代密码学理论与实践-13使用对称密码实现单向认证l可以把KDC使用方法应用于此，不需要最终交换nonce1. AKDC: IDA | IDB | N12. KDCA: EKaKs | IDB | N1 | EKbKs|IDA 3. AB: EKbKs|IDA | EKsMl 不能抗重放攻击l可以在消息中加入时间戳，由于电子邮件处理可能存在大量时延，加入时间戳的作用是有限的2024/7/2120现代密码学理论与实践-13公钥加密方法实现单向认证l已有一些适用的公钥方法l如果保密是主要关心的问题，可以使用AB: EKUbKs | EKsMl消息和会话密钥都加密了l如果需要认证，则可基于数字证书使用数字签名的方法AB: M | EKRaH(M) | EKRasT|IDA|KUa l这里有消息, 签名, 证书2024/7/2121现代密码学理论与实践-1313.3 数字签名标准(DSS)lDSS是美国政府作为标准FIPS 186发布的lDSS使用SHA作为散列算法 l由NIST和NSA在90年代早期设计 lDSS是标准, DSA是其算法lDSS是ElGamal和Schnorr算法的变形 lDSS产生320位数字签名, 但是具有512-1024位的安全性lDSS的安全依赖于DLP问题 2024/7/2122现代密码学理论与实践-132024/7/2123现代密码学理论与实践-13DSA密钥产生l全局共享的公开密钥值为(p, q, g)lp是大素数 p = 2L lL为512到1024位并且是64的倍数 l选择q, 是p-1的160位的素因子l选择g, 使得 g = h(p-1)/q lwhere h 1 l用户选择私钥，并计算其公开密钥 l选择 xq l计算 y = gx (mod p) 2024/7/2124现代密码学理论与实践-13DSA签名的产生l若要签名消息M, 签名方则l产生一个随机的签名密钥k, kq lk 必须是随机的，并且不能重复使用l计算签名 r = (gk(mod p) (mod q) s = k-1(SHA(M)+ x*r) (mod q) l把签名(r, s)和消息M一起发送给接收方2024/7/2125现代密码学理论与实践-13DSA签名的验证l接收方收到消息M和签名(r, s) l接收方计算 w = s-1(mod q) u1= (SHA(M) *w) (mod q) u2= (r*w) (mod q) v = (gu1 *yu2(mod p) (mod q) l如果v=r, 则签名通过验证 l更多的证明细节可以参考有关资料2024/7/2126现代密码学理论与实践-13DSS Signing and Verifying2024/7/2127现代密码学理论与实践-132024/7/2128现代密码学理论与实践-13lRSA方法的数字签名 给定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 = med mod n = m基于非对称密码体制的数字签名2024/7/2129现代密码学理论与实践-13l例：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 = 3l用数字签名和加密同时实现报文的秘密和认证的传送 设有用户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 用数字签名和加密同时实现报文的秘密和认证的传送2024/7/2130现代密码学理论与实践-13Both secrecy and authenticity: c = EB(DA(m) = (mdA mod nA)eB mod nBor: 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(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，要求既保密又认证地传送。用数字签名和加密同时实现报文的秘密和认证的传送2024/7/2131现代密码学理论与实践-13l假定A和B互相通信, 共享大素数p, 本原元素 0= m = p-1, gcd(, p) = 1, A和B各有自己的秘密xA和xBl加密A选择k0, p-1, k的作用即为xA, A访问公共区域找到B的公开密钥YB = xB mod p, 计算：K = (YB)k mod p，即K = xBk mod pc1 = k mod pc2 = mK mod p密文即为 (c1, c2)l解密B首先恢复K：K = c1xB mod p = kxB mod p然后恢复m：m = c2/K mod p = c2K-1 mod p重温：ElGamal的数据加密方法2024/7/2132现代密码学理论与实践-13 若A为B签署m，0m p-1，A随机选择k0, p-1，gcd(k, p-1) = 1计算r = k mod p计算m = YArrs mod p, 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的数字签名方法2024/7/2133现代密码学理论与实践-13l验证：给定m, r, 和s，容易计算 m mod p = YArrs mod p, 看其是否一致, k不能重复使用。l例：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 = 7ElGamal数字签名的验证2024/7/2134现代密码学理论与实践-13密钥管理的内容l原则l密钥难以窃取l在一定条件下即使窃得密钥也无用，有使用时间和范围限制l密钥分配和更新对用户透明l密钥组织结构l密钥的层次化管理结构：最高层密钥为主密钥，构成密钥管理系统之核心。下层的密钥按照某种密钥协议来生成，掌握了主密钥，就有可能找出下层的各个密钥。2024/7/2135现代密码学理论与实践-13l工作密钥(会话密钥 session key)l重复使用同一密钥容易导致泄漏，应该经常更换；l使用相同密钥，攻击者可以实施重播攻击；l密钥丢失，仅影响本次会话；l更换密钥，防止对方以后窃取信息。l密钥的连通：密钥共享的范围l密钥的分割：适用范围和时间限制l按空间分割l按时间分割l分割实现：静态/动态密钥的层次化管理结构2024/7/2136现代密码学理论与实践-13lANSI的X9.17定义了一种线性密钥空间的密钥生成方法。令k为主密钥，v0为64位的随机种子，T为时间戳，生成的密钥记为Ri，Ek为任意的加密算法，则Ri = Ek(Ek(Ti)vi)；vi+1 = Ek(TiRi)生成的Ri为64位, 去掉校验位, 则为标准的DES密钥。l非线性密钥空间中的密钥生成算法l将密钥分成两部分：k和Ek(Str)，Ek(Str)构成秘密预定义串；使用时先用k解密这个串，若正确，则正常使用k，否则强行启动另一个弱化了的加密算法。密钥的生成2024/7/2137现代密码学理论与实践-13l密钥的分配和传递l自动进行分配，集中传送和分散传送l密钥的验证l在传递密钥时附带一个用该密钥加密的密文；接收者通过解密来验证密钥的正确性，同时可以结合接收者身份认证。 l密钥的保存l可以分散保存，可以秘密分享secret sharing密钥的管理机制2024/7/2138现代密码学理论与实践-13Threshold Scheme: Secret Sharingl(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。2024/7/2139现代密码学理论与实践-13l拉格朗日插值多项式法Lagrange Interpolating Polynomial Scheme(1979, Shamir)l每个shadow由下列t-1次方的随机多项式导出: h(x) = (at-1xt-1 + + a1x1+ a0) mod p a0即为秘密K, a0=K, 是常数项, K p, w p, GF(p)l给定h(x)，则K = h(0)，ki= h(xi)，i =1, , w 每一对(xi, ki)就是h(x)函数曲线上的一个点，x1, x2, , xw无需保密，只是普通数字。l重组t-1次的多项式，只需要t个点就可以唯一地重组。这样，K可以从t个shadow中获得，少于t个shadow则不能重组h(x)和获得K。拉格朗日插值多项式法实现秘密分享2024/7/2140现代密码学理论与实践-13给定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 17k1 = h(1) = (2+10+13) mod 17 = 25 mod 17 = 8k2 = h(2) = (8+20+13) mod 17 = 41 mod 17 = 7k3 = h(3) = (18+30+13) mod 17 = 61 mod 17 = 10k4 = h(4) = (32+40+13) mod 17 = 85 mod 17 = 0k5 = h(5) = (50+50+13) mod 17 = 113 mod 17 = 11拉格朗日插值多项式法的实现2024/7/2141现代密码学理论与实践-13重组h(x)，t = 3，选k1, k3, k5：h(x) = 8 +10 +11 mod 17 = 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拉格朗日插值多项式法实现2024/7/2142现代密码学理论与实践-13lDiffie-Hellman方法 设用户A和B, 共享和P, 是本原元素, P是大素数。A、B各有一私有密钥, xA和xB, 公布他们的公开密钥：YA = xA mod PYB = xB mod P双方共享的会话密钥为 A：KAB = (YB)xA mod P = xAxB mod PB：KBA = (YA)xB mod P = xBxA mod P离散对数的方法实现密钥共享2024/7/2143现代密码学理论与实践-13lHughes对Diffie-Hellman方法的改进，目的是防假冒和桥接攻击l双方密钥的生成是异步进行的，A可以事先生成密钥，B在解密时才获得。lA: K = k mod PlB: Y = xB mod P AlA: X = Yk mod P = kxB mod P BlB: K = XxB-1 mod P = kxBxB-1 mod P = k mod P = Kl智能卡方式l将RSA与Diffie-Hellman协议相结合，通过KDC分配可进行密钥管理的智能卡，平时使用密钥时不需要KDC。全系统有一个通信各方均使用的公开密钥，对应的秘密密钥保留在发卡方。需要通信时由智能卡产生一个会话密钥。对假冒和桥接攻击的防范2024/7/2144现代密码学理论与实践-13lSteves Bellovin和Michael Merit提出Encrypted Key Exchange，用共享的对称密钥P来保护随机产生的公开密钥K：lA 随机产生一对公开/隐蔽密钥，使用对称密钥算法时将公开密钥K加密，将标识符A和Ep(K)发给BlB产生随机会话密钥K，向A发送Ep(EK(K)lA解出K，产生随机数RA，向B发送EK(RA)lB产生RB，向A发送EK(RA, RB)lA收到后，向B发送EK(RB)lA收到后确认RB正确，则交换与鉴别成功。前三步交换密钥，后三步双向身份认证。加密的密钥交换技术EKE2024/7/2145现代密码学理论与实践-1313章习题 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如何验证？2024/7/2146现代密码学理论与实践-1313章习题(续)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重组此二进制多项式2024/7/2147现代密码学理论与实践-13