现代密码学-第6章数字签名

《现代密码学-第6章数字签名》由会员分享，可在线阅读，更多相关《现代密码学-第6章数字签名（81页珍藏版）》请在金锄头文库上搜索。

1、1,第5章 Hash函数与数字签名,2,第5章 Hash函数与数字签名,5.6 数字签名概念 5.7 RSA数字签名体制 5.8 ElGamal数字签名体制 5.9 其它数字签名方案 5.10 数字签名标准 5.11 应用,3,5.6 数字签名概念,在政治、军事、外交、商业和日常生活中，人们经常需要对纸质材料进行签名。 签名起到确认、核准、生效和负责任等多种作用。 随着计算机网络技术的发展，电子商务、电子政务和电子金融等系统得到广泛应用，人们需要通过网络信息传输对电子的文件、契约、合同、信件和张单等进行数字签名以替代手写签名。,4,5.6 数字签名概念,签名是证明当事人的身份和数据真实性的一种

2、信息。 在传统的以书面文件为基础的事物处理中，采用书面签名的形式，如手签、手印和印章等。书面签名得到司法部门的支持，具有一定的法律意义,5,5.6 数字签名概念,在以计算机文件为基础的现代事物处理中，应采用电子形式的签名，即数字签名（digital signature）。 数字签名的目的是提供一种手段，使得一个实体把他的身份与某个信息捆绑在一起。 一个信息的数字签名实际上是一个数，它仅仅依赖于签名者的密钥和被签名的消息。,6,5.6.1 数字签名的基本概念,（1）消息空间:由所有任意长度消息组成的集合,（2）签名空间: 由所有签名组成的集合。签名长度不超过n。,（3）密钥空间:,一个数字签名体

3、制是一个满足以下条件的五元组:,7,5.6.1 数字签名的基本概念,（6）,8,5.6.1 数字签名的基本概念,数字签名基本要求 对每一个密钥K, sigK和verK应该是多项式时间函数 verK是公开的函数, 而sigK是保密的 给定一个消息x, 除了发送者本人以外, 任何其他人找到满足verK(x,y)为真的数字签名y,应该是计算上不可行的 如果攻击者能够找到满足verK(x,y)的数据对(x,y),而发送者事先又没有对x签名,则称y是伪造(forgery)的数字签名。,数字签名算法必须满足的条件 签名者事后不能否认自己的签名； 其他人不能伪造签名； 当通信双方为签名真伪发生争执时, 可以

4、由第三方解决争端,9,5.6.1 数字签名的基本概念,手写签名与数字签名的区别 手写签名是所签文件的物理组成部分，数字签名必须与所签文件捆绑在一起。 手写签名通过与标准签名进行比较或检查笔迹来验证，数字签名是通过验证算法来验证。手写签名容易伪造，好的数字签名算法应该使伪造签名十分困难。 手写签名不易复制。数字签名是一个二进制串，容易复制。所以必须防止数字签名重复使用。,10,5.6.1 数字签名的基本概念,签名算法进行分类 按应用目的 普通数字签名 特殊目的数字签名: 不可否认数字签名、盲签名、群签名等 按验证方法 在验证时需要输入被签名信息 在验证时自动恢复被签名信息 按签名时是否使用随机数

5、 分成确定性数字签名 随机数字签名,11,5.6.2 数字签名的基本构造方法,利用Hash函数和加密算法可以构造有效的数字签名方案。 基于Hash函数和单钥密码算法构造数字签名,12,5.6.2 数字签名的基本构造方法,基于Hash函数和双钥密码算法构造数字签名,13,5.6.2 数字签名的基本构造方法,具有保密作用的数字签名 双钥密码体制：SK是发送方的私钥，PK是发送方的公钥， E1和D1分别是加密算法与解密算法。 单钥密码体制密钥：K是双方公用密钥，E2和D2分别是对应的加密算法和解密算法。,14,5.6.3 数字签名的安全需求,数字签名的攻击模型 唯密钥攻击（keyonly attac

6、k）攻击者E拥有签名者A的公钥K，因而能够计算验证函数verK。 已知消息攻击（known message attack）攻击者E拥有一系列以前由签名者A所签名的消息。即E具有数据对（xi，yi），其中xi是消息，yi=sigK (xi)是A对xi的签名（i=1, 2, ）。 选择消息攻击（chosen message attack）攻击者E可以选择一些消息请求签名者A签名。即E选择消息xi，并将xi发送给签名者A，请求A对xi签名。A计算yi=sigK(xi)，并将yi发给E。所以，E具有A的有效数字签名（xi，yi）（i=1, 2, ）。,15,5.6.3 数字签名的安全需求,攻击者对数字

7、签名系统的攻击目的 完全破译（total break）攻击者E能确定签名者A的私钥K，因而能够计算签名函数sigK，可以对任何消息产生有效的签名。 选择性伪造（selective forgery）攻击者E能以某一个不可忽略的概率对另外某个人选定的消息产生一个有效的签名。也就是说，如果给E选定一个消息x，那么他能以一个正的概率找到x的签名y=sigK(x)，并且签名者A以前未对x签名。 存在性伪造（existential forgery）攻击者E至少能够为一个消息产生一个有效的签名。也就是说，E可能生成一个数据对（x，y），其中x是消息，y=sigK(x)。签名者A以前未对x签名。,16,5.6

8、.3 数字签名的安全需求,Hash函数与数字签名的安全性 对消息的散列值签名,17,5.6.3 数字签名的安全需求,使用已知消息攻击的存在性伪造攻击者E从一个有效的签名(x, y)开始,其中y=sigK(h(x).然后他计算z=h(x),并企图找到xx,使得h(x)=h(x).如果E能做到这一点,则(x, y)就是一个有效的签名, 从而y是消息x的一个伪造签名.为了阻止这种攻击, 必须要求Hash函数h是弱无碰撞的. 使用选择消息攻击的存在性伪造攻击者E首先找到xx, 使得h(x)=h(x). 然后将消息x发给签名者A, 并让A对消息的散列值h(x)签名, 从而得到y=sigK(h(x). 所

9、以E能够成功伪造签名(x, y). 为了阻止这种攻击,必须要求Hash函数h是强无碰撞的.,18,5.6.3 数字签名的安全需求,使用唯密钥攻击的存在性伪造当签名算法遭到唯密钥攻击时, 即攻击者E拥有签名者A的公钥K.E就可能对一个随机的散列值z伪造签名y=sigK(z). 此时, 如果Hash函数h不是单向的,则E可能找到一个消息x，使得z=h(x).所以E能够成功伪造一个签名(x, y).为了阻止这种攻击, 必须要求Hash函数h是单向的.,19,第5章 Hash函数与数字签名,5.6 数字签名概念 5.7 RSA数字签名体制 5.8 ElGamal数字签名体制 5.9 其它数字签名方案

10、5.10 数字签名标准 5.11 应用,20,5.7 RSA数字签名体制,利用RSA加密算法构造的数字签名称为RAS数字签名体制。 5.7.1 RSA算法描述 1密钥生成算法 选取两个大素数p，q，计算n=pq，(n)=( p 1) ( q 1)。 任选整数e，满足：0 e (n)，且gcd(e ,(n)=1。 用扩展Euclidean算法求e模(n)的逆d，即ed=1 mod (n)。 签名者的公钥: n，e，私钥: p，q，d。,21,5.7.1 RSA算法描述,2签名算法设消息为x，则x的RAS签名是,22,5.7.2 RSA数字签名的安全性,1一般攻击 攻击方法: 设n与e为用户A的公

11、钥，攻击者首先随意选择一个数据y，并用A的公钥计算x=ye mod n，于是可以伪造A的一个RSA数字签名（x，y）。因为xd =(ye)d =yed =y mod n，所以用户A对x的RSA数字签名是y。 这种攻击实际上成功的概率是不高的因为对于选择的数据y，得到的x=ye mod n具有正确语义的概率是很低的。 抵抗措施 仔细设计数据格式 对数据的Hash值进行签名,23,5.7.2 RSA数字签名的安全性,2选择消息攻击 攻击方法: 假设攻击者E想伪造消息x的签名，他容易找到两个数据x1和x2，使得,攻击者E设法让用户A分别对x1和x2 进行签名，得到,然后E可以计算,于是攻击者E得到了

12、用户A对消息x的RSA数字签名y 抵抗措施 用户不要轻易地对其他人提供的随机数据进行签名 对数据的Hash值进行签名,24,5.7.2 RSA数字签名的安全性,3利用签名进行攻击从而获得明文 攻击方法假设攻击者E已截获了秘文c=xe mod n，他想求出明文x。于是，他选择一个小的随机数r，并计算,因为s=re,所以sd=( re)d= mod n，r=sd mod n.然后E 设法让签名者对l签名. 于是E又获得k=ld mod n. 攻击者E再计算：,于是，获得了秘文x。 抵抗措施 用户不要轻易地对其他人提供的随机数据进行签名 对数据的Hash值进行签名,25,5.7.2 RSA数字签名的

13、安全性,4对先加密后签名方案的攻击 攻击方法假设签名者A采用先加密后签名的方案把消息x发送给接收者B ,则他先用B的公开密钥eB对x加密, 然后用自己的私钥dA签名.设A的模数为nA,B的模数为nB.于是A发送给B的数据为:,如果B是不诚实的,那么B可能伪造A的签名.例如,假设B想抵赖收到A发的消息x, 慌称收到的是x1.因为nB是B的模数,所以B知道nB的分解,于是能够计算模nB的离散对数.即他能找到k满足:,然后，B再公布他的新公开密钥为keB。现在B宣布他收到的消息是x1，而不是x。由于下式成立，所以A无法争辩。,26,5.7.2 RSA数字签名的安全性,4对先加密后签名方案的攻击 抵抗

14、措施 签名者A应当在发送的数据中加入时间戳，从而可证明是用公开密钥eB对x加密，而不是用新公开密钥keB对x1加密。 对数据的Hash值进行签名。,综上所述，对于RSA数字签名系统，必须采取如下安全措施： 不直接对消息进行签名，而应该对消息的Hash值进行签名。 要采用先签名后加密的方式，而不要采用先加密后签名的方式。,27,第5章 Hash函数与数字签名,5.6 数字签名概念 5.7 RSA数字签名体制 5.8 ElGamal数字签名体制 5.9 其它数字签名方案 5.10 数字签名标准 5.11 应用,28,5.8 ElGamal数字签名体制,在1985年，ElGamal T. 提出了一个

15、基于离散对数问题的数字签名体制，通常称为ElGamal数字签名体制。 ElGamal签名体制的安全性主要是基于有限域上离散对数问题的难解性。,29,5.8.1 ElGamal签名算法描述,1参数生成算法 选取一个大素数p，gZp*是一个本原元，p和g是系统公开参数。 任选整数x，满足：1xp2。计算y=gx mod p. 签名者的公钥为y，私钥为x。,30,5.8.1 ElGamal签名算法描述,31,5.8.1 ElGamal签名算法描述,签名者A对M=5的ElGamal签名为（6, 3）。 接收者B可以对消息M=5的签名（6, 3）进行验证。因为,32,5.8.2 ElGamal数字签名的

16、安全性,ElGamal数字签名算法的实现 需要作一次模指数运算 一次扩展Euclidean算法运算（求随机数k的逆元） 二次模乘运算 前两个运算可以离线进行 是一个随机的数字签名体制 ElGamal数字签名体制的参数p p的选择与在Zp*中计算离散对数的算法有直接关系。从目前的计算水平来看，p至少应该是二进制512位的素数，从长期安全性考虑，应使用1024位或更长的素数。 p1最好有大的素因子 私钥x最好是Zp*的素数阶子群的生成元。,33,6.3.2 ElGamal数字签名的安全性,1不知道私钥的攻击 假设攻击者E不知道私钥x，要想伪造消息M的签名(r,s), 则E可能使用的攻击方式有： (1) 攻击者已知消息M,选择一个值r,再求另一个值s.此时,因为有所以攻击者E必须计算离散对数。,