(1)参数的选取：p,q,e,d。 (2)不可使用公共模数。 (3)明文的熵要尽可能的大。 (4)尽量使用散列函数。 (5)若RSA的模数n=2k bits，则：
❖ 若消息的长度<k bits，采用带消息恢复的RSA签名 ❖ 否则，采用带附录的RSA签名
兰州交通大学电子与信息工程学院
2020/5/13
兰州交通大学电子与信息工程学院
2020/5/13
5/47
➢数字签名的产生
数字签名
兰州交通大学电子与信息工程学院
重要证书、证件采用的防 伪技术是使用特殊材料或 者信息隐藏等
网 络
1.否认 2.伪造 3.冒充 4.篡改
2020/5/13
6/47
➢数字签名标准
ISO/IEC 9796是数字签名的第一个国际标准， 1991公布。
2020/5/13
22/47
➢RSA的签名生成与验证
实体A执行如下操作：
1.计算取值在区间0,n 1内的整数m~ Rm
2.计算s m~d mod n 3.A对m的签名为s
为验证A的签名s且恢复消息m，B执行如下操作：
1.获得A的可信公钥(n, e) 2.计算m~ se mod n 3.验证m~ M R ;否则拒绝接受签名
记号 M Ms S
R
MR
R-1 R h Mh
含义 消息空间 待签空间 签名空间 从M到Ms的1-1映射，称为冗余函数 R的像（即M R=Im（R））
R的逆（即R-1 ： M R→ M ） 签名指标集 定义域为M的单向函数 h的像（即h： M → M h）；
兰州交通大学电子与信息工程学院
2020/5/13
兰州交通大学电子与信息工程学院
2020/5/13
24/47
➢RSA签名和RSA加密的异同点
➢ 相同点
都使用一对密钥：公钥(n，e)和私钥d
➢ 不同点
RSA加密：用公钥加密，用私钥解密，多人加密，一人解密 s=me mod n m=sd mod n
RSA签名：用私钥签名，用公钥验证，一人签名，多人验证 s=md mod n m=se mod n
兰州交通大学电子与信息工程学院
2020/5/13
10/47
➢准备知识
1.Hash函数（即杂凑函数）（见参考书籍1/1.9） 2.冗余函数 3.整数因子分解问题（见参考书籍1/3.2） 4.计算两个整数的最大公因子的欧几里得算法 （见参考书籍1/2.1.4） 5.扩展的欧几里得算法（见参考书籍1/2.107） 6.模n平方根的困难性（见参考书籍1/3.5.2） 7.求a模素数p的平方根（见参考书籍1/3.39） 8.模n的二次剩余集(见参考书籍4/11.3.9) 9.剩余类集合 10.勒让德符号(见参考书籍4/11.3.10) 11.雅可比符号(见参考书籍4/11.3.11)
兰州交通大学电子与信息工程学院
2020/5/13
25/47
➢有关RSA签名的可能攻击
整数因子分解 (公钥为(n，e) )
de≡1 mod (n)
❖ 分解n=p×q
❖ 再计算出(n)=(p－1)(q－1) ❖ 由(n)和e，推导出私钥d
为了防止此攻击，签署 者必须选择p和q，使得 分解n是一个计算上不 可行的任务。
RSA的乘性质
❖ s1=m1d mod n
为了防止此攻击，要求冗余
❖ s2=m2d mod n
函数R的非乘性。
❖ (s1×s2)=(m1×m2)d mod n
❖ 要求冗余函数R具有非乘性，即R(a×b)≠R(a) ×R(b)
(必要条件）
兰州交通大学电子与信息工程学院
2020/5/13
26/47
➢实际中的RSA签名
3.剩余类的集合 4.合数
。而e必须满足gcd(e, )=1，所以
e是奇数。
5.勒让德符号
6.雅可比符号
兰州交通大学电子与信息工程学院
2020/5/13
29/47
➢Rabin公钥签名方案的密钥生成
概要：每个实体生成各自的公钥和相应私钥。 实体A执行如下操作：
1.随机产生两个不同的大素数p和q 2.计算n=pq 3.A的公钥是n，私钥是(p，q)
计算 n=p×q，其欧拉函数值(n)=(p－1)(q－1) 随机选一整数e，1e<(n)，满足gcd((n), e)=1
利用扩展的欧几里德算法，计算惟一的整数d，
1＜d ＜(n),满足de ≡1 mod (n)
公钥为(n，e) ；私钥为d。(p, q不再需要，可以 销毁。)
兰州交通大学电子与信息工程学院
2020/5/13
2/47
➢主要内容：
11.1 引言 11.2 数字签名机制的框架 11.3 RSA和相关的签名方案 11.4 Fiat-Shamir签名方案 11.5 DSA和相关签名方案 11.6 一次数字签名 11.7 其他数字签名 11.8 带附加功能的签名
兰州交通大学电子与信息工程学院
2020/5/13
4.恢复m R1m~
兰州交通大学电子与信息工程学院
2020/5/13
23/47
➢RSA签名实例讲解
1）若Bob选择了p=11和q＝13 2）那么，n=11 × 13=143, (n)=10×12＝120 3）再选取一个与(n)=120互质的数,例如e=7 4）找到一个值d=103满足e×d≡1 mod (n)
1994年美国政府正式颁发了美国数字签名标准 DSS(Digital Signature Standard)
1995年我国也制定了自己的数字签名标准 (GB15851-1995)
2004年我国颁发《中华人民共和国电子签名法》
兰州交通大学电子与信息工程学院
2020/5/13
7/47
➢数字签名的原理
兰州交通大学电子与信息工程学院
2020/5/13
20/47
➢RSA签名方案
RSA是以它的三个发明者Ron Rivest，Adi Shamir和 Leoard Adleman的名字命名。
RSA算法既可以用于加密，也可以用于数字签名。因为 其加密变换是双射的，所以只要互换加密与解密的角色 就可以得到数字签名方个消息的签名，
但敌手对被伪造签名所对应的消息几乎没有控 制能力
兰州交通大学电子与信息工程学院
2020/5/13
19/47
11.3 RSA和相关签名方案
RSA签名方案 有关RSA签名的可能攻击 实际中的RSA签名 Rabin签名方案 ISO/IEC 9796规范 PKCS #1规范
3/47
11.1 引言
➢本章要研究的问题
本章要考虑的技术是如何设计手写签名的数字相似 物——数字签名
兰州交通大学电子与信息工程学院
2020/5/13
4/47
➢研究背景
计算机网络的产生把我们带进一个信息化社会。在信 息社会里，大量传输和存储信息的安全保密和防伪问题成 为人们关注的一个重要课题。
普遍的观点认为，现代密码技术是解决信息安全的最 有效地方法，因此，密码学的研究成为当前国际上的一个 热点。
15/47
➢带附录的数字签名方案
兰州交通大学电子与信息工程学院
2020/5/13
M:消息空间={m} Mh：消息摘要空间={ } S：消息签名空间={s*} h: Hash函数 SA,k: 签名变换(1-1映射) VA:验证变换
16/47
➢带消息恢复的数字签名方案
M:消息空间={m} MMRS：：待消签息空的间冗余值空间={ } S：消息的签名空间={s*} R: 冗余函数（可逆） (1-1映射) SA,k: 签名变换(1-1映射)
兰州交通大学电子与信息工程学院
2020/5/13
11/47
11.2 数字签名机制的框架
➢基本定义
1.数字签名是一个数字串，它将一条数字形式的消息与某发 起实体相关联。
2.数字签名生成算法是产生数字签名的某种方法。
3.数字签名验证算法是检验一个数字签名是否可信（即是否 真的是由指定的实体生成）的某种方法。
13/47
➢数字签名方案的分类
带附录的数字签名方案：要求初始消息作为验 证算法的输入
❖ DSA、ElGamal和Schnorr签名方案 ❖ 消息可以是任意长度
带消息恢复的数字签名方案：消息可从签名自 身恢复，不要求初始消息作为验证算法的输入
❖ RSA、Rabin等公钥签名方案 ❖ 通常消息的长度固定
4.数字签名方案（或机制）由签名生成算法和相关的验证算 法组成。
5.数字签名的签名过程包括数字签名生成算法，以及某种将 数据格式化为可签名消息的方法。
6.数字签名的验证过程包括验证算法，以及某种由消息恢复 数据的方法。
兰州交通大学电子与信息工程学院
2020/5/13
12/47
➢数字签名机制中的记号
（7×103=721，除以120余1） 5）（n=143,e=7）为公钥，d=103为私钥。 6）Bob在一个目录中公开公钥：n=143和e=7 7）现假设Bob想发送消息85给Alice，他用自己的密钥
（d=103）进行签名：85103(mod 143)=6，于是发送消息85 和签名6给Alice 8）当Alice接收到消息85和签名6时，用Bob公开的公钥 （e＝7）进行验证：67（mod 143)=85，跟Bob发送的消 息一致，于是确定该消息是由Bob所发送，且没有被修改。
兰州交通大学电子与信息工程学院
2020/5/13
17/47
➢从带消息恢复的方案得到带附录的签名方案
先杂凑消息m； 再对该杂凑值h(m)签名
兰州交通大学电子与信息工程学院
2020/5/13
18/47
➢签名方案的攻击类型
敌手的目标是：伪造签名