第5章 数字签名.ppt

1、第5章 数字签名,5.1 数字签名的基本概念 5.2 RSA数字签名 5.3 ElGamal数字签名 5.4 数字签名标准DSS 5.5 其他数字签名5.5.1 基于离散对数问题的数字签名5.5.2 基于大整数分解问题的数字签名5.5.3 具有特殊用途的数字签名,现代密码学,电子科技大学,5.1 数字签名的基本概念,数字签名应具有以下特性： （1）不可伪造性 除了签名者外，任何人都不能伪造签名者的合法签名。 （2）认证性 接收者相信这份签名来自签名者。 （3）不可重复使用性 一个消息的签名不能用于其他消息。 （4）不可修改性 一个消息在签名后不能被修改。 （5）不可否认性 签名者事后不能否认自

2、己的签名。,现代密码学,电子科技大学,一个数字签名体制（也称为数字签名方案）一般有两个组成部分，即签名算法（signature algorithm）和验证算法（verification algorithm）。签名算法的输入是消息m和密钥k，输出是对m的数字签名，记为s = （m）。验证算法输入的是消息m和签名s，输出是真或伪，记为：算法的安全性在于从m和s难以推出密钥k或伪造一个消息使和s可被验证为真。,现代密码学,电子科技大学,数字签名可按以下几种方式进行分类： 按用途来分，数字签名可分为普通数字签名和具有特殊用途的数字签名如盲签名（blind signature）、不可否认签名（unden

3、iable signature）、群签名（group signature）、代理签名（proxy signature）等。,现代密码学,电子科技大学,数字签名的分类, 按是否具有消息恢复功能来分，数字签名可分为具有消息恢复功能的数字签名和不具有消息恢复功能的数字签名。 按是否使用随机数来分，数字签名可分为确定性数字签名和随机化数字签名（randomized digital signature）,1参数与密钥生成 （1）选取两个保密的大素数p和q。 （2）计算n = pq, ，其中 是n的欧拉函数值。 （3）随机选取整数e，1e ，满足 。 （4）计算d，满足 。 （5）公钥为(e,n)，私钥为

4、d。,5.2 RSA数字签名,现代密码学,电子科技大学,2签名 对于消息m ，签名为： 3验证 对于消息签名对(m, s)，如果：则s是m的有效签名。,现代密码学,电子科技大学,5.2 RSA数字签名,RSA数字签名方案存在以下缺陷： 任何人都可以伪造某签名者对于随机消息m的签名s。其方法是先选取s，再用该签名者的公钥(e,n)计算 。s就是该签名者对消息m的签名。,现代密码学,电子科技大学, 如果敌手知道消息 和 的签名分别是 和 ，则敌手可以伪造 的签名 ，这是因为在RSA签名方案中，存在以下性质：, 由于在RSA签名方案中，要签名的消息 ，所以每次只能对位长的消息进行签名。然而，实际需要

5、签名的消息可能比n大，解决的办法是先对消息进行分组，然后对每组消息分别进行签名。这样做的缺点是签名长度变长，运算量增大。,克服上述缺陷的方法之一是在对消息进行签名前先对消息做Hash变换，然后对变换后的消息进行签名。即签名为：验证时，先计算h（m），再检查等式：是否成立。,现代密码学,电子科技大学,5.3 ElGamal数字签名,现代密码学,电子科技大学,5.3 ElGamal数字签名算法,1参数与密钥生成 选取大素数p, 是一个本原元。p和g公开。 随机选取整数x,1xp2，计算 公钥为y，私钥为x。,现代密码学,电子科技大学,2签名对于消息m，首先随机选取一个整数k, 1kp2 ，然后计算

6、： 则m的签名为(r, s)，其中h为Hash函数。,5.3 ElGamal数字签名算法,3验证对于消息签名对(m, (r, s)，如果：则(r, s)是m的有效签名。,5.3 ElGamal数字签名算法,5.4 DSS数字签名标准,现代密码学,电子科技大学,5.4 DSS数字签名标准,1参数与密钥生成 选取大素数p，满足 p ，其中512L1024且L是64的倍数。显然，p是L位长的素数，L从512到1024且是64的倍数。 选取大素数q，q是p1的一个素因子且 ，即q是160位的素数且是p1的素因子。,现代密码学,电子科技大学,1参数与密钥生成, 选取一个生成元 ，其中h是一个整数，满足1

7、hp1并且 。 随机选取整数x，0xq，计算 。 p、q和g是公开参数，y为公钥，x为私钥。,5.4 DSS数字签名标准,2签名 对于消息m，首先随机选取一个整数k , 0kq，然后计算：则m的签名为(r, s)，其中h为Hash函数，DSS规定Hash函数为SHA-1。,现代密码学,电子科技大学,5.4 DSS数字签名标准,3验证对于消息签名对(m, (r, s)，首先计算：然后验证：如果等式成立，则(r, s)是m的有效签名；否则签名无效。,DSS的框图下图所示，其中的4个函数分别为：,现代密码学,电子科技大学,5.5 其他数字签名 5.5.1 基于离散对数问题的数字签名,现代密码学,电子

8、科技大学,1离散对数签名方案ElGamal签名方案、DSA签名方案、Schnorr签名方案都可以归结为离散对数签名方案的特例。,现代密码学,电子科技大学,1离散对数签名方案 （1）参数与密钥生成p：大素数。q：p 1或p 1的大素因子。g： ，且 ，其中 表示g 是从 中随机选取的，这里的 。x：用户A的私钥，1xq。y：用户A的公钥，y g x mod p。,1离散对数签名方案 （2）签名 对于消息m，A执行以下步骤： 计算的m的Hash值h(m)。 随机选择整数k,1kq。 计算r gk mod p。 从签名方程：ak (b+cx)mod q中解出s，其中方程的系数a、b、c有多种选择，表

9、5-1给出了一部分可能的选择。对消息m的签名为(r, s)。,现代密码学,电子科技大学,表5-1 参数a、b、c可能的选择,注：表中 。,现代密码学,电子科技大学,1离散对数签名方案 （3）验证 接收者在收到消息m和签名(r, s)后，可以按照以下验证方程检查签名的合法性：,现代密码学,电子科技大学,2Schnorr签名方案,（1）参数与密钥生成 p：大素数且p2512 。 q：大素数且q|（p1）, q2160 。 g： ，且gq 1 mod p。 x：用户A的私钥，1xq。 y：用户A的公钥，y gx mod p。,现代密码学,电子科技大学,（2）签名 对于消息m，A执行以下步骤： 随机选

10、择整数k,1kq。 计算r gk mod p。 计算e=h（r,m）。 计算s （xe+k）mod q。 对消息m的签名为（e, s）。,现代密码学,电子科技大学,2Schnorr签名方案,（3）验证接收者在收到消息m和签名（e, s）后，通过以下步骤来检验签名的合法性： 计算 。 按照以下方程进行验证：Schnorr签名的正确性可由下式证明：,现代密码学,电子科技大学,2Schnorr签名方案,3Nyberg-Rueppel签名方案,（1）参数与密钥生成 p：大素数。 q：大素数且q|（p1）。 g： ，且gq 1 mod p。 x：用户A的私钥，1xq。 y：用户A的公钥，y gx mod

11、 p,现代密码学,电子科技大学,（2）签名对于消息m，A执行以下步骤： 计算 ，其中R是从消息空间到签名空间的一个单一映射，并且容易求逆，称为冗余函数。 随机选择整数k，1kq1。 计算r g-k mod p。 计算 。 计算s （xe+k）mod q。 对消息m的签名为（e, s）。,（3）验证接收者在收到消息m和签名（e, s）后，通过以下步骤来验证签名的合法性： 验证是否有0ep成立，如果不成立，拒绝该签名。 验证是否有0sp成立，如果不成立，拒绝该签名。,现代密码学,电子科技大学,计算 和 。验证是否有 ，如果 ，拒绝该签名，这里M R 表示R的值域。 恢复消息 。 下面证明Nyber

12、g-Rueppel签名方案的正确性。 因为所以,现代密码学,电子科技大学,5.5.2 基于大整数分解的数字签名方案,1Feige-Fiat-Shamir签名方案 （1）参数与密钥生成 n：n=pq，其中p和q是两个保密的大素数。 k：固定的正整数。：用户A的私钥， 。：用户A的公钥，,现代密码学,电子科技大学,（2）签名对于消息m，A执行以下步骤： 随机选择整数r,1rn1。 计算u r mod n。 计算e=（e , e , e ）=h（m, u），e 0,1。 计算 。 对消息m的签名为（e, s）。,现代密码学,电子科技大学,（3）验证接收者在收到消息m和签名（e, s）后，通过以下步骤

13、来检验签名的合法性： 计算 。 按照以下方程进行验证：Feige-Fiat-Shamir签名的正确性可由下式证明：,现代密码学,电子科技大学,2Guillou-Quisquater签名方案,（1）参数与密钥生成 n：n = pq，其中p和q是两个保密的大素数。 k：k 1, 2, n1且 x：用户A的私钥， 。 y：用户A的公钥， 且 。,现代密码学,电子科技大学,（2）签名对于消息m，A执行以下步骤： 随机选择整数 。 计算u rk mod n。 计算e=h（m,u）。 计算s=rxe mod n。对消息m的签名为（e, s）。,现代密码学,电子科技大学,（3）验证接收者在收到消息m和签名（

14、e, s）后，通过以下步骤来验证签名的合法性： 计算 。 按照以下方程进行验证：Guillou-Quisquater签名的正确性可由下式证明：,现代密码学,电子科技大学,群签名具有以下特点： 只有群体中的合法成员才能代表整个群体进行签名。 接收者可以用群公钥验证群签名的合法性，但不知道该群签名是由群体中的哪个成员所签。 在发生争议时，群管理员（权威机构）可以识别出实际的签名者。,现代密码学,电子科技大学,5.5.3 具有特殊用途的数字签名 1群签名,一个群签名方案由以下几个部分组成：（1）建立（setup） 一个用以产生群公钥和私钥的多项式概率算法。 （2）加入（join） 一个用户和群管理员

15、之间的交互式协议。执行该协议可以使用户成为群成员，群管理员得到群成员的秘密的成员管理密钥，并产生群成员的私钥和成员证书。,现代密码学,电子科技大学,1群签名,（3）签名（sign） 一个概率算法，当输入一个消息、一个群成员的私钥和一个群公钥后，输出对该消息的签名。 （4）验证（verify） 给定一个消息的签名和一个群公钥后，判断该签名相对于该群公钥是否有效。 （5）打开（open） 给定一个签名、群公钥和群私钥的条件下确定签名者的身份。,群签名,一个好的群签名方案应该满足以下几条性质： 正确性（correctness） 不可伪造性（unforgeability） 匿名性（anonymity）

16、 不可关联性（unlinkability） 可跟踪性（traceability） 可开脱性（exculpability） 抗联合攻击（coalition-resistance）,现代密码学,电子科技大学,电子科技大学,群签名,2代理签名,一个代理签名方案由以下几个部分组成： 系统建立 选定代理签名方案的系统参数，用户的密钥等。 签名权力的委托 原始签名者将自己的签名权力委托给代理签名者。 代理签名的产生 代理签名者代表原始签名者产生代理签名。 代理签名的验证 验证人验证代理签名的有效性。,现代密码学,电子科技大学,根据签名权力委托的方式不同，代理签名可以分为以下几类： （1）完全代理（full

17、 delegation） （2）部分代理（partial delegation） （3）具有证书的代理（delegation by warrant） （4）具有证书的部分代理（partial delegation with warrant）,现代密码学,电子科技大学,2代理签名,根据原始签名者能否产生同代理签名者一样的签名，代理签名又可分为两类：1）代理非保护（proxy-unprotected） 原始签名者能够产生有效的代理签名。 2）代理保护（proxy-protected） 原始签名者不能够产生有效的代理签名。,现代密码学,电子科技大学,2代理签名,一个强代理签名方案应满足以下几条性质：

18、 可区分性（distinguishability） 可验证性（verifiability） 强不可伪造性（strong unforgeability） 强可识别性（strong identifiability） 强不可否认性（strong undeniability） 防止滥用（prevention of misuse）,现代密码学,电子科技大学,3. 盲签名,盲签名允许使用者获得一个消息的签名，而签名者既不知道该消息的内容，也不知道该消息的签名。盲签名可用于需要提供匿名性的密码协议中，如电子投票和电子现金。一个盲签名方案由以下几个部分组成： （1）消息盲化 使用者利用盲因子对要签名的消息进行

19、盲化处理，然后将盲化后的消息发送给签名者。,现代密码学,电子科技大学,3. 盲签名,（2）盲消息签名 签名者对盲化后的消息进行签名，因此他并不知道真实消息的具体内容。 （3）恢复签名 使用者除去盲因子，得到真实消息的签名。,习题,1在RSA签名方案中，设p = 7，q = 17，公钥e=5，消息m的Hash值为19，试计算私钥d并给出对该消息的签名和验证过程。 2在ElGamal签名方案中，设p=19，g=2，私钥x=9，则公钥y=29 mod 19=18。若消息m的Hash值为152，试给出选取随机数k=5时的签名和验证过程。,现代密码学,电子科技大学,3试给出椭圆曲线上的ElGamal签名方案。 4在DSA签名算法中，如果一个签名者在对两个不同的消息签名时使用了相同的随机整数k，试显示攻击者可以恢复出该签名者的私钥。,习题,5在数字签名标准DSS中，设q=13，p=4q +1=53，g=16，签名者的私钥x=3，公钥y=163 mod 53=15，消息m的Hash值为5，试给出选取随机数k=2时的签名和验证过程。 6如果用户A想对消息m进行签名并秘密地将m发送给用户B，请问A是先签名后加密好还是先加密后签名好，并说明理由。 7简述群签名、代理签名和盲签名的用途。,现代密码学,电子科技大学,习题,