第7章 认证理论与技术—数字签名ppt课件

西安电子科技大学出版社 二00九年十二月 应用密码学 张仕斌万武南张金全孙宣东编著 第7章认证理论与技术 数字签名 知识点 数字签名的原理及分类 RSA及ElGamal数字签名算法 数字签名标准DSS 其他数字专用签名方案 盲签名方案及其应用 7 1 概述 由于计算机和网络的快速发展 电子商务日渐兴起 通过在文档上签字盖章的方式进行商务活动 显得效率很低 例如 一个在中国的公司和一个在美国的公司进行合作 双方达成协议后 要签订一个合同 则需要一方签名盖章后 邮寄或派人到另一方去签名盖章 于是人们就想 能不能对已经协商好的电子文档进行和手写签名一样的电子签名呢 并且这个电子签名和要求手写签名具有相同的法律效力 同时也是安全的 也即不能被伪造 这样 一方签名后 可以通过电子邮件发送给另一方 效率高而且花费小 数字签名的概念由Diffie和Hellman于1976年提出 目的是通过签名者对电子文件进行电子签名 使签名者无法否认自己的签名 同时别人也不能伪造 实现与手写签名相同的功能 具有与手写签名相同的法律效力 由于数字签名技术在现在和未来社会里对政府 企事业 一般团体和个人的重要影响 世界各国都加强了对它的研究 1994年美国政府正式颁发了美国数字签名标准DSS DigitalSignatureStandard 1995年我国也制定了自己的数字签名标准 GB15851 1995 2004年我国颁发 中华人民共和国电子签名法 数字签名与手工签名的区别数字签名 数字的 因消息而异手工签名 模拟的 因人而异 数字签名与消息认证的区别数字签名 第三者可以确认收发双方的消息传送消息认证 只有收发双方才能确认消息的传送 认证数据完整性不可抵赖性大型网络的公钥证书中 数字签名的应用 7 2数字签名的原理及分类 在RSA加密算法中 假如用户Bob的参数选取简单写为n pq de 1mod n 则 e n 为公开密钥 d n 为秘密密钥 对于一个秘密密钥 d n 在满足de 1mod n 的条件下 只有唯一的 e n 与之对应 如同在介绍RSA加密算法时所提及的那样 一个用户的公钥会在较长时间内保持不变 故我们可以说 在一定时间内 e n 表示了秘密密钥 d n 的持有者的身份 如果秘密密钥 d n 的持有者Bob声明某个信息m并放于公共媒介如网络之上 那么其他人如何确定这个消息就是他发布的原信息而没有被其他人更改过呢 也就是如何确定消息的完整性呢 我们可以通过下面这种方式达到目的 让消息发布者Bob先计算s mdmodn 然后把s附于消息m之后 一起放到公共媒介上 因为大家都知道 e n 唯一代表了消息发布者Bob的身份 故可以通过计算m semodn成立与否 来判定消息是不是Bob所发 以及消息是否被篡改 因为Bob是秘密密钥 d n 的唯一持有者 只有他才能通过s mdmodn计算出s的值来 其他人如果想算出s的值 他必须要能破解大数分解问题才行 7 2 2数字签名的分类 当前 数字签名应具有的性质 1 收方能确认或证实发方的签字 但不能伪造 2 发方发出签名后的消息 就不能否认所签消息 3 收方对已收到的消息不能否认 4 第三者可以确认收发双方之间的消息传送 但不能伪造这一过程 5 必须能够验证签名者及其签名的日期时间 6 必须能够认证被签名消息的内容 7 签名必须能够由第三方验证 以解决争议 注 数字签名功能包含了认证的功能 按数字签名的所依赖的理论基础分 主要可以分为 1 基于大数分解难题的数字签名 如7 3节及7 6节介绍的例子 2 基于离散对数的数字签名 如7 4节介绍的DSA 3 基于椭圆曲线离散对数的数字签名 这类签名往往由基于离散对数的数字签名改进而来 近年来 随着密码理论的发展 人们也提出了基于双线性对的数字签名等 从数字签名的用途分 可以把数字签名分为普通的数字签名和特殊用途的数字签名 普通的数字签名往往可以和身份认证相互转换特殊用途的数字签名 如盲签名 代理签名 群签名 门限签名等 多是在某些特殊的场合下使用 盲签名通常用于需要匿名的小额电子现金的支付 代理签名可以用于委托别人在自己无法签名的时候 如外出旅游 代替签名等 这部分内容请参考7 5节 7 3数字签名算法 在本节中 我们介绍比较经典的数字签名算法 一个是RSA签名算法一个是ElGamal签名算法RSA签名算法提出的时间比较早 并且一直到现在 以其为基础的应用都还在使用 而ElGamal签名算法的变型算法之一 就是后来的数字签名算法 DSA 7 3 1RSA数字签名 1 参数选择 选择两个满足需要的大素数p和q 计算n p q n p 1 q 1 其中 n 是n的欧拉函数值 选一个整数e 满足1 e n 且gcd n e 1 通过d e 1mod n 计算出d 以 e n 为公开密钥 d n 为秘密密钥 1 RSA数字签名描述 2 签名过程假设签名者为Bob 则只有Bob知道秘密密钥 d n 设需要签名的消息为m 则签名者Bob通过如下计算对m签名 s mdmodn m s 为对消息m的签名 Bob在公共媒体上宣称他发布了消息m 同时把对m的签名s置于消息后用于公众验证签名 3 验证过程 公众在看到消息m和对其签名s后 利用Bob的公开验证密钥 e n 对消息进行验证 公众计算 m semodn是否成立 若成立 则Bob的签名有效 公众认为消息m的确是Bob所发布 且消息内容没有被篡改 也就是说 公众可以容易鉴别发布人发布的消息的完整性 2 对上述RSA签名算法的一个攻击 前面所描述的RSA签名算法是有缺陷的 假设攻击者Eve在得到Bob的两次对消息的签名后 很容易实现伪造 若已知 1 Bob对消息M1的签名为S1 即S1 M1dmodn 2 Bob对消息M2的签名为S2 即S2 M2dmodn 则攻击者Eve可以构造消息M3 M1 M2的签名S3 S3 M3d M1 M2 dmodn S2 S1虽然说在已知M1 M2的情况下 M3往往只是一个数值 一般来说是没有意义的 但不排除有意义的可能性 故导致了算法的不安全 3 对上述RSA签名算法的改进 假设公开的安全哈希函数为H 参数选择如前 其签名过程和验证过程如下 1 签名过程设需要签名的消息为m 签名者Bob通过如下计算对其签名 s H m dmodn m s 为对消息m的签名 2 验证过程在收到消息m和签名s后 验证H m semodn是否成立 若成立 则发送方的签名有效 数字签名的步骤 数字签名与验证过程 第一步 将消息按散列算法计算得到一个固定位数的消息摘要值 在数学上保证 只要改动消息的任何一位 重新计算出的消息摘要就会与原先值不符 这样就保证了消息的不可更改 第二步 对消息摘要值用发送者的私有密钥加密 所产生的密文即称数字签名 然后该数字签名同原消息一起发送给接收者 第三步 接收方收到消息和数字签名后 用同样的散列算法对消息计算摘要值 然后与用发送者的公开密钥对数字签名进行解密 将解密后的结果与计算的摘要值相比较 如相等则说明报文确实来自发送者 数字签名与验证过程图示 当M3 M1 M2时 H M3 H M1 H M2 一般不成立 有效的防止了这类攻击方法 可以看到 通过使用哈希函数 有效防止了对签名的伪造 增强了签名算法的安全性 这也是在很多签名算法中使用哈希函数的原因之一 7 3 2ElGamal数字签名 ElGamal签名算法也是基于离散对数难题的 于1985年提出 其变型之一成为美国国家标准技术研究所 NationalInstituteofStandardsandTechnology 简称NIST 提出的DSA digitalsignatureAlgorithm 算法的基础 2 对于ElGamal签名算法的理解 需注意 1 这个方案还是存在一定的不足 比如 对于消息没有用哈希函数进行处理 签名容易被伪造 2 签名时所使用的随机值k不能泄露 否则攻击者可以计算出签名的私钥 通过变换 m x k 1mod p 1 可知x m k 1mod p 1 3 对于两个不同的消息签名时 不要使用相同的k 否则容易求得k的值 从而知道签名者的私钥 通过对上面两个算法的学习 我们可以看到 数字签名的一个重要作用 就是保证了被签名文档的完整性 一旦被签名的文档内容发生了改变 则通不过验证 从而防止了文档被篡改和伪造 而且 签名是与文档内容紧密联系的 这样 对一个文档的签名 如果复制到另外一个文档上 就通不过验证 使得签名对该文档无效 7 4数字签名标准 DSS 1991年8月 NIST提出将数字签名算法 DSA DigitalSignatureAlgorithm 用于数字签名标准 DSS DigitalSignatureStandard 中 由于RSA算法及签名的广泛使用等各种原因 使得DSS的出现引起了很多的争议 1994年 在考虑了公众的建议后 该标准最终颁布 7 4 1DSA的描述 1 算法的参数 p是L比特长的素数 L的长度为512到1024且是64的倍数 q是160比特长且为p 1的素因子 g h p 1 qmodp 其中h g是整数 1 h p 1 且要求g大于1 x是签名者的私钥 由签名者选取的随机数 要求是小于q的正整数 y gxmodp为签名者的公钥 选择安全散列算法H 标准中指定为SHA 签名者公开 p q g y 及安全散列算法H 保密x DSA的安全性是基于求解离散对数困难性的基础之上的 并使用了安全散列算法 它也是Schnorr和ElGamal签名算法的变型 对于DSA算法 人们有一些批评意见 比如认为验证比签名快 q的长度160比特太短 不能用于加密和分配密钥等 另外 由于DSA算法是ElGamal签名算法的变型 故所有对ElGamal签名算法的攻击 也可以用于对DSA算法的攻击 不过就已有的攻击来看 DSA算法还是安全的 与RSA数字签名算法比较 DSA在管理上有一个优点 对于RSA数字签名算法 每个用户都要有不同的公钥 故针对每个用户 都要去产生大的素数p和q 去计算d 而对于DSA算法 管理机构只需要计算一次p g q 通常又叫全局公开钥 每个用户只需要选择私钥x 然后计算公钥y 通常又叫用户公钥 为什么 7 4 2DSA举例 对于DSA签名算法的举例 如果在例子中采用了对消息进行消息摘要值的计算H m 大数的运算容易让初学者望而生畏 我们在这里采用小的整数代替H m 如果读者关心在算法中使用了消息摘要的例子 可以参看DSA的标准fips 186 标准中提到了用MillerRabin素性检测算法产生素数 用ANSIX9 17产生随机数 以及其他参数的选取等 假设q 101 p 78 101 1 7879 h 19 则g 1978mod7879 367取x 69 则y gxmodp 36769mod7879 1292 假设想签名的消息为m 3456 且选择的随机值为k 27 可以计算k 1 15mod101 故可以算出签名为r gkmodp modq 36727mod7879 mod101 6797mod101 30s k 1 m xr modq 15 3456 69 30 mod101 70可以得到对m的签名为 30 70 验证签名 w s 1modq 70 1mod101 13u1 mwmodq 3456 13mod101 84u2 rwmodq 30 13mod101 87v gu1yu2modp modq 36784129287mod7879 mod101 2456 1687mod7879 mod101 6797mod101 30v r 因此签名是有效的注 可以看到 签名和验证过程中的运算量是很大的 其中最主要的运算集中在模幂运算上 而且上面的举例中 素数的取值也是比较小的 这些运算可以通过简单编程实现 如果是按标准中的取值 模幂运算及大数的处理对初学者来说还是有挑战性的 7 5其他专用数字签名方案 针对实际应用中大量特殊场合的签名需要 数字签名领域也转向了针对特殊签名的广泛研究阶段 1 盲签名用户需要让签名者对明文消息文件进行数字签名 而又不希望签名者知晓明文消息文件的具体内容 这就需要盲数字签名 简称盲签名 BlindSignature 盲签名是一种特殊的数字签名方法 相对于一般的数字签名而言还应当具有下列2个特性 盲性 所签消息的内容对签名人是盲的 即签名人签名时不能看见消息的具体内容 不可追踪性 即使在盲签名公开后 签名者仍然不能跟踪消息 签名对 即不能把签名和其在签名时的看到的信息联系起来 盲签名主要用于基于Internet的匿名金融交易 如匿名电子现金支付系统 匿名电子拍卖系统等应用中 2 门限签名 在有n个成员的群体中 至少有t个成员才能代表群体对文件进行有效的数字签名 门限签名通过共享密钥方法实现 它将密钥分为n份 只有当将超过t份的子密钥组合在一起时才能重构出密钥 门限签名在密钥托管技术中得到了很好的应用 某人的私钥由政府的n个部门托管 当其中超过t个部门决定对其实行监听时 便可重构密钥 实现监听 3 代理签名1996年 Mambo Usuda和Okamoto提出了代理签名的概念 代理签名允许密钥持有者授权给第三方 获得授权的第三方能够代表签名持有者进行数字签名 代理签名相当于一个人把自己的印章托付给自己信赖的人 让他代替自己行使权力 由于代理签名在实际应用中起着重要作用 所以代理签名一提出便受到关注 被广泛研究 4 群签名允许一个群体中的成员以整个群体的名义进行数字签名 并且验证者能够确认签名者的身份 一个好的群签名方案应满足以下的安全性要求 匿名性 给定一个群签名后 对除了唯一的群管理人之外的任何人来说 确定签名人的身份在计算上是不可行的 不关联性 在不打开签名的情况下 确定两个不同的签名是否为同一个群成员所做在计算上是困难的 防伪造性 只有群成员才能产生有效的群签名 可跟踪性 群管理人在必要时可以打开一个签名以确定出签名人的身份 而且签名人不能阻止一个合法签名的打开 防陷害攻击 包括群管理人在内的任何人都不能以其他群成员的名义产生合法的群签名 抗联合攻击 即使一些群成员串通在一起也不能产生一个合法的不能被跟踪的群签名 在D Chaum和E vanHeyst提出群数字签名的定义 并给出了四个实现方案后 由于群签名的实用性 人们对群签名加以了更加广泛的研究 提出了分级多群签名 群盲签名 多群签名 满足门限性质的群签名 前向安全的群签名等 5 前向安全的数字签名方案普通数字签名具有如下局限性 若签名者的密钥被泄漏 那么这个签名者所有的签名 过去的和将来的 都有可能泄漏 前向安全的数字签名方案主要思想是当前密钥的泄露并不影响以前时间段签名的安全性 在提出以上这些签名之后 研究者们根据不同的需要 又给出了一些综合以上性质的签名 如前向安全的群签名 盲代理签名 代理门限签名 代理多重签名 公平盲签名等 7 6盲签名方案 1983年 Chaum提出了盲签名概念 在此基础上提出了一个盲签名方案 并指出盲签名应该满足如下两个性质 1 盲性 所签消息的内容对签名人是盲的 即签名人签名时不能看见消息的具体内容 2 不可追踪性 即使在盲签名公开后 签名者仍然不能跟踪消息 签名对 即不能把签名和其在签名时的看到的信息联系起来 一般来说 盲签名的协议有如下几个步骤 初始化过程 盲化过程 签名过程 脱盲过程 验证过程 7 6 1基于整数分解难题的盲签名 1 RSA盲数字签名描述 1 参数选择 选择两个满足需要的大素数p和q 计算n p q n p 1 q 1 其中 n 是n的欧拉函数值 选一个整数e 满足1 e n 且gcd n e 1 通过d e 1mod n 计算出d 以 e n 为公开密钥 d n 为秘密密钥 选择安全的单向hash函数h 仍然把Bob作为签名者 则Bob知道秘密密钥 d n 所有人都知道公开密钥 e n 和算法中选择的hash函数h 2 盲化过程设需要签名的消息为m 请求签名者Alice随机选择一个整数r作为盲化因子 然后进行如下计算 re h m modn 然后发送 给签名者Bob 3 签名过程Bob在收到 后 计算t dmodn 然后把t发送给Alice 4 脱盲过程Alice接收到t后 计算s t r 1modn 就得到了消息m的签名 m s 5 验证过程通过如下计算 任何人都可以验证签名的有效性 se h m modn是否成立 若成立 则发送方的签名有效 下面来体会一下这个签名方案为什么叫做盲签名方案 签名者看到的信息是 根据 e n 签名者显然不能计算出h m 来 因为还有一个变量r 盲化因子 即所签消息的内容对签名人是盲的 即签名人Bob签名时不能看见消息的具体内容 在Alice得到Bob的签名后 Bob即使看到了自己的签名 m s 仍然不能把它与签名时的 联系起来 即盲签名的第二个性质 不可追踪性 7 6 2基于离散对数难题的盲签名 基于离散对数难题的盲签名出现的时间相对比较晚 1994年 J Camenisch在DSA和Nyberg Rueppel方案的基础上 各提出了一个盲签名方案 后来 随着研究进展 出现了强盲签名和弱盲签名的分化 再后来出现了跟其他签名结合的签名方案 如盲代理签名 盲群签名等 下面选择Schnorr盲签名算法来学习基于离散对数难题的盲签名 可以看到 在该算法中 同样满足盲签名的两个特征 即签名者在签名时不知道所签消息的内容 事后即使看到了签名 m c s 也不能把它与签名时收到的消息v联系起来 从而实现了盲签名 7 6 3盲签名的应用 著名密码学家DavidChaum1982年首次提出了利用盲签字实现电子现金的方法 DigiCash是DividChaum发起的提供电子支付系统的专业公司 eCashTM是DigiCash开发的用软件实现的第一个完全匿名的在线电子现金系统 它的基本算法是RSA盲签名算法 1995年MarkTwain银行就开始发行Internet网上电子现金 一个电子现金支付系统通常包括三个参与方 银行 电子现金支付者 电子现金接收者 在电子货币支付时 电子现金支付者从银行取出他的电子货币 然后将电子货币支付给接收者 接收者将收到的电子货币存入银行 其关系可以用下页图表示 其中箭头方向表示了电子货币的流向 1 eCashTM系统相关的参数 设银行的签名公钥为e 支付公钥PKbank 秘密钥为d 模为n 采用安全单向函数为h h 的使用使伪造电子现金的变得不可行银行的公开信息是 e n h 支付公钥PKbank 秘密信息是 d p q n p q p q是安全素数 使得分解大整数n是困难的 系统假设用户Alice已经在银行里存了一笔钱在账户NA上以备提取 2 电子现金提取协议这里使用的是一个单位面值的电子现金 即对给定消息m 约定h m 的e次根 即d次幂值为一个单位面值 用户提取电子现金的协议如下 1 Alice选取随机数r serial 计算b re h serial modn 发送b 账号NA和身份IDA给银行 其中serial 表示选取的电子现金的面值 这里仅指一个单位面值 2 银行验证身份IDA的合法性 若合法 计算B bdmodn 在用户账户上减掉一个单位面值的电子现金 发送B给Alice 3 Alice计算S B rmodn 于是用户Alice获得了银行发行一个的单位面值的电子现金Coin serial S 在这里使用了盲签名技术 实现了用户Alice的电子现金的不可追踪性 3 支付协议 任何人如果知道某个没有花费的Coin 就可使用 用户支付Coin时 不能让接收者看到Coin eCashTM为了保证这点 银行使用了一个用来完成支付的公钥PKbank 用户支付时用PKbank对Coin加密 保证了只有电子现金拥有者在申请后和银行在电子现金拥有者完成支付时才能看到它 假定电子现金支付者和接收者商定了支付银行bankID 支付金额amount 币种currency 电子现金个数nCoins 时戳timestamp 接收者身份merchant Ids与其银行帐户对应 交易描述description以备将来解决支付者和接收者的可能争议 支付者的秘密随机数payer code也用来解决支付者和接收者的可能争议 Payment inf bankID amount currency nCoins timestamp merchant Ids h description h payer code 在支付过程中 银行不能知道description的信息 只能知道description的hash值 具体支付协议如下 1 电子现金支付者计算payment payment inf nCoins merchant Ids PKbank 发送payment到电子现金接收者 其中 nCoins merchant Ids PKbank表示用PKbank加密 nCoins merchant Ids 2 电子现金接收者验证payment inf 发送payment给银行 3 银行验证 nCoins merchant Ids PKbank确信Coins没有重复花费 把nCoins列入已花费的coins 给merc