<4D F736F F F696E74202D20BDB2D2E531372D31385FCAFDD7D6C7A9C3FBD3EBC9EDB7DDC8CFD6A42E707074>

Size: px

Start display at page:

Download "<4D F736F F F696E74202D20BDB2D2E531372D31385FCAFDD7D6C7A9C3FBD3EBC9EDB7DDC8CFD6A42E707074>"

求均堀古
5 years ago
Views:

1 数字签名与身份认证裴士辉 QQ:

2 手工签名签名印章手印 2

3 电子签名问题 : 电子签名很容易拷贝要求 : 电子签名是消息的一个函数, 并且只有 Alice 可以计算 Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 3

4 令银行和 Alice 共享密钥 K 如果 MAC 用于数字签名? 数字签名应该还具备如下特性 : 甚至连银行也不能伪造签名签名的认证者不应该和签名者共享密钥 Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 4

5 数字签名方案定义签名方案是一个由三个算法组成的三元组 ( Gen, Sig, Ver ) 1 密钥生成算法 Gen, 输出一对密钥 ( pk, sk ), 分别称为公钥和私钥 2 签名算法 Sig 的输入为私钥 sk 和消息 m { 01, } *, 输出为签名, 表示为 : Sig ( m) sk 3 验证算法 Ver 的输入为公钥 pk 消息 m 和一个签名输出为一位 b, 当 b 1时表示签名有效, 当 b 0时表示签名无效. b: Ver ( m, ) pk 此方案要求对所有由 Gen 输出的密钥 ( pk, sk ), 以及任意的 m { 01, } *, 必须满足 Ver ( m, Sig ( m)) 1 pk sk 5

6 攻击目标数字签名方案的安全性 1. 完全破译攻击者能够确定签名者私钥 2. 选择性伪造 (selective forgery) 3. 存在性伪造 (existential forgery) 攻击的模型 1. 唯密钥攻击 (key-only attack) 攻击者只知道签名人的公钥 2. 已知消息攻击 (known message attack) 3. 选择消息攻击 (chosen message attack) 6

7 uf-cma 攻击者 uf-cma 攻击者 : 在选择消息模型下存在性伪造的攻击者 m 1 1 sk pk Sig 攻击者 A m q q (m, ) pk Ver b 如果 : b 1, 并且 m ( m1, m q ) 则攻击者 A 获得成功 Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 7

8 RSA 数字签名方案定义 RSA 签名方案是由三个算法组成的三元组 ( Gen, Sig, Ver ) 1 密钥生成算法 Gen: 输出 {( n, p, q, a, b): n pq, p, q是素数, ab 1(mod ( n)} 公钥 pk ( n, b), 私钥 sk ( n, a) 2 签名算法 Sig: 输入 sk ( n, a) 和消息 m n, 计算 : a : Sig ( m) m modn sk 3 验证算法 Ver : 输入公钥 pk ( n, b) 消息 m n和一个签名 n 输出 : b 1, if mmodn Verpk ( m, ) b 0, if mmodn 8

9 对于 uf-cma 攻击者 A: 已知 : pk ( n, b) 对 RSA 数字签名方案的攻击 1 输出消息- 签名对 ( m, ) 其中 m 1, 1 2 输出消息- 签名对 ( m, ) 随机选择 x n b m x mod n, x Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 9

10 RSA 的同态性 (Homomorphic) 令 pk ( n, b), sk ( n, a) 为 RSA 的公钥和私钥. 对于 x1, x2 n和 y1, y2 n, 有 : ( xx) x x modn a a a ( yy) y y modn b b b Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 10

11 对 RSA 数字签名方案的攻击 uf-cma 攻击者 : 在选择消息模型下存在性伪造的攻击者 m 1 1 sk pk Sig 攻击者 A m 2 2 (m, ) pk Ver b 其中 ( m mm modn, modn) Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 11

12 另外的问题在 RSA 签名方案中, 消息 m, 但在实际中要求消息是任意长度的字符串 n Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 12

13 Hash 函数 H 的选择一个好的 hash 函数 H 可能是这样的 : H ( m ) = 如下位串的前 n 位 : m SHA 1 m S HA 11 m SHA Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 13

14 Full-Domain-Hash (FDH) RSA-FDH 签名方案定义 RSA-FDH 签名方案是由三个算法组成 ( Gen, Sig, Ver ) 1 密钥生成算法 Gen: 按照和 RSA 签名方案相同的方法生成 : 公钥 pk ( n, b, H ), 私钥 sk ( n, a, H ) 其中 H :{ 01, } * n是一个随机预言机 (random oracle) 2 签名算法 Sig : 输入 sk ( n, a) H :{ 01, } * n 和消息 m { 01, } * H a, 计算 : : Sig ( m) H( m) modn sk 3 验证算法 Ver : 输入公钥 pk ( n, b) H :{ 01, } * n 消息 m { 01, } * 和一个签名 n 输出 : Ver H pk b 1, if H( m)modn ( m, ) b 0, if H( m)modn 14

15 RSA-FDH 签名方案的安全性虽然目前没有攻击表明 RSA-FDH 的安全性小于 RSA, 即模 n 为 1024 位的 RSA-FDH 的安全性小于 80 位但是为了达到可证明安全性, 要达到和 RSA 同等的安全性, 建议 RSA-FDH 采用更长的模数. 例如 : 为了达到 80 位的安全性 [2] 的分析结果表明 RSA-FDH 的模 n 应为 3700 位 [1] 的分析结果表明 RSA-FDH 的模 n 应为 2800 位 1 Jean-Sébastien Coron(AF): On the Exact Security of Full Domain Hash. CRYPTO 2000: pp Mihir Bellare, Phillip Rogaway: The Exact Security of Digital Signatures - How to Sign with RSA and Rabin. EUROCRYPT 1996: pp Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 15

16 RSA-PSS 签名方案 PSS:Probabilistic Signature standard 概率签名标准 Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 16

17 RSA-PSS 签名方案的使用 RSA PKCS#1 v2.1. IEEE P1363a ANSI X9.31 RFC 3447 ISO/IEC CRYPTREC NESSIE Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 17

18 ElGamal 签名方案定义 ElGamal 签名方案由三个算法组成 ( Gen, Sig, Ver ) 1 密钥生成算法 Gen: a 输出 {( p,, a, ) : p 是素数, 是本原元, mod p} 公钥 pk ( p,, ), 私钥 sk ( p,, a) 2 签名算法 Sig: 输入 sk ( p,, a) 消息 m 和秘密的随机 k, 输出 : Sig ( mk, ) (, ), 其中 : * 数 p 1 k 1 mod p, ( m a ) k mod( p 1) sk 3 验证算法 Ver : 输入公钥 pk ( p,, ) 消息 m 和一个签名 (, ) Ver pk m 1, if mod p ( m,(, )) m 0, if mod p * p * p * p 18

19 针对 ElGamal 签名的存在性伪造攻击攻击者已知签名人的公钥 pk ( p,, ) 其计算过程为 : 1 选择 i, j,0 i, j p 2 其中 gcd( j, p 1) 1 2 计算签名 : i j mod p, 1 j p mod( 1) 3 计算消息 m imod( p 1) 输出 : 消息 - 签名对 ( m,(, )) 19

20 数字签名标准 DSS 美国国家标准与技术协会 (NIST) 发布的 FIPS 186, 被称为数字签名标准 (DSS) 1991 年提出,1993 年定为 FIPS 186 目前已经发布了 4 个版本 : FIPS 186-1(1996) FIPS (2000) FIPS (2009)FIPS 186-4(2013) DSS 指标准, DSA 指算法维基百科 20

21 DSA 签名算法的密钥生成参数生成 : 1 选择 hash 函数 H 2 确定长度参数 N 和 L FIPS186-3 建议为 (1024,160), (2048,224), (2048,256) 和 (3072,256) 3 选取长度为 N 的素数 p 4 选取长度为 L 的素数 q, q p 1 5 选取元素 g, 其模 p 的阶为 q ( p 1)/ q 任意选取 h, 1 h p 1, 令 g h mod p 生成密钥 : q 生成 {( H, pqga,,,, ) : g mod p}, 其中 1 a q 1 输出 pk { H, p, q, g, }, sk { a} 21

22 签名算法 Sig: DSA 的签名和验证算法输入 sk ( a) 参数{ H, pqg,, } 消息 m { 01, } * 和秘密的随机数 H 1 k q 1, 输出 : Sig ( mk, ) ( rs, ), 其中 : sk ( k 1 r g mod p)modq, s ( Hm ( ) ark ) modq 验证算法 Ver : 输入公钥 pk ( H, p, q, g, ) 消息 m { 01, } * ( rs, ) 计算: 和一个签名 1 w s 1 modq 2 u 1 wh( m)modq 3 u 2 wrmodq ( u u v g mod p)modq Ver H pk 1, if v rmodq ( m,( r, s)) 0, if v rmodq 22

23 临时密钥 k 为什么要保密? 如果临时密钥 k 被公开, 则当攻击者 Eve 截获了签名消息 (m, r, s) 后, 他计算 h=h(m); 再从等式 s=(k -1 (h+ar))(modq) 中计算出 Alice 的私钥 a: a=(sk-h)r -1 (modq) DSA 被攻破 23

24 临时密钥 k 为什么要临时随机地选择? 设临时密钥 k 是保密的, 但是是固定的设攻击者 Eve 截获了两个签名消息 (m, r, s) 和 (m, r, s ) Eve 能够计算出 h=h(m),h =H(m ) Eve 还知道 : s=(k -1 (h+ar))(modq), s =(k -1 (h +ar ))(modq) 这是关于未知量 (k -1,k -1 a) 的二元一次方程组 ( 只不过是模方程组 ), 可以很简单地解出 (k -1,k -1 a), 因此解出 (k,a) DSA 被攻破 24

25 DSA 的标准化参数的位长度和安全等级 p q hash 输出长度安全等级 Christof Paar 等著, 深入浅出密码学 25

26 椭圆曲线数字签名算法 ECDSA 1998 年美国国家标准局 (ANSI) 对于 ECDSA 进行了标准化 2000 年作为 FIPS186-2 得到了批准 26

27 ECDSA 签名算法的密钥生成参数生成 : 1 选择 hash 函数 H 2 确定椭圆曲线 E ( ab, ) p 3 确定椭圆曲线 E ( ab, ) 的基点 G, 以及 G 的阶 n 要求 n 为素数生成密钥 : p 生成 {( H, E ( a, b), G, n, d, C) : C d G}, 其中 0 d n 1 输出 pk { H, EP ( a, b), G, n, C} sk { d} P 27

28 签名算法 Sig: ECDSA 的签名和验证算法输入 sk ( d ) 参数{ H, E ( a, b), G, n } 消息 m { 01, } * 和秘密的 P H 随机数 1 k n 1, 输出 : Sig ( m, k) ( r, s), 计算过程为 : ( x1, y1) k G, r x modn, 1 1 s ( Hm ( ) drk ) modn 验证算法 Ver : 输入公钥 pk ( H, E ( a, b), G, n, C) 消息 m { 01, } * 和一个签名 ( rs, ) 计算: P 1 w s 1 modn 2 u 1 wh( m)modn 3 u 2 wrmodn sk 4 ( x 1, y 1 ) u 1 G u 2 C H Ver ( m,( r, s)) pk 1, if r x1 modn 0, if r x1 modn 28

29 ECDSA 的位长度和安全等级 n 的长度 ( 位 ) hash 函数的输出长度安全等级 Christof Paar 等著, 深入浅出密码学 29

30 数字签名法美国的犹他州于 1995 年颁布的数字签名法是全世界范围内第一部全面规范电子签名的法律美国 2000 年开始实行数字签名法, 数字签名法具有法律效率美国目前已经建立了覆盖全国的 PKI 网络, 联邦州和大型企业之间的 PKI 实现了桥接欧洲各国已经建立了自己的 PKI 2001 年欧盟建立了桥接的 CA,2002 年欧盟开始实行数字签名法亚洲范围内的日本韩国和新加坡在 PKI 建设方面起步较早, 这 3 个国家目前已经实现了交叉认证 30

31 数字签名法我国的立法从 2002 年开始的, 形成了中华人民共和国电子签名法 ( 草案 ) 2004 年 8 月 28 日中华人民共和国第十届全国人民代表大会常务委员会第十一次会议通过了中华人民共和国电子签名法 2005 年 4 月 1 日起施行 31

32 数字证书数字证书是由第三方提供的一种确保该公钥是由主体所拥有的一种方式是绑定共钥和主体的数据结构通常第三方称为 CA( 证书授权机构 ) CA(Certification Authorities) 32

33 X.509 证书 X.509 是一个广泛应用的数字证书标准它有三个版本 : V1: 1988 年发布, 得到了广泛使用 ; V2: 引入了主体和发布者唯一标识的概念 ; V3: 1996 年发布, 支持扩展的概念, 这使得任何人可定义一个扩展并将其包含在证书中 33

34 版本序列号签名算法标识发布者名称有效期主体名称主体的 X.500 命名标准主体的公钥签名 X.509 v1 证书的组成 34

35 主体的 X.500 命名标准 CN 普通名字 OU 机构单位 O 机构 L 机构的位置 ( 城市 ) ST 机构所在的州 C 国家 35

36 数字证书的签发验证信息 ( 主体公钥 ) 签名算法证书证书机构私钥 36

37 数字证书的验证证书信息 Hash() 消息摘要 CA 的公钥?= 证书中的签名验证算法消息摘要 37

38 公钥基础设施 PKI 公钥基础设施 (Public Key Infrastructure), 是一组由硬件软件参与者管理政策与流程组成的基础架构, 其目的在于创造管理分配使用存储以及撤销数字证书维基百科 38

39 PKI 主要组成部分数字证书认证机构 CA(certificate authority ) 将使用者的个人身分跟公开密钥链结在一起注册管理中心 RA(registration authority) 对用户的信息进行审查 VA (validation authority) 代表 CA 对用户提供的数字证书进行验证维基百科 39

40 公钥基础设施 PKI 维基百科 40

41 公钥环境下的交互认证 ( 挑战 - 响应 ) 方案 1 Bob 选择一个随机的挑战 r, 1 并发送如下信息给 Alice: Cert(Bob), r 1 2 Alice 选择一个随机的挑战 r, 2 计算 : y Sig _ ( ID( Bob) r r ), 1 sk Alice 1 2 并发送如下信息给 Alice: Cert(Allice), r 2, y 1 3 Bob 首先验证 : Ver _ ( ID( Bob) r1 r2, y 1) pk Alice 若验证通过, 计算并发送给 Alice 如下信息 : y2 Sig _ ( ID( Alice) r2) sk Bob Douhlas R.Stinson 密码学原理与实践 ( 第三版 ) 41

42 公钥环境下的交互认证 ( 挑战 - 响应 ) 方案 4 Alice 验证 : Ver ID Alice r y pk _ Bob( ( ) 2, 2) 若验证通过,Alice 接受, 否则拒绝 Douhlas R.Stinson 密码学原理与实践 ( 第三版 ) 42

43 公钥环境下的交互认证方案 Alice Bob Cert(B), r 1 y Sig ( B r r ) 1 A 1 2 Cert(A), r 2, y 1 y 2 VerA ( B r1 r2, y1) 1? y2 Sig ( ) B A r2 Ver ( B A r, ) 2 y2 1? Douhlas R.Stinson 密码学原理与实践 ( 第三版 ) 43

44 公钥环境下的交互认证方案 ( 不安全版 ) Alice Bob Cert(B), r 1 y Sig ( B r r ) 1 A 1 2 Cert(A), r 2, y 1 y 2 VerA ( B r1 r2, y1) 1? y Sig ( A r r ) 2 B 2 3 Ver ( A r 2 r B 3, y 2 ) 1? Douhlas R.Stinson 密码学原理与实践 ( 第三版 ) 44

信息安全概论第二讲密码学-new.ppt

信息安全概论第二讲密码学-new.ppt guojpeng@whu.edu.cn 1. 2. 3. 4. 5.PGP QQ 32315476 1 A B DES 1977 RSA1977 -- -- 1.1 : (Cryptology) = (Cryptography) + (Cryptoanalysis) 1.2 cipher algorithm AB A B A restricted C=EM M C C M M=DC key