(现代密码学课件)07数字签名

1、第七章 数字签字和密码协议数字签字的基本概念数字签字标准其他签字方案认证协议身份证明技术其他密码协议1第七章 数字签字和密码协议数字签字的基本概念1一、数字签字的基本概念2一、数字签字的基本概念2数字签字应具有的性质能够验证签字产生者的身份，以及产生签字的日期和时间能用于证实被签消息的内容数字签字可由第三方验证，从而能够解决通信双方的争议3数字签字应具有的性质能够验证签字产生者的身份，以及产生签字的(现代密码学课件)07数字签名(现代密码学课件)07数字签名数字签字的产生方式由加密算法产生数字签字由签字算法产生数字签字6数字签字的产生方式由加密算法产生数字签字6由加密算法产生数字签字单钥加密M

2、MEKDK无法实现数字签名 向B保证收到的消息确实来自A B恢复M后，可相信B未被窜改，否则B将得到无意义的比特序列7由加密算法产生数字签字单钥加密MMEKDK无法实现 向B保证由加密算法产生数字签字公钥加密MMESKADPKA只有A才能用SKA加密，可使B相信消息来自A,不提供保密性MMESKADPKAEPKBDSKB提供保密性和认证性8由加密算法产生数字签字公钥加密MMESKADPKA只有A才能由加密算法产生数字签字RSA签字体制体制参数大素数p,q，n=pq, y(n)=(p-1)(q-1)。选整数1e y(n),且gcd(e, y(n)=1;计算d满足de1 mod y(n). e,n

3、为公开密钥，d,n为秘密密钥。签字过程S=Md mod n验证过程M=Se mod n实际应用中加密是对H(M)进行的。9由加密算法产生数字签字RSA签字体制9由加密算法产生数字签字外部保密数字签字直接对需要签字的消息生成内部保密数字签字对已加密的消息产生外部保密有利于争议的解决。10由加密算法产生数字签字外部保密10由签字算法产生数字签字签字体制=(M, S, K, V) M:明文空间，S:签字的集合，K:密钥空间， V:证实函数的值域，由真和伪组成。 (1) 签字算法： 对每一mM和每一kK，易于计算对m的签字 s=Sigk(m)S 签字密钥是秘密的，只有签字人掌握； (2)验证算法： 1

4、1由签字算法产生数字签字签字体制=(M, S, K, V)11由签字算法产生数字签字体制的安全性：从M和其签字S难于推出K或伪造一个M使M和S可被证实为真。与消息加密不同点：消息加密和解密可能是一次性的，它要求在解密之前是安全的；而一个签字的消息可能作为一个法律上的文件，如合同等，很可能在对消息签署多年之后才验证其签字，且可能需要多次验证此签字。12由签字算法产生数字签字体制的安全性：从M和其签字S难于推出K数字签字的执行方式直接方式 数字签字的执行过程只有通信的双方参与，并假定双方有共享的秘密密钥或者接收一方知道发送方的公开钥。缺点：方案的有效性取决于发方密钥的安全性。发方可声称秘密钥丢失或

5、被窃13数字签字的执行方式直接方式13数字签字的执行方式直接方式 数字签字的执行过程只有通信的双方参与，并假定双方有共享的秘密密钥或者接收一方知道发送方的公开钥。缺点：方案的有效性取决于发方密钥的安全性。发方可声称秘密钥丢失或被窃14数字签字的执行方式直接方式14数字签字的执行方式具有仲裁方式的数字签字发方X对发往收方Y的消息签字将消息和签字先发往仲裁者AA对消息和签字验证完后，再连同一个表示已通过验证的指令一起发给Y.15数字签字的执行方式具有仲裁方式的数字签字15具有仲裁方式的数字签字例1：XA: M|AY:E：单钥加密算法KXA,KAY:A与X和Y的共享密钥M：消息T：时戳IDX：X的身

6、份H(M)：M的杂凑值A必须获得X和Y的高度信任X相信A不会泄漏KXA，并且不会X的签字Y相信A只有对 中的杂凑值及X签字验证无误后才将其发给YX，Y都相信A可公正的解决争议16具有仲裁方式的数字签字例1：E：单钥加密算法A必须获得X和Y具有仲裁方式的数字签字例2XA: IDX|AY:X对M的签字X和Y的共享密钥此方案提供了对M的保密性和前一方案相同，仲裁者可和发方共谋否认发方曾发过的消息，也可和收方共谋产生发方的签字17具有仲裁方式的数字签字例2X对M的签字X和Y的共享密钥此方案具有仲裁方式的数字签字例3X的私钥Y的公钥18具有仲裁方式的数字签字例3X的私钥Y的公钥18二、数字签名标准Dig

7、ital Signature Standard (DSS)19二、数字签名标准Digital Signature Stan概况由NIST1991年公布1993年公布修改版美国联邦信息处理标准FIPS PUB 186签名长度320比特只能用于数字签字，不能用于加密20概况由NIST1991年公布20DSS的基本方式M|HESKAMHDPKA比较RSA签字DSS签字M|HSKAMsHPKG比较VerPKGk随机数rPKASig全局公开钥21DSS的基本方式M|HESKAMHDPKA比较RSA签字D数字签字算法DSA在Elgamal和Schnorr两个方案基础上设计的算法描述:(a) 全局公钥( p

8、, q, g ) p：是2L-1 p 2L中的大素数，512 L 1024，L是64的倍数； q：p-1的素因子，且2159 q 2160，即字长160比特； g：g= h(p-1)/q mod p，且1 h 1。(b) 用户秘密钥 x：x为在0 xq内的随机数。(c) 用户公钥 y：y=gx mod p。(d) 用户每个消息用的秘密随机数k：在0kq内的随机数22数字签字算法DSA在Elgamal和Schnorr两个方案基数字签字算法DSA(e) 签字过程：对消息M，其签字为S=Sigk(M, k)=(r, s)， r (gk mod p) mod q s k-1 (H(M)xr) mod

9、q (f) 验证过程：计算 w = s-1 mod q ; u1 =H(M)w mod q ; u2 = rw mod q ; v = (gu1yu2) mod p mod q。Ver(M, r, s)=真 v = r23数字签字算法DSA(e) 签字过程：对消息M，其签字为S=S三、其他签字方案24三、其他签字方案24离散对数签字体制体制参数 p：大素数 q：(p1)或p-1的大素因子 g：gRZp*,gq=1 mod p。 x：用户秘密钥, x为在1xq内的随机数。y：用户公钥 gx= mod p。25离散对数签字体制体制参数25离散对数签字体制签字产生过程计算m的杂凑值选择随机数k:1k

10、q，计算rgk mod p从签字方程ak=b+cx mod q中解出s.（r,s)为数字签字。abcrrH(m)rH(m)H(m)rH(m)ss s H(m)srsrsH(m)111126离散对数签字体制签字产生过程abcrs H(m)26离散对数签字体制签字验证过程27离散对数签字体制签字验证过程27Elgamal签字体制离散对数签字体制的特例体制参数 p：一个大素数； g：是Zp中乘群Zp*的一个生成元或本原元素； M：消息空间，为Zp*； S：签字空间，为Zp*Zp1； x：用户秘密钥xZp*； y：用户公钥，ygx mod p p，g，y为公钥，x为秘密钥。28Elgamal签字体制离

11、散对数签字体制的特例28Elgamal签字体制签字过程：给定消息M，进行下述工作。 (a) 选择秘密随机数kZp*； (b) 计算 H(M)； (c) 计算 r=gk mod ps=(H(M)xr)k-1 mod (p1) (r,s)作为签字.29Elgamal签字体制签字过程：给定消息M，进行下述工作。2Elgamal签字体制验证过程： 收信人收到M，(r,s)，先计算H(M)，并按下式验证 Verk(H(M), r, s)=真 yrrsgH(M) mod p 因为yrrsgrxgskg(rx+sk) mod p， (rx+sk) H(M) mod(p1) 故有yrrsgH(M) mod p

12、30Elgamal签字体制验证过程：30Schnorr签字体制 体制参数 p, q：大素数，q|p-1。q是大于等于160 bits的整数，p是大于等于512 bits的整数，保证Zp中求解离散对数困难； g：Zp*中元素，且gq1 mod p； x：用户密钥1xq； y：用户公钥ygx mod p。 消息空间M=Zp*，签字空间S=Zp*Zq；密钥空间K=(p,q,g,x,y): ygx mod p31Schnorr签字体制 体制参数31Schnorr签字体制签字过程：令待签消息为M，对给定的M做下述运算：(a) 发用户任选一秘密随机数kZq (b) 计算 rgk mod p skxe mo

13、d p 式中 e=H(r|M) (c) 签字S=Sigk(M)=(e,s)32Schnorr签字体制签字过程：令待签消息为M，对给定的M做Schnorr签字体制验证过程：收信人收到消息M及签字S=(e,s)后(a) 计算rgsye mod p 而后计算H(r |M)。 (b) 验证 Ver(M, r, s) H(r|M)=e 因为，若(e|s)是M的合法签字，则有g sy -egk-xegxegkr mod p。33Schnorr签字体制验证过程：收信人收到消息M及签字S=(Schnorr签字体制Schnorr签字与ElGamal签字的不同点： 在ElGamal体制中，g为Z*p的本原元素；而

14、在Schnorr体制中，g为Zp*中子集Zq*的本原元素，它不是Zp*的本原元素。显然ElGamal的安全性要高于Schnorr。 Schnorr的签字较短，由|q|及|H(M)|决定。 在Schnorr签字中，r=gk mod p可以预先计算，k与M无关，因而签字只需一次mod q乘法及减法。所需计算量少，速度快。34Schnorr签字体制Schnorr签字与ElGamal签字四、认证协议Authentication Protocols35四、认证协议Authentication Protocols相互认证A，B双方在建立共享密钥时需要考虑保密性和实时性。保密性：会话密钥应以密文传送，因此双

15、方应事先共享密钥或者使用公钥实时性:防止重放序列号方法时戳询问应答36相互认证A，B双方在建立共享密钥时需要考虑保密性和实时性。3序列号方法对交换的每一条消息加上序列号，序列号正确才被接收要求每个用户分别记录与其他每一用户交互的序列号，增加用户负担，因而很少使用37序列号方法对交换的每一条消息加上序列号，序列号正确才被接收3时戳法A收到消息中包含时戳，且A看来这一时戳充分接近自己的当前时刻，A才认为收到的消息是新的并接收要求各方时间同步38时戳法A收到消息中包含时戳，且A看来这一时戳充分接近自己的当询问应答用户A向B发出一个一次性随机数作为询问，如果收到B发来的应答消息也包含一正确的一次性随机

16、数，A就认为消息是新的并接受之。39询问应答用户A向B发出一个一次性随机数作为询问，如果收到B各种方法的比较时戳法不适用于面向连接的应用过程要求不同的处理器之间时间同步，所用的协议必须是容错的以处理网络错误协议中任何一方时钟出现错误失去同步，则敌手攻击的可能性增加网络中存在延迟，不能期待保持精确同步，必须允许误差范围40各种方法的比较时戳法不适用于面向连接的应用过程40各种方法的比较询问应答不适合于无连接的应用过程在传输前需要经过询问应答这一额外的握手过程，与无连接应用过程的本质特性不符。无连接应用最好使用安全时间服务器提供同步41各种方法的比较询问应答不适合于无连接的应用过程41Needha

17、m-Schroeder协议2. 4. KDCAB1. IDA| IDB |N13. 5. 如果敌手获得了旧会话密钥，则可以冒充A重放3，并且可回答5，成功的欺骗B42Needham-Schroeder协议2. 4. KDCABNeedham-Schroeder改进协议12. 4. KDCAB1. IDA| IDB3. 5. 以时戳替代随机数，用以向A，B保证Ks的新鲜性|ClockT|t1+t2 Clock:本地时钟t1：本地时钟与KDC时钟误差估计值t2 ：网络延迟时间要求各方时钟同步如果发方时钟超前B方时钟，可能导致等待重放攻击43Needham-Schroeder改进协议12. 4. K

18、DNeedham-Schroeder改进协议2KDCAB3. 1. 4. 2. 会话密钥的截止时间44Needham-Schroeder改进协议2KDCAB3. Needham-Schroeder改进协议2AB1.2.3.有效期内可不通过KDC直接认证45Needham-Schroeder改进协议2AB1.2.3.公钥加密体制ASAB1. IDA| IDB2. 3. 时戳防止重放，要求时钟同步46公钥加密体制ASAB1. IDA| IDB2. 3. 时戳公钥加密体制ASAB2. 1. IDA| IDB3. 4. 6747公钥加密体制ASAB2. 1. IDA| IDB3. 4.单向认证不需要双

19、方同时在线（电子邮件）邮件接收者希望认证邮件的来源以防假冒分为单钥加密方法和公钥加密方法48单向认证不需要双方同时在线（电子邮件）48单钥加密2. KDCAB1. IDA| IDB |N13. 不要求B同时在线，保证只有B能解读消息，提供对A的认证。不能防止重放攻击。49单钥加密2. KDCAB1. IDA| IDB |N13公钥加密AB对发送消息提供保密性对发送消息提供认证性AB对发送消息提供保密和认证性ABA的证书50公钥加密AB对发送消息提供保密性对发送消息提供认证性AB对发五、身份证明技术51五、身份证明技术51身份证明技术 传统的身份证明： 一般是通过检验“物”的有效性来确认持该物的

20、的身份。徽章、工作证、信用卡、驾驶执照、身份证、护照等，卡上含有个人照片(易于换成指纹、视网膜图样、牙齿的X适用的射像等)。 信息系统常用方式： 用户名和口令52身份证明技术 传统的身份证明：52交互式证明两方参与 示证者P(Prover)，知道某一秘密，使V相信自己掌握这一秘密； 验证者V(Verifier)，验证P掌握秘密；每轮V向P发出一询问，P向V做应答。V检查P是否每一轮都能正确应答。53交互式证明两方参与53交互证明与数学证明的区别数学证明的证明者可自己独立的完成证明交互证明由P产生证明，V验证证明的有效性来实现，双方之间要有通信交互系统应满足完备性：如果P知道某一秘密，V将接收P

21、的证明正确性：如果P能以一定的概率使V相信P的证明，则P知道相应的秘密54交互证明与数学证明的区别数学证明的证明者可自己独立的完成证明Fiat-Shamir身份识别方案参数：选定一个随机模m=pq。产生随机数v，且使s2=v，即v为模m的平方剩余。 m和v是公开的，s作为P的秘密55Fiat-Shamir身份识别方案参数：55Fiat-Shamir身份识别方案(1) P取随机数r(m)，计算x= r 2 mod m，送给V；(2) V将一随机bit b送给P；(3) 若b=0，则P将r送给V；若b=1，则P将y=rs送给V；(4) 若b=0，则V证实x=r 2 mod m，从而证明P知道，若b

22、=1，则B证实 xv=y2 mod m，从而证明A知道。 这是一次证明，A和B可将此协议重复t次，直到B相信A知道s为止。56Fiat-Shamir身份识别方案(1) P取随机数r(mFiat-Shamir身份识别方案完备性如果P和V遵守协议，且P知道s，则应答rs是应是模m下xv的平方根，V接收P的证明，所以协议是完备的。正确性P不知道s，他也可取r，送x=r2 mod m给V，V送b给P。P可将r送出，当b=0时则V可通过检验而受骗，当b=1时，则V可发现P不知s，B受骗概率为1/2，但连续t次受骗的概率将仅为2-tV无法知道P的秘密，因为V没有机会产生(0,1）以外的信息，P送给V的消息

23、中仅为P知道v的平方根这一事实。57Fiat-Shamir身份识别方案完备性57零知识证明最小泄露证明和零知识证明： 以一种有效的数学方法，使V可以检验每一步成立，最终确信P知道其秘密，而又能保证不泄露P所知道的信息。58零知识证明最小泄露证明和零知识证明：58零知识证明的基本协议例Quisquater等1989 。 设P知道咒语， 可打开C和D之间的秘密门，不知道者都将走向死胡同中。ABCD59零知识证明的基本协议例Quisquater等1989 。零知识证明的基本协议 (1) V站在A点； (2) P进入洞中任一点C或D； (3) 当P进洞之后，V走到B点； (4) V叫P：(a)从左边出

24、来，或(b)从右边出来； (5) P按要求实现(以咒语，即解数学难题帮助)； (6) P和V重复执行 (1)(5)共n次。 若A不知咒语，则在B点，只有50 %的机会猜中B的要求，协议执行n次，则只有2-n的机会完全猜中，若n=16，则若每次均通过B的检验，B受骗机会仅为1/65 53660零知识证明的基本协议 (1) V站在A点；60零知识证明的基本协议哈米尔顿回路 图论中有一个著名问题，对有n个顶点的全连通图G，若有一条通路可通过且仅通过各顶点一次，则称其为哈米尔顿回路。Blum1986 最早将其用于零知识证明。当n大时，要想找到一条Hamilton回路，用计算机做也要好多年，它是一种单向

25、函数问题。若A知道一条回路，如何使B相信他知道，且不告诉他具体回路？ 61零知识证明的基本协议哈米尔顿回路61零知识证明的基本协议A将G进行随机置换，对其顶点进行移动，并改变其标号得到一个新的有限图H。因 ，故G上的Hamilton回路与H上的Hamilton回路一一对应。已知G上的Hamilton回路易于找出H上的相应回路；A将H的复本给B；B向A提出下述问题之一：(a) 出示证明G和H同构，(b) 出示H上的Hamilton回路；A执行下述任务之一：(a) 证明G和H同构，但不出示H上的Hamilton回路，(b) 出示H上的Hamilton回路但不证明G和H同构；A和B重复执行 (1)(4)共n次。62零知识证明的基本协议A将G进行随机置换，对其顶点进行移动，并六、其他密码协议63六、其他密码协议63智力扑克A和B通过网络进行智力扑克比赛，不用第三方做裁判，发牌者由任一方担任，要求发牌过程满足任一副牌是等可能的发给A，B的牌没有重复每人知道自己手中的牌，不知道别人的牌比赛结束后，每一方都能发现对方的欺骗行为为满足要求，A,B方需要加密一些信息，比赛结束前，这些机密算法都是保密的。64智力扑克A和B通过网络进行智力扑克比赛，不用第三方做裁判，发智力扑克A和B的加密解密算法记为EA，EB，D