现代密码学(第五章)课件

数字签名一、杂凑函数一、杂凑函数二、数字签名的基本概念二、数字签名的基本概念三、几种常用的数字签名三、几种常用的数字签名四、特殊用途的数字签名四、特殊用途的数字签名2024/7/71一、杂凑函数一、杂凑函数杂凑函数又称为：杂凑函数又称为：（1）Hash编码；（2）Hash函数；（3）散列编码：（4）散列函数；（5）单向压缩函数。2024/7/72一、杂凑函数一、杂凑函数在公钥密码的内容中，已经介绍了“单向函数”的概念。而杂凑函数是一类特殊的单向函数。设数据文件是任意长度的比特串x。在密码应用中，希望有这样的函数 y=H(x)，满足（1）将x压缩成为固定长度的比特串y。（2）不同的x一定要生成不同的y。（3）由y的值无法倒算x的值。（这就是说，希望y的作用相当于x 的“身份识别符号”，或者“摘要”。比如人的指纹、DNA、虹膜等。）2024/7/73一、杂凑函数一、杂凑函数一个注解一个注解对函数y=H(x)的前两条希望是互不相容的。这就是说，在要求“将任意长度的比特串x压缩成为固定长度的比特串y”时，无法做到“不同的x生成不同的y”。（散列编码是原始数据文件的压缩，而不是带格式的文件的压缩，如ZIP等）例如：y=H(x)，其中设x的长度在128到256之间；设y的固定长度为128。（在这里，比特串x是数据文件，必须假设它“可能是任何一个长度在128到256之间的比特串”。）一共有2128+2129+2130+2256个不同的x。一共有2128个不同的y。x的个数多于y的个数，必然有不同的x压缩成相同的y。2024/7/74一、杂凑函数一、杂凑函数实际性质：杂凑函数实际性质：杂凑函数函数 y=H(x)满足（1）将任意长度的比特串x压缩成为固定长度的比特串y。（2）已知x，计算y=H(x)很容易；已知y，找一个x满足y=H(x)却很困难。这一性质称为单向性。（3）找(x1，x2)，x1x2，H(x1)=H(x2)，很困难。这一性质称为无碰撞性。这样的函数称为杂凑函数杂凑函数。2024/7/75一、杂凑函数一、杂凑函数（单向性的准确解释：或许已经知道了许多对(x*，y*)，满足y*=H(x*)；或许一个新的y确实存在一个x满足y=H(x)；然而实际找到这样的x却很困难，在计算上行不通。无碰撞性的准确解释：或许已经知道了许多对(x*，y*)，满足y*=H(x*)；或许确实存在(x1，x2)满足：x1x2，H(x1)=H(x2)，实际找到这样的(x1，x2)却很困难，在计算上行不通。）2024/7/76一、杂凑函数一、杂凑函数杂凑函数的性质（3）强于性质（2），即由无碰撞性能够得到单向性。例如，设函数 y=H(x)，x的长度固定为N，y的长度为L。设每个y有2N-L个x使y=H(x)。（均衡函数）随机地取m个x值。则P(有个x值满足H(x)=y)=1-(1-2-L)m；P(有两个x值具有相同的H(x)值)=1-(2L)(2L-1)(2L-2)(2L-m+1)2-Lm=1-(1-02-L)(1-12-L)(1-22-L)(1-(m-1)2-L)。2024/7/77一、杂凑函数一、杂凑函数（什么样的函数能作为杂凑函数？这个问题的含义非常广泛。以下仅举出几个简单的例子说明，什么样的函数不能作为杂凑函数。）2024/7/78一、杂凑函数一、杂凑函数例例1：设函数y=H(x)具有可加性：对任意的 x1，x2，H(x1)+H(x2)=H(x1+x2)。这样的函数不能作为杂凑函数。取x1并计算y1=H(x1)；取x2并计算y2=H(x2)。记y=y1+y2。求一个x使得y=H(x)，可以取x=x1+x2。例例2：设函数y=H(x)具有线性：对任意的 x，a，aH(x)=H(ax)。这样的函数不能作为杂凑函数。取x1并计算y1=H(x1)。记y=ay1。求一个x使得y=H(x)，可以取x=ax1。2024/7/79一、杂凑函数一、杂凑函数例例3：设函数y=H(x)具有局部置换性：x的第一个比特总等于y的第三个比特，无论x为何值。这样的函数不能作为杂凑函数。取x1并计算y1=H(x1)。取y为将y1改变第三个比特。求一个x使得y=H(x)，可以取为将x1改变第一个比特。例例4：设函数y=H(x)具有某种连续性：当 y1与y2“距离很近”时，存在 x1与x2“距离很近”，且y1=H(x1)，y2=H(x2)。这样的函数不能作为杂凑函数。取x1并计算y1=H(x1)。取y2与y1“距离很近”。寻找一个x2使y2=H(x2)，只需要在x1的“附近”寻找，搜索量远远低于穷举搜索。2024/7/710一、杂凑函数一、杂凑函数例例4：设函数y=H(x)，y的固定长度太小。这样的函数不能作为杂凑函数，因为可以用穷举的方法进行碰撞攻击。设y的固定长度为8。注意到不同的y的值的个数有28=256个。取257个不同的x，并对每个x计算y=H(x)，得到了257个y。这257个y必然有两个具有相同的值。2024/7/711一、杂凑函数一、杂凑函数由此可见，杂凑函数y=H(x)不能具有任何“整齐”的性质，并且x的任一个比特影响y的每一个比特，就像揉面一样，达到充分的混淆和扩散。此外，y的长度不能太短，一般在128以上，以防止用穷举的方法进行碰撞攻击。我们发现，杂凑函数的设计准则颇像分组密码的设计准则。所不同的是，分组密码不具有压缩功能。2024/7/712一、杂凑函数一、杂凑函数散列编码的用途散列编码的用途用途一：公平提交方案用途一：公平提交方案Alice猜测了一个号码x1，但不知道中奖号码x2；Bob设置了中奖号码x2，但不知道Alice猜测的号码x1。Alice希望首先获得x2，然后重新确定x1使得x1=x2。Bob希望首先获得x1，然后重新确定x2使得x2x1。防止两人作弊的方案称为“公平提交方案”。两人使用一个公开的杂凑函数y=H(x)。方案如下：2024/7/713一、杂凑函数一、杂凑函数（1）Alice计算y1=H(x1)，并将y1发送给Bob。（2）Bob计算y2=H(x2)，并将y2发送给Alice。（3）Alice收到y2后，将x1发送给Bob。（4）Bob收到y1后，将x2发送给Alice。（5）Alice收到x2后，检验是否y2=H(x2)，若是则x2是真实的中奖号码。（6）Bob收到x1后，检验是否y1=H(x1)，若是则x1是Alice的真实的猜测号码。2024/7/714一、杂凑函数一、杂凑函数2024/7/715一、杂凑函数一、杂凑函数方案分析：方案分析：Alice发送y1给Bob，Bob发送y2给Alice，这叫做承诺。Alice发送x1给Bob，Bob发送x2给Alice，这叫做践诺。当承诺值确定以后，无法改变践诺值。当对方发送来了承诺值以后，己方无法计算出对方的践诺值，因而无法“随机应变地”确定自己的践诺值，以重合或避开对方的践诺值。综上所述，杂凑函数阻止了双方作弊。2024/7/716一、杂凑函数一、杂凑函数用途二：简易的身份识别用途二：简易的身份识别设Bob拥有Alice的身份密号x2。现在Alice需要向Bob证明自己的身份，即要向Bob证明自己知道x2。但必须通过不安全的公共信道来进行证明。这就是说，信道上有攻击者Eve在截听。两人使用一个公开的杂凑函数y=H(x)。方案如下：2024/7/717一、杂凑函数一、杂凑函数（1）Alice向Bob发送信息“我是Alice”。（2）Bob收到信息后，向Alice发送一个随机的比特串x1。（3）Alice 收到x1后，与自己的身份密号x2联立，得到x=(x1，x2)。（4）Alice计算y=H(x)，并向Bob发送y。（5）Bob收到y后，取出Alice的身份密号x2，并与x1联立得到x=(x1，x2)，然后验证是否y=H(x)，若是则认为“Alice”是真正的Alice；若否则认为“Alice”是假冒的Alice。2024/7/718一、杂凑函数一、杂凑函数2024/7/719一、杂凑函数一、杂凑函数方案分析：方案分析：设攻击者Eve截听到了Alice和Bob之间的证明全过程。这就是说，Eve知道了随机比特串x1，知道了杂凑函数值 y=H(x1，x2)，但不知道Alice的身份密号x2。根据杂凑函数的性质，Eve不可能由x1和y计算出x2。那么，Eve在不知道x2的前提下，能否在以后向Bob冒充Alice呢？如果Bob发送的x1保持不变，则Eve能够冒充成功。（见方案）。但每次发送的x1是随机的，重复发送的概率是微乎其微的。2024/7/720一、杂凑函数一、杂凑函数用途三：用途三：数字签名的辅助函数数字签名的辅助函数使用了散列编码的数字签名将更加安使用了散列编码的数字签名将更加安全。全。（将在以后介绍）（将在以后介绍）2024/7/721一、杂凑函数一、杂凑函数著名的散列编码函数著名的散列编码函数nSHA-1，美国政府的安全散列编码算法标准。nMD5，由RSA数据安全公司研制的散列编码算法。（2004年5月，中国山东大学的尚小云教授攻破了MD5。尚小云的攻击算法可以在几分钟内找到一批碰撞）2024/7/722二、数字签名的基本概念二、数字签名的基本概念数字签名应该具有的性质数字签名应该具有的性质完整性完整性一个被签了名的消息，无法分割成为若干个被签了名的子消息。这一性质保证了被签名的消息不能被断章取义。（这个性质的本质是：）当一个签名消息被分割子消息发送出去，则签名已经被破坏了，收到消息的人会辨认出签名是无效的（不合法的）。2024/7/723二、数字签名的基本概念二、数字签名的基本概念身份唯一性（不可伪造性）身份唯一性（不可伪造性）被Alice签名的消息只能由Alice生成。（这个性质的本质是：）Bob在收到一个“被Alice签名的消息”时，他有办法检验，该签名是否真的被Alice签名的消息。或许攻击者Eve截获了大量的被Alice签名的消息，但他仍然不能伪造出一个新的，别人认可的“被Alice签名的消息”。如果无论Eve截获多少被Alice签名的消息，他伪造新的“被Alice签名的消息”的成功概率仍然没有丝毫提高，则称该签名算法是零知识的。2024/7/724二、数字签名的基本概念二、数字签名的基本概念不可否认性（公开可验证性）不可否认性（公开可验证性）被Alice签名的消息，在未来不能被Alice否认。（这个性质的本质是：）Bob在收到一个被Alice签名的消息时，他有办法向第三方证明该签名是真的被Alice签名的消息。如果一个数字签名具有不可伪造性不可伪造性，则Bob能够自行验证签名消息的真伪；而如果一个数字签名具有公公开可验证性开可验证性，则Bob能够向他人证明签名消息的真伪。2024/7/725二、数字签名的基本概念二、数字签名的基本概念公钥密码的签名思想公钥密码的签名思想既然要求数字签名具有这么多的性质，怎样来构造数字签名？答案是：以公钥密码为基础的数字签名算法才能具有如此强大的信息安全功能。回忆公钥密码：n明文m，密文c。nAlice的加密密钥（公钥）是z，解密密钥（私钥）是k。n加密方程c=E(m,z)，解密方程m=D(c,k)。2024/7/726二、数字签名的基本概念二、数字签名的基本概念公钥密码的签名方案（一）公钥密码的签名方案（一）Alice欲发消息m给Bob。（1）Alice用自己的私钥k对消息m“解密”s=D(m,k)，s就是对消息m的签名值，(m，s)就是一个签名消息。（2）Alice将(m，s)发送给Bob。（3）Bob收到(m，s)后，用Alice的公钥z，将消息m与签名s做如下的检验：是否m=E(s,z)。若是则(m，s)是Alice发送的签名消息。2024/7/727二、数字签名的基本概念二、数字签名的基本概念在上述方案中，n“密文”变成了消息m，“解密方程”变成了签名方程s=D(m,k)。n“明文”变成了签名值s，“加密方程”变成了验证方程m=E(s,z)。n任何人只要拥有Alice的公钥z，都可以对签名消息(m，s)进行验证。n是否只有Alice自己才能生成自己的签名消息呢？2024/7/728二、数字签名的基本概念二、数字签名的基本概念签名方案（一）的安全性分析：签名方案（一）的安全性分析：（1）设Eve知道Alice的公钥z，选定消息m，对签名值s进行伪造。n要想让伪造的签名值s通过检验，Eve必须选择s满足验证方程m=E(s,z)。然而在验证方程中是解不出s的，必须得到Alice的私钥k，用签名方程得到s：s=D(m,k)。n这就是说，对事先设定的消息m来说，签名消息(m，s)具有身份唯一性和不可伪造性。2024/7/729二、数字签名的基本概念二、数字签名的基本概念（2）设Eve知道Alice的公钥z，设定签名值s，反过来对消息m进行伪造。此时消息m的内容就不能是选定的。nEve选择一个“签名值”s，用验证方程计算“消息”m=E(s,z)。nEve冒充Alice将(m，s)发送给Bob。nBob用验证方程检验得m=E(s,z)。于是Bob认为(m，s)就是Alice发送的签名消息。攻击成功。为了抵抗这种攻击，合法签名消息(m，s)中的消息m必须是有意义的课文，而不是乱码。2024/7/730二、数字签名的基本概念二、数字签名的基本概念公钥密码的签名方案（二）公钥密码的签名方案（二）额外使用一个公开的杂凑函数H。设Alice欲发消息m给Bob。（1）Alice用H将消息m进行处理，得h=H(m)。（2）Alice用自己的私钥k对h“解密”s=D(h,k)，s就是对消息m的签名值，(m，s)就是一个签名消息。（3）Alice将(m，s)发送给Bob。（4）Bob收到(m，s)后，用Alice的公钥z，将消息m与签名s做如下的检验：是否H(m)=E(s,z)。若是则(m，s)是Alice发送的签名消息。2024/7/731二、数字签名的基本概念二、数字签名的基本概念在上述方案中，n签名方程是s=D(H(m),k)。n验证方程是H(m)=E(s,z)。n任何人只要拥有Alice的公钥z，都可以对签名消息(m，s)进行验证。n设攻击者Eve知道Alice的公钥z，他试图伪造一个(m，s)，让Bob相信(m，s)是Alice的签名消息。伪造的(m，s)必须满足验证方程H(m)=E(s,z)。2024/7/732二、数字签名的基本概念二、数字签名的基本概念Eve面临着两难问题：n如果选定消息m，再匹配签名值s，则在验证方程H(m)=E(s,z)中无法解出s。（这是公钥密码的基本安全性）n如果选定签名值s，再匹配消息m，则在验证方程H(m)=E(s,z)中能够解出H(m)，却无法得到m。（这是杂凑函数的性质）如此看来，签名方案（二）似乎具有身份唯一性和不可伪造性。2024/7/733二、数字签名的基本概念二、数字签名的基本概念签名方案（二）存在的问题签名方案（二）存在的问题（1）如果给Eve更加宽松的条件，设他不但知道Alice的公钥z，而且已经截获了许多Alice的签名消息(m(1)，s(1)，(m(2)，s(2)，(m(N)，s(N)。Eve伪造新的Alice的签名消息(m，s)是否更加容易？如果允许重复发送，则Eve的伪造是轻而易举的，他只需要发送(m(n)，s(n)即可。此称为重放攻击。2024/7/734二、数字签名的基本概念二、数字签名的基本概念为了使签名方案（二）抵抗重放攻击，通常使用两种方法：nAlice已经发送过的签名消息必须存储备案，不得再次发送。一旦发现有再次发送，则肯定是重放攻击。但Eve可以根据公钥密码的结构缺陷来伪造。比如(m，s)=(m(1)m(2)，s(1)s(2)。第一种方法没有抵抗这种伪造的能力。n Alice的签名消息中必须含有时戳。一旦发现发送时间过于久远，则肯定是重放攻击。但“时间过于久远”的标准很模糊。2024/7/735二、数字签名的基本概念二、数字签名的基本概念（2）注意到Alice先得到h=H(m)，再计算出s=D(h,k)。这就要求：公钥密码对课文h能够正确进行解密运算。换句话说，对课文h进行解密运算的结果，再进行加密就得到h。事实上，许多公钥密码具有如下的性质：当某个明文加密得到h，则对h解密再加密就得到h；当h是随意选择的，则对h解密再加密很难得到h。比如，NTRU就是这样的公钥密码。因此NTRU无法用签名方案（二）来构造数字签名。2024/7/736三、几种常用的数字签名三、几种常用的数字签名RSA数字签名数字签名RSA的密钥生成：选择两个大的素数p和q。选择两个正整数e和d，满足：ed是(p-1)(q-1)的倍数加1。计算n=pq。Alice的公钥是（n，e），私钥是d。签名方案是上述的签名方案(二)，额外使用一个公开的杂凑函数H。设Alice欲发消息m给Bob。2024/7/737三、几种常用的数字签名三、几种常用的数字签名（1）Alice用H将消息m进行处理，得散列值h=H(m)。（2）Alice用自己的私钥d对h“解密”得s=hd(modn)。（3）Alice将(m，s)发送给Bob。（4）Bob用Alice的公钥e，检验是否H(m)=se(modn)。若是则(m，s)是Alice发送的签名消息。2024/7/738三、几种常用的数字签名三、几种常用的数字签名ElGamal数字签名数字签名ElGamal的密钥生成：选择一个大的素数p。选择g为域GF(p)的本原元素。选择正整数x。计算y=gx(modp)。Alice的公钥是（p，g，y），私钥是x。签名方案是上述的签名方案(二)，额外使用一个公开的杂凑函数H。设Alice欲发消息m给Bob。2024/7/739三、几种常用的数字签名三、几种常用的数字签名（1）Alice用H将消息m进行处理，得h=H(m)。（2）Alice选择秘密随机数k，满足0kp-1，且(k,p-1)=1，计算r=gk(modp)；s=(h-xr)k-1(mod(p1)。（3）Alice将(m，r，s)发送给Bob。（4）Bob用Alice的公钥，检验是否yrrs=gH(m)(mod p)。若是则(m，r，s)是Alice发送的签名消息。2024/7/740三、几种常用的数字签名三、几种常用的数字签名Schnorr数字签名数字签名Alice拥有3个正整数(p，q，g)，向自己的通信伙伴公开。其中：np是模数（即将要进行(modp)模数运算），它是一个素数，值的范围在2511到2512之间（即p是一个长度为512的比特串）。nq也是模数（即将要进行(modq)模数运算），它是一个素数，2159 q（即q是一个长度不小于160的比特串），并且q是p-1的一个因子。ng是域GF(p)的元素，且gq=1(modp)。2024/7/741三、几种常用的数字签名三、几种常用的数字签名Alice选择x，其中1xq。Alice计算y=gx(modp)。Alice的公钥是(p，q，g，y)，Alice的私钥是x。签名方案是上述的签名方案(二)，额外使用一个公开的杂凑函数H，H的输出长度是160比特。设Alice欲发消息m给Bob。2024/7/742三、几种常用的数字签名三、几种常用的数字签名（1）Alice选择秘密随机数k，满足0kq，计算r=gk(modp)；e=H(r,m)；s=kxe(modq)。（3）Alice将(m，e，s)发送给Bob。（4）Bob用Alice的公钥，计算r=gsy-e(mod p)。检验是否e=H(r,m)。若是则(m，e，s)是Alice发送的签名消息。2024/7/743三、几种常用的数字签名三、几种常用的数字签名Schnorr签名与签名与ElGamal签名的不同点：签名的不同点：在ElGamal体制中，g为域GF(p)的本原元素；而在Schnorr体制中，g只是域GF(p)的阶为q的元素，而非本原元素。因此，虽然两者都是基于离散对数的困难性，然而ElGamal的离散对数阶为p-1，Schnorr的离散对数阶为qp-1。从这个角度上说，ElGamal的安全性似乎高于Schnorr。2024/7/744三、几种常用的数字签名三、几种常用的数字签名签名长度比较：Schnorr比ElGamal签名长度短。ElGamal：(m，r，s)，其中r的长度为|p|，s的长度为|p-1|。Schnorr：(m，e，s)，其中e的长度为|q|，s的长度为|q|。在Schnorr签名中，r=gk(modp)可以预先计算，k与m无关，因而签名只需一次modq乘法及减法。所需计算量少，速度快，适用于灵巧卡采用。2024/7/745三、几种常用的数字签名三、几种常用的数字签名数字签名算法数字签名算法DSA（Digital Signature Algorithm）1991年8月，美国国家标准研究所(NIST)发布了其所提议的数字签名标准(DSS)，向社会征求意见，该标准定义了数字签名算法DSA。经过公众的评议并做了少许改进后，1994年，DSS首次作为联邦信息处理标准(FIPS)对外公布。2024/7/746三、几种常用的数字签名三、几种常用的数字签名DSA的参数的参数Alice拥有3个正整数(p，q，g)，向自己的通信伙伴公开。其中：np是模数（即将要进行(modp)模数运算），它是一个素数，值的范围在2511到2512之间（即p是一个长度为512的比特串）。nq也是模数（即将要进行(modq)模数运算），它是一个素数，2159 q 2160（即q是一个长度为160的比特串），并且q是p-1的一个因子。2024/7/747三、几种常用的数字签名三、几种常用的数字签名ng是这样确定的：g=j(p-1)/q(modp)；其中1j1。实际上，就是要求g1，gq(modp)=1。Alice选择x，其中1xq。Alice计算y=gx(modp)。Alice的公钥是(p，q，g，y)，Alice的私钥是x。2024/7/748三、几种常用的数字签名三、几种常用的数字签名DSA的签名过程的签名过程签名方案是上节的签名方案(二)。设Alice欲发消息m给Bob。（1）Alice用H将消息m进行处理，得h=H(m)。（2）Alice随机地选择一个整数k(0kq)，计算r=(gk(modp)(modq)；s=(k-1(h+xr)(modq)。其中k-1是k的关于(modq)的逆元，即k-1k(modq)=1，0 k-1 q。(r,s)就是对消息m的签名，(m,r,s)就是发送给Bob的签名消息。2024/7/749三、几种常用的数字签名三、几种常用的数字签名DSADSA的验证过程的验证过程Bob收到(m,r,s)后，用Alice的公钥(p，q，g，y)，将消息m与签名(r,s)做如下的检验：（1）是否0rq，0sq。若是则继续检验，否则拒收签名。（2）计算h=H(m)，w=s-1(modq)，u1=hw(modq)，u2=rw(modq)，v=(gu1yu2(modp)(modq)。2024/7/750三、几种常用的数字签名三、几种常用的数字签名如果v=r，则验证了签名是有效的，否则拒收签名。（一个有效的签名一定会通过检验，而一个伪造的签名几乎不可能通过检验。）2024/7/751三、几种常用的数字签名三、几种常用的数字签名若干说明若干说明说明一：关于(modq)的逆元。因为q是素数，所以当0kq时，有唯一的l满足：0lq，kl(modq)=1。此时称l为k的关于(modq)的逆元，记l为 k-1。当q很小时，求k的关于(modq)的逆元只需要穷举。而当q是一个大素数时，求k的关于(modq)的逆元也不是一个困难问题。使用欧几里德算法（辗转相除法），简单快速。2024/7/752三、几种常用的数字签名三、几种常用的数字签名说明二：关于随机选择的整数k。Alice在每次生成签名时，都要临时随机地选择一个整数k(0kq)。k并不发送给Bob，只是在签名算法中参加运算，因此可以看作是Alice的另一个私钥，称为临时密钥。临时密钥k为什么要保密？如果临时密钥k被公开，则当攻击者Eve截获了签名消息(m,r,s)后，他计算h=H(m)；再从等式s=(k-1(h+xr)(modq)中计算出Alice的私钥x：x=(sk-h)r-1(modq)。DSA被攻破。2024/7/753三、几种常用的数字签名三、几种常用的数字签名临时密钥k为什么要临时随机地选择？设临时密钥k是保密的，但是是固定的。设攻击者Eve截获了两个签名消息(m,r,s)和(m,r,s)。Eve能够计算出h=H(m)，h=H(m)。Eve还知道：s=(k-1(h+xr)(modq)，s=(k-1(h+xr)(modq)。这是关于未知量（k-1，k-1x）的二元一次方程组（只不过是模方程组），可以很简单地解出（k-1，k-1x），因此解出（k，x）。DSA被攻破。2024/7/754三、几种常用的数字签名三、几种常用的数字签名综上所述，临时密钥k应该是保密的，且必须临时随机选择。于是会出现以下的现象：nAlice在时刻1发送签名消息(m,r1,s1)。nAlice在时刻2发送签名消息(m,r2,s2)。在不同时刻发送相同的消息m，得到不同的签名(r1,s1)和(r2,s2)，都是有效签名。2024/7/755三、几种常用的数字签名三、几种常用的数字签名说明三：检验过程的合理性（即有效的签名一定满足等式v=r）。w=s-1(modq)=(k-1(h+xr)-1(modq)=k(h+xr)-1(modq)。u1=hw(modq)=hk(h+xr)-1(modq)。u2=rw(modq)=rk(h+xr)-1(modq)。所以u1+xu2(modq)=hk(h+xr)-1+xrk(h+xr)-1(modq)=(h+xr)k(h+xr)-1(modq)=k。2024/7/756三、几种常用的数字签名三、几种常用的数字签名所以：v=(gu1yu2(modp)(modq)=(gu1gxu2(modp)(modq)=(gu1+xu2(modp)(modq)=(gu1+xu2(modq)(modp)(modq)=(gk(modp)(modq)=r。2024/7/757三、几种常用的数字签名三、几种常用的数字签名说明四：伪造签名的困难性。（如果攻击者Eve获得了Alice的私钥x，则DSA被攻破，Eve可以任意地冒充Alice签名）设Eve并不知道x，而试图伪造Alice的签名消息(m,r,s)通过检验方程v=r，即(gu1yu2(modp)(modq)=r，2024/7/758三、几种常用的数字签名三、几种常用的数字签名又即这是一个复杂的求解离散对数的问题。2024/7/759三、几种常用的数字签名三、几种常用的数字签名公众对公众对DSA的反应：的反应：RSA Data Security Inc(DSI)想以RSA算法做为标准，因而对此反应强烈。在标准公布之前就指出采用公用模可能使政府能够进行伪造签名。许多大的软件公司早已得到RSA的许可证而反对DSS。主要批评意见有：DSA不能用于加密或密钥分配；DSA算法中可能设有陷门；DSA比RSA慢；RSA已是一个实际上的标准，而DSS与现行国际标准不相容；DSA未经公开选择过程，还没有足够的时间进行分析证明；DSA可能侵犯了其它专利（Schnorr签名算法，Diffie-Hellman的公钥密钥分配算法）；由512 bit所限定密钥量太小。现已改为5121 024中可被64除尽的即可供使用。2024/7/760三、几种常用的数字签名三、几种常用的数字签名DSA的实现速度的实现速度 预计算预计算：随机数r与消息无关，选k预先计算出其r。对k-1也可这样做。预计算大大加快了DSA的速度。2024/7/761三、几种常用的数字签名三、几种常用的数字签名其它其它签名算法签名算法GOST签名标准签名标准，为俄国采用的数字签名标准，自1995启用，正式称为GOST R34.10-94。算法与Schnorr模式下的ElGamal签名及NIST的DSA很相似。算法中也有一个类似于SHA的杂凑函数H(x)，其标准号为GOST R34.11-94。ESIGN签名体制。签名体制。日本NTT的T.Okamoto等设计的签名方案。宣称在密钥签名长度相同条件下，至少和RSA，DSA一样安全，且比它们都快。OSS签名体制，签名体制，Ong，Schnorr和Shamir1984提出的一种利用mod n下多项式的签名算法。方案基于二次多项式。2024/7/762四、特殊用途的数字签名四、特殊用途的数字签名盲签名盲签名一般数字签名中，总是要先知道文件内容而后才签署。但有时需要某人对一个文件签名，但又不让他知道文件内容，称此为盲签名盲签名(Blind Signature)，它是由Chaum1983最先提出的。在选举投票和数字货币协议中将会碰到这类要求。设B是一位仲裁人，A要B签署一个文件，但不想让他知道所签的是什么，而B也并不关心所签的内容，他只是要确保在需要时可以对此进行仲裁。可通过下述协议实现。2024/7/763四、特殊用途的数字签名四、特殊用途的数字签名(a)A取一文件并以一随机值乘之。称此随机值为盲盲因子因子，称用盲因子盲因子乘后的文件为盲文件。(b)A将此盲文件送给B。(c)B对盲文件签名。(d)A以盲因子除之，得到B对原文件的签名。（若签名函数和乘法函数是可换的，则上述作法成立。否则要采用其它方法(而不是乘法)修改原文件。）2024/7/764四、特殊用途的数字签名四、特殊用途的数字签名安全性讨论安全性讨论 B可以欺诈吗？是否可以获取有关文件的信息？若盲因子完全随机，则可保证B不能由(b)中所看到的盲文件得出原文件的信息。即使B将(c)中所签盲文件复制，他也不能(对任何人)证明在此协议中所签的真正文件，而只是知道其签名是合法的，并可向他人证实其签名合法。即使他签了100万个文件，也无从得到所签文件的信息。2024/7/765四、特殊用途的数字签名四、特殊用途的数字签名盲签名算法盲签名算法 D.Chaum曾提出第一个实现盲签名的算法，他采用了RSA算法。令B的公钥为e，秘密钥为d，模为n。(a)A需要B对消息m进行盲签名，选1k n，作t=mke(modn)B。(b)B对t签名,td=(mke)d(modn)A。(c)A计算 s=td/k(modn)得s=(mke)d/k(modn)=md(modn)，(m,s)就是B对m按RSA体制的合法签名，任何知道公钥e的人都能验证se=m(modn)。2024/7/766写在最后写在最后成功的基成功的基础在于好的学在于好的学习习惯The foundation of success lies in good habits67 结束语当你尽了自己的最大努力时，失败也是伟大的，所以不要放弃，坚持就是正确的。When You Do Your Best,Failure Is Great,So DonT Give Up,Stick To The End演讲人：XXXXXX 时 间：XX年XX月XX日