第5章数字签名.ppt

第5章 数字签名5.1 数字签名的基本概念数字签名的基本概念5.2 RSA数字签名数字签名5.3 ElGamal数字签名数字签名5.4 数字签名标准数字签名标准DSS5.5 其他数字签名其他数字签名 5.5.1 基于离散对数问题的数字签名基于离散对数问题的数字签名 5.5.2 基于大整数分解问题的数字签名基于大整数分解问题的数字签名 5.5.3 具有特殊用途的数字签名具有特殊用途的数字签名现代密码学现代密码学电子科技大学电子科技大学5.1 数字签名的基本概念数字签名应具有以下特性：（1）不可伪造性 除了签名者外，任何人都不能伪造签名者的合法签名2）认证性 接收者相信这份签名来自签名者3）不可重复使用性 一个消息的签名不能用于其他消息4）不可修改性 一个消息在签名后不能被修改5）不可否认性 签名者事后不能否认自己的签名现代密码学现代密码学电子科技大学电子科技大学u一个数字签名体制（也称为数字签名方案）一般一个数字签名体制（也称为数字签名方案）一般有两个组成部分，即有两个组成部分，即签名算法（（signature signature algorithmalgorithm）和）和验证算法（（verification verification algorithmalgorithm）。

签名算法的输入是消息）签名算法的输入是消息m m和密钥和密钥k k，，输出是对输出是对m m的数字签名，记为的数字签名，记为s s = = （（m m）验证算法输入的是消息证算法输入的是消息m m和签名和签名s s，输出是真或伪，，输出是真或伪，记为：记为：u算法的安全性在于从算法的安全性在于从m m和和s s难以推出密钥难以推出密钥k k或伪造一或伪造一个消息使和个消息使和s s可被验证为真可被验证为真现代密码学现代密码学电子科技大学电子科技大学数字签名可按以下几种方式进行分类：数字签名可按以下几种方式进行分类：① ① 按用途来分，数字签名可分为普通数字签名和具按用途来分，数字签名可分为普通数字签名和具有特殊用途的数字签名有特殊用途的数字签名[ [如盲签名（如盲签名（blind blind signaturesignature）、不可否认签名（）、不可否认签名（undeniable undeniable signaturesignature）、群签名（）、群签名（group signaturegroup signature）、代理）、代理签名（签名（proxy signatureproxy signature）等）等] ]。

现代密码学现代密码学电子科技大学电子科技大学数字签名的分类电子科技大学 现代密码学现代密码学电子科技大学电子科技大学② ② 按是否具有消息恢复功能来分，数字签名可分为按是否具有消息恢复功能来分，数字签名可分为具有消息恢复功能的数字签名和不具有消息恢复功能具有消息恢复功能的数字签名和不具有消息恢复功能的数字签名的数字签名③ ③ 按是否使用随机数来分，数字签名可分为确定性按是否使用随机数来分，数字签名可分为确定性数字签名和随机化数字签名（数字签名和随机化数字签名（randomized digital randomized digital signaturesignature））u1．参数与密钥生成．参数与密钥生成（（1）选取两个保密的大素数）选取两个保密的大素数p和和q2）计算）计算n = pq, ，其中，其中 是是n的欧拉函数值的欧拉函数值3）随机选取整数）随机选取整数e，，1＜＜e＜＜ ，满足，满足 4）计算）计算d，满足，满足 。

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

然而，实，所以每次只能对位长的消息进行签名然而，实际需要签名的消息可能比际需要签名的消息可能比n大，解决的办法是先对大，解决的办法是先对消息进行分组，然后对每组消息分别进行签名这消息进行分组，然后对每组消息分别进行签名这样做的缺点是签名长度变长，运算量增大样做的缺点是签名长度变长，运算量增大 u克服上述缺陷的方法之一是在对消息进行克服上述缺陷的方法之一是在对消息进行签名前先对消息做签名前先对消息做Hash变换，然后对变换变换，然后对变换后的消息进行签名即签名为：后的消息进行签名即签名为： u验证时，先计算验证时，先计算h（（m），再检查等式：），再检查等式： 是否成立是否成立现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学现代密码学电子科技大学电子科技大学5.3 ElGamal数字签名现代密码学现代密码学电子科技大学电子科技大学5.3 ElGamal数字签名算法u1．参数与密钥生成．参数与密钥生成 ①① 选取大素数选取大素数p, 是一个本原元。

是一个本原元p和和g公开 ②② 随机选取整数随机选取整数x,1≤x≤p 2，计算，计算 ③③ 公钥为公钥为y，私钥为，私钥为x现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学现代密码学电子科技大学电子科技大学u2．签名．签名 对于消息对于消息m，首先随机选取一个整数，首先随机选取一个整数k, 1≤k≤p 2 ，然后计算：，然后计算： 则则m的签名为的签名为(r, s)，其中，其中h为为Hash函数5.3 ElGamal数字签名算法电子科技大学 现代密码学现代密码学电子科技大学电子科技大学u3．验证．验证 对于消息签名对对于消息签名对(m, (r, s))，如果：，如果： 则则(r, s)是是m的有效签名的有效签名5.3 ElGamal数字签名算法数字签名算法5.4 DSS数字签名标准数字签名标准现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学现代密码学电子科技大学电子科技大学5.4 DSS数字签名标准u1．参数与密钥生成．参数与密钥生成①① 选取大素数选取大素数p，满足，满足 ＜＜p＜＜ ，其中，其中512≤L≤1024且且L是是64的倍数。

显然，的倍数显然，p是是L位长的素位长的素数，数，L从从512到到1024且是且是64的倍数②② 选取大素数选取大素数q，，q是是p 1的一个素因子且的一个素因子且 ，即，即q是是160位的素数且是位的素数且是p 1的素因子的素因子现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学现代密码学电子科技大学电子科技大学1．参数与密钥生成．参数与密钥生成③③ 选取一个生成元选取一个生成元 ，其中，其中h是一是一个整数，满足个整数，满足1＜＜h＜＜p 1并且并且 ④④ 随机选取整数随机选取整数x，，0＜＜x＜＜q，计算，计算 ⑤⑤ p、、q和和g是公开参数，是公开参数，y为公钥，为公钥，x为私钥5.4 DSS数字签名标准u2．签名．签名 对于消息对于消息m，首先随机选取一个整数，首先随机选取一个整数k , 0＜＜k＜＜q，然后计算：，然后计算：则则m的签名为的签名为(r, s)，其中，其中h为为Hash函数，函数，DSS规定规定Hash函数为函数为SHA-1。

现代密码学现代密码学电子科技大学电子科技大学5.4 DSS数字签名标准电子科技大学 现代密码学现代密码学电子科技大学电子科技大学u3．验证．验证 对于消息签名对对于消息签名对(m, (r, s))，首先计算：，首先计算： 然后验证：然后验证： 如果等式成立，则如果等式成立，则(r, s)是是m的有效签名；否则签的有效签名；否则签名无效uDSS的框图下图所示，其中的的框图下图所示，其中的4个函数分别为：个函数分别为：现代密码学现代密码学电子科技大学电子科技大学5.5 其他数字签名5.5.1 基于离散对数问题的数字签名现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学现代密码学电子科技大学电子科技大学u1．离散对数签名方案．离散对数签名方案uElGamal签名方案、签名方案、DSA签名方案、签名方案、Schnorr签名方案都可以归结为离散对数签签名方案都可以归结为离散对数签名方案的特例名方案的特例现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学现代密码学电子科技大学电子科技大学u1．离散对数签名方案．离散对数签名方案（（1）参数与密钥生成）参数与密钥生成 p：大素数。

大素数 q：：p  1或或p   1的大素因子的大素因子 g：： ，且，且 ，其中，其中 表示表示g 是从是从 中随机选取的，这里的中随机选取的，这里的 x：用户：用户A的私钥，的私钥，1＜＜x＜＜q y：用户：用户A的公钥，的公钥，y   g x mod pu1．离散对数签名方案．离散对数签名方案u（（2）签名）签名对于消息对于消息m，，A执行以下步骤：执行以下步骤：①① 计算的计算的m的的Hash值值h(m)②② 随机选择整数随机选择整数k,1＜＜k＜＜q③③ 计算计算r   gk mod p④④ 从签名方程：从签名方程：ak  (b+cx)mod q中解出中解出s，，其中方程的系数其中方程的系数a、、b、、c有多种选择，表有多种选择，表5-1给出了一部分可能的选择对消息给出了一部分可能的选择对消息m的签名的签名为为(r, s)现代密码学现代密码学电子科技大学电子科技大学u表5-1 参数a、b、c可能的选择1111注：表中 。

现代密码学现代密码学电子科技大学电子科技大学u1．离散对数签名方案．离散对数签名方案u（（3）验证）验证接收者在收到消息接收者在收到消息m和签名和签名(r, s)后，可以按后，可以按照以下验证方程检查签名的合法性：照以下验证方程检查签名的合法性：现代密码学现代密码学电子科技大学电子科技大学2．Schnorr签名方案u（（1）参数与密钥生成）参数与密钥生成p：大素数且：大素数且p≥2512 q：大素数且：大素数且q|（（p 1））, q≥2160 g：： ，且，且gq   1 mod px：用户：用户A的私钥，的私钥，1＜＜x＜＜qy：用户：用户A的公钥，的公钥，y   gx mod p现代密码学现代密码学电子科技大学电子科技大学u（2）签名对于消息对于消息m，，A执行以下步骤：执行以下步骤：①① 随机选择整数随机选择整数k,1＜＜k＜＜q②② 计算计算r   gk mod p③③ 计算计算e=h（（r,m）④④ 计算计算s  （（xe+k））mod q对消息对消息m的签名为（的签名为（e, s）现代密码学现代密码学电子科技大学电子科技大学2．Schnorr签名方案u（3）验证 接收者在收到消息接收者在收到消息m和签名（和签名（e, s）后，通）后，通过以下步骤来检验签名的合法性：过以下步骤来检验签名的合法性：①① 计算计算 。

②② 按照以下方程进行验证：按照以下方程进行验证：Schnorr签名的正确性可由下式证明：签名的正确性可由下式证明：现代密码学现代密码学电子科技大学电子科技大学2．Schnorr签名方案3．Nyberg-Rueppel签名方案u（1）参数与密钥生成p：大素数q：大素数且：大素数且q|（（p 1）g：： ，且，且gq   1 mod px：用户：用户A的私钥，的私钥，1＜＜x＜＜qy：用户：用户A的公钥，的公钥，y   gx mod p 现代密码学现代密码学电子科技大学电子科技大学u（（2）签名）签名 对于消息对于消息m，，A执行以下步骤：执行以下步骤：①① 计算计算 ，其中，其中R是从消息空间到签是从消息空间到签名空间的一个单一映射，并且容易求逆，称名空间的一个单一映射，并且容易求逆，称为冗余函数为冗余函数②② 随机选择整数随机选择整数k，，1≤k≤q 1③③ 计算计算r   g-k mod p④④ 计算计算 ⑤⑤ 计算计算s  （（xe+k））mod q。

对消息对消息m的签名为（的签名为（e, s）u（（3）验证）验证 接收者在收到消息接收者在收到消息m和签名（和签名（e, s）后，通过以下）后，通过以下步骤来验证签名的合法性：步骤来验证签名的合法性：①①验证是否有验证是否有0＜＜e＜＜p成立，如果不成立，拒绝该签成立，如果不成立，拒绝该签名②②验证是否有验证是否有0≤s＜＜p成立，如果不成立，拒绝该签名成立，如果不成立，拒绝该签名现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学现代密码学电子科技大学电子科技大学③③计算计算 和和 ④④验证是否有验证是否有 ，如果，如果 ，拒绝该签名，，拒绝该签名，这里这里M R 表示表示R的值域⑤⑤恢复消息恢复消息 下面证明下面证明Nyberg-Rueppel签名方案的正确性签名方案的正确性因为因为所以所以现代密码学现代密码学电子科技大学电子科技大学5.5.2 基于大整数分解的数字签名方案u1．Feige-Fiat-Shamir签名方案u（1）参数与密钥生成n：：n=pq，其中，其中p和和q是两个保密的大素数。

是两个保密的大素数k：固定的正整数固定的正整数 ：用户：用户A的私钥，的私钥， ：用户：用户A的公钥，的公钥， 现代密码学现代密码学电子科技大学电子科技大学u（2）签名 对于消息对于消息m，，A执行以下步骤：执行以下步骤：①① 随机选择整数随机选择整数r,1≤r≤n 1②② 计算计算u   r mod n③③ 计算计算e=（（e , e ,…, e ））=h（（m, u），），e ∈ ∈{0,1}④④ 计算计算 对消息对消息m的签名为（的签名为（e, s）现代密码学现代密码学电子科技大学电子科技大学u（（3）验证）验证 接收者在收到消息接收者在收到消息m和签名（和签名（e, s）后，通）后，通过以下步骤来检验签名的合法性：过以下步骤来检验签名的合法性：①① 计算计算 。

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

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

执行该协议可以使用户成为群成员，群管式协议执行该协议可以使用户成为群成员，群管理员得到群成员的秘密的成员管理密钥，并产生群理员得到群成员的秘密的成员管理密钥，并产生群成员的私钥和成员证书成员的私钥和成员证书现代密码学现代密码学电子科技大学电子科技大学 1．群签名．群签名电子科技大学 现代密码学现代密码学电子科技大学电子科技大学（（3）签名（）签名（sign）） 一个概率算法，当输入一个概率算法，当输入一个消息、一个群成员的私钥和一个群公一个消息、一个群成员的私钥和一个群公钥后，输出对该消息的签名钥后，输出对该消息的签名4）验证（）验证（verify）） 给定一个消息的签名和给定一个消息的签名和一个群公钥后，判断该签名相对于该群公一个群公钥后，判断该签名相对于该群公钥是否有效钥是否有效5）打开（）打开（open）） 给定一个签名、群公钥给定一个签名、群公钥和群私钥的条件下确定签名者的身份和群私钥的条件下确定签名者的身份 群签名群签名一个好的群签名方案应该满足以下几条性质：① ① 正确性（正确性（correctnesscorrectness））② ② 不可伪造性（不可伪造性（unforgeabilityunforgeability）） ③ ③ 匿名性（匿名性（anonymityanonymity）） ④ ④ 不可关联性（不可关联性（unlinkabilityunlinkability）） ⑤ ⑤ 可跟踪性（可跟踪性（traceabilitytraceability）） ⑥ ⑥ 可开脱性（可开脱性（exculpabilityexculpability）） ⑦ ⑦ 抗联合攻击（抗联合攻击（coalition-resistancecoalition-resistance）） 现代密码学现代密码学电子科技大学电子科技大学电子科技大学电子科技大学 群签名群签名2．代理签名 一个代理签名方案由以下几个部分组成：u系统建立 选定代理签名方案的系统参数，用户选定代理签名方案的系统参数，用户的密钥等。

的密钥等u签名权力的委托 原始签名者将自己的签名权力原始签名者将自己的签名权力委托给代理签名者委托给代理签名者u代理签名的产生 代理签名者代表原始签名者产代理签名者代表原始签名者产生代理签名生代理签名u代理签名的验证 验证人验证代理签名的有效性验证人验证代理签名的有效性 现代密码学现代密码学电子科技大学电子科技大学 根据签名权力委托的方式不同，代理签名可以分为以下几类：（（1）完全代理（）完全代理（full delegation）） （（2）部分代理（）部分代理（partial delegation））（（3）具有证书的代理（）具有证书的代理（delegation by warrant））（（4）具有证书的部分代理（）具有证书的部分代理（partial delegation with warrant））现代密码学现代密码学电子科技大学电子科技大学2．代理签名 根据原始签名者能否产生同代理签名者一样的签名，代理签名又可分为两类：1）代理非保护（）代理非保护（proxy-unprotected）） 原始原始签名者能够产生有效的代理签名签名者能够产生有效的代理签名。

2）代理保护（）代理保护（proxy-protected）） 原始签名原始签名者不能够产生有效的代理签名者不能够产生有效的代理签名现代密码学现代密码学电子科技大学电子科技大学2．代理签名 一个强代理签名方案应满足以下几条性质：①① 可区分性（可区分性（distinguishability））②② 可验证性（可验证性（verifiability））③③ 强不可伪造性（强不可伪造性（strong unforgeability）） ④④强可识别性（强可识别性（strong identifiability）） ⑤⑤ 强不可否认性（强不可否认性（strong undeniability））⑥⑥ 防止滥用（防止滥用（prevention of misuse））现代密码学现代密码学电子科技大学电子科技大学3. 盲签名 盲签名允许使用者获得一个消息的签名，而盲签名允许使用者获得一个消息的签名，而签名者既不知道该消息的内容，也不知道该签名者既不知道该消息的内容，也不知道该消息的签名盲签名可用于需要提供匿名性消息的签名盲签名可用于需要提供匿名性的密码协议中，如电子投票和电子现金的密码协议中，如电子投票和电子现金。

一个盲签名方案由以下几个部分组成：（（1）消息盲化）消息盲化 使用者利用盲因子对要签名的使用者利用盲因子对要签名的消息进行盲化处理，然后将盲化后的消息发消息进行盲化处理，然后将盲化后的消息发送给签名者送给签名者现代密码学现代密码学电子科技大学电子科技大学电子科技大学 现代密码学现代密码学电子科技大学电子科技大学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．简述群签名、代理签名和盲签名的用途．简述群签名、代理签名和盲签名的用途。

现代密码学现代密码学电子科技大学电子科技大学习题习题。