密码学PPT电子课件教案-第六章数字签名.ppt

2019/4/4,1,第六章 数字签名,一、数字签名的概念 二、rsa数字签名体制 三、elgamal数字签名体制 四、其他数字签名 五、数字签名标准,一、数字签名基本概念,2019/4/4,3,数字签名就是两个数学变换，首先发送方对信息施以数学变换，接受方进行逆变换，得到原始信息。发送方的变换就是签名，通常是一种加密，对应的逆变换就是对签名的认证，通常是一种解密措施。数字签名体制一般包括两个部分：一是签名部分，对消息m签名，可以记为s=sig（k，m），k是签名者的私钥，是秘密的。二是接收方的认证部分，可以记成ver（m，s，k）=（真，假）。,2019/4/4,4,数字签名示意图,公钥算法 加 密,公钥算法解 密,数字签 名,消 息 原 文,消 息 原 文,消 息 原 文,比较,2019/4/4,5,数字签名的特点,（1） 签名是可信的:任何人都可以方便的验证签名的有效性. （2） 签名是不可伪造的:除了合法的签名者外,任何其它人伪造签名是困难的，这种困难性指计算上是不可行的。 （3） 签名是不可复制的：如果签名是从别的地方复制的，任何人都可发现消息与签名的不一致，从而拒绝签名。,2019/4/4,6,数字签名的特点,（4） 签名的消息是不可改变的：经过的签名不能被篡改。 （5） 签名是不可抵赖的：签名者不能否认自己的签名。,2019/4/4,7,数字签名与加密的区别,(1)在加密中：公钥加密，私钥解密。 (2)数字签名中：签名者用私钥签名，接收者用 签名者的公钥验证。,2019/4/4,8,数字签名的应用,在网络应用中，凡是要解决伪造、抵赖、冒充、篡改与身份鉴别的问题，都可以运用数字签名来处理： 1.网上银行通过因特网向客户提供信息查询、网上支付、信贷等，都需要数字签名。 2.在电子商务中，企业与企业之间，企业与消费者之间，在网上进行的商业交换活动，也需要数字签名。 3.在电子政务中,必须提供身份认证服务、权限控制服务、信息保密服务等，而这些都离不开数字签名。,2019/4/4,9,二、rsa数字签名体制,2019/4/4,10,rsa是以它的三个发明者ron rivest，adi shamir和leoard adleman的名字命名。该算法既可以用于加密，也可以用于数字签名。rsa的安全性基于大数分解的困难性，该算法已经经受住了多年深入的密码分析，密码分析者既不能证明也不能否认rsa的安全性，这恰恰说明该算法有一定的可信度。,2019/4/4,11,算法描述,参数选择 (1)令 是两个素数, (2)随机选择e,满足 ，那么私钥就是（e,n) (3)计算 ,私钥就是（d,n).,2019/4/4,12,签名过程 （）计算消息的散列值（） （）加密散列值： （）签名为,2019/4/4,13,签名验证 (1)解密签名: (2)比较h=h(m),如果等号相等，签名有效；否则签名无效。,2019/4/4,14,rsa签名过程图,m | m h 比较 h e d,图中h：表示hah运算；m：消息；e：加密；d解密;kus ：用户秘密钥; kup ：用户公开密钥。,2019/4/4,15,举例,(1)选择素数p=5,q=11；n=pq=55, (2)选择私钥e=3,由 计算私钥d=27 假设消息m=19 (3)签名生成： (4)签名验证：,2019/4/4,16,安全性分析,rsa算法的安全性就是基于大整数的因子分解困难之上的，到目前为止其还是安全的。要分析rsa算法的安全性，我们从攻击rsa的角度来审视。总的来分，rsa算法攻击可以区分为三类： (1)蛮力攻击：它通过实验所有的可能私钥，来达到目的。 (2)数字攻击：使用数学技巧，类似于分解n来达到攻击目的。,2019/4/4,17,(3)时间攻击：通过观察解密算法运行的时间来达到目的。 其中抵抗蛮力攻击的方法，与其他加密系统是一致的使用大的密钥空间，使穷举法无能为力。因此e和d位数的长度应该与实际应用系统有综合的权衡。,2019/4/4,18,因子分解问题,从因子分解问题着手的使用数学手段攻击rsa的方法可以区分为如下三类： （1）将n分解为两个素因子。这就是要计算 ，然后可以确定d。 （2）在不确定p和q的情况下，而直接确定 。当 然同样可以计算 。 （3）在不确定 的情况下，直接确定d。,2019/4/4,19,目前大部分rsa密码分析的讨论都集中于对n进行素因子分解。给定n去确定 ，就等价于对n进行因子分解。给定e和n，使用目前已知的攻击算法求出d的时间开销至少和因子分解问题的时间开销一样大。所以我们通常把因子分解的性能作为评价rsa安全性基准。,2019/4/4,20,定时攻击,定时攻击被安全专家称为“有创意的攻击”。因为该攻击与常规攻击方式完全不同，同时其仅仅使用密文进行攻击。其提出者是密码分析家p.c.kocher,于1996年提出。kocher 曾发明了一种办法，通过监视耗电量的微小波动，可以推导出一张加密的智能卡中内嵌的密钥。之后，他又因设计了一种能够攻破rsa算法实现的技术而轰动一时，该方法其不是通过正面攻击算法，而是通过观察系统处理特定函数所花费的时间来寻找破解的蛛丝马迹。,2019/4/4,21,其他攻击,攻击rsa还有其他方法，如：迭代攻击、选择明文攻击、公共模数攻击、低加密指数攻击等。,2019/4/4,22,使用rsa的建议,（1）不可使用公共模数。 （2）明文的熵要尽可能的大。 （3）尽量使用散列函数。,2019/4/4,23,三、lamal数字签名体制,2019/4/4,24,lamal数字签名体制,elamal算法既可用于数字签名，也可用于加密，其安全性依赖于计算有限域上离散对数的困难性上 elamal数字签名体制是由amal于年提出的，其变体已经使用于中,elamal数字签名体制是abin签名体制的变形，也是使用了随机数，称为随机化的数签名已经将elamal数字签名体制采纳为签名的标准算法,2019/4/4,25,构造参数,全局参数 p：是一个大的素数，确保在 中求解离散对数在计算上的困难； g:是 zp中的乘法群 的一个生成元，或称为本原元素 私钥参数 x：用户的私钥，,2019/4/4,26,公钥参数 y:用户的公钥， 算法中常还使用一个随机数k另外，在本签名体制中，要签字的消息空间为 ，签名结果的值空间为 。,2019/4/4,27,签名生成,给定要签名的消息为，签名过程如下所述 (1)生成一个随机数 (2)计算 (3)计算 到此，签名结果为（r,s） (4)把消息和签名结果（,r,s)发送给接收者,2019/4/4,28,签名验证,接收方收到消息和签名结果（m,r,s)后，可以按下面的步骤验证签名的有效性。 (1)如果rp-1，那么继续后续步骤；否则，签名是不合法。 (2)计算 (3)计算 (4)比较 和 如果 ，表示签名有效；否则，签名无效,2019/4/4,29,签名验证证明,我们先对签名过程中等式 进行处理有,2019/4/4,30,下面考察认证过程中的等式： 因为 所以可以说明该算法是成立的,2019/4/4,31,举例,1.参数生成 取p=2357,g=2;2是 的一个生成元选择一个数x=1751作为私钥再计算公钥 y: 现在假定消息为mh（m）=1463,2019/4/4,32,签名生成,2.签名过程： 选随机数k=1529;计算： 签名结果为（r,s）=(1490,1777),2019/4/4,33,签名验证,3.签名验证 接收方在受到消息和签名结果之后，计算： （1） （2） 因为 ，所以签名有效,2019/4/4,34,elamal签名体制的变型,elamal数字签名体制有很多变形，我们把签名过程中的等式 修改为： （称为签名方程） 其中，如果 ，那么签名方程就是elamal签名过程中使用的等式。 如果我们把u、v、w分别对应不同次序的h（m）、r、s就可以得到其他的elamal数字签名变体体制,2019/4/4,35,elamal签名体制的6种变形,2019/4/4,36,安全性,下面讨论一下elamal数字签名体制的安全 不知道明文密文对的攻击， 由于攻击者不知道用户私钥，所以要伪造用户签名，需要先选取定一个r(或s)，然后实验求取另外一个值s(或r)都属于求解离散对数问题. 已经知道明文密文对的攻击 攻击者知道（r,s)是消息的合法签字那么攻击者可以先择整数h,i,j，计算：,2019/4/4,37,那么， 的合法签字就是 如果攻击者要预先确定消息 ，并得到该消息的合法签名，他还是面临解决离散对数问题。所以攻击者还是不能得逞。,2019/4/4,38,（3）如果攻击者知道了两个消息 ，及其相应的签字 ， 并且这两次签名都是使用的同一个随机数，那么有： 那么攻击者可以求解出用户的私钥x。 所以在签名过程中，要求使用随机数，同时使用的随机数不能泄露。,2019/4/4,39,四、其他数字签名体制,2019/4/4,40,fiat-shamir 签名方案,fiat-shamir签名方案是由fei-fiat-shamir身份鉴别方案变来的，较之rsa主要好处在于速度， fiat-shamir签名方案只需要rsa的1/100-4/100的模乘法。,2019/4/4,41,选择n为两个大素数之积。产生公开密钥 ， ，和私人密钥 ， ，满足 （1）alice取t个1到n之间的随机整数： ， ，并计算 ， ，满足 （2）alice对消息和这些x串的连接做散列运算，得到一个位序列： ，她将串开始的 位作为 之值，其中1it,1jk。,2019/4/4,42,（3）alice计算 ， （对于每一个i，她对基于随机 值的 值做乘法运算。如果 等于1，则乘 如果 等于0，则不乘 （4） alice将 ， 和 发送给bob,他已经获取了alice的公开密钥： ， （5）bob计算 ， ,2019/4/4,43,（6）bob验证 ， 开始的 个位是alice发送给他的 值。 正如身份鉴别方案一样，这种签名方案的安全性正比于1/ 。它也依赖于分解n的难度。fiat和shamir指出当分解n的复杂性低于 时,伪造一个签名很容易。并且，由于生日类型的攻击，他们推荐 应从20至少增至72，他们建议取k=9,t=8,2019/4/4,44,schnorr数字签名体制,schnorr数字签名体制是一个比较著名的eigamal签名体制的变种形式。由c. schnorr于1989年提出的，其密钥的产生与dsa算法的密钥产生是一样的，但是对p、q没有大小的约束。 下面是算法描述,2019/4/4,45,构造参数,1.全局参数 p、q是大的素数。其中p|(q-1);q是位数大于等于160bit的整数；p是位数大于等于152bit的整数，以确保在 中求解离散对数的困难性。 且 。 以上全局参数，作为所有用户共同使用的参数。 2.私钥参x ：用户的私钥，1xq。 3.公钥参数y:用户的公钥，,2019/4/4,46,签名生成,需要签名的消息为m，那么签名的过程如下： 1.生成一个随机数k, ； 2.计算 3.计算 4.计算 签名结果就是（s,e)。,2019/4/4,47,认证过程,接收方收到（m,s,e)后，通过如下步骤进行认证： （1）取得发送方的公钥y； （2）计算 （3）计算 （4）如果 则表示签名有效；否则签名无效。,2019/4/4,48,签名认证证明,如果收到（m,s,e)中，（s,e）是合法的签名，则有：,2019/4/4,49,schnorr与elgamal比较,（1）在elgamal签名中，g是 的本原原素； schnorr中，g是 的子集 的本原原素。所 elgamal签名体制安全性高于schnorr。 （2）schnorr的签名结果较短，其长度由 和 确定 （3）在schnorr签名体制中，可以预先计算，因为随机数与要签名的消息m无关。,2019/4/4,50,举例,(1) 取p=129841,q=541,其中（p-1）/q=240.可以计算找出一个g=26,有 。 (2)随机选择x=423q,把x作为用户私钥。计算用户公钥y: (3)选择随机数k=327,计算r： 然后计算e:e=h(r|m)=155.,2019/4/4,51,举例,（4）计算s: s 签名结果为（s,e）=（431，155）。 （5）如果（m,s,e）是合法签名则有： 从而验证了签名是有效的。,2019/4/4,52,不可否认数字签名,一般的数字签名能够被准确复制，其他人都可以用复制品来验证签名的有效性；这个性质有时是有用的，如公开宣传品的发布等。但是，有时也带来一些问题，如签名的私人信件、商业函件等，是不希望其他人验证的。由此1989年，chaum和antwerpen等引入了不可否认数字签名的概念。 不可否认数字签名，最本质的是在无签字者的配合下，不可能验证签字的有效性。利用这个特殊的性质，可以在一定程度上防止复制或散布他所签字的文件的可能性，从而使产权所有者可以控制产品的散发。这在电子出版领域的知识保护中有用途。,2019/4/4,53,如果签字者拒绝合作就无法验证签名的有效性。但确实是签字者的数字签名，其又拒绝合作时，又如何处理？那么可以在法庭等第三方的监督下，启用否认协议（disavowal protocol），以证明签名的真假。如果对方拒绝参与否认协议，那么，就是他签名的；如果不是他签名的，否认协议可以确认他没有签名。 下面是算法描述：,2019/4/4,54,构造参数,(1)全局参数p,g p,q为素数，且p=2q+1。那么在 可以构造一个q阶乘法子群g。g是 本原元素 （2）用户私钥x x:满足 （3）用户公钥y y:,2019/4/4,55,签名生成,对消息m的签名如下： s就是签名结果。在没有签名者的配合下，签名s不能被证实。,2019/4/4,56,验证过程,在签名者的配合之下，验证如下： （1）验收者收到消息和签名（m,s）。 （2）接收者选择两个随机数a、 b (3)接收者然后计算： 将c发给签名者。,2019/4/4,57,签名验证,（4）签名者计算： 将d发送给接收签名的用户。 （5）接收者验证下面等式： 如果等式成立，那么，签名成立，否则是签名无效。,2019/4/4,58,否认协议,上面的验证过程必须要得到签名者的配合才能完成。如果签名者拒绝配合过程，那么就需要启动否认协议来确定签名的有效性。 （1）接收者选择随机数a、b， （2）接收者计算： 将c发给签名 者。,2019/4/4,59,否认协议,（3）签名者计算： , 将d发给接收者； （4）接收者验证： 如果等式成立，说明签名有效，终止协议。 （5）接收者再选择随机数i、j, ; (6)接收者计算： ，将c发送给签名者；,2019/4/4,60,否认协议,（7）签名者计算： ， 将d发送给接收者； （8）接收者验证： 如果等式成立，说明签名有效，终止协议。,2019/4/4,61,（9）接收者判定，如果下列等式： 成立，那么接收者可以判定签名s是假的；否则签名有效。 上面的协议经过了两个回合，（1）-（4）和（5）-（8）都是认证过程的重复；最后通过（9）的一致性检验可以使接受方能够确定出签名者是否如实的执行了上述规定的协议。,2019/4/4,62,可变换的不可否认签名,1990年，boyar提出了一种可变换的不可否认数字签名（convertible undeniable signature)算法.该不可否认数字签名能够转换为常规的数字签名，也就是此时允许所有人验证签名的有效性。该算法是基于elgamal签名算法的。,2019/4/4,63,算法描述,构造参数 与elgamal签名算法非常相似。首先是全局参数： p、q：都是素数，并且 g: h:是一个随机数 ，并且：,2019/4/4,64,私钥参数： x, z, 公钥参数： y, u, 2.签名过程 对消息签名过程如下： （）选择随机数t, . （）计算：,2019/4/4,65,（）选择随机数， ，且 （）计算 （）利用欧几里德除法求s，满足 消息的签名结果为（r,s,t)。,2019/4/4,66,3.签名验证过程 （）接收者产生两个随机数 ， 并计算 ，将c送给签名者。 （）签名者产生随机数k，并计算 将 、 发送给接收者。 （）接收者将 发送给签字者。,签名验证过程,2019/4/4,67,（）签字者验证如下等式： 成立之后，将随机数k发送给接收者。 （）接收者验证： 如果验证成立，表示签名有效。 上述的数字签名算法，当签名者把参数z公开，该签名方案就化为普通的数字签名方案。,2019/4/4,68,盲签名体制,2019/4/4,69,盲签名,前面介绍的数字签名，签名者可以查看所签息的内容，这和日常生活的情形相符合：我们通常需要在知道文件内容之后才会签署。而在有些时候，要求签名者对所签署消息是不可见的，就需要盲签名。 盲签名（blind signature)是由david chanm于1983年提出的。盲签名在数字现金，电子投票等领域都有较大的应用价值，特别是目前的数字现金，大部分都是采用盲签名的原理实现。,2019/4/4,70,盲签名的基本思想是：签名者把明文消息m通过盲变换为 ， 隐藏了明文m的内容；然后把 给签字者（仲裁者）进行签名，得到签名结果 ；最后，签名者取回 ，采用解盲变处理得到s（m），就是m的签名，,盲签名的基本思想,2019/4/4,71,盲签名简图,明文m s（m）,2019/4/4,72,完全盲签名协议,假定请求签名者为a，签字者（仲裁者）为b。盲签名就是要求a让b签署一个文件，而不让b知悉文件的内容，仅仅要求以后在需要时b可以对他所签署的文件进行仲裁。那么可以通过下面称为完全盲签名的协议来完成； （1）a把文件用一个随机数乘之，该随机数常称为盲因子（blinding factor）。 （2）a将上面处理后的文件盲文件传送给b。,2019/4/4,73,（3）b对盲文件签名。 （4）a取回b的签名结果，并用盲因子除之，得到b对原文件的签名。 显然，在上面的协议中，如果签名函数与乘法可交换，那么上述协议成立。否则盲变换不能用乘法，而采用其他变换方法。,2019/4/4,74,那么上面协议中，b可以获得文件内容吗？如果盲因子是完全随机数，显然b不能获得所签署文件内容，即使他签署了a的上万份文件。但是这些文件确实是他签署的，并且可以在以后得到证实。 上面的协议使签名者一无所知，虽然具有盲签名的特点，但是与实际应用还是有差距。有时签名者希望知道他正在签署的文件是哪方面的内容，而请求签名者又要求签名者不能知道所签文件的确切内容。满足该要求就使用下面协议。,2019/4/4,75,盲签名协议,使用分割-选择（cut-and-choose）技术，可以使签名者b知道他所签署的是哪方面的信息，但是还保留盲签名的特征他不知道所签署文件的具体内容。下面也使用讲述盲签名通常使用的例子来加以解说，这些例子在王育民和b.schneier等人的著作中都可以见到。,2019/4/4,76,【例】海关的抽检,【例】海关的抽检。 在繁忙的海关，需要检查进出的人员中有没有贩毒者。显然检查进出的每一个人是不可能的，他们采用概率的方法来进行抽查。例如： 对其中1/10的人进行检查，那么贩毒者有1/10的机会被抓获。 当然为了提高对贩毒者的抓获率，就得提高抽检比例。合理的调整抽检的比例，再辅以其他手段如高额罚款、科以重刑等，就能够有效的遏制通过海关的贩毒行为。,2019/4/4,77,rsa模式的盲签名算法,第一个盲签名算法的实现是d.chaum于1985年提出的，该算法使用了rsa算法。下面设定签名者b的公钥参数为e，私钥参数为d，而模为n。 下面a让b进行盲签名，签署消息m： （1）a盲变换：选用盲因子k,1km ,计算： 将t传送给b,2019/4/4,78,（2）b签名：b对t进行签名，计算 将签名s(t)传送给a （3）a取得签名：a计算取得签名 该签名算法显然成立，s其实就是b对消息m进行的rsa签名,2019/4/4,79,五、数字签名标准,2019/4/4,80,美国数字签名标准dss,数字签名标准dss（digital signature standard）是美国国家标准与技术研究所（nist）在1991年8月公布的，1994年5月19正式公布的，1994年12月1日正式作为美国联邦信息处理标准fips186颁布（该标准经过一定的修改，现在叫fips186-2）。dss中所用的算法为dsa (digital signature algorithm) 注意：dsa是算法，dss是标准。标准采用算法，算法是标准的一部分。,2019/4/4,81,dsa的争议,（1）dsa不能用于加密或密钥分配。 （2）dsa是由nsa研制的，可能存在馅门。 （3）dsa比rsa慢，二者产生签名的速度相同，但签名验证dsa比rsa慢40倍。 （4）rsa是一个事实上的标准。,2019/4/4,82,dsa的争议,（5）dsa的选择过程不公开，并且提供的分析时间不充分。 （6）dsa可能侵犯了其他专利。 （7）密钥长度太短。,2019/4/4,83,dsa签名与认证简图,我们先用图来表示dsa算法的签名过程认证过程。然后再具体的加以介绍。 m | m h h 签字 证实 k 比较,2019/4/4,84,dsa算法作为eigamal和schnorr签名算法的变形，显然其安全性也是基于求解离散对数的困难性上。其算法由参数构造，签名生成，签名验证构成。,dsa算法描述,2019/4/4,85,构造参数,参数可以分为全局参数、用户私钥和用户公钥三类。 1、全局参数 p：是一个大的素数， ； 其中， ，并且按64bit的幅度递增。 q:是（p-1）的素因子，并且其字长为160bit， 即 g: ，其中h是一个整数，1h(p-1), 且要求 。 以上三个参数p、q、g，是所有用户公用的参数，所以称之为全局参数，有的也称之为共享的化共模。,2019/4/4,86,2.用户私钥 x:选取一个随机数,要求0xq。 3.用户公钥 y:可以通过计算求得 。 签名的消息空间可以表示为 ，而签字结果的值空间可以表示为 。因为签名时需要一个随机数k，所以dsa算法需要一个随机数生成器。,2019/4/4,87,签名过程,对消息m的签名过程可以用如下步骤表示： （1）生成随机数k，0kq; （2）计算 ; （3）计算 ,消息m的签字结果就是（r,s） （4）发送消息和签名结果（m，r，s） 其中散列函数h，dss标准规定使用sha，sha算法由shs