现代密码学第8讲：数字签名

1数字签名《现代密码学》第八讲2上章内容回顾公钥密码体制的提出及分类公钥密码体制的基本概念单向陷门函数的概念设计公钥加密算法--背包密码体制RSA算法及攻击方法ElGmal算法椭圆曲线密码体制3本章主要内容数字签名的基本概念一般数字签名算法RSA数字签名技术数字签名标准基于离散对数的数字签名椭圆曲线数字签名4数字签名的基本概念手写签名与数字签名的区别手写签名是一种传统的确认方式，如写信、签订协议、支付确认、批复文件等.手写签名是所签文件的物理组成部分；数字签名必须与所签文件捆绑在一起。手写签名通过与标准签名比较或检查笔迹来验证，伪造签名比较容易；数字签名是通过公开的验证算法来验证。好的数字签名算法应该伪造签名十分困难。手写签名不易复制；数字签名是一个二进制信息，十分容易复制，所以必须防止数字签名重复使用。5数字签名和消息认证码的异同：消息完整性验证、消息源认证.消息认证的作用是保护通信双方以防第三方的攻击，然而却不能保护通信双方中的一方防止另一方的欺骗或伪造.①B伪造一个消息并使用与A共享的密钥产生该消息的认证码，然后声称该消息来自于A.②由于B有可能伪造A发来的消息，所以A就可以对自己发过的消息予以否认.数字签名的基本概念6数字签名技术则可有效解决这一问题,类似于手书签名，数字签名应具有以下性质：①能够验证签名产生者的身份，以及产生签名的日期和时间.②能保证被签消息的内容的完整性.③数字签名可由第三方公开验证，从而能够解决通信双方的上述争议.数字签名在网络安全中提供数据完整性、数据源认证性、数据不可否认性等性质数字签名的基本概念7数字签名的基本概念所谓数字签名（DigitalSignature），也称电子签名，是指附加在某一电子文档中的一组特定的符号或代码，它是利用数学方法对该电子文档进行关键信息提取并与用户私有信息进行混合运算而形成的，用于标识签发者的身份以及签发者对电子文档的认可，并能被接收者用来验证该电子文档在传输过程中是否被篡改或伪造.8数字签名的基本概念数字签名的目的是提供一种手段，使得一个实体把他的身份与某个信息捆绑在一起.一个消息的数字签名实际上是一个数，它仅仅依赖于签名者知道的某个秘密和被签名信息的本身.数字签名基于两条基本的假设：一是私钥是安全的，只有其拥有者才能获得；二是产生数字签名的惟一途径是使用私钥。9数字签名的基本概念1976，WDiffie和MHellman在“NewDirectionsinCryptography”,首先提出了数字签名的思想并猜测存在这样的方案1978，RRivest,AShamir,和LAdleman发明了RSA算法可以用作数字签名算法.1984,SGoldwasser,SMicali,和RRivest首次粗略提出了数字签名算法的安全性要求.2004，中国颁布电子签章法10数字签名的攻击：惟密钥攻击：攻击者只有用户公开的密钥.已知消息攻击：攻击者拥有一些消息的合法签名，但是消息不由他选择.选择消息攻击：攻击者可以自由选择消息并获取消息的签名.攻击结果：完全破译：攻击者恢复出用户的密钥.一致伪造：攻击者对于任意消息可以伪造其签名.选择性伪造：攻击者可以对一个自己选取的消息伪造签名.存在性伪造：攻击者可以生成一些消息的签名，但在伪造前对该消息一无所知.数字签名的基本概念11数字签名的基本概念数字签名算法满足的条件：签名是可以被确认--接受者能够核实发送者对消息的签名.签名是不可伪造--除了发送者，任何人（包括接受者）不能伪造消息的签名.签名是不可重用--同一消息不同时刻其签名是有区别的.签名是不可抵赖--发送者事后不能抵赖对消息的签名，出现争议时，第三方可解决争端.12一般签名算法包含密钥生成（公钥/私钥）消息签名S=Sigx(M)用私钥对消息（消息摘要）进行签名运算消息验证用公钥验证消息的签名是否正确，输出“True”或“False”一般数字签名算法任何人（包含消息接收方）都可以验证消息是否正确消息摘要的用途：效率更高（公钥算法效率较低）；避免消息分块签名，完整性保证。,xxxTrueSSigMVerSMFalseSSigM13①参数和密钥生成选两个保密的大素数p和q，计算n=p×q，φ(n)=(p-1)(q-1)；选一整数e，满足1eφ(n)，且gcd(φ(n),e)=1；计算d，满足d·e≡1modφ(n)；以{e,n}为公开钥,{d,n}为秘密密钥.一般数字签名算法--RSA14②签名过程设消息为m，对其签名为s≡mdmodn③验证过程接收方在收到消息m和签名s后，验证是否成立，若成立，则发送方的签名有效.?modemsn一般数字签名算法--RSA实际应用时，数字签名是对消息摘要加密产生，而不是直接对消息加密产生15RSA数字签名加密算法和签名算法同用，攻击者可以方便解密一般攻击者是将某一信息作一下伪装(Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。解决方法：不对自己一无所知的信息签名；不对陌生人送来的随机文档签名；签名时首先使用One-WayHashFunction对文档作HASH处理；同时使用不同的签名算法。16数字签名标准DSS(DigitalSignatureStandard)是美国NIST公布的联邦信息处理标准FIPSPUB186，其中采用了SHA和新的签名技术--DSA(DigitalSignatureAlgorithm).DSS最初公布于1991年，在考虑了公众对其安全性的反馈意见后，于1993年公布了其修改版.一般数字签名算法-DSA17①参数p：满足2L-1p2L的大素数，其中512≤L≤1024且L是64的倍数.q：p-1的素因子，满足2159q2160，即q长为160比特.g：g≡h(p-1)/qmodp，其中h是满足1hp-1且使得h(p-1)/qmodp1的任一整数.用户秘密钥x（0xq的随机数或伪随机数）；用户的公开钥y：y≡gxmodp.一般数字签名算法-DSA18②签名过程用户为待签消息选取的秘密数k，k是满足0kq的随机数(伪随机数).用户对消息m的签名为(r,s)r≡(gkmodp)modq,s≡[k-1(h(m)+xr)]modq，H(M)是由SHA求出的消息M的杂凑值.一般数字签名算法-DSA19③验证过程设接收方收到的消息为M’及其签名(r’,s’),计算w≡(s’)-1modq,u1≡[h(M’)w]modqu2≡r’wmodq,v≡[(gu1yu2)modp]modq检查若相等，则认为签名有效.?vr一般数字签名算法-DSA20一般数字签名算法-DSA正确性证明因为若(m´,r´,s´)=(m,r,s)，则DSA是在ElGamal和Schnorr两个签名方案的基础上设计的，其安全性基于有限域上求离散对数的困难性.1()(())[()mod]mod[mod]mod(mod)modhmwxrwhmxrskvggpqgpqgpqr21DSA安全性基于离散对数的困难性，敌手从r恢复k或从s恢复x都是不可行的.注1.最初建议使用一个共同的素数模p；现在建议不同的工作组使用不同的(p,q,g)。注2.GusSimmons发现存在潜信道，能够泄露私钥。注3.签名产生过程中的运算主要是求r的模指数运算r=(gkmodp)modq，而这一运算与待签的消息无关，因此能被预先计算.事实上，用户可以预先计算出很多r和k-1以备以后的签名使用，从而可大大加快产生签名的速度。一般数字签名算法-DSA22RSA签名与DSA签名的异同23RSA签名与DSA签名的异同RSA算法既能用于加密和签名，又能用于密钥交换;DSS使用的算法只能提供数字签名功能.RSA算法是确定算法，相同消息，其签名相同;DSA是非确定算法，它有随机输入，相同消息签名不同.RSA的安全性基于分解因子；DSA的安全性基于离散对数24基于离散对数问题的数字签名体制是数字签名体制中最为常用的一类，其中包括ElGamal签名体制、DSA签名体制、Okamoto签名体制等.一般数字签名算法25离散对数签名体制1)参数和密钥生成p：大素数；q：p-1或p-1的大素因子；g：g∈RZ*p，且gq≡1(modp)，g∈RZ*p表示g是从Z*p中随机选取的，Z*p=Zp-{0}；x：用户A的秘密钥，1xq；y：用户A的公开钥，y≡gx(modp).一般数字签名算法262)签名的产生过程对于待签名的消息m，A执行以下步骤：①计算m的杂凑值h(m)。②选择随机数k：1kq，计算r≡(gkmodp)modq.③从签名方程ak≡b+cx(modq)中解出s,以(r,s)作为产生的数字签名.一般数字签名算法27方程的系数a、b、c共有120中选择方法：一般数字签名算法1±r±sh(m)2±h(m)*r±s13±h(m)*r±h(m)*s14±h(m)*r±sr15±h(m)*s±sr1281）a=r,b=s,c=h(m);2）a=r,b=h(m),c=s;3）a=s,b=r,c=h(m);4）a=s,b=h(m),c=r;5）a=h(m),b=r,c=s;6）a=h(m),b=s,c=r.7）a=-r,b=s,c=h(m);8）a=-r,b=h(m),c=s;9）a=s,b=-r,c=h(m);10）a=s,b=h(m),c=-r;11）a=h(m),b=-r,c=s;12）a=h(m),b=s,c=-r.13）a=r,b=-s,c=h(m);14）a=r,b=h(m),c=-s;15）a=-s,b=r,c=h(m);16）a=-s,b=h(m),c=r;17）a=h(m),b=r,c=-s;18）a=h(m),b=-s,c=r.19）a=-r,b=-s,c=h(m);20）a=-r,b=h(m),c=-s;21）a=-s,b=-r,c=h(m);22）a=-s,b=h(m),c=-r;23）a=h(m),b=-r,c=-s;24）a=h(m),b=-s,c=-r.一般数字签名算法例：a,b,c的值从第一行选取，共有24中取法293)签名的验证过程接收方在收到消息m和签名(r,s)后，可以按照以下验证方程检验：(,(,),)modmod.abcVeryrsmTruergypq一般数字签名算法30一般数字签名算法例：a,b,c从第一行选取，都只选正号情况1）a=r,b=s,c=h(m);2）a=r,b=h(m),c=s;3）a=s,b=r,c=h(m);4）a=s,b=h(m),c=r;5）a=h(m),b=r,c=s;6）a=h(m),b=s,c=r.31签名等式1）2）3）4）5）6）()(mod)rkhmsxq()(mod)rkshmxq()(mod)(mod)rshmrgypq一般数字签名算法()(mod)skrhmxq()(mod)hmksrxq()(mod)hmkrsxq验证等式()(mod)skhmrxq()(mod)(mod)rhmsrgypq()(mod)(mod)srhmrgypq()(mod)(mod)shmrrgypq()(mod)(mod)hmsrrgypq()(mod)(mod)hmrsrgypq32例.ElGamal签名算法1)参数：p：大素数；g：Z*p的一个生成元；x：用户A的秘密钥，x∈RZ*p；y：用户A的公开钥，y≡gx(modp).一般数字签名算法332)签名的产生过程对于待签名的消息m，A执行以下步骤：①计算m的杂凑值h(m);②选择随机数k：k∈Z*p，计算r≡gk(modp);③计算s≡(h(m)-xr)k-1(modp-1),以(r,s)作为产生的数字签名.一般数字签名算法343)签名验证过程接收方在收到消息m和数字签名(r,s)后，先计算h(m)，并按下式验证：正确性可由下式证明：.()(,(,),())(