上海交大密码学课件--第12讲 数字签名算法

第12讲数字签名算法上海交通大学1.数字签名方案•公钥签名方案：•利用私钥生成签名•利用公钥验证签名•只有私钥的拥有者才能生成签名•所以能够用于证明谁生成的消息•任何知道公钥的人可以验证消息•（他们要确认公钥拥有者的身份，这是公钥的密钥分配问题）•通常不对整个消息签名，因为这将会使交换信息长度增加一倍•使用消息的hash值•数字签名可以提供消息的不可否认性,2.RSA•RSA加密解密是可交换的•可以用于数字签名方案•给定RSA方案{(e,R),(d,p,q)}•要签名消息M：计算:h=H(M)•S=hd(modR)(M,S)•要验证签名,计算:h=H(M)•Se(modR)=h’e.d(modR)=h’(modR)•h’=h?•3.RSA使用•使用RSA加密、认证：•使用发送者的私钥签名一个消息•使用接收者的公钥加密消息•看起来，一个消息可用RSA加密、签名而不改变大小•但是，加密使用的是消息接收者的模，签名是消息发送者的模，后着可能比前者小•交换两者顺序？•签名常使用HASH函数值•4.ElGamalSignatureScheme•ElGamal加密算法是不可交换的•存在一个相关的签名算法•安全性是基于计算离散对数的困难性•方案的密钥生成是相同的:•有个共享的素数p,公开的本原根a•每个用户选择一个随机数作为私钥x•计算各自的公开密钥:y=axmodp•公钥是(y,a,p)•私钥是(x)5.ElGamal签名方案的使用•签名消息M:•选择随机数k,GCD(k,p-1)=1•计算K=ak(modp)•用Euclidean(inverse)扩展算法求S:M=x.K+k.Smod(p-1);即求•S=k-1(M-x.K)mod(p-1)•签名是(M,K,S)•k应该被销毁•同ElGamal加密方案，签名信息也是消息的2倍•验证(K,S)是对M的签名:•yK.KSmodp=aMmodp6.ElGamal签名方案举例•取p=11,a=2•选择私钥x=8•计算:y=axmodp=28mod11=3•公钥是:y=3,a=2,p=11•对M=5签名：•选择随机数k=9•确定gcd(10,9)=1•计算:K=akmodp=29mod11=6•解:5=8.6+9.Smod10;nb9-1=9mod10;因此S=9.(5-8.6)=3mod10•签名是(K=6,S=3)•要验证签名,确认:36.63=25mod113.7=32=10mod11•7.DSA(DigitalSignatureAlgorithm)•USFederalGovtapprovedsignaturescheme(FIPSPUB186)•使用SHAhashalg•NIST&NSA在90‘s初设计•DSA是算法,DSS是标准•对此标准宣布的争议!•是否需要使用RSA•DSA是ElGamal及Schnorralgorithms的变形•生成320bit签名•安全性是基于离散对数•被广泛接收8.DSA密钥生成•首先选取公开参数(p,q,g):•选取大素数p=2L•L=512to1024bits（64倍数）•选取q,160bit素因子（ofp-1）•选择g=h(p-1)/q•对任何hp-1,h(p-1)/q(modp)1•每个用户选取私钥并计算他们的公钥:•选取xq•计算y=gx(modp)9.DSA签名生成与验证•签名消息M•生成随机签名密钥k,kq•计算•r=(gk(modp))(modq)•s=k-1.(SHA(M)+x.r(modq))•发送签名(r,s)及消息M•k=s-1.(SHA(M)+x.r(modq))•验证签名,计算:•w=s-1(modq)•u1=(SHA(M).w)(modq)•u2=r.w(modq)•v=(g^u1.y^u2(modp))(modq)•v=r签名有效10.DSA安全性•基于离散对数•最初建议使用一个共同的modulusp•现在建议不同的工作组使用不同的(p,q,g)•GusSimmons发现存在潜信道，能够泄露私钥13.带密钥的HASH•以上的签名方法都是公钥技术•计算与数据量较大•需要私钥的认证方案•好的方法是使用快速的hash函数：•密钥与消息同时参加运算:KeyedHash=Hash(Key|Message)•有一些弱点•随后建议:KeyedHash=Hash(Key1|Hash(Key2|Message))•14.HMAC•HMAC是使用带密钥的HASH函数的结果•成为internet标准(RFC2104)•结构：HMACK=Hash((K+XORopad)||Hash((K+XORipad)||M))•K+是经过填充的密钥•opad,ipad特殊的填充值•Opad=01011010重复b/8次•ipad=00110110重复b/8次•安全性是基于原来的HASH函数的安全性•任何MD5,SHA-1,RIPEMD-160都可以这样使用•15.小结•数字签名(RSA,ElGamal,DSA,)•HMAC16.练习1.IllustratetheoperationofElGamalsignatures,giventhefollowingparameters:primep=31primroota=3Determineasuitableprivateandpublickey,andthenshowthesigningandverificationofamessageM=7.