《数字签名算法》PPT课件.ppt
第十二讲 数字签名算法,上海交通大学计算机科学与工程系,郑东,要求：掌握数字签名的基本原理及用途掌握RSA,ElGamal,DSA数字签名算法,1.数字签名方案,公钥签名方案：利用私钥生成签名 利用公钥验证签名 只有私钥的拥有者才能生成签名 所以能够用于证明谁生成的消息 任何知道公钥的人可以验证消息（他们要确认公钥拥有者的身份，这是公钥的密钥分配问题）通常不对整个消息签名，因为这将会使交换信息长度增加一倍使用消息的 hash 值数字签名可以提供消息的不可否认性,2.RSA,RSA 加密解密是可交换的 可以用于数字签名方案 给定 RSA 方案(e,R),(d,p,q)要签名消息M：计算:S=Md(mod R)要验证签名,计算:M=Se(mod R)=Me.d(mod R)=M(mod R),3.RSA 使用,使用RSA加密、认证：使用发送者的私钥签名一个消息使用接收者的公钥加密消息看起来，一个消息可用RSA加密、签名而不改变大小但是，加密使用的是消息接收者的模，签名是消息发送者的模，后着可能比前者小交换两者顺序？签名常使用HASH函数值,4.El Gamal Signature Scheme,ElGamal 加密算法是不可交换的 存在一个相关的签名算法 安全性是基于计算离散对数的困难性方案的密钥生成是相同的:有个共享的素数 p,公开的本原根 a 每个用户选择一个随机数作为私钥 x 计算各自的公开密钥:y=ax mod p 公钥是(y,a,p)私钥是(x),5.El Gamal 签名方案的使用,签名消息 M:选择随机数 k,GCD(k,p-1)=1 计算 K=ak(mod p)用 Euclidean(inverse)扩展算法求 S:M=x.K+k.S mod(p-1);即求S=k-1(M-x.K)mod(p-1)签名是(K,S)k 应该被销毁同ElGamal 加密方案，签名信息也是消息的2倍验证(K,S)是 对M的签名:yK.KSmod p=aMmod p,6.ElGamal 签名方案举例,取 p=11,g=2 选择私钥 x=8 计算:y=ax mod p=28 mod 11=3 公钥是:y=3,g=2,p=11 对 M=5 签名：选择随机数 k=9 确定 gcd(10,9)=1 计算:K=ak mod p=29 mod 11=6 解:5=8.6+9.S mod 10;nb 9-1=9 mod 10;因此 S=9.(5-8.6)=3 mod 10 签名是(K=6,S=3)要验证签名,确认:36.63=25 mod 113.7=32=10 mod 11,7.DSA(Digital Signature Algorithm),US Federal Govt approved signature scheme(FIPS PUB 186)使用 SHA hash alg NIST&NSA 在 90s初设计 DSA 是算法,DSS 是标准 对此标准宣布的争议!是否需要使用 RSADSA 是 ElGamal 及Schnorr algorithms 的变形生成 320 bit 签名安全性是基于离散对数 被广泛接收,8.DSA 密钥生成,首先选取公开参数(p,q,g):选取大素数 p=2L L=512 to 1024 bits（64倍数）选取 q,160 bit 素因子（of p-1）选择 g=h(p-1)/q 对任何 h1 每个用户选取私钥并计算他们的公钥:选取 xq 计算 y=gx(mod p),9.DSA 签名生成与验证,签名消息 M 生成随机签名蜜钥 k,kq 计算r=(gk(mod p)(mod q)s=k-1.SHA(M)+x.r(mod q)发送签名(r,s)及消息M验证签名,计算:w=s-1(mod q)u1=(SHA(M).w)(mod q)u2=r.w(mod q)v=(gu1.yu2(mod p)(mod q)v=r 签名有效,10.DSA 安全性,基于离散对数 最初建议使用一个共同的 modulus p 现在建议不同的工作组使用不同的(p,q,g)Gus Simmons 发现存在潜信道，能够泄露私钥,13.带密钥的HASH,以上的签名方法都是公钥技术 计算与数据量较大 需要私钥的认证方案 好的方法是使用快速的hash 函数：密钥与消息同时参加运算:KeyedHash=Hash(Key|Message)有一些弱点 随后建议:KeyedHash=Hash(Key1|Hash(Key2|Message),14.HMAC,HMAC 是使用带密钥的HASH函数的结果成为internet标准(RFC2104)结构：HMACK=Hash(K+XOR opad)|Hash(K+XOR ipad)|M)K+是经过填充的密钥 opad,ipad 特殊的填充值Opad=01011010重复b/8次 ipad=00110110重复b/8次安全性是基于原来的HASH函数的安全性 任何 MD5,SHA-1,RIPEMD-160 都可以这样使用,15.小结,数字签名(RSA,ElGamal,DSA,)HMAC,练习,Illustrate the operation of El Gamal signatures,given the following parameters:prime p=31 prim root a=3 Determine a suitable private and public key,and then show the signing and verification of a message M=7.,
