B
第13章 数字签名和认证协议
• 数字签名
↓
* PKCS#1
↓
* RSA签名示例（in
OpenSSL） ↓
* ElGamal签名方案
↓
• 数字签名标准DSS
↓
• 认证协议
↓
* 专题讨论
↓
B
为了承诺
• 数字签名是密码学发展过程中
的最重要的概念之一。数字签
名可以提供其他方法难以实现
的安全特性，即抗抵赖。
B
数字签名 Digital Signature
• 加密
• 报文鉴别
• 数字签名
– 抵制通信双方的抵赖
– 对方(自己)否认发送过或收到过某个
报文
– 向对方表明自己的身份
B
数字签名
• 消息认证基于共享秘密，不能防
止抵赖
– 只是2方合作抵抗第3方窜改/假冒
• 共享的秘密不具有排他性质
– 双方有同样的不分彼此地能力；因
此对某个报文的存在和有效性，每
一方都不能证明是自己所为，或者
是和自己无关
• 特异性
– 要想实现类似签名的安全能力，必
须使每个人使用独有的秘密
B
考察手写签名的特性
• 签名的含义
– 签名者慎重表达认可文件内容的意
向的行为
• 主要形式
– 手写签名、签章、手指纹印(其他生
物技术)
• 特性
– 不可伪造，特异性
– 不可重用，日期和时间相关性
– 不可改变，能发现涂改、转移意义
或用途
– 不可抵赖，能够质证
– 可仲裁的，可做为法律证据
B
引用
• 第40页：密码故事(the code
book)
B
数字签名: 要适应的新变化
• 数字签名 手写签名
– 数字文件 纸版文件
– 数字小文件 手写字（签章）
– 如何绑定? 同一页纸
• 关于扫描手写字迹、鼠标手写
– No!
B
手写签名的数字化改造
• 数学支持: 签名函数
– 被签署的是文件(大文件)
– 签名生成另外一个文件(小文件)
– 签名过程一定有签署人的身份和某
种秘密(别人不知的)参与
– 简单易行
计算/存储
B
签名验证操作抽象图
• 签名
• 验证
签名函数报文(大)
报文
签名(小)
秘密
报文
签名
验证函数
身份
是
否
身份
B
用私钥加密当作签名
• 主要操作
– 输入 报文明文、私钥
m^d = s
– 输出 报文明文、报文密文(签名)
(m, s)
– 验证
s^e =? m
• 是否满足签名要求的特性
– 不可伪造
– 不可改变
– 抗抵赖
B
散列 || 签名
• 讨论
– 私钥(其实是公钥)的管理: 和身份
绑定、更新等
– 签名过程太慢: 启用散列函数
• 改进
– 对报文的散列值用私钥加密得到
和n等宽的签名值
B
无中心数字签名
• 直接使用自己的私钥加密作为签
名
– 无中心
• 存在问题
– 声称私钥被偷窃而抵赖。虽然可以
给报文添加时间戳，并要求用户必
须及时挂失私钥，但是盗用者仍可
以伪造较早期的签名。
• 引入中心可以有很多优点，同时
也很多缺点。
B
有信任中心帮助的签名
• 优点：可以简化用户的考虑，甚至可以使用对称算法
缺点：中心的安全故障、在线瓶颈、可靠性等问题
B
PKCS# Outline
• RSA public key ：(n，e)
• RSA private key：(n，d)
ed≡1 mod λ(n)
其中λ是n的(素因子-1)的LCM
• I2OSP (Integer-to-Octet-String
primitive)
给定正整数x，输出字节串X=X1X2X3…
x＝2560X1＋2561X2＋2562X3＋…
• OS2IP (Octet-String-to-Integer
primitive)
输入字节串，返回整数值
B
RSA Primitive
• RSAEP ((n, e), m) c = me
mod n
• RSADP ((n,d), c) m = cd
mod n
• RSASP1((n,d), m) s = md
mod n
• RSAVP1((n,e), s) m = se
mod n
B
Encryption Schemes
• ES
RSAES-OAEP (Optimal Asymmetric Encryption
Padding)
• new, recommended
RSAES-PKCS1-v1_5
• obsolete
• RSAES-OAEP
EME-OAEP＋
RSAEP/RSADP
• RSAES-PKCS1-v1_5
EME-PKCS1-v1_5＋
RSAEP/RSADP
B
RSAES-OAEP
• RSAES-OAEP-ENCRYPT((n, e), M, L)
– Option: Hash of hLen-byte
– MGF mask generation function (output, an octet string)
– mLen <= k-2hLen-2
– L optional label to be associated with the message
• |L| <= 2^61-1 octets for SHA-1
– EME-OAEP encoding
• EM = 0x00 || maskedSeed || maskedDB
– m = OS2IP (EM)
– c = RSAEP ((n, e), m)
– C = I2OSP (c, k)
• RSAES-OAEP-DECRYPT (K＝(n, d), C, L)
BEME-OAEP encoding
operation
B
RSAES-PKCS1-v1_5
• RSAES-PKCS1-V1_5-
ENCRYPT((n, e), M)
– mLen <= k – 11
– PS是k-mLen-3字节(至少8字节)伪
随机数
– EM = 0x00 || 0x02 || PS || 0x00 ||
M
– m = OS2IP(EM)
– c = RSAEP((n, e), m)
– C = I2OSP(c, k)
• RSAES-PKCS1-V1_5-
DECRYPT((n, d), C)
BSignature schemes with
appendix
• SS
RSASSA-PSS (Probabilistic
Signature Scheme)
• new, recommended
RSASSA-PKCS1-v1_5
• obsolete
• RSASSA-PSS
EMSA-PSS＋RSASP1/RSAVP1
• RSASSA-PKCS1-v1_5
EMSA-PKCS1-v1_5＋
RSASP1/RSAVP1
B
RSASSA-PSS
• RSASSA-PSS-SIGN (K=(n,d),
M)
– EM = EMSA-PSS-ENCODE (M,
modBits – 1)
–m = OS2IP (EM)
– s = RSASP1 (K, m)
– S = I2OSP (s, k)
• RSASSA-PSS-VERIFY ((n, e),
M, S)
B
RSASSA-PKCS1-v1_5
• RSASSA-PKCS1-V1_5-SIGN (K
＝(n, d), M)
– EM = EMSA-PKCS1-V1_5-
ENCODE (M, k)
– m = OS2IP (EM)
– s = RSASP1 (K, m)
– S = I2OSP (s, k)
• RSASSA-PKCS1-V1_5-
VERIFY((n, e), M, S)
BEncoding methods for signatures
with appendix
• EM
– EMSA-PSS
– EMSA-PKCS1-v1_5
• EMSA-PSS
– EMSA-PSS-ENCODE (M, emBits)
– EMSA-PSS-VERIFY (M, EM,
emBits)
• EMSA-PKCS1-v1_5
– EMSA-PKCS1-v1_5-ENCODE (M,
emLen)
BEMSA-PSS encoding
operation
B
EMSA-PKCS1-v1_5
• EMSA-PKCS1-v1_5-ENCODE
(M, emLen)
– Option: Hash of hLen-byte
– emLen at least tLen + 11
– H = Hash (M)
– T = HashID＋H (编码)
• DigestInfo ::= SEQUENCE {
digestAlgorithm
AlgorithmIdentifier,
digest OCTET STRING }
– PS: emLen-tLen-3(8+B) octets with
value 0xff
– EM = 0x00 || 0x01 || PS || 0x00 || T
B
对HASH的编码
(in EMSA-PKCS1-v1_5)
• MD2 ref layman’s guide
30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 02 05 00 04 10 || H
• MD5
30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 05 05 00 04 10 || H
• SHA-1
30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 || H
• SHA-256
30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 || H
• SHA-384
30 41 30 0d 06 09 60 86 48 01 65 03 04 02 02 05 00 04 30 || H
• SHA-512
30 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 || H
B
Reading
B
RSA签名示例
用OpenSSL函数签名的例子
• 读入或产生RSA的key
• 签署一个报文
• 验证之
B
RSA四种操作总结
• 公钥加密 RSA_public_encrypt
()
• 私钥解密 RSA_private_decrypt
()
• 私钥加密 RSA_private_encrypt
()
• 公钥解密 RSA_public_decrypt
()
• 签名 RSA_sign() (私钥
加密)
• 验证 RSA_verify() (公
钥解密)
B
{ 回顾ElGamal加密体制 }
• 准备
– 素数p，Zp*中本原元g，公开参数
– 私钥a，公钥b=ga mod p
• 加密
– 对明文1<=m<=p-1，选随机数k
– 密文(c1, c2)
c1=gk mod p, c2=mbk mod p
• 解密
– m＝c2 (c1a)-1＝mbk ((gk)a)-1
＝m(ga)k (g-ka)
＝m mod p
B
ElGamal签名方案
• Zp满足离散对数问题难解，α是生
成元
设P ＝ Zp* ，A＝ Zp*×Zp-1
K ＝{(p,α, a,β), β=αa (mod p)
}
私钥是a
• 签名时，取秘密随机数k∈Zp-1*，
定义sig(x,k) = (γ,δ),
＝(αk mod p, (x-aγ)k-1 mod (p-
1))
• 验证
ver(x, (γ,δ))： βγγδ＝?αx mod
p
B
验证正确性证明
• 如果 (x,γ,δ)是真实签名
βγγδ＝αaγαkδ＝αaγ+kδ
而 δ ＝ (x-aγ) k-1 mod Φ(p)
即 aγ＝x-kδ mod Φ(p)
故 βγγδ ＝ αnΦ(p)+x-kδ+kδ
＝αnΦ(p)+x
＝αnΦ(p)αx
＝ αx mod p
• 其实δ就是签名时从 kδ＋aγ＝
x解出来得
B
签名计算实例
• p＝467，α＝2，a＝127，则
β＝αa mod p ＝ 2127 mod 467 ＝
132
• 签名x＝100，取k＝213(注: k得和
p-1互素)，则
k-1＝213-1 mod 466 = 431
γ＝αk mod p ＝ 2213 mod 467
＝ 29
δ＝ (x-aγ) k-1 mod Φ(p)
＝ (100-127×29)×431 mod
466
＝51
签名值：（100，(29,51)）
B
验证计算实例
• p＝467，α＝2，a＝127, β＝
132
（x,(γ,δ)）＝（100，(29,51)）
• 判断是否：βγγδ＝αx mod p
事实上
βγγδ＝13229×2951＝189 mod
467
αx＝2100＝189 mod 467
• 而且，如果（100，(29,51)）的
任何改变都会导致验证失败
B
Subject links
• DSS/DSA
– FIPS 186
• P1363
–
3/
B
数字签名标准
• Digital Signature Standard
（DSS）
Digital Signature Algorithm
（DSA）
• DSS标准－DSA
– FIPS 186 NIST 1991 1993
– 只能签名，不能加密
• 概念对比
RSA：M＋Eki(H(M))，ki是私钥
DSS：M＋Eki(H(M), k)，ki是私钥
k是随机数
B
图示 RSA vs. DSS
•
B
DSA
• 准备
– 素数p，约512＋比特；
– 素数q，约160比特，要求是p-1的因子
– 选择g＝h^(p-1/q) mod p
• 密钥
– 用户私钥x，x<q
– 公钥y，y＝g^x mod p
• 签名，对报文M
– 产生随机数k
– r＝(g^k mod p) mod q
– s= k-1 (H(M)+xr) mod q
– (r，s)即是签名，连同明文的M
• 验证，测试是否v＝r’，其中
– v＝g^u1×y^u2 mod p mod q
u1＝H(M’) ×s’-1 mod q
u2＝r’×s’-1 mod q
B
DSA Figure
•
B
练习：DSA算法 in OpenSSL
• OpenSSL支持DSA签名算法
DSA API in OpenSSL
– int DSA_sign(int type,const unsigned char *dgst,int
dlen, unsigned char *sig, unsigned int *siglen, DSA
*dsa);
– int DSA_verify(int type,const unsigned char *dgst,int
dgst_len, const unsigned char *sigbuf, int siglen, DSA
*dsa);
• 练习给出使用DSA签名的例子程序，演示
– DSA密钥产生
– 对文件签名
– 验证
B
认证协议
• （消息认证）
• 身份是在加密之前需要首先进行
的步骤，为的是防假冒身份。认
证的思路是基于对方知道某个秘
密。这个秘密你可能知道，也可
能你并不知道，但是你必须能判
断对方是否正确知晓。
• 比如如何鉴别在网上遇见的自称
是你同学的人？你可以提问几个
问题(班主任的名字等)，看他能
否正确回答。当然，这种基于周
(双方)知事实的鉴别有其局限性。
B
帐号口令机制（以POP3为例）
• 准备
– 服务器知道所有用户的帐号、口令
– 用户知道自己的帐号、口令
• 用户连接服务器
• 服务器发送hello信息
• 用户声明自己的身份帐号
• 服务器判断是否有效，
并决定是否要求口令
• 用户提交口令
• 服务器判断口令是否匹配，
从而决定是否授权
+OK POP3 ready
USER xxxx
+OK
PASS yyyy
+OK ????(eyou mta)
…
B
B
B
帐号口令机制的改进考虑
• 改进 (争取不要传输直接的明文口
令)
– 传输口令的变化: 口令的散列值
– 传输口令的变化: 口令和时间的散列
值
– 由服务器发起挑战: 一随机数
用户返回散列值 [随机数 || 口令]
– 客户也可掺入自己的随机因素，即
[随机数 || 口令 || 随机数’] || 随机数’
• CRAM
Challenge-Response Authentication
Mechanism
一般用户之间的基于共享秘密的鉴别，
这个思路也用在基于公钥的鉴别体
制中。
B
CHAP
•
B
使用对称加密和KDC的鉴别
• Needham-Schroeder
1 A－>K IDa || IDb || Na
2 A<－K
Eka(Ks||IDb||Na||Ekb(Ks||IDa))
3 A－>B Ekb(Ks||IDa)
4 A<－B Eks(Nb)
5 A－>B Eks(f(Nb))
• 缺点
– 若对手已知某旧的Ks，则其可从第
3步开始模仿A
• 改进
– Denning’ Kehne’
B
Needham-Schroeder协议
• NS协议是最著名的早期协议
• NSSK - Needham Schroeder
Symmetric Key
• NSPK - Needham-Schroeder
Public Key
B
Denning'
1 A －>K IDa || IDb
2 A<－ K
Eka(Ks||IDb||T||Ekb(Ks||IDa||T))
3 A －>B Ekb(Ks||IDa||T)
4 A<－ B Eks(Nb)
5 A －>B Eks(f(Nb))
需要一个网络全局时钟T
B
Kehne'
1 A －> B IDa || Na
2 B －> K IDb || Nb ||
Ekb(IDa||Na||Tb)
3 A<－ K Eka(IDb||Na||Ks||Tb)
||
Ekb(IDa||Ks||Tb) || Nb
4 A －> B Ekb(IDa||Ks||Tb) ||
Eks(Nb)
不需全局同步时钟
B
使用公钥(私钥)鉴别身份
• 准备
– 公钥公开发布
– 私钥私人秘藏
• 鉴别过程
– 你有真实对方的公钥
– 让对方证明他有相应的私钥
– 怎么办？让对方签个名来看看即可
• 注意随便签署报文是很危险的!
– 挑战-应答机制
• SIGk(Na||Nb)
B
A鉴别所谓的B是否是真正的B
• (A事先知道真实B的真实公钥e，这是前提)
• A和对方建立连接，A现在要核实对方是否是B
– 现在只能说对方可能是B，或仅仅是对方自己声称自己
是B
• A只需核实对方是否有私钥d(和e对应的那个d)即可
– 只有真实的B才有相应的d，别人不可能拥有d
– A需要一种旁敲侧击的手段来试试对方是否拥有d
• A于是决定请对方用d签个名来看看
– A －>B：随机数m (即随机报文)
– A <－ B：s＝signature(m, d)
– A判断签名(m, s)是否是B的真实签名，从而知道对方是
否是真正的B
* 不要随便对别人给你的报文签名
– 那个报文可能对你不利，可能是张欠条 (当然你欠人家
的)
– 因此B必须在签署消息m前用自己的随机数干扰一下
B
专题讨论
• 电子签名法
• Windows中的文件防篡改机制
• Linux中的系统文件保护
• 思考：MD5算法分析进展对签名
的影响
• 预习：
– 文件交换及存储的通用混合密码体
制方案
B
电子签名法
B
Windows系统文件的签名
• “Windows文件保护能够检测到其他程序要替换或
移动受保护的系统文件的意图，那么它是依据什
么来检测的呢？
– 其实，Windows文件保护是通过检测文件的数字签名，
以确定新文件的版本是否为正确的Microsoft版本，如
果文件版本不正确，Windows文件保护会自动调用
dllcache文件夹或Windows中存储的备份文件替换该
文件，如果Windows文件保护无法定位相应的文件，
那么会提示用户输入该位置或插入安装光盘。”
• Windows的核心文件 vs.
有些非windows自带的驱动程序（可能导致问题）
• 开启和关闭保护
B
Linux中的系统文件保护
• 练习：
Linux系统中是如何保护系统
文件
不受侵害的？
用了Hash或是签名吗？
• Tripwire
B
MD5算法分析进展
• 思考和课堂讨论：
MD5算法分析进展对签名的影响
B
预习：邮件中的应用
• 侧重保密
A－B：Eks(M) || Ekb(Ks)， Kb是b
的公钥
• 侧重鉴别，不保密
A－B：M || Eka(H(M))，ka是a的
私钥
• 既保密又签名鉴别
A－B：Eks(M || Eka(H(M)))||
Ekb(Ks)
其中a的私钥，b的公钥
• PGP
* 邮件应用的特点是非在线、非交
互
B
Links
B
关键词 Key Terms
• arbiter timestamp
• nonce replay attack
• arbitrated digital signature
• direct digital signature
• digital signature
• digital signature algorithm (DSA)
• digital signature standard (DSS)
• mutual authentication
• one-way authentication
• suppress-replay attack
B
小结
• 数字签名的法律地位已经被确立。
• 在签名算法前一般都先对消息执
行Hash算法，因此Hash算法的
安全性也备受关注，尤其是
MD5分析上的重大进展。
