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

《上海交大密码学课件第12讲数字签名算法.ppt》由会员分享，可在线阅读，更多相关《上海交大密码学课件第12讲数字签名算法.ppt（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第12讲 数字签名算法上海交通大学1.数字签名方案数字签名方案公钥签名方案：利用私钥生成签名 利用公钥验证签名 只有私钥的拥有者才能生成签名 所以能够用于证明谁生成的消息 任何知道公钥的人可以验证消息（他们要确认公钥拥有者的身份，这是公钥的密钥分配问题）通常不对整个消息签名，因为这将会使交换信息长度增加一倍使用消息的 hashhash 值数字签名可以提供消息的不可否认性,2.RSA RSA 加密解密是可交换的 可以用于数字签名方案 给定 RSA 方案(e,R),(d,p,q)要签名消息M：计算:h=H(M)S=hd(mod R)(M,S)要验证签名,计算:h=H(M)Se(mod R)=he.

2、d(mod R)=h(mod R)h=h?3.RSA 使用使用 使用RSA加密、认证：使用发送者的私钥签名一个消息使用接收者的公钥加密消息看起来，一个消息可用RSA加密、签名而不改变大小但是，加密使用的是消息接收者的模，签名是消息发送者的模，后着可能比前者小交换两者顺序？签名常使用HASH函数值 4.El Gamal Signature Scheme ElGamal 加密算法是不可交换的加密算法是不可交换的 存在一个相关的签名算法存在一个相关的签名算法 安全性是基于计算离散对数的困难性安全性是基于计算离散对数的困难性方案的密钥生成是相同的方案的密钥生成是相同的:有个共享的素数有个共享的素数 p

3、 p,公开的本原根公开的本原根 a a 每个用户选择一个随机数作为私钥每个用户选择一个随机数作为私钥 x x 计算各自的公开密钥计算各自的公开密钥:y=ay=ax x mod p mod p 公钥是公钥是(y,a,p)(y,a,p)私钥是私钥是(x)(x)5.El Gamal 签名方案的使用签名方案的使用签名消息签名消息 M:选择随机数选择随机数 k,GCD(k,p-1)=1k,GCD(k,p-1)=1 计算计算 K=K=a ak k(mod(mod p)p)用用 Euclidean(inverse)扩展算法求扩展算法求 S S:M=x.K+k.S mod(p-1)M=x.K+k.S mod(

4、p-1);即即求求S=kS=k-1-1(M-x.K)mod(p-1)(M-x.K)mod(p-1)签名是签名是(M,K,S)(M,K,S)k k 应该被销毁应该被销毁同同ElGamal 加密方案，加密方案，签名信息也是消息的签名信息也是消息的2倍倍验证验证(K,S)(K,S)是是 对对MM的签名的签名:y yK K.K.KS Smodmod p=p=a aMMmodmod p p 6.ElGamal 签名方案举例签名方案举例取取 p=11,a=2 p=11,a=2 选择私钥选择私钥 x=8 x=8 计算计算:y=a:y=ax x mod p=2 mod p=28 8 mod 11=3 mod

5、11=3 公钥是公钥是:y=3,a=2,p=11:y=3,a=2,p=11 对对 M=5 M=5 签名：签名：选择随机数选择随机数 k=9 k=9 确定确定 gcd(10,9)=1 gcd(10,9)=1 计算计算:K=:K=a ak k mod p=2 mod p=29 9 mod 11=6 mod 11=6 解解:5=8.6+9.S mod 10;:5=8.6+9.S mod 10;nbnb 9 9-1-1=9 mod 10;=9 mod 10;因此因此 S=9.(5-8.6)=3 mod 10 S=9.(5-8.6)=3 mod 10 签名是签名是 (K=6,S=3)(K=6,S=3)要

6、验证签名要验证签名,确认确认:3 36.6.6 63 3=2=25 5 mod 11 mod 113.7=32=10 mod 11 3.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 签名安全性是基于离散

7、对数 被广泛接收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)及消息Mk=s-1.(SHA(M)+x.r(mod q)验证签名,计算:w=s-1(mod q)u

8、1=(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(Key

9、2|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,)HMAC16.练习练习1.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.