1、12SchnorrDSA椭圆曲线RSA-PSSp 数字签名简介数字签名简介p 特征p 攻击与伪造p 数字签名需求p 直接数字签名p 数字签名方案数字签名方案p ElGamalp Schnorrp 数字签名标准（DSA）p 椭圆曲线数字签名算法p RSA-PSS数字签名算法3SchnorrDSA椭圆曲线RSA-PSSp 数字签名数字签名特征特征（为什么需要数字签名）（为什么需要数字签名）p 消息认证可以保护信息交换不受第三方的攻击，但不能处理通信双方自身发生的攻击p 接收者伪造与发送者否认p 数字签名可以解决上述问题，特征为数字签名可以解决上述问题，特征为: 1.验证签名者、签名的日期和时间2.
2、认证消息内容3.可由第三方仲裁，以解决争执p 因此，因此，数字签名具有认证功能数字签名具有认证功能4SchnorrDSA椭圆曲线RSA-PSSDigital Signature Model5SchnorrDSA椭圆曲线RSA-PSSDigital Signature Model6SchnorrDSA椭圆曲线RSA-PSSp 针对数字签名的针对数字签名的攻击攻击和和伪造伪造p 攻击攻击p 唯密钥攻击key-only attack：C仅知道A的公钥p 已知消息攻击known message attack：C掌握部分(消息-签名)对p 一般选择消息攻击：掌握公钥前，选择一些消息，获得A的签名p 定向
3、选择消息攻击：掌握公钥后，选择一些消息，获得A的签名p 适应性选择消息攻击：允许C把A作为“oracle”进行轮询p 攻击成功等级攻击成功等级p 完全破译：得到私钥p 通用伪造：掌握一个有效算法，对任意消息生成合法签名p 选择伪造：C对于特定消息能伪造合法签名p 存在性伪造：C可以造出一个合法签名，但无法控制签名内容7SchnorrDSA椭圆曲线RSA-PSSp 数字签名数字签名应满足的应满足的条件条件p 签名值必须依赖于所签的消息，与消息相关的二进制位串p 必须使用发送者独有的信息 以防止伪造和否认p 产生签名比较容易p 识别和验证签名比较容易p 伪造数字签名在计算上是不可行的。包括 已知数
4、字签名，伪造新的消息 已知消息，伪造数字签名p 保存数字签名的拷贝是可行的8SchnorrDSA椭圆曲线RSA-PSSp 数字签名数字签名的分类的分类p 以方式分 直接数字签名direct digital signature 仲裁数字签名arbitrated digital signaturep 以安全性分 无条件安全的数字签名 计算上安全的数字签名p 以可签名次数分 一次性的数字签名 多次性的数字签名9SchnorrDSA椭圆曲线RSA-PSSp 数字签名数字签名的的分类：直接数字签名分类：直接数字签名p 只涉及收发双方p 假定接收方已知发送方的公钥p 发送方可以用自己的私钥对整个消息内容或
5、消息内容的hash值进行加密，完成数字签名。p 可以用接收者的公钥来加密以提供保密性p 先签名后加密，很重要。p 缺点：安全性依赖于发送方私钥的安全性10SchnorrDSA椭圆曲线RSA-PSSp 数字签名数字签名的的分类分类：仲裁仲裁数字签名数字签名p 仲裁者A 验证任何签名的消息 给消息加上日期并发送给接收者p 需要对仲裁者有合适的信任级别p 既可在私钥体制中实现，又可在公钥体制中实现p 仲裁者可以或者不可以阅读消息11SchnorrDSA椭圆曲线RSA-PSSp直接直接数字签名数字签名(1) AB: EKRaM提供了鉴别与签名： 只有A具有KRa进行加密; 传输中没有被篡改； 需要某些
6、格式信息/冗余度； 任何第三方可以用KUa 验证签名(1) A B: EKUb EKRa(M) 提供了保密(KUb)、鉴别与签名(KRa)12SchnorrDSA椭圆曲线RSA-PSSp直接直接数字签名数字签名(2) AB: M|EKRaH(M)提供了鉴别与签名： H(M) 受到密码算法的保护； 只有A能够生成 EKRaH(M)(2) AB: EKM|EKRaH(M) 提供保密性、鉴别和数字签名。13SchnorrDSA椭圆曲线RSA-PSSp直接数字签名的直接数字签名的p 签名有效性依赖依赖于于发送方私钥的安全性；p 发送方要抵赖发送某一消息时，可能会声称其私钥丢失或被窃，从而他人伪造了他的
7、签名。p 通常需要采用与私有密钥安全性相关的行政管理控制手段来制止或至少是削弱这种情况，但威胁在某种程度上依然存在。p 改进的方式例如可以要求被签名的信息包含一个时间戳，并要求将已暴露的密钥报告给一个授权中心。p X的某些私有密钥确实在时间T被窃取，敌方可以伪造X的签名及早于或等于时间早于或等于时间T的时间戳的时间戳。p 解决方法：数字证书管理中心（解决方法：数字证书管理中心（CA，14章）章）14SchnorrDSA椭圆曲线RSA-PSSp仲裁仲裁数字签名数字签名p 引入仲裁者。通常的做法是所有从发送方X到接收方Y的签名消息首先送到仲裁者AA将消息及其签名进行一系列测试，以检查其来源和内容然
8、后A将消息加上日期并与已被仲裁者验证通过的指示一起发给Y。p 仲裁者在这一类签名模式中扮演敏感和关键的角色。p 所有的参与者必须极大地相信这一仲裁机制工作正常。15SchnorrDSA椭圆曲线RSA-PSSp仲裁仲裁数字签名技术数字签名技术(a) 单密钥加密方式，仲裁者可以看见消息(1) XA：M|EKxaIDx| H(M)(2) AY：EKayIDx| M | EKxaIDx| H(M) | TX与A之间共享密钥Kxa，Y与A之间共享密钥Kay；X：准备消息M，计算其散列码H(M)，用X的标识符IDx 和散列值构成签名，并将消息及签名经Kxa加密后发送给A；A：解密签名，用H(M)验证消息M
9、，然后将IDx，M，签名，和时间戳 一起经Kay加密后发送给Y；Y：解密A发来的信息，并可将M和签名保存起来。p 解决纠纷：解决纠纷：Y：向A发送 EKayIDx| M | EKxaIDx| H(M) A：用Kay恢复IDx，M，和签名（ EKxaIDx| H(M)），然后用Kxa解密签名并验证散列码16SchnorrDSA椭圆曲线RSA-PSSp仲裁仲裁数字签名技术数字签名技术(a) 单密钥加密方式，仲裁者可以看见消息(1) XA：M|EKxaIDx| H(M)(2) AY：EKayIDx| M | EKxaIDx| H(M) | T(b) 单密钥加密方式，仲裁者不可以看见消息(1) XA：
10、 IDx | EKxyM|EKxaIDx| H(EKxyM)(2) AY：EKayIDx|EKxyM | EKxaIDx| H(EKxyM) | T(c) 双密钥加密方式，仲裁者不可以看见消息(1) XA： IDx | EKRxIDx | EKUy (EKRxM)(2) AY： EKRaIDx| EKUyEKRxM | T17SchnorrDSA椭圆曲线RSA-PSSp数字签名数字签名算法算法p 普通数字签名算法EIGamal SchnorrDSS/DSA椭圆曲线RSA-PSSp 不可否认的数字签名算法p 群签名算法p 盲签名算法18数字签名SchnorrDSA椭圆曲线RSA-PSSpD-H密
11、钥交换与密钥交换与EIGamal公钥加密回顾公钥加密回顾协商大素数p，本原根g选择随机数XA、XB计算YA=gXA，YB=gXB (mod p)Alice计算K= (YB ) XA(mod p); Bob计算K = (YA ) XB(mod p), K = K =g XA XB(mod p)协商大素数q，本原根选择随机数XAAlice计算YA= XA (mod q); PU= q, , YA SU= XABob随机选择k，K= YakC1= k, C2=KMAliceK=C1XAM=C2K-1签名：C=E(PRa, M)验证：M=D(PUa, C)19数字签名SchnorrDSA椭圆曲线RSA
12、-PSSpEIGamal签名方案签名方案p ElGamal签名是一种随机附属签名机制，它可以对任意长度的二进制消息格式进行签名。p ElGamal 加密算法是不可交换的 p 存在一个相关的签名算法 安全性是基于计算离散对数的困难性p 方案的密钥生成与加密算法相同: 有个共享的素数 q, 公开的本原根 a （全局参数）每个用户选择一个随机数作为私钥 XA计算各自的公开密钥: YA = axA mod p 公钥是 (YA, a, q) 私钥是 (XA) 20数字签名SchnorrDSA椭圆曲线RSA-PSSpEIGamal签名方案签名方案p 素数 q, 本原根 a ；私钥：随机数 XA ；公钥是
13、(YA, a, q) p 签名消息 M: 选择随机数 K, GCD(K, q-1)=1 计算 S S1 1= = a aK K(mod q)(mod q) 用 Euclidean 算法求 S2，使得:M = XA *S1 + K*S2 mod (q-1); 即求S2 = K-1(M - XA*S1) mod (q-1) p 签名是 (S1,S2) p K 应该被销毁p 验证 (S1,S2)是 对M的签名: YA S1 *S1S2 mod q = aMmod q 21数字签名SchnorrDSA椭圆曲线RSA-PSSpEIGamal签名方案举例签名方案举例p 取 q=11, a=2 p 选择私钥
14、 XA=8 p 计算: YA = aXA mod p = 28 mod 11 = 3 p 公钥是: YA=3, a=2,p=11 p 对 M=5 签名：p 选择随机数 K=9 p 确定 gcd(10,9)=1 p 计算: S1 = aK mod p = 29 mod 11 = 6 p 解: 5=8*6+9*S mod 10; 9-1=9 mod 10;因此 S2 = 9*(5-8*6) = 3 mod 10 p 签名是 (S1=6,S2=3) p 要验证签名, 确认:p 36*63与25是否在模11下相等22数字签名SchnorrDSA椭圆曲线RSA-PSSpEIGamal签名方案举例签名方案
15、举例2*46712721311467,2127mod2mod467132,100213,( ,1)(213,466)1mod2mod46729()mod1(10012729)213mod46651(51,29)100 xkpxyppyxmkk prpsmxr kpB例：用户A选择素数是的生成元，选择计算公开， 保密对消息签名选择是消息的签名用户 用验证Z Z295111002100(51,29)mod132 29mod467189mod2mod467189(51,29)100rsmAVy rpVp算法验证用户 对消息的签名所以是消息的签名23数字签名SchnorrDSA椭圆曲线RSA-PSSp
16、EIGamal签名方案安全性分析签名方案安全性分析24数字签名ElGamalDSA椭圆曲线RSA-PSSpSchnorr签名方案签名方案p 同样基于离散对数难题：同样基于离散对数难题：1024位大素数位大素数p，要求：，要求：p-1含有含有大素因子大素因子q，q为为160位位p 公私公私钥对生成：钥对生成：p 选择素数p和q；q是p-1的因子p 选择整数a，使得aq=1mod p；a、p、q为全局公钥p 用户随机选择s，0sq，s作为私钥p 计算v=a-s mod p，v作为用户公钥25数字签名ElGamalDSA椭圆曲线RSA-PSSpSchnorr签名方案签名方案p 私钥对生成：私钥对生成
17、：p 选择素数p和q；q是p-1的因子，aq=1mod pp v=a-s mod p，v作为用户公钥，s为用户私钥p 产生签名产生签名p 随机选择r，0rq，计算x=ar mod p；可预处理，与消息无关p x附在消息后面求Hash：e=H(M|x)p 计算y=r+se mod q，签名包括(e，y)p 验证验证p 计算x=ayve mod pp 验证e是否等于 H(M|x)26数字签名ElGamalSchnorr椭圆曲线RSA-PSSp数字签名数字签名标准标准p Digital Signature Standard (DSS)p 美国政府的签名方案p 由NIST 和NSA，在20世纪90年代
18、设计p 1991年，作为FIPS-186发布p 1993, 1996 ，2000进行了修改p 采用SHA hash算法 p DSS 是标准 DSA 算法。p FIPS 186-2 (2000) 包括可选的 RSA 和椭圆曲线签名算法27数字签名ElGamalSchnorr椭圆曲线RSA-PSSp数字签名算法数字签名算法 Digital Signature Algorithm (DSA)p 产生320 bit的签名值p 可以提供512-1024 bit 的安全性p 比RSA小且快p 仅是一个数字签名方案（不能用于加密）p 安全性依赖于计算离散对数的困难性p 是ElGamal 和Schnorr 方
19、案的变体28数字签名ElGamalSchnorr椭圆曲线RSA-PSSp数字签名算法数字签名算法 Digital Signature Algorithm (DSA)p 产生320 bit的签名值p 可以提供512-1024 bit 的安全性p 比RSA小且快p 仅是一个数字签名方案（不能用于加密）p 安全性依赖于计算里算对数的困难性p 是ElGamal 和Schnorr 方案的变体29数字签名ElGamalSchnorr椭圆曲线RSA-PSSp DSA过程过程p 密钥生成密钥生成p全局公钥 (p, q, g): p选择一个大的素数 p 2L 其中 L= 512 to 1024 bits 且L
20、是64的倍数p选择q, 位长为160 bit q 是 (p-1)的素因子p选择 g = h(p-1)/q mod p其中 h 1 p用户选择私钥并计算对应的公钥: p随机选择私钥 0 xq p计算公钥 y = gx (mod p) 30数字签名ElGamalSchnorr椭圆曲线RSA-PSSp DSA过程过程p 密钥生成密钥生成p全局公钥 (p, q, g): q 是 (p-1)的素因子， g = h(p-1)/q mod pp用户选择私钥并计算对应的公钥: y = gx (mod p) p签名签名生成（发送者）生成（发送者）p产生随机密钥k（k是随机数，用后销毁）p计算签名对(r, s)：
21、r = ( gk ( mod p ) ) (mod q) s = ( k-1*H( M ) + x*r) (mod q) p验证过程：w = s-1(mod q) u1= (H(M)*w)(mod q) u2= (r*w)(mod q) v = (gu1*yu2(mod p) (mod q) 检验v是否等于r31数字签名ElGamalSchnorr椭圆曲线RSA-PSSp DSA过程过程p密钥：全局公钥 (p, q, g): q 是 (p-1)的素因子， g = h(p-1)/q mod pp用户选择私钥并计算对应的公钥: y = gx (mod p) p签名：产生随机密钥k（k是随机数，用后
22、销毁）p计算签名对(r, s)：r = ( gk ( mod p ) ) (mod q) s = (k-1*(H( M ) + x*r) (mod q) p验证过程：w = s-1(mod q) u1= (H(M)*w)(mod q) u2= (r*w)(mod q) v = (gu1*yu2(mod p) (mod q) pgt modp = gt mod q mod p32数字签名ElGamalSchnorr椭圆曲线RSA-PSSp DSA过程过程33数字签名ElGamalSchnorrDSARSA-PSS34数字签名ElGamalSchnorrDSA椭圆曲线35本章作业：本章作业： 无无p 数字签名简介p 特征p 攻击与伪造p 数字签名需求p 直接数字签名p 数字签名方案p ElGamalp Schnorrp 数字签名标准（DSA）p 椭圆曲线数字签名算法p RSA-PSS数字签名算法
