《数字签名(1)课件.ppt》由会员分享，可在线阅读，更多相关《数字签名(1)课件.ppt（54页珍藏版）》请在三一办公上搜索。
1、数字签名,潘玉婷,1,1.什么是数字签名,2,数字签名,只有信息的发送者才能产生的别人无法伪造的一段数字串，这段数字串同时也是对信息的发送者发送信息真实性的一个有效证明。一种类似写在纸上的普通的物理签名，但是使用了公钥加密领域的技术实现，用于鉴别数字信息的方法。一套数字签名通常定义两种互补的运算，一个用于签名，另一个用于验证。,3,功能,保证信息传输的完整性、发送者的身份认证、防止交易中的抵赖发生。,4,原理：将摘要信息用发送者的私钥加密，与原文一起传送给接收者。接收者只有用发送者的公钥才能解密被加密的摘要信息，然后用HASH函数对收到的原文产生一个摘要信息，与解密的摘要信息对比。相同-信息是
2、完整的，在传输过程中没有被修改 不相同-信息被修改过 因此，数字签名能够验证信息的完整性。,5,数字签名是加密的过程数字签名验证是解密的过程。,6,网上扒的小例子,7,susan使用公钥加密文件，只有Bob的私钥能解密，其他人的公钥不行。,8,文件，使用Bob的软件和哈希函数，提取出摘要,用秘钥加密摘要,9,这就是数字签名，然后将签名和文件一起发送给Pat,10,Pat使用他的软件和哈希函数从文件提取摘要，使用公钥解密签名，对比两份摘要是否一致,11,如果有人想冒充Bob给别人发送公钥办？,12,Susan是验证中心的，专门打假，在需要时可以改变秘钥和公钥,13,2.RSA数字签名,14,相关
3、知识：,素数，1和它本身若整数a和b最大公约数为1，则称a，b互素，记为（gcd（a，b）=1）设n为正整数，a和b为整数，若a和b被n除后所得余数相同，称a和b模n同余，记为ab（mod n）。此式被称为同余式。存在整数s使得a=sn+b。,15,同余式的一些运算性质,若ab（mod n），cd（mod n）则有acbd（mod n）。特别的有，kakb（mod n），k为任意整数。若ab（mod n），d是a，b，n的公因数，则(a/d)(b/d)（mod n/d）。特别的有anbn（mod n），n为正整数。若kakb（mod n），且k与n互素时，有ab（mod n）。（同余式消去律）
4、,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（mod p）。,18,构造剩余系法证明-费马小定理,设a与p互素，a，2a，a（p-1）构成p的一组非零
5、剩余系，而1,2,3，（p-1）是p的一组非零剩余系，所以有 a*2a*3a*，*a(p-1)=1*2*3*，*（p-1）(mod p)化简得 a(p-1)*(p-1)!=(p-1)!(mod p)两边同除以（p-1）!，即得 a(p-1)1(mod p)即：apa(mod p)而当p|a时，费马小定理显然成立,19,RSA定理,设p，q是不同的素数，n=pq记(n)=(p-1)(q-1),如果e，d是与(n)互素的两个正整数（e,d(n),并满足ed1(mod(n),则对于每个整数x,都有xedx(mod n)。,20,证明,为证xedx(mod n)，只需证(n)是xed-x的因数。又n=
6、pq，而p，q都是素数，故证明p和q都是xed-x的因数即可，即xedx(mod p)（1）xedx(mod q)（2）,21,证明xedx(mod p),若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（mod p）所以xedx*（1）(k(q-1)x（mod p）同理可证xedx(mod q),22,RSA加密算法,(1)取两个大素数p,q(保密)；(2)计算 n=p*q(公开),(n)=(p-1)*(q-1)(保密)；(3)随机
7、选取整数e，满足 gcd(e,(n)=1（e与(n)互素）(公开)；(4)计算 d 满足 d*e1(mod(n)(保密)；(5)e，n为公钥，d，n为私钥，也可以用e，d表示密钥对(6)加密时c=xe mod n；解密时 x=cd mod n(7)签名时c=xd mod n；解密时 x=ce mod n,23,问题：为什么xedx(mod n)就能保证(6)和(7)正确？,分析：解xedx(mod n)同余式方程，该方程可能有n个解，这n个解都在模n的同一个剩余类中，小于n的解只有一个，由于明文小于n，则该解即是明文x。而xed mod n得到的就是小于n的那个解。另外，注意密文c并不等于xe
8、而是cxe（mod n）。这里有上一段中我们知道要想求出明文x，解同余式方程xedx(mod n)可得，这时只要等式左边的数与X同余就能得到正确的明文。由于cxe（mod n），所以可得cdxed（mod n）,所以cdxe（mod n）。,24,3.ELGamal数字签名和DSA,25,ELGamal数字签名,1985年，ELGamal基于离散对数难题提出一种数字签名方案，称为ELGamal数字签名方案。那么，什么是离散对数问题？,26,离散对数问题,设p是一个素数，g是模p的本原元，每一个y值都是g的一个幂，求ygx(mod p)称为 模p的幂运算，反过来，若求ygx(mod p)成立，已
9、知y求x的问题称为 模p的离散对数问题.将已知y求x的离散对数定义为寻求符合条件 1=x=p-1的 x.如果g不是p的本原元，那么就不会为y值定义离散对数。,27,相关知识,欧拉函数：对于正数n,少于或等于n的数中与n互质的数的个数 例如p=7 则(p)=6本原元：设本原元为a,则ad1(mod p)成立,其中d=(p)(p)是欧拉函数 即：a(p)1(mod p)a=2时,a81(mod 7),但是3不是(7),所以 a不是本原元a=3时,a61(mod 7),此时 3就是本原元一个域的本原元非唯一,28,1）密码选择,选p是一个大素数，p-1有大素数因子，a是一个模p的本原元，将p和a公开
10、；用户随机地选择一个整数x作为自己的秘钥，1=x=p-2计算yax(mod p)，取y为公钥,29,2）产生签名,设明文消息m，0形式发给用户B,30,3）验证签名,用户接受，用A的公钥y验证：amyr*rs(mod p)是否成立，若成立则为真，反之相反。签名的可验证性证明如下：因为 s(m-xr)/k(mod p-1)所以mxr+ks(mod p-1)故 ama(xr+ks)(axr)*(aks)yr*rs(mod p)故签名可验证,31,安全性,为了安全，随机数k应是一次性的，否则时间一长，k可能泄露，因为x(m-ks)/r(mod p-1)如果k重复使用，则m1xr+ks1(mod p-
11、1)m1xr+ks1(mod p-1)=(s1-s2)k(m1-m2)(mod p-1)如果知道m1和m2，就可以求出k，进而求出秘钥!,32,是Schnorr和ElGamal签名算法的变种，美国国家标准技术研究所(NIST)1994年5月19日公布了数字签名标准的(DSS),标准采用的算法便是DSA，密钥长度为5121024位。密钥长度愈长，签名速度愈慢，制约运算速度的只要因素是大数的模指数运算。,DSA,是基于整数有限域离散对数难题的，其安全性与RSA相比差不多。DSA的一个重要特点是两个素数公开，这样，当使用别人的p和q时，即使不知道私钥，你也能确认它们是否是随机产生的，还是作了手脚。R
12、SA算法却做不到。,33,算法中应用了下述参数：,p：L bits长的素数。L是64的倍数，范围是512到1024；q：p-1的160bits的素因子；g：g=h(p-1)/q)mod p，h满足h 1；x：x q，x为私钥；y：y=gx mod p，(p,q,g,y)为公钥；H(x)：Hash函数。p,q,g可由一组用户共享，但在实际应用中，使用公共模数可能会带来一定的威胁。,34,签名及验证协议如下：,1.P产生随机数k，k q；2.P计算 r=(gk mod p)mod q s=(k(-1)(H(m)+xr)mod q 签名结果是(m,r,s)。3.验证时计算 w=s(-1)mod q
13、u1=(H(m)*w)mod q u2=(r*w)mod q v=(gu1*yu2)mod p)mod q 若v=r，则认为签名有效。,35,推导,已知，gcd（h，p）=1，费马定理：h(p-1)1(mod p)对任意整数n：g(nq)mod p=(h(p-1)/q)mod p)nq mod p=h(n*(p-1)mod p=(h(p-1)mod p)n mod p=1n mod p=1,36,证明前的必要推导,已知，gcd（h，p）=1，费马定理：h(p-1)1(mod p)，对任意整数n：g(nq)mod p=1对任意整数t，t=nq+z，其中n，q是非负整数，0zqgt mod p=g
14、(nq+z)mod p=(gnq mod p)(gz mod p)=gz mod p=g(t mod q)mod p 即：g(t mod q)mod p=gt mod p,37,证明,因为：r=(gk mod p)mod q;s=(h(m)+xr)k(-1)mod q;w=s(-1)mod qu1=(h(m)*w)mod qu2=(r*w)mod qv=(gu1*yu2)mod p)mod q,38,证明,所以：v=(gu1*yu2)mod p)mod q=(g(h(m)*w)*y(r*w)mod p)mod q=(g(h(m)*w)*g(x*r*w)mod p)mod q=(g(h(m)+x
15、*r)*w)mod p)mod q=(g(s*k*w)mod p)mod q=(gk mod p)mod q=r 所以，最后验证的时候只要v=r的时候，即可认为通过验证,39,4.GGH基于格的数字签名,40,格的定义,线性独立空间上有集合，格就是这些向量的线性组合用公式表示如下：格L的维数等于格中向量的个数。,41,假定,是格中格L的基，则有必然存在 整系数使得：这样的话，格中的问题就是矩阵运算了。,42,最接近向量问题（CVP）：对于一个非格L中的向量w，在格中寻找一个向量v，使得|w-v|最小。,43,Babai最接近向量算法（第六章内容）,格L，维数n=2，向量v1=(137,312)
16、,v2=(215,-187)是格的基，寻找L中的一个向量V满足|w-v|最小。其中，w=(53172,81743).解：要寻找一个最接近向量，即w=t1v1+t2v2=53172=137t1+215t2 81743=312t1-187t2=t1=296.85 t2=58.15=v=t1v1+t2v2=(53159,81818)检查：|v-w|=76.12 效果不错，比较接近w,44,马哈达比例 Hadamard ratio,我们把接近于1的基称为好基，接近于0的基称为坏基。哈达马系数的范围是(0,1)的。例如，上题中，,45,GGH数字签名过程,公钥生成 选择一个好基v1,vn和一个坏基w1,
17、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
18、签名为（1531010，-553385，-878505），公布验证：s=1531010w1-553385w2-878505w3=|s-d|=34.89,47,5.NTRU数字签名,48,NTRU数字签名,一个基于多项式环的密码体制具有生成速度快，占用资源少，密钥产生容易等优点它的安全性依赖于格中最短向量问题,49,1）创建公共参数(N，q，d)2）创建钥匙 选择三元多项式 f，g T(d+1，d)计算小向量 F 和 G，满足 f*Gg*F=q（具体计算在后面）计算 h f(1)*g(mod q)公布验证钥匙 h,过程,50,签名 选择小文件 D=(D1，D2)mod q 计算 v1=(D1*G
19、D2*F)/q，v2=(D1*g+D2*f)/q 计算 s=v1*f+v2*F 公布签名(D，s)4）验证 计算 t h*s(mod q)验证（s，t）接近 D,51,找到多项式 f1(x)，f2(x)，g1(x)，g2(x)Zx 和正整数 Rf，Rg满足 f1(x)f(x)+f2(x)(xN 1)=Rf，g1(x)g(x)+g2(x)(xN 1)=Rg设 gcd(Rf，Rg)=1找到整数 Sf 和 Sg，满足 SfRf+SgRg=1 让 A(x)=q Sf f1(x)，B(x)=q Sg g1(x).注意 A(x)*f(x)B(x)*g(x)=q，在 Zx/(xN 1),求解 F 和 G,52,计算 倒数 f(x)(1)和 g(x)(1)，在Rx/(xN 1)计算 C(x)=1/2 B(x)*f(x)(1)+A(x)*g(x)(1)*6=F(x)=B(x)C(x)*f(x)和 G(x)=A(x)C(x)*g(x),53,54,
