Winnermakesithappenloserletithappen数字签名课件

《Winnermakesithappenloserletithappen数字签名课件》由会员分享，可在线阅读，更多相关《Winnermakesithappenloserletithappen数字签名课件（79页珍藏版）》请在金锄头文库上搜索。

1、数字签名数字签名现代密码学第现代密码学第8章章1Winnermakesithappenloserletithappen数字签名本章主要内容本章主要内容n1 1、数字签名的基本概念数字签名的基本概念n2、数字签名标准、数字签名标准n3、其他签名方案、其他签名方案n习题习题2Winnermakesithappenloserletithappen数字签名 数字签名由公钥密码发展而来，它在网络安全，包括身份认证、数据完整性、不可否认性以及匿名性等方面有着重要应用。本章首先介绍数字签名的基本概念和一些常用的数字签名算法，然后介绍身份认证协议、身份证明技术以及其他一些常用的密码协议。1. 数字签名的基本概

2、念数字签名的基本概念3Winnermakesithappenloserletithappen数字签名 上一章介绍的消息认证其作用是保护通信双方以防第三方的攻击，然而却不能保护通信双方中的一方防止另一方的欺骗或伪造。通信双方之间也可能有多种形式的欺骗，例如通信双方A和B（设A为发方，B为收方）使用消息认证码的基本方式通信，则可能发生以下欺骗： 1.1 数字签名应满足的要求数字签名应满足的要求4Winnermakesithappenloserletithappen数字签名 B伪造一个消息并使用与A共享的密钥产生该消息的认证码，然后声称该消息来自于A。 由于B有可能伪造A发来的消息，所以A就可以对自

3、己发过的消息予以否认。 这两种欺骗在实际的网络安全应用中都有可能发生，例如在电子资金传输中，收方增加收到的资金数，并声称这一数目来自发方。又如用户通过电子邮件向其证券经纪人发送对某笔业务的指令，以后这笔业务赔钱了，用户就可否认曾发送过相应的指令。数字签名应满足的要求数字签名应满足的要求5Winnermakesithappenloserletithappen数字签名 因此在收发双方未建立起完全的信任关系且存在利害冲突的情况下，单纯的消息认证就显得不够。数字签名技术则可有效解决这一问题。类似于手书签名，数字签名应具有以下性质： 能够验证签名产生者的身份，以及产生签名的日期和时间。 能用于证实被签消

4、息的内容。 数字签名可由第三方验证，从而能够解决通信双方的争议。数字签名应满足的要求数字签名应满足的要求6Winnermakesithappenloserletithappen数字签名 由此可见，数字签名具有认证功能。为实现上述3条性质，数字签名应满足以下要求： 签名的产生必须使用发方独有的一些信息以防伪造和否认。 签名的产生应较为容易。 签名的识别和验证应较为容易。 对已知的数字签名构造一新的消息或对已知的消息构造一假冒的数字签名在计算上都是不可行的。数字签名应满足的要求数字签名应满足的要求7Winnermakesithappenloserletithappen数字签名 数字签名的产生可用加

5、密算法或特定的签名算法。1. 由加密算法产生数字签名利用加密算法产生数字签名是指将消息或消息的摘要加密后的密文作为对该消息的数字签名，其用法又根据是单钥加密还是公钥加密而有所不同。1.2 数字签名的产生方式数字签名的产生方式8Winnermakesithappenloserletithappen数字签名(1) 单钥加密 如图1(a)所示，发送方A根据单钥加密算法以与接收方B共享的密钥K对消息M加密后的密文作为对M的数字签名发往B。该系统能向B保证所收到的消息的确来自A，因为只有A知道密钥K。再者B恢复出M后，可相信M未被篡改，因为敌手不知道K就不知如何通过修改密文而修改明文。具体来说，就是B执

6、行解密运算Y=DK(X)，如果X是合法消息M加密后的密文，则B得到的Y就是明文消息M，否则Y将是无意义的比特序列。1. 由加密算法产生数字签名由加密算法产生数字签名9Winnermakesithappenloserletithappen数字签名消息加密产生数字签名的基本方式消息加密产生数字签名的基本方式10Winnermakesithappenloserletithappen数字签名(2) 公钥加密 如图1(b)所示，发送方A使用自己的秘密钥SKA对消息M加密后的密文作为对M的数字签名，B使用A的公开钥PKA对消息解密，由于只有A才拥有加密密钥SKA，因此可使B相信自己收到的消息的确来自A。然

7、而由于任何人都可使用A的公开钥解密密文，所以这种方案不提供保密性。为提供保密性，A可用B的公开钥再一次加密，如图1(c)所示。1. 由加密算法产生数字签名由加密算法产生数字签名11Winnermakesithappenloserletithappen数字签名 下面以RSA签名体制为例说明数字签名的产生过程。 体制参数。选两个保密的大素数p和q，计算n=pq，(n)=(p-1)(q-1)；选一整数e，满足1e(n)，且gcd(n),e)=1；计算d，满足de1 mod (n)；以e,n为公开钥,d,n为秘密钥。 签名过程。设消息为M，对其签名为SMd mod n1. 由加密算法产生数字签名由加密

8、算法产生数字签名12Winnermakesithappenloserletithappen数字签名 验证过程。 接收方在收到消息M和签名S后，验证 是否成立，若成立，则发送方的签名有效。实际应用时，数字签名是对消息摘要加密产生，而不是直接对消息加密产生，如图6.3(a)图6.3(d)所示。1. 由加密算法产生数字签名由加密算法产生数字签名13Winnermakesithappenloserletithappen数字签名 由加密算法产生数字签名又分为外部保密方式外部保密方式和内部保密方式内部保密方式，外部保密方式是指数字签名是直接对需要签名的消息生成而不是对已加密的消息生成，否则称为内部保密方式

9、。 外部保密方式便于解决争议，因为第3方在处理争议时，需得到明文消息及其签名。但如果采用内部保密方式，第3方必须得到消息的解密密钥后才能得到明文消息。如果采用外部保密方式，接收方就可将明文消息及其数字签名存储下来以备以后万一出现争议时使用。1. 由加密算法产生数字签名由加密算法产生数字签名14Winnermakesithappenloserletithappen数字签名2. 由签名算法产生数字签名 签名算法的输入是明文消息M和密钥x，输出是对M的数字签名，表示为S=Sigx(M)。相应于签名算法，有一验证算法，表示为Verx(S,M)，其取值为 算法的安全性在于从M和S难以推出密钥x或伪造一个

10、消息M使M和S可被验证为真。2. 由签名算法产生数字签名由签名算法产生数字签名15Winnermakesithappenloserletithappen数字签名公钥签名方案公钥签名方案n公钥签名方案： n利用私钥生成签名，利用公钥验证签名，只有私钥的拥有者才能生成签名，所以能够用于证明谁生成的消息。 n任何知道公钥的人可以验证消息，（他们要确认公钥拥有者的身份，这是公钥的密钥分配问题），通常不对整个消息签名，因为这将会使交换信息长度增加一倍，使用消息的 hashhash 值，n数字签名可以提供消息的不可否认性, 16Winnermakesithappenloserletithappen数字签名

11、 数字签名的执行方式有两类： 直接方式和具有仲裁的方式。1. 直接方式 直接方式是指数字签名的执行过程只有通信双方参与，并假定双方有共享的秘密钥或接收一方知道发方的公开钥。1.3 数字签名的执行方式数字签名的执行方式17Winnermakesithappenloserletithappen数字签名 直接方式的数字签名有一公共弱点，即方案的有效性取决于发方秘密钥的安全性。如果发方想对已发出的消息予以否认，就可声称自己的秘密钥已丢失或被窃，因此自己的签名是他人伪造的。可采取某些行政手段，虽然不能完全避免但可在某种程度上减弱这种威胁。例如，要求每一被签名的消息都包含有一个时戳（日期和时间）并要求密钥

12、丢失后立即向管理机构报告。这种方式的数字签名还存在发方的秘密钥真的被偷的危险，例如敌手在时刻T偷得发方的秘密钥，然后可伪造一消息，用偷得的秘密钥为其签名并加上T以前的时刻作为时戳。1. 直接方式直接方式18Winnermakesithappenloserletithappen数字签名 上述直接方式的数字签名所具有的缺陷都可通过使用仲裁者得以解决。和直接方式的数字签名一样，具有仲裁方式的数字签名也有很多实现方案，这些方案都按以下方式运行： 发方X对发往收方Y的消息签名后，将消息及其签名先发给仲裁者A，A对消息及其签名验证完后，再连同一个表示已通过验证的指令一起发往收方Y。此时由于A的存在，X无法

13、对自己发出的消息予以否认。在这种方式中，仲裁者起着重要的作用并应取得所有用户的信任。2. 具有仲裁方式的数字签名具有仲裁方式的数字签名19Winnermakesithappenloserletithappen数字签名 以下是具有仲裁方式数字签名的几个实例，其中X表示发方，Y表示收方，A是仲裁者，M是消息，XY： M表示X给Y发送一消息M。2. 具有仲裁方式的数字签名具有仲裁方式的数字签名20Winnermakesithappenloserletithappen数字签名例1 签名过程如下： XA：MEKXAIDXH(M)。 AY：EKAYIDXMEKXAIDXH(M)T。 其中E是单钥加密算法，

14、KXA和KAY分别是X与A共享的密钥和A与Y共享的密钥，H(M)是M的杂凑值，T是时戳，IDX是X的身份。2. 具有仲裁方式的数字签名具有仲裁方式的数字签名21Winnermakesithappenloserletithappen数字签名 在中，X以EKXAIDXH(M)作为自己对M的签名，将M及签名发往A。在中A将从X收到的内容和IDX、T一起加密后发往Y，其中的T用于向Y表示所发的消息不是旧消息的重放。Y对收到的内容解密后,将解密结果存储起来以备出现争议时使用。2. 具有仲裁方式的数字签名具有仲裁方式的数字签名22Winnermakesithappenloserletithappen数字签

15、名n如果出现争议，Y可声称自己收到的M的确来自X，并将EKAYIDXMEKXAIDXH(M)n发给A，由A仲裁，A由KAY解密后，再用KXA对EKXAIDXH(M)解密，并对H(M)加以验证，从而验证了X的签名。2. 具有仲裁方式的数字签名具有仲裁方式的数字签名23Winnermakesithappenloserletithappen数字签名 以上过程中，由于Y不知KXA，因此不能直接检查X的签名，但Y认为消息来自于A因而是可信的。 所以在整个过程中，A必须取得X和Y的高度信任： X相信A不会泄露KXA，并且不会伪造X的签名; Y相信A只有在对EKAYIDXMEKXAIDXH(M)T中的杂凑值

16、及X的签名验证无误后才将之发给Y; X，Y都相信A可公正地解决争议。 如果A已取得各方的信任，则X就能相信没有人能伪造自己的签名，Y就可相信X不能对自己的签名予以否认。2. 具有仲裁方式的数字签名具有仲裁方式的数字签名24Winnermakesithappenloserletithappen数字签名 本例中消息M是以明文形式发送的，因此未提供保密性，下面两个例子可提供保密性。例2 签名过程如下： XA: IDXEKXYMEKXAIDXH(EKXYM)。 AY: EKAYIDXEKXYMEKXAIDXH(EKXYM)T。2. 具有仲裁方式的数字签名具有仲裁方式的数字签名25Winnermakes

17、ithappenloserletithappen数字签名 其中KXY是X，Y共享的密钥，其他符号与例1相同。X以EKXAIDXH(EKXYM)作为对M的签名，与由KXY加密的消息M一起发给A。A对EKXAIDXH(EKXYM)解密后通过验证杂凑值以验证X的签名，但始终未能读取明文M。 A验证完X的签名后，对X发来的消息加一时戳，再用KAY加密后发往Y。解决争议的方法与例1一样。2. 具有仲裁方式的数字签名具有仲裁方式的数字签名26Winnermakesithappenloserletithappen数字签名 本例虽然提供了保密性，但还存在与上例相同的一个问题，即仲裁者可和发方共谋以否认发方曾发

18、过的消息，也可和收方共谋以伪造发方的签名。这一问题可通过下例所示的采用公钥加密技术的方法得以解决。 例3 签名过程如下： XA：IDXESKXIDXEPKYESKXM。 AY：ESKAIDXEPKYESKXMT。2. 具有仲裁方式的数字签名具有仲裁方式的数字签名27Winnermakesithappenloserletithappen数字签名 其中SKA和SKX分别是A和X的秘密钥，PKY是Y的公开钥，其他符号与前两例相同。 第步中，X用自己的秘密钥SKX和Y的公开钥PKY对消息加密后作为对M的签名，以这种方式使得任何第3方（包括A）都不能得到M的明文消息。A收到X发来的内容后，用X的公开钥可

19、对ESKXIDXEPKYESKXM解密，并将解密得到的IDX与收到的IDX加以比较，从而可确信这一消息是来自于X的（因只有X有SKX）。 第步，A将X的身份IDX和X对M的签名加上一时戳后，再用自己的秘密钥加密发往Y。2. 具有仲裁方式的数字签名具有仲裁方式的数字签名28Winnermakesithappenloserletithappen数字签名 与前两种方案相比，第3种方案有很多优点。 首先，在协议执行以前，各方都不必有共享的信息，从而可防止共谋。 第二，只要仲裁者的秘密钥不被泄露，任何人包括发方就不能发送重放的消息。 最后，对任何第三方（包括A）来说，X发往Y的消息都是保密的。2. 具有

20、仲裁方式的数字签名具有仲裁方式的数字签名29Winnermakesithappenloserletithappen数字签名数字签名标准DSS(Digital Signature Standard)是由美国NIST公布的联邦信息处理标准FIPS PUB 186，其中采用了上一章介绍的SHA和一新的签名技术，称为DSA(Digital Signature Algorithm)。DSS最初于1991年公布，在考虑了公众对其安全性的反馈意见后，于1993年公布了其修改版。2. 数字签名标准数字签名标准30Winnermakesithappenloserletithappen数字签名 首先将DSS与RS

21、A的签名方式做一比较。RSA算法既能用于加密和签名，又能用于密钥交换。与此不同，DSS使用的算法只能提供数字签名功能。图2用于比较RSA签名和DSS签名的不同方式。2.1 DSS的基本方式的基本方式31Winnermakesithappenloserletithappen数字签名RSA 签名签名nRSA 加密解密是可交换的 n可以用于数字签名方案 n给定 RSA 方案 (e,R), (d,p,q) n要签名消息M：计算: nS=Md(modR) n要验证签名,计算: nM=Se(modR)=Me.d(modR)=M(modR) 32Winnermakesithappenloserletitha

22、ppen数字签名n使用RSA加密、认证： n使用发送者的私钥签名一个消息，使用接收者的公钥加密消息n看起来，一个消息可用RSA加密、签名而不改变大小，但是，加密使用的是消息接收者的模，签名是消息发送者的模，后着可能比前者小n交换两者顺序？n签名常使用HASH函数值。RSA 签名的使用签名的使用33Winnermakesithappenloserletithappen数字签名RSA签名与签名与DSS签名的不同方式签名的不同方式34Winnermakesithappenloserletithappen数字签名 采用RSA签名时，将消息输入到一个杂凑函数以产生一个固定长度的安全杂凑值，再用发方的秘密

23、钥加密杂凑值就形成了对消息的签名。消息及其签名被一起发给收方，收方得到消息后再产生出消息的杂凑值，且使用发方的公开钥对收到的签名解密。 这样收方就得了两个杂凑值，如果两个杂凑值是一样的，则认为收到的签名是有效的。RSA签名与签名与DSS签名的不同签名的不同35Winnermakesithappenloserletithappen数字签名 DSS签名也利用一杂凑函数产生消息的一个杂凑值，杂凑值连同一随机数k一起作为签名函数的输入，签名函数还需使用发送方的秘密钥SKA和供所有用户使用的一族参数，称这一族参数为全局公开钥全局公开钥PKG。 RSA签名与签名与DSS签名的不同签名的不同36Winner

24、makesithappenloserletithappen数字签名n 签名函数的两个输出s和r就构成了消息的签名(s，r)。接收方收到消息后再产生出消息的杂凑值，将杂凑值与收到的签名一起输入验证函数，验证函数还需输入全局公开钥PKG和发送方的公开钥PKA。验证函数的输出如果与收到的签名成分r相等，则验证了签名是有效的。nRSA签名与签名与DSS签名的不同签名的不同37Winnermakesithappenloserletithappen数字签名n US Federal Govt approved signature scheme (FIPS PUB 186) ，使用 SHA hash alg，

25、NIST & NSA 在 90s初设计。 nDSA 是算法, DSS 是标准 n对此标准宣布的争议! n是否需要使用 RSAnDSA 是 ElGamal 及Schnorr algorithms 的变形n生成 320 bit 签名n安全性是基于离散对数 n被广泛接收2.2 数字签名算法数字签名算法DSA38Winnermakesithappenloserletithappen数字签名 DSA是在ElGamal和Schnorr两个签名方案(见下一节)的基础上设计的，其安全性基于求离散对数的困难性。算法描述如下： (1) 全局公开钥p：满足2L-1p2L 的大素数，其中512L1024且L是64的倍

26、数。q：p-1的素因子，满足2159q2160 ，即q长为160比特。g：gh(p-1)/q mod p，其中h是满足1h1的任一整数。DSA (Digital Signature Algorithm) 39Winnermakesithappenloserletithappen数字签名(2) 用户秘密钥xx是满足0xq的随机数或伪随机数。(3) 用户的公开钥yygx mod p。(4) 用户为待签消息选取的秘密数kk是满足0kq的随机数或伪随机数。(5) 签名过程用户对消息M的签名为(r, s)，其中r(gk mod p) mod q,sk-1(H(M)+xr) mod q，H(M)是由SHA

27、求出的杂凑值。数字签名算法数字签名算法DSA40Winnermakesithappenloserletithappen数字签名(6) 验证过程设接收方收到的消息为M，签名为(r,s)。计算w(s)-1 mod q,u1H(M)w mod qu2r w mod q,v(gu1yu2) mod p mod q 检查 ，若相等，则认为签名有效。这是因为若(M,r,s)=(M,r,s)，则数字签名算法数字签名算法DSA41Winnermakesithappenloserletithappen数字签名 算法的框图如图3所示，其中的4个函数分别为sf1H(M),k,x,r,qk-1(H(M)+xr) mo

28、d qr =f2(k,p,q,g)(gk mod p) mod qw =f3(s,q)(s)-1 mod qv =f4(y,q,g,H(M),w,r) (g(H(M)w) mod qyrw mod q) mod p mod q数字签名算法数字签名算法DSA42Winnermakesithappenloserletithappen数字签名DSA的框图的框图43Winnermakesithappenloserletithappen数字签名 由于离散对数的困难性，敌手从r恢复k或从s恢复x都是不可行的。 还有一个问题值得注意，即签名产生过程中的运算主要是求r的模指数运算r=(gk mod p) mo

29、d q，而这一运算与待签的消息无关，因此能被预先计算。 事实上，用户可以预先计算出很多r和k-1以备以后的签名使用，从而可大大加快产生签名的速度。数字签名算法数字签名算法DSA44Winnermakesithappenloserletithappen数字签名DSA 安全性安全性n基于离散对数，最初建议使用一个共同的 modulus p ；现在建议不同的工作组使用不同的 (p,q,g)。Gus Simmons 发现存在潜信道，能够泄露私钥45Winnermakesithappenloserletithappen数字签名 基于离散对数问题的数字签名体制是数字签名体制中最为常用的一类，其中包括ElG

30、amal签名体制、DSA签名体制、Okamoto签名体制等。3.1 基于离散对数问题的数字签名体制基于离散对数问题的数字签名体制3. 3. 其他签名方案其他签名方案46Winnermakesithappenloserletithappen数字签名 ElGamal、DSA、Okamoto等签名体制都可归结为离散对数签名体制的特例。(1) 体制参数p：大素数；q：p-1或p-1的大素因子；g：gRZ*p，且gq1(mod p)，其中gR Z*p表示g是从Z*p中随机选取的，其中Z*p=Zp-0；x：用户A的秘密钥，1xq；y：用户A的公开钥，ygx(mod p)。1. 离散对数签名体制离散对数签名

31、体制47Winnermakesithappenloserletithappen数字签名(2) 签名的产生过程 对于待签名的消息m，A执行以下步骤： 计算m的杂凑值H(m)。 选择随机数k：1kq，计算 rgk(mod p)。 从签名方程akb+cx(mod q)中解出s。方程的系数a、b、c有许多种不同的选择方法，表7.1给出了这些可能选择中的一小部分，以(r, s)作为产生的数字签名。（见171页表7.1）1. 离散对数签名体制离散对数签名体制48Winnermakesithappenloserletithappen数字签名(3) 签名的验证过程接收方在收到消息m和签名(r, s)后，可以按

32、照以下验证方程检验： 1. 离散对数签名体制离散对数签名体制49Winnermakesithappenloserletithappen数字签名2. ElGamal签名体制(1) 体制参数p：大素数；g：Z*p的一个生成元；x：用户A的秘密钥，xRZ*p；y：用户A的公开钥，ygx(mod p)。2.2.ElGamal签名体制签名体制50Winnermakesithappenloserletithappen数字签名El Gamal Signature Scheme nElGamal 加密算法是不可交换的，存在一个相关的签名算法，安全性是基于计算离散对数的困难性，方案的密钥生成是相同的: n有个共

33、享的素数 p, 公开的本原根 a n每个用户选择一个随机数作为私钥 x n计算各自的公开密钥: y=axmodp n公钥是 (y,a,p) n私钥是 (x) 51Winnermakesithappenloserletithappen数字签名El Gamal 签名方案的使用签名方案的使用n签名消息 M: n选择随机数 k,GCD(k,p-1)=1 n计算 K=ak(modp) n用 Euclidean (inverse) 扩展算法求 S:M=x.K+k.Smod(p-1); 即求nS=k-1(M-x.K)mod(p-1) n签名是 (K,S) ，k 应该被销毁n同ElGamal 加密方案， 签名

34、信息也是消息的2倍n验证 (K,S) 是 对M的签名: yK.KSmodp=aMmodp 52Winnermakesithappenloserletithappen数字签名(2) 签名的产生过程对于待签名的消息m，A执行以下步骤： 计算m的杂凑值H(m)。 选择随机数k：kZ*p，计算rgk(mod p)。 计算s(H(m)-xr)k-1(mod p-1)。以(r,s)作为产生的数字签名。ElGamal签名体制签名体制53Winnermakesithappenloserletithappen数字签名(3) 签名验证过程 接收方在收到消息m和数字签名(r, s)后，先计算H(m)，并按下式验证：

35、 正确性可由下式证明：ElGamal签名体制签名体制54Winnermakesithappenloserletithappen数字签名ElGamal 签名方案举例签名方案举例n取 p=11, g=2；选择私钥 x=8 ；n计算: y = ax mod p = 28 mod 11 = 3 n公钥是: y=3,g=2,p=11；对 M=5 签名：n选择随机数 k=9，确定 gcd(10,9)=1， n计算: K = ak mod p = 29 mod 11 = 6 n解: 5 = 8.6+9.S mod 10; nb 9-1 = 9 mod 10;因此 S = 9.(5-8.6) = 3 mod

36、10 n签名是 (K=6,S=3)。n要验证签名, 确认: 36.63 = 25 mod 11； 3.7 = 32 = 10 mod 1155Winnermakesithappenloserletithappen数字签名3. Schnorr签名体制(1) 体制参数p：大素数，p2512；q：大素数，q|(p-1)，q2160；g：gRZ*p,且gq1(mod p)；x：用户A的秘密钥，1xq；y：用户A的公开钥，ygx(mod p)。3. Schnorr签名体制签名体制56Winnermakesithappenloserletithappen数字签名(2) 签名的产生过程 对于待签名的消息m，

37、A执行以下步骤： 选择随机数k：1kq，计算 rgk(mod p)。 计算e=H(r, m)。 计算sxe+k(mod q)。以(e, s)作为产生的数字签名。3. Schnorr签名体制签名体制57Winnermakesithappenloserletithappen数字签名(3) 签名验证过程 接收方在收到消息m和数字签名(e, s)后，先计算rgsy-e(mod p)，然后计算H(r,m)，并按下式验证其正确性可由下式证明：3. Schnorr签名体制签名体制58Winnermakesithappenloserletithappen数字签名4. Neberg-Rueppel签名体制 该体

38、制是一个消息恢复式签名体制，即验证人可从签名中恢复出原始消息，因此签名人不需要将被签消息发送给验证人。(1) 体制参数p：大素数；q：大素数，q|(p-1)；g：gRZ*p，且gq1(mod p)；x：用户A的秘密钥，xRZ*p；y：用户A的公开钥，ygx(mod p)。4. Neberg-Rueppel签名体制签名体制59Winnermakesithappenloserletithappen数字签名(2) 签名的产生过程对于待签名的消息m，A执行以下步骤： 计算出 ，其中R是一个单一映射，并且容易求逆，称为冗余函数。 选择一个随机数k(0kq)，计算rg-k mod p。 计算 。 计算sx

39、e+k(mod q)。以(e, s)作为对m的数字签名。4. Neberg-Rueppel签名体制签名体制60Winnermakesithappenloserletithappen数字签名(3) 签名的验证过程 接收方收到数字签名(e, s)后，通过以下步骤来验证签名的有效性： 验证是否0ep。 验证是否0sq。 计算vgsy-e(mod p)。4. Neberg-Rueppel签名体制签名体制61Winnermakesithappenloserletithappen数字签名n 计算mve(mod p)。n 验证是否mR(m)，其中R(m)表示R的值域。n 恢复出m=R-1(m)。n这个签名体

40、制的正确性可以由以下等式证明：4. Neberg-Rueppel签名体制签名体制62Winnermakesithappenloserletithappen数字签名5. Okamoto签名体制(1) 体制参数p：大素数，且p2512;q：大素数，q|(p-1)，且q2140；g1, g2：两个与q同长的随机数；x1, x2：用户A的秘密钥，两个小于q的随机数；y：用户A的公开钥，yg-x11g-x22(mod p)。5. Okamoto签名体制签名体制63Winnermakesithappenloserletithappen数字签名(2) 签名的产生过程对于待签名的消息m，A执行以下步骤： 选择

41、两个小于q的随机数k1,k2RZ*q。 计算杂凑值：eH(gk11gk22(mod p),m)。 计算：s1(k1+ex1)(mod q)。 计算：s2(k2+ex2)(mod q)。以(e, s1, s2)作为对m的数字签名。5. Okamoto签名体制签名体制64Winnermakesithappenloserletithappen数字签名(3) 签名的验证过程 接收方在收到消息m和数字签名(e, s1, s2)后，通过以下步骤来验证签名的有效性： 计算vgs11gs22ye(mod p)。 计算e=H(v,m)。 验证：其正确性可通过下式证明：5. Okamoto签名体制签名体制65Wi

42、nnermakesithappenloserletithappen数字签名 设n是一个大合数，找出n的所有素因子是一个困难问题，称之为大数分解问题。下面介绍的两个数字签名体制都基于这个问题的困难性。3.2 基于大数分解问题的数字签名体制基于大数分解问题的数字签名体制66Winnermakesithappenloserletithappen数字签名1. Fiat-Shamir签名体制(1) 体制参数n：n=pq，其中p和q是两个保密的大素数；k：固定的正整数；y1,y2,yk：用户A的公开钥，对任何i(1ik)，yi都是模n的平方剩余；x1,x2,xk：用户A的秘密钥，对任何i(1ik)， 。1

43、. Fiat-Shamir签名体制签名体制67Winnermakesithappenloserletithappen数字签名(2) 签名的产生过程对于待签名的消息m，A执行以下步骤： 随机选取一个正整数t。 随机选取t个介于1和n之间的数r1,r2,rt，并对任何j(1jt)，计算Rjr2j(mod n)。1. Fiat-Shamir签名体制签名体制68Winnermakesithappenloserletithappen数字签名n 计算杂凑值H(m,R1,R2,Rt)，并依次取出H(m,R1,R2,Rt)的前kt个比特值b11,b1t,b21,b2t,bk1,bkt。n 对任何j(1jt)，

44、计算 。 以(b11,b1t,b21,b2t,bk1,bkt),(s1,st)作为对m的数字签名。1. Fiat-Shamir签名体制签名体制69Winnermakesithappenloserletithappen数字签名(3) 签名的验证过程收方在收到消息m和签名(b11,b1t,b21，,b2t,bk1,bkt),(s1,st)后，用以下步骤来验证： 对任何j(1jt)，计算 。 计算H(m,R1,R2,Rt)。1. Fiat-Shamir签名体制签名体制70Winnermakesithappenloserletithappen数字签名n 验证b11,b1t,b21,b2t,bk1,bk

45、t是否依次是H(m,R1,R2,Rt)的前kt个比特。如果是，则以上数字签名是有效的。n正确性可以由以下算式证明：1. Fiat-Shamir签名体制签名体制71Winnermakesithappenloserletithappen数字签名2. Guillou-Quisquater签名体制(1) 体制参数n：n=pq，p和q是两个保密的大素数；v：gcd(v,(p-1)(q-1)=1；x：用户A的秘密钥，xRZ*n；y：用户A的公开钥，yZ*n， 且xvy1(mod n)。2. Guillou-Quisquater签名体制签名体制72Winnermakesithappenloserletith

46、appen数字签名(2) 签名的产生过程对于待签消息m，A进行以下步骤： 随机选择一个数kZ*n，计算 Tkv(mod n)。 计算杂凑值： e=H(m,T)，且使1ev；否则，返回步骤。 计算skxe mod n。以(e, s)作为对m的签名。2. Guillou-Quisquater签名体制签名体制73Winnermakesithappenloserletithappen数字签名(3) 签名的验证过程 接收方在收到消息m和数字签名(e, s)后，用以下步骤来验证： 计算出Tsvye(mod n)。 计算出e=H(m,T)。 验证： 正确性可由以下算式证明：2. Guillou-Quisqu

47、ater签名体制签名体制74Winnermakesithappenloserletithappen数字签名带密钥的带密钥的HASH n以上的签名方法都是公钥技术，计算与数据量较大 ，需要私钥的认证方案。 n好的方法是使用快速的hash 函数：n密钥与消息同时参加运算:KeyedHash=Hash(Key|Message) n有一些弱点 ，随后建议:KeyedHash=Hash(Key1|Hash(Key2|Message) 75Winnermakesithappenloserletithappen数字签名HMAC nHMAC 是使用带密钥的HASH函数的结果，成为internet标准 (RFC

48、2104)。 n结构：HMACK=Hash(K+XORopad)|Hash(K+XORipad)|M)n K+ 是经过填充的密钥 ，opad,ipad 特殊的填充值，nOpad=01011010重复b/8次； nipad=00110110重复b/8次n安全性是基于原来的HASH函数的安全性。任何 MD5, SHA-1, RIPEMD-160 都可以这样使用。76Winnermakesithappenloserletithappen数字签名 1. 在DSS数字签名标准中，取p=83=241+1，q=41，h=2，于是g224 mod 83，若取x=57，则ygx457=77 mod 83。在对消

49、息M=56签名时，选择k=23，计算签名并进行验证。 2. 在DSA签名算法中，参数k泄露会产生什么后果？习题习题77Winnermakesithappenloserletithappen数字签名 3. Illustrate the operation of El Gamal signatures, given the following parameters: primep=31；primroota=3 Determine a suitable private and public key, and then show the signing and verification of a message M=7. 习题习题78Winnermakesithappenloserletithappen数字签名THE END！79Winnermakesithappenloserletithappen数字签名