数字签名与身份认证 裴士辉 QQ:1628159305
手工签名 签名 印章 手印 2
电子签名 问题 : 电子签名很容易拷贝 要求 : 电子签名是消息的一个函数, 并且只有 Alice 可以计算 Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 3
令银行和 Alice 共享密钥 K 如果 MAC 用于数字签名? 数字签名应该还具备如下特性 : 甚至连银行也不能伪造签名 签名的认证者不应该和签名者共享密钥 Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 4
数字签名方案 定义签名方案是一个由三个算法组成的三元组 ( 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
攻击目标 数字签名方案的安全性 1. 完全破译攻击者能够确定签名者私钥 2. 选择性伪造 (selective forgery) 3. 存在性伪造 (existential forgery) 攻击的模型 1. 唯密钥攻击 (key-only attack) 攻击者只知道签名人的公钥 2. 已知消息攻击 (known message attack) 3. 选择消息攻击 (chosen message attack) 6
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
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
对于 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
RSA 的同态性 (Homomorphic) 令 pk ( n, b), sk ( n, a) 为 RSA 的公钥和私钥. 对于 x1, x2 n和 y1, y2 n, 有 : ( xx) x x modn a a a 1 2 1 2 ( yy) y y modn b b b 1 2 1 2 Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 10
对 RSA 数字签名方案的攻击 uf-cma 攻击者 : 在选择消息模型下存在性伪造的攻击者 m 1 1 sk pk Sig 攻击者 A m 2 2 (m, ) pk Ver b 其中 ( m mm modn, modn) 1 2 1 2 Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 11
另外的问题 在 RSA 签名方案中, 消息 m, 但在实际中要求消息是任意 长度的字符串 n Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 12
Hash 函数 H 的选择 一个好的 hash 函数 H 可能是这样的 : H ( m ) = 如下位串的前 n 位 : m SHA 1 m S HA 11 m SHA1 1 1 1 Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 13
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
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: pp229 235 2 Mihir Bellare, Phillip Rogaway: The Exact Security of Digital Signatures - How to Sign with RSA and Rabin. EUROCRYPT 1996: pp399 416 Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 15
RSA-PSS 签名方案 PSS:Probabilistic Signature standard 概率签名标准 Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 16
RSA-PSS 签名方案的使用 RSA PKCS#1 v2.1. IEEE P1363a ANSI X9.31 RFC 3447 ISO/IEC 9796-2 CRYPTREC NESSIE Mihir Bellare and Phillip Rogaway,Introduction to Modern Cryptography 课程讲义 17
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
针对 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
数字签名标准 DSS 美国国家标准与技术协会 (NIST) 发布的 FIPS 186, 被称为数字签名标准 (DSS) 1991 年提出,1993 年定为 FIPS 186 目前已经发布了 4 个版本 : FIPS 186-1(1996) FIPS 186-2 (2000) FIPS 186-3 (2009)FIPS 186-4(2013) DSS 指标准, DSA 指算法 维基百科 20
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
签名算法 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 4 1 2 ( u u v g mod p)modq Ver H pk 1, if v rmodq ( m,( r, s)) 0, if v rmodq 22
临时密钥 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
临时密钥 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
DSA 的标准化参数的位长度和安全等级 p q hash 输出长度 安全等级 1024 160 160 80 2048 224 224 112 3072 256 256 128 Christof Paar 等著, 深入浅出密码学 25
椭圆曲线数字签名算法 ECDSA 1998 年美国国家标准局 (ANSI) 对于 ECDSA 进行了标准化 2000 年作为 FIPS186-2 得到了批准 26
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
签名算法 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
ECDSA 的位长度和安全等级 n 的长度 ( 位 ) hash 函数的输出长度 192 192 224 224 256 256 384 384 512 512 安全等级 96 112 128 192 256 Christof Paar 等著, 深入浅出密码学 29
数字签名法 美国的犹他州于 1995 年颁布的 数字签名法 是全世界范围内第一部全面规范电子签名的法律 美国 2000 年开始实行 数字签名法, 数字签名法具有法律效率 美国目前已经建立了覆盖全国的 PKI 网络, 联邦 州和大型企业之间的 PKI 实现了桥接 欧洲各国已经建立了自己的 PKI 2001 年欧盟建立了桥接的 CA,2002 年欧盟开始实行 数字签名法 亚洲范围内的日本 韩国和新加坡在 PKI 建设方面起步较早, 这 3 个国家目前已经实现了交叉认证 30
数字签名法 我国的立法从 2002 年开始的, 形成了 中华人民共和国电子签名法 ( 草案 ) 2004 年 8 月 28 日中华人民共和国第十届全国人民代表大会常务委员会第十一次会议通过了 中华人民共和国电子签名法 2005 年 4 月 1 日起施行 31
数字证书 数字证书是由第三方提供的一种确保该公钥是由主体所拥有的一种方式 是绑定共钥和主体的数据结构 通常第三方称为 CA( 证书授权机构 ) CA(Certification Authorities) 32
X.509 证书 X.509 是一个广泛应用的数字证书标准 它有三个版本 : V1: 1988 年发布, 得到了广泛使用 ; V2: 引入了主体和发布者唯一标识的概念 ; V3: 1996 年发布, 支持扩展的概念, 这使得任何人可定义一个扩展并将其包含在证书中 33
版本 序列号 签名算法标识 发布者名称 有效期 主体名称主体的 X.500 命名标准 主体的公钥 签名 X.509 v1 证书的组成 34
主体的 X.500 命名标准 CN 普通名字 OU 机构单位 O 机构 L 机构的位置 ( 城市 ) ST 机构所在的州 C 国家 35
数字证书的签发 验证信息 ( 主体公钥 ) 签名算法 证书 证书机构私钥 36
数字证书的验证 证书信息 Hash() 消息摘要 CA 的公钥?= 证书中的签名 验证算法 消息摘要 37
公钥基础设施 PKI 公钥基础设施 (Public Key Infrastructure), 是一组由硬件 软件 参与者 管理政策与流程组成的基础架构, 其目的在于创造 管理 分配 使用 存储以及撤销数字证书 维基百科 38
PKI 主要组成部分 数字证书认证机构 CA(certificate authority ) 将使用者的个人身分跟公开密钥链结在一起 注册管理中心 RA(registration authority) 对用户的信息进行审查 VA (validation authority) 代表 CA 对用户提供的数字证书进行验证 维基百科 39
公钥基础设施 PKI 维基百科 40
公钥环境下的交互认证 ( 挑战 - 响应 ) 方案 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
公钥环境下的交互认证 ( 挑战 - 响应 ) 方案 4 Alice 验证 : Ver ID Alice r y pk _ Bob( ( ) 2, 2) 若验证通过,Alice 接受, 否则 拒绝 Douhlas R.Stinson 密码学原理与实践 ( 第三版 ) 42
公钥环境下的交互认证方案 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
公钥环境下的交互认证方案 ( 不安全版 ) 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