《数字签名技术》PPT课件.pptVIP

1 47 兰州交通大学电子与信息工程学院 2020 2 9 应用密码学手册 数字签名 2 47 兰州交通大学电子与信息工程学院 2020 2 9 参考书籍 HandbookofAppliedCryptography Chapter11 数字签名理论 赵泽茂 应用密码学 孙淑玲 应用密码学 协议 算法与C源程序 W 迪菲 3 47 兰州交通大学电子与信息工程学院 2020 2 9 11 1引言11 2数字签名机制的框架11 3RSA和相关的签名方案11 4Fiat Shamir签名方案11 5DSA和相关签名方案11 6一次数字签名11 7其他数字签名11 8带附加功能的签名 主要内容 4 47 兰州交通大学电子与信息工程学院 2020 2 9 11 1引言 本章要研究的问题 本章要考虑的技术是如何设计手写签名的数字相似物 数字签名 5 47 兰州交通大学电子与信息工程学院 2020 2 9 研究背景 计算机网络的产生把我们带进一个信息化社会 在信息社会里 大量传输和存储信息的安全保密和防伪问题成为人们关注的一个重要课题 普遍的观点认为 现代密码技术是解决信息安全的最有效地方法 因此 密码学的研究成为当前国际上的一个热点 6 47 兰州交通大学电子与信息工程学院 2020 2 9 数字签名的产生 重要证书 证件采用的防伪技术是使用特殊材料或者信息隐藏等 网络 1 否认2 伪造3 冒充4 篡改 数字签名 7 47 兰州交通大学电子与信息工程学院 2020 2 9 数字签名标准 ISO IEC9796是数字签名的第一个国际标准 1991公布 1994年美国政府正式颁发了美国数字签名标准DSS DigitalSignatureStandard 1995年我国也制定了自己的数字签名标准 GB15851 1995 2004年我国颁发 中华人民共和国电子签名法 8 47 兰州交通大学电子与信息工程学院 2020 2 9 数字签名的原理 9 47 兰州交通大学电子与信息工程学院 2020 2 9 数字签名的功能 1 机密性2 完整性3 身份验证4 防伪造5 防抵赖6 防重放攻击 10 47 兰州交通大学电子与信息工程学院 2020 2 9 数字签名技术的应用 用户登录认证数据完整性不可抵赖性大型网络的公钥证书中电子交易和电子货币等领域 11 47 兰州交通大学电子与信息工程学院 2020 2 9 准备知识 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 12 47 兰州交通大学电子与信息工程学院 2020 2 9 11 2数字签名机制的框架 基本定义 1 数字签名是一个数字串 它将一条数字形式的消息与某发起实体相关联 2 数字签名生成算法是产生数字签名的某种方法 3 数字签名验证算法是检验一个数字签名是否可信 即是否真的是由指定的实体生成 的某种方法 4 数字签名方案 或机制 由签名生成算法和相关的验证算法组成 5 数字签名的签名过程包括数字签名生成算法 以及某种将数据格式化为可签名消息的方法 6 数字签名的验证过程包括验证算法 以及某种由消息恢复数据的方法 13 47 兰州交通大学电子与信息工程学院 2020 2 9 数字签名机制中的记号 14 47 兰州交通大学电子与信息工程学院 2020 2 9 数字签名方案的分类 带附录的数字签名方案 要求初始消息作为验证算法的输入DSA ElGamal和Schnorr签名方案消息可以是任意长度带消息恢复的数字签名方案 消息可从签名自身恢复 不要求初始消息作为验证算法的输入RSA Rabin等公钥签名方案通常消息的长度固定 15 47 兰州交通大学电子与信息工程学院 2020 2 9 数字签名方案的分类 数字签名方案 带消息恢复 带附录 随机化的 确定性的 随机化的 确定性的 针对一个数字签名方案 如果有 R 1 则称此签名方案是随机化数字签名方案 否则称它是确定性数字签名方案 16 47 兰州交通大学电子与信息工程学院 2020 2 9 带附录的数字签名方案 M 消息空间 m Mh 消息摘要空间 S 消息签名空间 s h Hash函数SA k 签名变换 1 1映射 VA 验证变换 17 47 兰州交通大学电子与信息工程学院 2020 2 9 带消息恢复的数字签名方案 M 消息空间 m MR 消息的冗余值空间 MS 待签空间S 消息的签名空间 s R 冗余函数 可逆 1 1映射 SA k 签名变换 1 1映射 18 47 兰州交通大学电子与信息工程学院 2020 2 9 从带消息恢复的方案得到带附录的签名方案 先杂凑消息m 再对该杂凑值h m 签名 19 47 兰州交通大学电子与信息工程学院 2020 2 9 签名方案的攻击类型 敌手的目标是 伪造签名完全攻克 敌手能计算出私钥选择性伪造 敌手能对一个特殊的消息或者预先选定的一类消息构造出正确的签名存在性伪造 敌手能伪造至少一个消息的签名 但敌手对被伪造签名所对应的消息几乎没有控制能力 20 47 兰州交通大学电子与信息工程学院 2020 2 9 11 3RSA和相关签名方案 RSA签名方案有关RSA签名的可能攻击实际中的RSA签名Rabin签名方案ISO IEC9796规范PKCS 1规范 21 47 兰州交通大学电子与信息工程学院 2020 2 9 RSA签名方案 RSA是以它的三个发明者RonRivest AdiShamir和LeoardAdleman的名字命名 RSA算法既可以用于加密 也可以用于数字签名 因为其加密变换是双射的 所以只要互换加密与解密的角色就可以得到数字签名方案 RSA的安全性基于大数分解的困难性 该算法已经经受住了多年深入的密码分析 密码分析者既不能证明也不能否认RSA的安全性 这恰恰说明该算法有一定的可信度 22 47 兰州交通大学电子与信息工程学院 2020 2 9 RSA签名方案的密钥生成 实体A执行如下操作 随即产生大小相近的两个不同大素数p和q计算n p q 其欧拉函数值 n p 1 q 1 随机选一整数e 1 e n 满足gcd n e 1利用扩展的欧几里德算法 计算惟一的整数d 1 d n 满足de 1mod n 公钥为 n e 私钥为d p q不再需要 可以销毁 23 47 兰州交通大学电子与信息工程学院 2020 2 9 RSA的签名生成与验证 实体A执行如下操作 为验证A的签名s且恢复消息m B执行如下操作 24 47 兰州交通大学电子与信息工程学院 2020 2 9 RSA签名实例讲解 1 若Bob选择了p 11和q 132 那么 n 11 13 143 n 10 12 1203 再选取一个与 n 120互质的数 例如e 74 找到一个值d 103满足e d 1mod n 7 103 721 除以120余1 5 n 143 e 7 为公钥 d 103为私钥 6 Bob在一个目录中公开公钥 n 143和e 77 现假设Bob想发送消息85给Alice 他用自己的密钥 d 103 进行签名 85103 mod143 6 于是发送消息85和签名6给Alice8 当Alice接收到消息85和签名6时 用Bob公开的公钥 e 7 进行验证 67 mod143 85 跟Bob发送的消息一致 于是确定该消息是由Bob所发送 且没有被修改 25 47 兰州交通大学电子与信息工程学院 2020 2 9 RSA签名和RSA加密的异同点 相同点 都使用一对密钥 公钥 n e 和私钥d 不同点 RSA加密 用公钥加密 用私钥解密 多人加密 一人解密s memodnm sdmodnRSA签名 用私钥签名 用公钥验证 一人签名 多人验证s mdmodnm semodn 26 47 兰州交通大学电子与信息工程学院 2020 2 9 有关RSA签名的可能攻击 整数因子分解 公钥为 n e de 1mod n 分解n p q再计算出 n p 1 q 1 由 n 和e 推导出私钥dRSA的乘性质s1 m1dmodns2 m2dmodn s1 s2 m1 m2 dmodn要求冗余函数R具有非乘性 即R a b R a R b 必要条件 为了防止此攻击 签署者必须选择p和q 使得分解n是一个计算上不可行的任务 为了防止此攻击 要求冗余函数R的非乘性 27 47 兰州交通大学电子与信息工程学院 2020 2 9 实际中的RSA签名 通常是 实体A将消息先签名再加密 然后发给B假设 nA eA 和 nB eB 分别是A和B的公钥有以下问题 1 重分组问题2 冗余函数的选择3 参数的选取4 带宽效率5 系统范围参数6 消息长短的比较 28 47 兰州交通大学电子与信息工程学院 2020 2 9 使用RSA签名的建议 1 参数的选取 p q e d 2 不可使用公共模数 3 明文的熵要尽可能的大 4 尽量使用散列函数 5 若RSA的模数n 2kbits 则 若消息的长度 kbits 采用带消息恢复的RSA签名否则 采用带附录的RSA签名 29 47 兰州交通大学电子与信息工程学院 2020 2 9 Rabin公钥签名方案 Rabin公钥签名方案与RSA方案类似 不过它使用的公开指数e是偶数 为简单起见 假定e 2 待签名空间Ms是Qn 模n的二次剩余集 并且签名是Qn中元素的平方根 用到的知识 1 模n的二次剩余集2 模n的平方根3 剩余类的集合4 合数5 勒让德符号6 雅可比符号 RSA签名方案中p和q是不同的素数 从而 n p 1 q 1 是偶数 而e必须满足gcd e 1 所以e是奇数 30 47 兰州交通大学电子与信息工程学院 2020 2 9 Rabin公钥签名方案的密钥生成 概要 每个实体生成各自的公钥和相应私钥 1 随机产生两个不同的大素数p和q 实体A执行如下操作 2 计算n pq 3 A的公钥是n 私钥是 p q 31 47 兰州交通大学电子与信息工程学院 2020 2 9 Rabin方案的签名生成和验证 概要 实体A签署消息m 任何实体B都可以验证A的签名 并从中恢复消息m 实体A执行如下操作 为验证A的签名s且恢复消息m B执行如下操作 32 47 兰州交通大学电子与信息工程学院 2020 2 9 签名验证 B计算 既然 那么B接受签名并恢复出消息 密钥生成 实体A选择素数p 7 q 11 计算n 77 则A的公钥是n 77 私钥是 p 7 q 11 待签空间 模n的二次剩余集 MS Qn 1 4 9 15 16 23 25 36 37 53 58 60 64 67 71 为简单起见 取M MS 并且设冗余函数R是恒等映射 即 签名生成 消息m 23 A计算 然后找出模77的一个平方根 在此 s 10 32 45 67 选取m的签名为s 45 Rabin公钥签名方案举例 33 47 兰州交通大学电子与信息工程学院 2020 2 9 Rabin公钥签名方案注意问题 1 选择合适的冗余函数R对Rabin签名方案的安全性极为重要 2 对Rabin方案而言 设消息m是比特串 则R可以将它赋值为二元表示是该消息的整数 然而 却不能保证那个整数是模n的二次剩余 这可能导致无法计算平方根 所以人们试图尝试用确定性方法 为了克服第二种问题 下面给出基本Rabin签名方案的一种修改版本 此处用到的技术类似于ISO IEC9796标准 它提供一种确定性方法将消息和待签空间的元素相关联 从而可计算平方根 34 47 兰州交通大学电子与信息工程学院 2020 2 9 修改的Rabin公钥签名方案 修改的Rabin签名方案的待签消息取自 下表列出了此方案中的集合和一些函数定义记号 35 47 兰州交通大学电子与信息工程学院 2020 2 9 修改的Rabin公钥签名方案的密钥生成 概要 每个实体生成各自的公钥和相应的私钥 实体A执行如下操作 1 随机选择素数p 3 mod8 q 7 mod8 并计算n pq 2 A的公钥是n 私钥是d n p q 5 8 36 47 兰州交通大学电子与信息工程学院 2020 2 9 1 签名生成 实体A执行以下操作 1 计算 2 计算雅可比符号 3 若J 1 则计算 4 若J 1 则计算 5 A对m的签名是s 修改的Rabin方案的签名生成与验证 1 37 47 兰州交通大学电子与信息工程学院 2020 2 9 2 签名验证 实体B执行以下操作 1 获得A的可信公钥n 2 计算 注意不需要初始消息m 3 4 5 6 7 验证 否则拒绝 8 修改的Rabin方案的签名生成与验证 2 38 47 兰州交通大学电子与信息工程学院 2020 2 9 修改的Rabin公钥签名方案举例 密钥生成 A选择p 19 q 31 并计算n pq 589和d n p q 5 8 68 则A的公钥是n 589 私钥是d 68 下表列出了待签名空间MS的每个元素及其雅可比符号 39 47 兰州交通大学电子与信息工程学院 2020 2 9 修改的Rabin公钥签名方案举例 续 签名生成 签名验证 40 47 兰州交通大学电子与信息工程学院 2020 2 9 ISO IEC9796规范 是数字签名的第一个国际标准 1991公布 它规定了一套数字签名程序 并采用一种带消息恢复的数字签名机制主要特点 基于公钥密码学未指定特定签名算法 但必须是kbits映射为kbits用于签署有限长度的消息提供消息恢复描述了必需的消息填充RSA Rabin算法 41 47 兰州交通大学电子与信息工程学院 2020 2 9 PKCS 1规范 公钥密码技术标准 PKCS 是包含RSA加密和签名的技术的一套规范PKCS 1不采用RSA签名方案的消息恢复特性采用带附录的签名机制使用Hash函数 MD2或MD5 42 47 兰州交通大学电子与信息工程学院 2020 2 9 11 4Fiat Shamir签名方案 是由Fiege Fiat Shamir身份识别方案转变而来的安全性基于计算模n平方根的困难性签名生成的计算量远远小于RSA签名适合于需快速执行签名生成 且不限制密钥空间存储量的应用实体A对消息签名后 再由实体B来验证签名的有效性 具体包含 密钥生成签名生成和验证 43 47 兰州交通大学电子与信息工程学院 2020 2 9 Feige Fiat Shamir签名方案的密钥生成 随机产生不同的私密素数p和q 保密 最好用完丢弃 计算n p q 并公开n 选择正整数k及k个与n互素 且互不相同的随机整数