第5章 数字签名 5.1 数字签名的基本概念 5.2 RSA数字签名 5.3 ElGamal数字签名 5.4 数字签名标准DSS

Presentation on theme: "第5章 数字签名 5.1 数字签名的基本概念 5.2 RSA数字签名 5.3 ElGamal数字签名 5.4 数字签名标准DSS"— Presentation transcript:

1 第5章 数字签名 5.1 数字签名的基本概念 5.2 RSA数字签名 5.3 ElGamal数字签名 5.4 数字签名标准DSS
现代密码学 第5章 数字签名 5.1 数字签名的基本概念 5.2 RSA数字签名 5.3 ElGamal数字签名 5.4 数字签名标准DSS 5.5 其他数字签名 基于离散对数问题的数字签名 基于大整数分解问题的数字签名 具有特殊用途的数字签名 电子科技大学

2 5.1 数字签名的基本概念 数字签名应具有以下特性： （1）不可伪造性 除了签名者外，任何人都不能伪造签名者的合法签名。
现代密码学 5.1 数字签名的基本概念 数字签名应具有以下特性： （1）不可伪造性 除了签名者外，任何人都不能伪造签名者的合法签名。 （2）认证性 接收者相信这份签名来自签名者。 （3）不可重复使用性 一个消息的签名不能用于其他消息。 （4）不可修改性 一个消息在签名后不能被修改。 （5）不可否认性 签名者事后不能否认自己的签名。 电子科技大学

3 算法的安全性在于从m和s难以推出密钥k或伪造一个消息使和s可被验证为真。
现代密码学 一个数字签名体制（也称为数字签名方案）一般有两个组成部分，即签名算法（signature algorithm）和验证算法（verification algorithm）。签名算法的输入是消息m和密钥k，输出是对m的数字签名，记为s = （m）。验证算法输入的是消息m和签名s，输出是真或伪，记为： 算法的安全性在于从m和s难以推出密钥k或伪造一个消息使和s可被验证为真。 电子科技大学

4 数字签名的分类 数字签名可按以下几种方式进行分类：
现代密码学 数字签名的分类 数字签名可按以下几种方式进行分类： ① 按用途来分，数字签名可分为普通数字签名和具有特殊用途的数字签名[如盲签名（blind signature）、不可否认签名（undeniable signature）、群签名（group signature）、代理签名（proxy signature）等]。 电子科技大学

5 ② 按是否具有消息恢复功能来分，数字签名可分为具有消息恢复功能的数字签名和不具有消息恢复功能的数字签名。
③ 按是否使用随机数来分，数字签名可分为确定性数字签名和随机化数字签名（randomized digital signature）

6 5.2 RSA数字签名 1．参数与密钥生成 （1）选取两个保密的大素数p和q。 （2）计算n = pq, ，其中 是n的欧拉函数值。
现代密码学 5.2 RSA数字签名 1．参数与密钥生成 （1）选取两个保密的大素数p和q。 （2）计算n = pq, ，其中 是n的欧拉函数值。 （3）随机选取整数e，1＜e＜ ，满足 。 （4）计算d，满足 。 （5）公钥为(e,n)，私钥为d。 电子科技大学

7 5.2 RSA数字签名 2．签名 对于消息m∈ ，签名为： 3．验证 对于消息签名对(m, s)，如果： 则s是m的有效签名。 现代密码学
电子科技大学

8 现代密码学 RSA数字签名方案存在以下缺陷： ① 任何人都可以伪造某签名者对于随机消息m的签名s。其方法是先选取s，再用该签名者的公钥(e,n)计算 。s就是该签名者对消息m的签名。 电子科技大学

9 ② 如果敌手知道消息 和 的签名分别是 和 ，则敌手可以伪造 的签名 ，这是因为在RSA签名方案中，存在以下性质：

10 ③ 由于在RSA签名方案中，要签名的消息 ，所以每次只能对位长的消息进行签名。然而，实际需要签名的消息可能比n大，解决的办法是先对消息进行分组，然后对每组消息分别进行签名。这样做的缺点是签名长度变长，运算量增大。

11 克服上述缺陷的方法之一是在对消息进行签名前先对消息做Hash变换，然后对变换后的消息进行签名。即签名为：
现代密码学 克服上述缺陷的方法之一是在对消息进行签名前先对消息做Hash变换，然后对变换后的消息进行签名。即签名为： 验证时，先计算h（m），再检查等式： 是否成立。 电子科技大学

12 现代密码学 5.3 ElGamal数字签名 电子科技大学

13 5.3 ElGamal数字签名算法 1．参数与密钥生成 ① 选取大素数p, 是一个本原元。p和g公开。
现代密码学 5.3 ElGamal数字签名算法 1．参数与密钥生成 ① 选取大素数p, 是一个本原元。p和g公开。 ② 随机选取整数x,1≤x≤p2，计算 ③ 公钥为y，私钥为x。 电子科技大学

14 5.3 ElGamal数字签名算法 2．签名 对于消息m，首先随机选取一个整数k, 1≤k≤p2 ，然后计算：
则m的签名为(r, s)，其中h为Hash函数。

15 5.3 ElGamal数字签名算法 3．验证 对于消息签名对(m, (r, s))，如果： 则(r, s)是m的有效签名。

16 现代密码学 5.4 DSS数字签名标准 电子科技大学

17 现代密码学 5.4 DSS数字签名标准 1．参数与密钥生成 ① 选取大素数p，满足 ＜p＜ ，其中512≤L≤1024且L是64的倍数。显然，p是L位长的素数，L从512到1024且是64的倍数。 ② 选取大素数q，q是p1的一个素因子且 ，即q是160位的素数且是p1的素因子。 电子科技大学

18 5.4 DSS数字签名标准 1．参数与密钥生成 ③ 选取一个生成元 ，其中h是一个整数，满足1＜h＜p1并且 。
④ 随机选取整数x，0＜x＜q，计算 。 ⑤ p、q和g是公开参数，y为公钥，x为私钥。

19 2．签名 5.4 DSS数字签名标准 对于消息m，首先随机选取一个整数k , 0＜k＜q，然后计算：
现代密码学 5.4 DSS数字签名标准 2．签名 对于消息m，首先随机选取一个整数k , 0＜k＜q，然后计算： 则m的签名为(r, s)，其中h为Hash函数，DSS规定Hash函数为SHA-1。 电子科技大学

20 3．验证 对于消息签名对(m, (r, s))，首先计算： 然后验证： 如果等式成立，则(r, s)是m的有效签名；否则签名无效。

21 DSS的框图下图所示，其中的4个函数分别为：
现代密码学 DSS的框图下图所示，其中的4个函数分别为： 电子科技大学

22 现代密码学 5.5 其他数字签名 基于离散对数问题的数字签名 电子科技大学

23 ElGamal签名方案、DSA签名方案、Schnorr签名方案都可以归结为离散对数签名方案的特例。
现代密码学 1．离散对数签名方案 ElGamal签名方案、DSA签名方案、Schnorr签名方案都可以归结为离散对数签名方案的特例。 电子科技大学

24 （1）参数与密钥生成 p：大素数。 1．离散对数签名方案 q：p 1或p  1的大素因子。
g： ，且 ，其中 表示g 是从 中随机选取的，这里的 。 x：用户A的私钥，1＜x＜q。 y：用户A的公钥，y  g x mod p。

25 1．离散对数签名方案 （2）签名 对于消息m，A执行以下步骤： ① 计算的m的Hash值h(m)。 ② 随机选择整数k,1＜k＜q。
现代密码学 1．离散对数签名方案 （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)。 电子科技大学

26 现代密码学 表5-1 参数a、b、c可能的选择 1 注：表中 。 电子科技大学

27 接收者在收到消息m和签名(r, s)后，可以按照以下验证方程检查签名的合法性：
现代密码学 1．离散对数签名方案 （3）验证 接收者在收到消息m和签名(r, s)后，可以按照以下验证方程检查签名的合法性： 电子科技大学

28 2．Schnorr签名方案 （1）参数与密钥生成 p：大素数且p≥2512 。 q：大素数且q|（p1）, q≥2160 。
现代密码学 2．Schnorr签名方案 （1）参数与密钥生成 p：大素数且p≥ 。 q：大素数且q|（p1）, q≥ 。 g： ，且gq  1 mod p。 x：用户A的私钥，1＜x＜q。 y：用户A的公钥，y  gx mod p。 电子科技大学

29 2．Schnorr签名方案 （2）签名 对于消息m，A执行以下步骤： ① 随机选择整数k,1＜k＜q。 ② 计算r  gk mod p。
现代密码学 2．Schnorr签名方案 （2）签名 对于消息m，A执行以下步骤： ① 随机选择整数k,1＜k＜q。 ② 计算r  gk mod p。 ③ 计算e=h（r,m）。 ④ 计算s （xe+k）mod q。 对消息m的签名为（e, s）。 电子科技大学

30 2．Schnorr签名方案 （3）验证 接收者在收到消息m和签名（e, s）后，通过以下步骤来检验签名的合法性： ① 计算 。
现代密码学 2．Schnorr签名方案 （3）验证 接收者在收到消息m和签名（e, s）后，通过以下步骤来检验签名的合法性： ① 计算 。 ② 按照以下方程进行验证： Schnorr签名的正确性可由下式证明： 电子科技大学

31 3．Nyberg-Rueppel签名方案 （1）参数与密钥生成 p：大素数。 q：大素数且q|（p1）。
现代密码学 3．Nyberg-Rueppel签名方案 （1）参数与密钥生成 p：大素数。 q：大素数且q|（p1）。 g： ，且gq  1 mod p。 x：用户A的私钥，1＜x＜q。 y：用户A的公钥，y  gx mod p 电子科技大学

32 （2）签名 对于消息m，A执行以下步骤： ① 计算 ，其中R是从消息空间到签名空间的一个单一映射，并且容易求逆，称为冗余函数。 ② 随机选择整数k，1≤k≤q1。 ③ 计算r  g-k mod p。 ④ 计算 。 ⑤ 计算s （xe+k）mod q。 对消息m的签名为（e, s）。

33 接收者在收到消息m和签名（e, s）后，通过以下步骤来验证签名的合法性： ①验证是否有0＜e＜p成立，如果不成立，拒绝该签名。
现代密码学 （3）验证 接收者在收到消息m和签名（e, s）后，通过以下步骤来验证签名的合法性： ①验证是否有0＜e＜p成立，如果不成立，拒绝该签名。 ②验证是否有0≤s＜p成立，如果不成立，拒绝该签名。 电子科技大学

34 ④验证是否有 ，如果 ，拒绝该签名，这里M R 表示R的值域。 ⑤恢复消息 。 下面证明Nyberg-Rueppel签名方案的正确性。 因为
现代密码学 ③计算 和 。 ④验证是否有 ，如果 ，拒绝该签名，这里M R 表示R的值域。 ⑤恢复消息 。 下面证明Nyberg-Rueppel签名方案的正确性。 因为 所以 电子科技大学

35 1．Feige-Fiat-Shamir签名方案 （1）参数与密钥生成 n：n=pq，其中p和q是两个保密的大素数。 k：固定的正整数。
现代密码学 5.5.2 基于大整数分解的数字签名方案 1．Feige-Fiat-Shamir签名方案 （1）参数与密钥生成 n：n=pq，其中p和q是两个保密的大素数。 k：固定的正整数。 ：用户A的私钥， 。 ：用户A的公钥， 电子科技大学

36 ③ 计算e=（e , e ,…, e ）=h（m, u），e ∈{0,1}。 ④ 计算 。 对消息m的签名为（e, s）。
现代密码学 （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）。 电子科技大学

37 接收者在收到消息m和签名（e, s）后，通过以下步骤来检验签名的合法性： ① 计算 。 ② 按照以下方程进行验证：
现代密码学 （3）验证 接收者在收到消息m和签名（e, s）后，通过以下步骤来检验签名的合法性： ① 计算 。 ② 按照以下方程进行验证： Feige-Fiat-Shamir签名的正确性可由下式证明： 电子科技大学

38 2．Guillou-Quisquater签名方案
现代密码学 2．Guillou-Quisquater签名方案 （1）参数与密钥生成 n：n = pq，其中p和q是两个保密的大素数。 k：k ∈{1, 2,, n1}且 x：用户A的私钥， 。 y：用户A的公钥， 且 。 电子科技大学

39 （2）签名 对于消息m，A执行以下步骤： ① 随机选择整数 。 ② 计算u  rk mod n。 ③ 计算e=h（m,u）。
现代密码学 （2）签名 对于消息m，A执行以下步骤： ① 随机选择整数 。 ② 计算u  rk mod n。 ③ 计算e=h（m,u）。 ④ 计算s=rxe mod n。 对消息m的签名为（e, s）。 电子科技大学

40 接收者在收到消息m和签名（e, s）后，通过以下步骤来验证签名的合法性： ① 计算 。 ② 按照以下方程进行验证：
现代密码学 （3）验证 接收者在收到消息m和签名（e, s）后，通过以下步骤来验证签名的合法性： ① 计算 。 ② 按照以下方程进行验证： Guillou-Quisquater签名的正确性可由下式证明： 电子科技大学

41 5.5.3 具有特殊用途的数字签名 1．群签名 群签名具有以下特点： 只有群体中的合法成员才能代表整个群体进行签名。
现代密码学 具有特殊用途的数字签名 1．群签名 群签名具有以下特点： 只有群体中的合法成员才能代表整个群体进行签名。 接收者可以用群公钥验证群签名的合法性，但不知道该群签名是由群体中的哪个成员所签。 在发生争议时，群管理员（权威机构）可以识别出实际的签名者。 电子科技大学

42 1．群签名 一个群签名方案由以下几个部分组成： （1）建立（setup） 一个用以产生群公钥和私钥的多项式概率算法。
现代密码学 1．群签名 一个群签名方案由以下几个部分组成： （1）建立（setup） 一个用以产生群公钥和私钥的多项式概率算法。 （2）加入（join） 一个用户和群管理员之间的交互式协议。执行该协议可以使用户成为群成员，群管理员得到群成员的秘密的成员管理密钥，并产生群成员的私钥和成员证书。 电子科技大学

43 群签名 （3）签名（sign） 一个概率算法，当输入一个消息、一个群成员的私钥和一个群公钥后，输出对该消息的签名。 （4）验证（verify） 给定一个消息的签名和一个群公钥后，判断该签名相对于该群公钥是否有效。 （5）打开（open） 给定一个签名、群公钥和群私钥的条件下确定签名者的身份。

44 一个好的群签名方案应该满足以下几条性质： ① 正确性（correctness） ② 不可伪造性（unforgeability）
现代密码学 群签名 一个好的群签名方案应该满足以下几条性质： ① 正确性（correctness） ② 不可伪造性（unforgeability） ③ 匿名性（anonymity） ④ 不可关联性（unlinkability） ⑤ 可跟踪性（traceability） ⑥ 可开脱性（exculpability） ⑦ 抗联合攻击（coalition-resistance） 电子科技大学 电子科技大学

45 2．代理签名 一个代理签名方案由以下几个部分组成： 系统建立 选定代理签名方案的系统参数，用户的密钥等。
现代密码学 2．代理签名 一个代理签名方案由以下几个部分组成： 系统建立 选定代理签名方案的系统参数，用户的密钥等。 签名权力的委托 原始签名者将自己的签名权力委托给代理签名者。 代理签名的产生 代理签名者代表原始签名者产生代理签名。 代理签名的验证 验证人验证代理签名的有效性。 电子科技大学

46 根据签名权力委托的方式不同，代理签名可以分为以下几类： （1）完全代理（full delegation）
现代密码学 2．代理签名 根据签名权力委托的方式不同，代理签名可以分为以下几类： （1）完全代理（full delegation） （2）部分代理（partial delegation） （3）具有证书的代理（delegation by warrant） （4）具有证书的部分代理（partial delegation with warrant） 电子科技大学

47 根据原始签名者能否产生同代理签名者一样的签名，代理签名又可分为两类：
现代密码学 2．代理签名 根据原始签名者能否产生同代理签名者一样的签名，代理签名又可分为两类： 1）代理非保护（proxy-unprotected） 原始签名者能够产生有效的代理签名。 2）代理保护（proxy-protected） 原始签名者不能够产生有效的代理签名。 电子科技大学

48 ① 可区分性（distinguishability） ② 可验证性（verifiability）
现代密码学 一个强代理签名方案应满足以下几条性质： ① 可区分性（distinguishability） ② 可验证性（verifiability） ③ 强不可伪造性（strong unforgeability） ④强可识别性（strong identifiability） ⑤ 强不可否认性（strong undeniability） ⑥ 防止滥用（prevention of misuse） 电子科技大学

49 现代密码学 3. 盲签名 盲签名允许使用者获得一个消息的签名，而签名者既不知道该消息的内容，也不知道该消息的签名。盲签名可用于需要提供匿名性的密码协议中，如电子投票和电子现金。 一个盲签名方案由以下几个部分组成： （1）消息盲化 使用者利用盲因子对要签名的消息进行盲化处理，然后将盲化后的消息发送给签名者。 电子科技大学

50 3. 盲签名 （2）盲消息签名 签名者对盲化后的消息进行签名，因此他并不知道真实消息的具体内容。
3. 盲签名 （2）盲消息签名 签名者对盲化后的消息进行签名，因此他并不知道真实消息的具体内容。 （3）恢复签名 使用者除去盲因子，得到真实消息的签名。

51 习题 1．在RSA签名方案中，设p = 7，q = 17，公钥e=5，消息m的Hash值为19，试计算私钥d并给出对该消息的签名和验证过程。
现代密码学 习题 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时的签名和验证过程。 电子科技大学

52 习题 3．试给出椭圆曲线上的ElGamal签名方案。
4．在DSA签名算法中，如果一个签名者在对两个不同的消息签名时使用了相同的随机整数k，试显示攻击者可以恢复出该签名者的私钥。

53 现代密码学 习题 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．简述群签名、代理签名和盲签名的用途。 电子科技大学