数字签名算法培训讲学

第十二讲数字签名算法上海交通大学计算机科学与工程系郑东要求：掌握数字签名的基本原理及用途掌握RSA,ElGamal,DSA数字签名算法1.数字签名方案公钥签名方案：利用私钥生成签名利用公钥验证签名只有私钥的拥有者才能生成签名所以能够用于证明谁生成的消息任何知道公钥的人可以验证消息（他们要确认公钥拥有者的身份，这是公钥的密钥分配问题）通常不对整个消息签名，因为这将会使交换信息长度增加一倍使用消息的hash值数字签名可以提供消息的不可否认性,3.RSA使用

使用RSA加密、认证：使用发送者的私钥签名一个消息使用接收者的公钥加密消息看起来，一个消息可用RSA加密、签名而不改变大小但是，加密使用的是消息接收者的模，签名是消息发送者的模，后着可能比前者小交换两者顺序？签名常使用HASH函数值

4.ElGamalSignatureSchemeElGamal加密算法是不可交换的存在一个相关的签名算法安全性是基于计算离散对数的困难性方案的密钥生成是相同的:有个共享的素数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)

签名是(K,S)

k应该被销毁同ElGamal加密方案，签名信息也是消息的2倍验证(K,S)是对M的签名:yK.KSmodp=aMmodp

6.ElGamal签名方案举例

取p=11,g=2选择私钥x=8计算:y=axmodp=28mod11=3公钥是:y=3,g=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=25mod11

3.7=32=10mod11

7.DSA(DigitalSignatureAlgorithm)USFederalGovtapprovedsignaturescheme(FIPSPUB186)使用SHAhashalgNIST&NSA在90‘s初设计DSA是算法,DSS是标准对此标准宣布的争议!是否需要使用RSADSA是ElGamal及Schnorralgorithms的变形生成320bit签名安全性是基于离散对数被广泛接收8.DSA密钥生成首先选取公开参数(p,q,g):选取大素数p=2L

L=512to1024bits（64倍数）选取q,160bit素因子（ofp-1）选择g=h(p-1)/q

对任何h<p-1,h(p-1)/q(modp)>1

每个用户选取私钥并计算他们的公钥:选取x<q

计算y=gx(modp)

9.DSA签名生成与验证

签名消息M生成随机签名蜜钥k,k<q

计算r=(gk(modp))(modq)

s=k-1.SHA(M)+x.r(modq)

发送签名(r,s)及消息M验证签名,计算:w=s-1(modq)

u1=(SHA(M).w)(modq)

u2=r.w(modq)

v=(gu1.yu2(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,)

HMAC练习

/zhengdongIllustratetheoperationofElGamalsignatures,giventhefollowingparameters:primep=31