数字签名潘玉婷1.什么是数字签名数字签名•只有信息的发送者才能产生的别人无法伪造的一段数字串,这段数字串同时也是对信息的发送者发送信息真实性的一个有效证明。•一种类似写在纸上的普通的物理签名,但是使用了公钥加密领域的技术实现,用于鉴别数字信息的方法。•一套数字签名通常定义两种互补的运算,一个用于签名,另一个用于验证。功能•保证信息传输的完整性、发送者的身份认证、防止交易中的抵赖发生。•原理:将摘要信息用发送者的私钥加密,与原文一起传送给接收者。接收者只有用发送者的公钥才能解密被加密的摘要信息,然后用HASH函数对收到的原文产生一个摘要信息,与解密的摘要信息对比。相同------信息是完整的,在传输过程中没有被修改不相同------信息被修改过因此,数字签名能够验证信息的完整性。数字签名是加密的过程数字签名验证是解密的过程。网上扒的小例子susan使用公钥加密文件,只有Bob的私钥能解密,其他人的公钥不行。文件,使用Bob的软件和哈希函数,提取出摘要用秘钥加密摘要这就是数字签名,然后将签名和文件一起发送给PatPat使用他的软件和哈希函数从文件提取摘要,使用公钥解密签名,对比两份摘要是否一致如果有人想冒充Bob给别人发送公钥办???Susan是验证中心的,专门打假,在需要时可以改变秘钥和公钥2.RSA数字签名相关知识:•素数,1和它本身•若整数a和b最大公约数为1,则称a,b互素,记为(gcd(a,b)=1)•设n为正整数,a和b为整数,若a和b被n除后所得余数相同,称a和b模n同余,记为a≡b(modn)。此式被称为同余式。•存在整数s使得a=sn+b。同余式的一些运算性质•若a≡b(modn),c≡d(modn)则有ac≡bd(modn)。特别的有,ka≡kb(modn),k为任意整数。•若a≡b(modn),d是a,b,n的公因数,则(a/d)≡(b/d)(modn/d)。特别的有a^n≡b^n(modn),n为正整数。•若ka≡kb(modn),且k与n互素时,有a≡b(modn)。(同余式消去律)•设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不同余。费马小定理:•设任意整数a和素数p互素,则a^(p-1)≡1(modp)。构造剩余系法证明----费马小定理•设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)即:a^p≡a(modp)而当p|a时,费马小定理显然成立RSA定理•设p,q是不同的素数,n=pq记φ(n)=(p-1)(q-1),如果e,d是与φ(n)互素的两个正整数(e,dφ(n)),并满足ed≡1(modφ(n)),则对于每个整数x,都有x^ed≡x(modn)。证明•为证x^ed≡x(modn),只需证φ(n)是x^ed-x的因数。又n=pq,而p,q都是素数,故证明p和q都是x^ed-x的因数即可,即x^ed≡x(modp)(1)x^ed≡x(modq)(2)证明x^ed≡x(modp)•若p不是x的因数,则由ed≡1(modφ(n))得ed-1=k(p-1)(q-1),k为任意整数。则x^ed=x^(k(p-1)(q-1))+1=x*(xp-1)k(q-1)•根据费马小定理因为x与p互素,所以x^(p-1)≡1(modp)•所以x^ed≡x*(1)^(k(q-1))≡x(modp)•同理可证x^ed≡x(modq)RSA加密算法(1)取两个大素数p,q(保密);(2)计算n=p*q(公开),φ(n)=(p-1)*(q-1)(保密);(3)随机选取整数e,满足gcd(e,φ(n))=1(e与φ(n)互素)(公开);(4)计算d满足d*e≡1(modφ(n))(保密);(5){e,n}为公钥,{d,n}为私钥,也可以用{e,d}表示密钥对(6)加密时c=x^emodn;解密时x=c^dmodn(7)签名时c=x^dmodn;解密时x=c^emodn问题:为什么x^ed≡x(modn)就能保证(6)和(7)正确?分析:解x^ed≡x(modn)同余式方程,该方程可能有n个解,这n个解都在模n的同一个剩余类中,小于n的解只有一个,由于明文小于n,则该解即是明文x。而x^edmodn得到的就是小于n的那个解。另外,注意密文c并不等于x^e而是c≡x^e(modn)。这里有上一段中我们知道要想求出明文x,解同余式方程x^ed≡x(modn)可得,这时只要等式左边的数与X同余就能得到正确的明文。由于c≡x^e(modn),所以可得cd≡x^ed(modn),所以c^d≡x^e(modn)。3.ELGamal数字签名和DSAELGamal数字签名1985年,ELGamal基于离散对数难题提出一种数字签名方案,称为ELGamal数字签名方案。那么,什么是离散对数问题???离散对数问题设p是一个素数,g是模p的本原元,每一个y值都是g的一个幂,求y≡g^x(modp)称为模p的幂运算,反过来,若求y≡g^x(modp)成立,已知y求x的问题称为模p的离散对数问题.将已知y求x的离散对数定义为寻求符合条件1=x=p-1的x.如果g不是p的本原元,那么就不会为y值定义离散对数。相关知识欧拉函数:对于正数n,少于或等于n的数中与n互质的数的个数例如p=7则ψ(p)=6本原元:设本原元为a,则a^d≡1(modp)成立,其中d=ψ(p)ψ(p)是欧拉函数即:a^ψ(p)≡1(modp)a=2时,a³≡8≡1(mod7),但是3不是ψ(7),所以a不是本原元a=3时,a^6≡1(mod7),此时3就是本原元一个域的本原元非唯一1)密码选择选p是一个大素数,p-1有大素数因子,a是一个模p的本原元,将p和a公开;用户随机地选择一个整数x作为自己的秘钥,1=x=p-2计算y≡a^x(modp),取y为公钥2)产生签名设明文消息m,0=m=p-1,用哈希函数计算出H(m),签名过程如下:用户随机选择一个整数k,1kp-1,且(k,p-1)=1计算r≡a^k(modp)计算s≡(m-xr)/k(modp-1)取(r,s)作为m的签名,并以m,r,s形式发给用户B3)验证签名用户接受m,r,s,用A的公钥y验证:a^m≡y^r*r^s(modp)是否成立,若成立则为真,反之相反。签名的可验证性证明如下:因为s≡(m-xr)/k(modp-1)所以m≡xr+ks(modp-1)故a^m≡a^(xr+ks)≡(a^xr)*(a^ks)≡y^r*r^s(modp)故签名可验证安全性为了安全,随机数k应是一次性的,否则时间一长,k可能泄露,因为x≡(m-ks)/r(modp-1)如果k重复使用,则m1≡xr+ks1(modp-1)m1≡xr+ks1(modp-1)=(s1-s2)k≡(m1-m2)(modp-1)如果知道m1和m2,就可以求出k,进而求出秘钥!是Schnorr和ElGamal签名算法的变种,美国国家标准技术研究所(NIST)1994年5月19日公布了数字签名标准的(DSS),标准采用的算法便是DSA,密钥长度为512~1024位。密钥长度愈长,签名速度愈慢,制约运算速度的只要因素是大数的模指数运算。DSA是基于整数有限域离散对数难题的,其安全性与RSA相比差不多。DSA的一个重要特点是两个素数公开,这样,当使用别人的p和q时,即使不知道私钥,你也能确认它们是否是随机产生的,还是作了手脚。RSA算法却做不到。算法中应用了下述参数:p:Lbits长的素数。L是64的倍数,范围是512到1024;q:p-1的160bits的素因子;g:g=h^((p-1)/q)modp,h满足hp-1,h^((p-1)/q)modp1;x:xq,x为私钥;y:y=g^xmodp,(p,q,g,y)为公钥;H(x):Hash函数。。p,q,g可由一组用户共享,但在实际应用中,使用公共模数可能会带来一定的威胁。签名及验证协议如下:1.P产生随机数k,kq;2.P计算r=(g^kmodp)modqs=(k^(-1)(H(m)+xr))modq签名结果是(m,r,s)。3.验证时计算w=s^(-1)modqu1=(H(m)*w)modqu2=(r*w)modqv=((g^u1*y^u2)modp)modq若v=r,则认为签名有效。推导已知,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=1^nmodp=1证明前的必要推导已知,gcd(h,p)=1,费马定理:h^(p-1)≡1(modp),对任意整数n:g^(nq)modp=1对任意整数t,t=nq+z,其中n,q是非负整数,0zqg^tmodp=g^(nq+z)modp=(g^nqmodp)(g^zmodp)=g^zmodp=g^(tmodq)modp即:g^(tmodq)modp=g^tmodp证明因为:r=(g^kmodp)modq;s=(h(m)+xr)k^(-1)modq;w=s^(-1)modqu1=(h(m)*w)modqu2=(r*w)modqv=((g^u1*y^u2)modp)modq证明所以:v=((g^u1*y^u2)modp)modq=((g^(h(m)*w)*y^(r*w))modp)modq=((g^(h(m)*w)*g^(x*r*w))modp)modq=(g^((h(m)+x*r)*w)modp)modq=(g^(s*k*w)modp)modq=((g^kmodp)modq=r所以,最后验证的时候只要v=r的时候,即可认为通过验证4.GGH基于格的数字签名格的定义线性独立空间上有集合,格就是这些向量的线性组合用公式表示如下:格L的维数等于格中向量的个数。假定是格中格L的基,,则有必然存在整系数使得:这样的话,格中的问题就是矩阵运算了。最接近向量问题(CVP):对于一个非格L中的向量w,在格中寻找一个向量v,使得||w-v||最小。Babai最接近向量算法(第六章内容)格L,维数n=2,向量v1=(137,312),v2=(215,-187)是格的基,寻找L中的一个向量V满足||w-v||最小。其中,w=(53172,81743).解:要寻找一个最接近向量,即w=t1v1+t2v2=53172=137t1+215t281743=312t1-187t2=t1=296.85t2=58.15=v=[t1]v1+[t2]v2=(53159,81818)检查:||v-w||=76.12效果不错,比较接近w马哈达比例Hadamardratio我们把接近于1的基称为好基,接近于0的基称为坏基。哈达马系数的范围是(0,1)的。例如,上题中,GGH数字签名过程公钥生成选择一个好基v1,,,vn和一个坏基w1,,,,wn,公布坏基作为公钥签名选择文件d签名,使用Babai算法和一个好基v1,,,vn计算得到一个向量s,该向量接近于文件d,然后用坏基写出签名s=a1w1+,,,+anwn,将签名a1,,,an公布验证用公钥w1,,,wn和签名a1,,,an计算得出的结果s=a1w1+,,,+anwn是否接近于文件使用