数字签名(1)ppt课件

数字签名,潘玉婷,1,1.什么是数字签名,2,数字签名,只有信息的发送者才能产生的别人无法伪造的一段数字串，这段数字串同时也是对信息的发送者发送信息真实性的一个有效证明。一种类似写在纸上的普通的物理签名，但是使用了公钥加密领域的技术实现，用于鉴别数字信息的方法。一套数字签名通常定义两种互补的运算，一个用于签名，另一个用于验证。,3,功能,保证信息传输的完整性、发送者的身份认证、防止交易中的抵赖发生。,4,原理：将摘要信息用发送者的私钥加密，与原文一起传送给接收者。接收者只有用发送者的公钥才能解密被加密的摘要信息，然后用HASH函数对收到的原文产生一个摘要信息，与解密的摘要信息对比。相同-信息是完整的，在传输过程中没有被修改不相同-信息被修改过因此，数字签名能够验证信息的完整性。,5,数字签名是加密的过程数字签名验证是解密的过程。,6,网上扒的小例子,7,susan使用公钥加密文件，只有Bob的私钥能解密，其他人的公钥不行。,8,文件，使用Bob的软件和哈希函数，提取出摘要,用秘钥加密摘要,9,这就是数字签名，然后将签名和文件一起发送给Pat,10,Pat使用他的软件和哈希函数从文件提取摘要，使用公钥解密签名，对比两份摘要是否一致,11,如果有人想冒充Bob给别人发送公钥办？,12,Susan是验证中心的，专门打假，在需要时可以改变秘钥和公钥,13,2.RSA数字签名,14,相关知识：,素数，1和它本身若整数a和b最大公约数为1，则称a，b互素，记为（gcd（a，b）=1）设n为正整数，a和b为整数，若a和b被n除后所得余数相同，称a和b模n同余，记为ab（modn）。此式被称为同余式。存在整数s使得a=sn+b。,15,同余式的一些运算性质,若ab（modn），cd（modn）则有acbd（modn）。特别的有，kakb（modn），k为任意整数。若ab（modn），d是a，b，n的公因数，则(a/d)(b/d)（modn/d）。特别的有anbn（modn），n为正整数。若kakb（modn），且k与n互素时，有ab（modn）。（同余式消去律）,16,设n为正整数,则任何一个整数被n除,余数必为0,1,2,n-1中的某一个,把整数集中被n除余数相同的数分别归为一类,记为0,1,2,n-1,这样就按模是否同余把整数集分成n类,其中每一类都称为模n的一个剩余类。显然,每个整数必属于上述类中的一类,被n除余数不同的数必属于上述的不同类中。若a0,a1,a3,an-1分别取自上述类的不同类中,称a0,a1,a3,an-1为模n的一个完全剩余系,该剩余系中的数两两模n不同余。,17,费马小定理：,设任意整数a和素数p互素，则a(p-1)1（modp）。,18,构造剩余系法证明-费马小定理,设a与p互素，a，2a，a（p-1）构成p的一组非零剩余系，而1,2,3，（p-1）是p的一组非零剩余系，所以有a*2a*3a*，*a(p-1)=1*2*3*，*（p-1）(modp)化简得a(p-1)*(p-1)!=(p-1)!(modp)两边同除以（p-1）!，即得a(p-1)1(modp)即：apa(modp)而当p|a时，费马小定理显然成立,19,RSA定理,设p，q是不同的素数，n=pq记(n)=(p-1)(q-1),如果e，d是与(n)互素的两个正整数（e,d(n),并满足ed1(mod(n),则对于每个整数x,都有xedx(modn)。,20,证明,为证xedx(modn)，只需证(n)是xed-x的因数。又n=pq，而p，q都是素数，故证明p和q都是xed-x的因数即可，即xedx(modp)（1）xedx(modq)（2）,21,证明xedx(modp),若p不是x的因数，则由ed1(mod(n)得ed-1=k(p-1)(q-1),k为任意整数。则xed=x(k(p-1)(q-1)+1=x*（xp-1）k(q-1)根据费马小定理因为x与p互素，所以x(p-1)1（modp）所以xedx*（1）(k(q-1)x（modp）同理可证xedx(modq),22,RSA加密算法,(1)取两个大素数p,q(保密)；(2)计算n=p*q(公开),(n)=(p-1)*(q-1)(保密)；(3)随机选取整数e，满足gcd(e,(n)=1（e与(n)互素）(公开)；(4)计算d满足d*e1(mod(n)(保密)；(5)e，n为公钥，d，n为私钥，也可以用e，d表示密钥对(6)加密时c=xemodn；解密时x=cdmodn(7)签名时c=xdmodn；解密时x=cemodn,23,问题：为什么xedx(modn)就能保证(6)和(7)正确？,分析：解xedx(modn)同余式方程，该方程可能有n个解，这n个解都在模n的同一个剩余类中，小于n的解只有一个，由于明文小于n，则该解即是明文x。而xedmodn得到的就是小于n的那个解。另外，注意密文c并不等于xe而是cxe（modn）。这里有上一段中我们知道要想求出明文x，解同余式方程xedx(modn)可得，这时只要等式左边的数与X同余就能得到正确的明文。由于cxe（modn），所以可得cdxed（modn）,所以cdxe（modn）。,24,3.ELGamal数字签名和DSA,25,ELGamal数字签名,1985年，ELGamal基于离散对数难题提出一种数字签名方案，称为ELGamal数字签名方案。那么，什么是离散对数问题？,26,离散对数问题,设p是一个素数，g是模p的本原元，每一个y值都是g的一个幂，求ygx(modp)称为模p的幂运算，反过来，若求ygx(modp)成立，已知y求x的问题称为模p的离散对数问题.将已知y求x的离散对数定义为寻求符合条件1=x=p-1的x.如果g不是p的本原元，那么就不会为y值定义离散对数。,27,相关知识,欧拉函数：对于正数n,少于或等于n的数中与n互质的数的个数例如p=7则(p)=6本原元：设本原元为a,则ad1(modp)成立,其中d=(p)(p)是欧拉函数即：a(p)1(modp)a=2时,a81(mod7),但是3不是(7),所以a不是本原元a=3时,a61(mod7),此时3就是本原元一个域的本原元非唯一,28,1）密码选择,选p是一个大素数，p-1有大素数因子，a是一个模p的本原元，将p和a公开；用户随机地选择一个整数x作为自己的秘钥，1=x(s1-s2)k(m1-m2)(modp-1)如果知道m1和m2，就可以求出k，进而求出秘钥!,32,是Schnorr和ElGamal签名算法的变种，美国国家标准技术研究所(NIST)1994年5月19日公布了数字签名标准的(DSS),标准采用的算法便是DSA，密钥长度为5121024位。密钥长度愈长，签名速度愈慢，制约运算速度的只要因素是大数的模指数运算。,DSA,是基于整数有限域离散对数难题的，其安全性与RSA相比差不多。DSA的一个重要特点是两个素数公开，这样，当使用别人的p和q时，即使不知道私钥，你也能确认它们是否是随机产生的，还是作了手脚。RSA算法却做不到。,33,算法中应用了下述参数：,p：Lbits长的素数。L是64的倍数，范围是512到1024；q：p-1的160bits的素因子；g：g=h(p-1)/q)modp，h满足h1；x：xq，x为私钥；y：y=gxmodp，(p,q,g,y)为公钥；H(x)：Hash函数。p,q,g可由一组用户共享，但在实际应用中，使用公共模数可能会带来一定的威胁。,34,签名及验证协议如下：,1.P产生随机数k，kq；2.P计算r=(gkmodp)modqs=(k(-1)(H(m)+xr)modq签名结果是(m,r,s)。3.验证时计算w=s(-1)modqu1=(H(m)*w)modqu2=(r*w)modqv=(gu1*yu2)modp)modq若v=r，则认为签名有效。,35,推导,已知，gcd（h，p）=1，费马定理：h(p-1)1(modp)对任意整数n：g(nq)modp=(h(p-1)/q)modp)nqmodp=h(n*(p-1)modp=(h(p-1)modp)nmodp=1nmodp=1,36,证明前的必要推导,已知，gcd（h，p）=1，费马定理：h(p-1)1(modp)，对任意整数n：g(nq)modp=1对任意整数t，t=nq+z，其中n，q是非负整数，0t1=296.85t2=58.15=v=t1v1+t2v2=(53159,81818)检查：|v-w|=76.12效果不错，比较接近w,44,马哈达比例Hadamardratio,我们把接近于1的基称为好基，接近于0的基称为坏基。哈达马系数的范围是(0,1)的。例如，上题中，,45,GGH数字签名过程,公钥生成选择一个好基v1,vn和一个坏基w1,wn，公布坏基作为公钥签名选择文件d签名，使用Babai算法和一个好基v1,vn计算得到一个向量s，该向量接近于文件d，然后用坏基写出签名s=a1w1+,+anwn，将签名a1,an公布验证用公钥w1,wn和签名a1,an计算得出的结果s=a1w1+,+anwn是否接近于文件,46,使用过程,文件d=(678846,651685,160467)，使用Babai算法和一个好基找到一个向量s=2213*v1+7082*v2-6231*v3=(678835,651671,160437)，接近于d,|s-d|=34.89然后依照坏基，s=1531010*w1-553385*w2-878505*w3签名为（1531010，-553385，-878505），公布验证：s=1531010w1-553385w2-878505w3=|s-d|=34.89,47,5.NTRU数字签名,48,NTRU数字签名,一个基于多项式环的密码体制具有生成速度快，占用资源少，密钥产生容易等优点它的安全性依赖于格中最短向量问题,49,1）创建公共参数(N，q，d)2）创建钥匙选择三元多项式f，gT(d+1，d)计算小向量F和G，满足f*Gg*F=q（具体计算在后面）计算hf(1)*g(modq)公布验证钥匙h,过程,50,签名选择小文件D=(D1，D2)modq计算v1=(D1*GD2*F)/q，v2=(D1*g+D2*f)/q计算s=v1*f+v2*F公布签名(D，s)4）验证计算th*s(modq)验证（s，t）接近D,51,找到多项式f1(x)，f2(x)，g1(x)，g2(x)Zx和正整数Rf，Rg满足f1(x)f(x)+f2(x)(xN1)=Rf，g1(x)g(x)+