人为小参数的RSA签名
密钥生成
Page 11
实体A选取素数 p 7927, q 6997，计算 n pq 55465219, 7926 6996 55450296 A选择 e 5，求解 ed 5d 1 mod55450296 得 d 44360237。 A的公钥是 n 55465219, e 5 ；私钥是 d 44360237 。
2

d 2 d 3
d
d
。
All rights reserved © 2010, Southeast University
实际中的RSA签名（1）—重分组问题（1）
Page 13
（重分组问题）设n 8387 7499 62894113,e 5,d 37726937；设 n 55465219, e 5, d 44360237 m 1368797 。 是带冗余度的消息，将 用A的私钥签名，然后用B的公钥加密。 A做下列计算：
– 选择元素 g ¢ *p ，并计算 g – 若 1 ，则返回上一步。
p1 / q
mod p 。
随机选取数 a 使得 1 a q 1 。 计算 y a mod p 。 A的公钥是 p, q, , y ；私钥是 a 。
All rights reserved © 2010, Southeast University
Page 3
数字签名机制的框架
RSA签名方案
数字签名算法DSA
All rights reserved © 2010, Southeast University
数字签名机制的框架（1）
Page 4
数字签名必须具备的特征
必须能验证签名者、签名日期和时间 必须能认证被签的消息内容 签名应能由第三方仲裁，以解决争执
° R m 。 m
验证。为验证A的签名 s 且恢复消息 m，实体B应当：
获得A的可信公钥 n, e 。 ° se mod n 。 计算 m ° M ；否则拒绝接受签名。 验证 m R ° 。 恢复 m R 1 m
All rights reserved © 2010, Southeast University
数字签名机制的框架（3）—带附录的数字签名
Page 6
带附录的数字签名，必须具有以下性质：
对每个 k R，都可以有效地计算 S 。 可以有效地计算 V 。 除A之外的其他实体要找m M和 s S使得 为真，是计算上不可行的。
A, k
A
*
° , s* VA m
（其中
° h m m ）
对每个 k R，都可以有效地计算 S 。 可以有效地计算 V 。 除A之外的其他实体要找任一个 s S使得 V s M ，是计算 上不可行的。
A, k
A
*
* A
R
M m
R
M
m
R

S A, k
S
s* S A, k m

MS
带消息恢复的数字签名方案
All rights reserved © 2010, Southeast University
获得A的可信公钥 p, q, , y 。
验证 0 r q 和
Байду номын сангаас
0 s q ；否则拒绝该签名。
计算 w s1 mod q 和 h m 。 计算 u1 wgh m mod q 和 计算 v u y u
1 2
u2 rw mod q。
M m
h
Mh m
S A, k
S
*

s S A, k m

M h S
VA
真
伪
签名过程
验证过程
All rights reserved © 2010, Southeast University
数字签名机制的框架（4）—带消息恢复数字签名
Page 7
带消息恢复的数字签名，必须具有以下性质：
数字签名应满足的条件
签名必须是与消息相关的二进制串 签名必须使用发送方某些独有的信息，以防伪造和否认 产生数字签名比较容易 识别和验证签名比较容易 伪造数字签名在计算上是不可行的 保存数字签名的拷贝是可行的
All rights reserved © 2010, Southeast University
Page 1
数字签名、认证与密钥管理
All rights reserved © 2010, Southeast University
内容提要
Page 2
数字签名
消息认证与认证协议
密钥交换与管理
All rights reserved © 2010, Southeast University
数字签名
数字签名机制的框架（2）
Page 5
数字签名方案的分类
带附录的数字签名方案：要求初始消息作为验证算法的输 入。 带消息恢复的数字签名方案：消息可从签名自身恢复。
随机化的 带消息恢复 确定性的 数字签名方案 随机化的 带附录 确定性的
All rights reserved © 2010, Southeast University
mod p mod q 。
当且仅当 v r 时接受签名。
签名验证可行性证明。
All rights reserved © 2010, Southeast University
人为小参数的DSA签名生成（1）
Page 20
密钥生成。
实体A选取素数 p 124540019, q 17389 ，满足 q 整除 p 1 。 A选择随机元 g 110217528 ¢ ，计算 g g mod p 10083255 。 A选择随机数 a 12496 满足 1 a q 1 ，并计算 y mod p 10083255 mod124540019 119946265 。 A的公钥是 p 124540019, q 17389, 10083255, y 119946265 ，而A的私钥 是 a 12496 。
All rights reserved © 2010, Southeast University
实际中的RSA签名（3）
Page 15
冗余函数 带附录的RSA数字签名
All rights reserved © 2010, Southeast University
DSA签名方案
Page 16
算法描述 DSA的安全性 DSA的性能特点
All rights reserved © 2010, Southeast University
数字签名算法DSA描述（1）
Page 17
算法1：DSA的密钥生成
概要：每个实体产生各自的公钥和相应私钥。 实体A执行如下操作：
选择素数 q 满足 2159 q 2160。 选取 t 使得 0 t 8 ，并选择素数 p 满足 251164t p 251264t ，且 q 整除 p 1 。 选择 ¢ *p中唯一 q 阶循环群的生成元 。
mod55465219 30729435
签名验证
° s mod n 30729435 mod55465219 31229978 B计算 m ° 31229978 B接受该签名，并恢复出 m R m 。
e 5
1
All rights reserved © 2010, Southeast University
$ s c d B mod nB 3884223544360237 mod 55465219 4382681
eA µ $ m s mod nA 43826815 mod 62894113 54383568
µ 观察发现 m m 。原因是s比模数 n 大，出现概率 n n / n 0.12
RSA签名方案
Page 8
算法描述 有关RSA签名的可能攻击
实际中的RSA签名
All rights reserved © 2010, Southeast University
RSA签名算法描述（1）
Page 9
算法1：RSA签名方案的密钥生成
概要：每个实体生成各自的RSA公钥和相应私钥。 实体A执行如下操作：
随机产生大小相近的两个不同大素数 p 和 q 。 计算 n pq 和 p 1 q 1 。 随机选取数 e,1 e ，满足 gcd e, 1 。 利用扩展的欧几里得算法，计算唯一的整数 d ,1 d ，满足 ed 1 mod 。 A的公钥是 n, e ；私钥是 d 。
A A A B B B

s md A mod nA 136879737726937 mod62894113 59847900 c seB mod nB 598479005 mod55465219 38842235
。 。 。 。
A B A
B做如下计算以恢复消息和验证签名：
有关RSA签名的可能攻击
Page 12
整数因子分解 RSA的乘性质 不安全的冗余函数： R m m2t
敌手打算伪造消息的签名m ，它知道 n 而不知道 d 。 ° R m m2 mw 应用扩展的欧几里得算法。 对n和 m ° r 在算法的每一步计算整数 x, y 和 r 使得 xn ym 。 如果敌手已获得合法签名s m mod n 和 s m mod n ，就可以计 算 m 的签名： s m rw r