《数字签名技术》PPT课件.ppt

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