《数字签名技术》PPT课件

1/47,兰州交通大学电子与信息工程学院,2020/5/16,应用密码学手册数字签名,2/47,兰州交通大学电子与信息工程学院,2020/5/16,参考书籍,HandbookofAppliedCryptography:Chapter11数字签名理论：赵泽茂应用密码学：孙淑玲应用密码学：协议、算法与C源程序W.迪菲,3/47,兰州交通大学电子与信息工程学院,2020/5/16,11.1引言11.2数字签名机制的框架11.3RSA和相关的签名方案11.4Fiat-Shamir签名方案11.5DSA和相关签名方案11.6一次数字签名11.7其他数字签名11.8带附加功能的签名,主要内容：,4/47,兰州交通大学电子与信息工程学院,2020/5/16,11.1引言,本章要研究的问题,本章要考虑的技术是如何设计手写签名的数字相似物数字签名,5/47,兰州交通大学电子与信息工程学院,2020/5/16,研究背景,计算机网络的产生把我们带进一个信息化社会。在信息社会里，大量传输和存储信息的安全保密和防伪问题成为人们关注的一个重要课题。,普遍的观点认为，现代密码技术是解决信息安全的最有效地方法，因此，密码学的研究成为当前国际上的一个热点。,6/47,兰州交通大学电子与信息工程学院,2020/5/16,数字签名的产生,重要证书、证件采用的防伪技术是使用特殊材料或者信息隐藏等,网络,1.否认2.伪造3.冒充4.篡改,数字签名,7/47,兰州交通大学电子与信息工程学院,2020/5/16,数字签名标准,ISO/IEC9796是数字签名的第一个国际标准，1991公布。1994年美国政府正式颁发了美国数字签名标准DSS(DigitalSignatureStandard)1995年我国也制定了自己的数字签名标准(GB15851-1995)2004年我国颁发中华人民共和国电子签名法,8/47,兰州交通大学电子与信息工程学院,2020/5/16,数字签名的原理,9/47,兰州交通大学电子与信息工程学院,2020/5/16,数字签名的功能,1.机密性2.完整性3.身份验证4.防伪造5.防抵赖6.防重放攻击,10/47,兰州交通大学电子与信息工程学院,2020/5/16,数字签名技术的应用,用户登录认证数据完整性不可抵赖性大型网络的公钥证书中电子交易和电子货币等领域,11/47,兰州交通大学电子与信息工程学院,2020/5/16,准备知识,1.Hash函数（即杂凑函数）（见参考书籍1/1.9）2.冗余函数3.整数因子分解问题（见参考书籍1/3.2）4.计算两个整数的最大公因子的欧几里得算法（见参考书籍1/2.1.4）5.扩展的欧几里得算法（见参考书籍1/2.107）6.模n平方根的困难性（见参考书籍1/3.5.2）7.求a模素数p的平方根（见参考书籍1/3.39）8.模n的二次剩余集(见参考书籍4/11.3.9)9.剩余类集合10.勒让德符号(见参考书籍4/11.3.10)11.雅可比符号(见参考书籍4/11.3.11),12/47,兰州交通大学电子与信息工程学院,2020/5/16,11.2数字签名机制的框架,基本定义,1.数字签名是一个数字串，它将一条数字形式的消息与某发起实体相关联。,2.数字签名生成算法是产生数字签名的某种方法。,3.数字签名验证算法是检验一个数字签名是否可信（即是否真的是由指定的实体生成）的某种方法。,4.数字签名方案（或机制）由签名生成算法和相关的验证算法组成。,5.数字签名的签名过程包括数字签名生成算法，以及某种将数据格式化为可签名消息的方法。,6.数字签名的验证过程包括验证算法，以及某种由消息恢复数据的方法。,13/47,兰州交通大学电子与信息工程学院,2020/5/16,数字签名机制中的记号,14/47,兰州交通大学电子与信息工程学院,2020/5/16,数字签名方案的分类,带附录的数字签名方案：要求初始消息作为验证算法的输入DSA、ElGamal和Schnorr签名方案消息可以是任意长度带消息恢复的数字签名方案：消息可从签名自身恢复，不要求初始消息作为验证算法的输入RSA、Rabin等公钥签名方案通常消息的长度固定,15/47,兰州交通大学电子与信息工程学院,2020/5/16,数字签名方案的分类,数字签名方案,带消息恢复,带附录,随机化的,确定性的,随机化的,确定性的,针对一个数字签名方案，如果有R1，则称此签名方案是随机化数字签名方案，否则称它是确定性数字签名方案。,16/47,兰州交通大学电子与信息工程学院,2020/5/16,带附录的数字签名方案,M:消息空间=mMh：消息摘要空间=S：消息签名空间=s*h:Hash函数SA,k:签名变换(1-1映射)VA:验证变换,17/47,兰州交通大学电子与信息工程学院,2020/5/16,带消息恢复的数字签名方案,M:消息空间=mMR：消息的冗余值空间=MS：待签空间S：消息的签名空间=s*R:冗余函数（可逆）(1-1映射)SA,k:签名变换(1-1映射),18/47,兰州交通大学电子与信息工程学院,2020/5/16,从带消息恢复的方案得到带附录的签名方案,先杂凑消息m；再对该杂凑值h(m)签名,19/47,兰州交通大学电子与信息工程学院,2020/5/16,签名方案的攻击类型,敌手的目标是：伪造签名完全攻克：敌手能计算出私钥选择性伪造：敌手能对一个特殊的消息或者预先选定的一类消息构造出正确的签名存在性伪造：敌手能伪造至少一个消息的签名，但敌手对被伪造签名所对应的消息几乎没有控制能力,20/47,兰州交通大学电子与信息工程学院,2020/5/16,11.3RSA和相关签名方案,RSA签名方案有关RSA签名的可能攻击实际中的RSA签名Rabin签名方案ISO/IEC9796规范PKCS#1规范,21/47,兰州交通大学电子与信息工程学院,2020/5/16,RSA签名方案,RSA是以它的三个发明者RonRivest，AdiShamir和LeoardAdleman的名字命名。RSA算法既可以用于加密，也可以用于数字签名。因为其加密变换是双射的，所以只要互换加密与解密的角色就可以得到数字签名方案。RSA的安全性基于大数分解的困难性，该算法已经经受住了多年深入的密码分析，密码分析者既不能证明也不能否认RSA的安全性，这恰恰说明该算法有一定的可信度。,22/47,兰州交通大学电子与信息工程学院,2020/5/16,RSA签名方案的密钥生成,实体A执行如下操作：随即产生大小相近的两个不同大素数p和q计算n=pq，其欧拉函数值(n)=(p1)(q1)随机选一整数e，1e(n)，满足gcd(n),e)=1利用扩展的欧几里德算法，计算惟一的整数d，1d(n),满足de1mod(n)公钥为(n，e)；私钥为d。(p,q不再需要，可以销毁。),23/47,兰州交通大学电子与信息工程学院,2020/5/16,RSA的签名生成与验证,实体A执行如下操作：,为验证A的签名s且恢复消息m，B执行如下操作：,24/47,兰州交通大学电子与信息工程学院,2020/5/16,RSA签名实例讲解,1）若Bob选择了p=11和q132）那么，n=1113=143,(n)=10121203）再选取一个与(n)=120互质的数,例如e=74）找到一个值d=103满足ed1mod(n)（7103=721，除以120余1）5）（n=143,e=7）为公钥，d=103为私钥。6）Bob在一个目录中公开公钥：n=143和e=77）现假设Bob想发送消息85给Alice，他用自己的密钥（d=103）进行签名：85103(mod143)=6，于是发送消息85和签名6给Alice8）当Alice接收到消息85和签名6时，用Bob公开的公钥（e7）进行验证：67（mod143)=85，跟Bob发送的消息一致，于是确定该消息是由Bob所发送，且没有被修改。,25/47,兰州交通大学电子与信息工程学院,2020/5/16,RSA签名和RSA加密的异同点,相同点,都使用一对密钥：公钥(n，e)和私钥d,不同点,RSA加密：用公钥加密，用私钥解密，多人加密，一人解密s=memodnm=sdmodnRSA签名：用私钥签名，用公钥验证，一人签名，多人验证s=mdmodnm=semodn,26/47,兰州交通大学电子与信息工程学院,2020/5/16,有关RSA签名的可能攻击,整数因子分解(公钥为(n，e)de1mod(n)分解n=pq再计算出(n)=(p1)(q1)由(n)和e，推导出私钥dRSA的乘性质s1=m1dmodns2=m2dmodn(s1s2)=(m1m2)dmodn要求冗余函数R具有非乘性，即R(ab)R(a)R(b)(必要条件）,为了防止此攻击，签署者必须选择p和q，使得分解n是一个计算上不可行的任务。,为了防止此攻击，要求冗余函数R的非乘性。,27/47,兰州交通大学电子与信息工程学院,2020/5/16,实际中的RSA签名,通常是：实体A将消息先签名再加密，然后发给B假设(nA,eA)和(nB,eB)分别是A和B的公钥有以下问题：1.重分组问题2.冗余函数的选择3.参数的选取4.带宽效率5.系统范围参数6.消息长短的比较,28/47,兰州交通大学电子与信息工程学院,2020/5/16,使用RSA签名的建议,(1)参数的选取：p,q,e,d。(2)不可使用公共模数。(3)明文的熵要尽可能的大。(4)尽量使用散列函数。(5)若RSA的模数n=2kbits，则：若消息的长度kbits，采用带消息恢复的RSA签名否则，采用带附录的RSA签名,29/47,兰州交通大学电子与信息工程学院,2020/5/16,Rabin公钥签名方案,Rabin公钥签名方案与RSA方案类似，不过它使用的公开指数e是偶数。为简单起见，假定e=2.待签名空间Ms是Qn(模n的二次剩余集)，并且签名是Qn中元素的平方根。,用到的知识：1.模n的二次剩余集2.模n的平方根3.剩余类的集合4.合数5.勒让德符号6.雅可比符号,RSA签名方案中p和q是不同的素数，从而(n)=(p1)(q1)是偶数。而e必须满足gcd(e,)=1，所以e是奇数。,30/47,兰州交通大学电子与信息工程学院,2020/5/16,Rabin公钥签名方案的密钥生成,概要：每个实体生成各自的公钥和相应私钥。,1.随机产生两个不同的大素数p和q,实体A执行如下操作：,2.计算n=pq,3.A的公钥是n，私钥是(p，q),31/47,兰州交通大学电子与信息工程学院,2020/5/16,Rabin方案的签名生成和验证,概要：实体A签署消息m，任何实体B都可以验证A的签名，并从中恢复消息m。,实体A执行如下操作：,为验证A的签名s且恢复消息m，B执行如下操作：,32/47,兰州交通大学电子与信息工程学院,2020/5/16,签名验证：B计算。既然，那么B接受签名并恢复出消息,密钥生成：实体A选择素数p=7,q=11,计算n=77.则A的公钥是n=77,私钥是(p=7,q=11)。待签空间(模n的二次剩余集)MS=Qn=1,4,9,15,16,23,25,36,37,53,58,60,64,67,71。为简单起见，取M=MS，并且设冗余函数R是恒等映射(即),签名生成：消息m=23，A计算，然后找出模77的一个平方根。在此，s=10,32,45,67。选取m的签名为s=45。,Rabin公钥签名方案举例,33/47,兰州交通大学电子与信息工程学院,2020/5/16,Rabin公钥签名方案注意问题,1)选择合适的冗余函数R对Rabin签名方案的安全性极为重要。2)对Rabin方案而言，设消息m是比特串，则R可以将它赋值为二元表示是该消息的整数。然而，却不能保证那个整数是模n的二次剩余，这可能导致无法计算平方根。所以人们试图尝试用确定性方法。,为了克服第二种问题，下面给出基本Rabin签名方案的一种修改版本。此处用到的技术类似于ISO/IEC9796标准，它提供一种确定性方法将消息和待签空间的元素相关联，从而可计算平方根。,34/47,兰州交通大学电子与信息工程学院,2020/5/16,修改的Rabin公钥签名方案,修改的Rabin签名方案的待签消息取自：,下表列出了此方案中的集合和一些函数定义记号：,35/47,兰州交通大学电子与信息工程学院,2020/5/16,修改的Rabin公钥签名方案的密钥生成,概要：每个实体生成各自的公钥和相应的私钥。实体A执行如下操作：,1.随机选择素数p3(mod8)，q7(mod8)，并计算n=pq，2.A的公钥是n，私钥是d=(n-p-q+5)/8,36/47,兰州交通大学电子与信息工程学院,2020/5/16,1.签名生成。实体A执行以下操作：(1)计算(2)计算雅可比符号(3)若J=1，则计算(4)若J=-1，则计算(5)A对m的签名是s,修改的Rabin方案的签名生成与验证(1),37/47,兰州交通大学电子与信息工程学院,2020/5/16,2.签名验证。实体B执行以下操作：(1)获得A的可信公钥n(2)计算（注意不需要初始消息m）(3)(4)(5)(6)(7)验证；否则拒绝(8),修改的Rabin方案的签名生成与验证(2),38/47,兰州交通大学电子与信息工程学院,2020/5/16,修改的Rabin公钥签名方案举例,密钥生成：A选择p=19，q=31，并计算n=pq=589和d=(n-p-q+5)/8=68。则A的公钥是n=589，私钥是d=68.下表列出了待签名空间MS的每个元素及其雅可比符号。,39/47,兰州交通大学电子与信息工程学院,2020/5/16,修改的Rabin公钥签名方案举例(续),签名生成：,签名验证：,40/47,兰州交通大学电子与信息工程学院,2020/5/16,ISO/IEC9796规范,是数字签名的第一个国际标准，1991公布。它规定了一套数字签名程序，并采用一种带消息恢复的数字签名机制主要特点：基于公钥密码学未指定特定签名算法，但必须是kbits映射为kbits用于签署有限长度的消息提供消息恢复描述了必需的消息填充RSA、Rabin算法,41/47,兰州交通大学电子与信息工程学院,2020/5/16,PKCS#1规范,公钥密码技术标准(PKCS)是包含RSA加密和签名的技术的一套规范PKCS#1不采用RSA签名方案的消息恢复特性采用带附录的签名机制使用Hash函数(MD2或MD5),42/47,兰州交通大学电子与信息工程学院,2020/5/16,11.4Fiat-Shamir签名方案,是由Fiege-Fiat-Shamir身份识别方案转变而来的安全性基于计算模n平方根的困难性签名生成的计算量远远小于RSA签名适合于需快速执行签名生成、且不限制密钥空间存储量的应用实体A对消息签名后，再由实体B来验证签名的有效性。具体包含：密钥生成签名生成和验证,43/47,兰州交通大学电子与信息工程学院,2020/5/16,Feige-Fiat-Shamir签名方案的密钥生成,随机产生不同的私密素数p和q(保密，最好用完丢弃)，计算n=pq，并公开n。选择正整数k及k个与n互素、且互不相同的