第十二讲 数字签名算法 郑东 上海交通大学计算机科学与工程系
要求： 掌握数字签名的基本原理及用途 掌握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加密、认证： 使用发送者的私钥签名一个消息 使用接收者的公钥加密消息 但是，加密使用的是消息接收者的模，签名是消息发送者的模，后着可能比前者小 交换两者顺序？ 签名常使用HASH函数值
4. El Gamal Signature Scheme 存在一个相关的签名算法 安全性是基于计算离散对数的困难性 方案的密钥生成是相同的: 有个共享的素数 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 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 在 90‘s初设计 DSA 是算法, DSS 是标准 对此标准宣布的争议! 是否需要使用 RSA DSA 是 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 对任何 h<p-1, h(p-1)/q(mod p)>1 每个用户选取私钥并计算他们的公钥: 选取 x<q 计算 y = gx(mod p)
9. DSA 签名生成与验证 签名消息 M 生成随机签名蜜钥 k, k<q 计算 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
练习 ftp.cs.sjtu.edu.cn/zhengdong 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.