第9章 数字签名

第9章数字签名数字签名的基本概念RSA数字签名方案EIGamal数字签名方案数字签名标准DSS基于离散对数问题的一般数字签名体制其它签名方案作业·数字签名的基本概念·数字签名：是一种给以电子形式存储的消息签名的方法。·数字签名与物理签名的差异：·签署文件的属性：在传统签名模式中，手写签名是所签署文件的物理部分。然而，数字签名没有物理地附加在所签文件上，因此签名算法必须以某种形式将签名“绑”到所签文件上。·签名的验证：一个传统的签名通过比较其它已认证的签名来验证当前签名的真伪。数字签名却能通过一个公开的验证算法对它进行确认。这样，“任何人”都能验证一个数字签名。安全数字签名方案的使用能阻止伪造签名的可能性。·签名的可复制性：数字签名文件的“拷贝”与原签名文件相同，而仿造（如复印）的手写签名文件能与原来的签名文件区分开来。这意味着我们必须采取措施防止一个数字签名消息被重复使用。·数字签名应具有的特征（1）签名是可信的（2）签名不可伪造（3）签名不可复制（4）签名的文件是不可改变的（5）签名是不可抵赖的定义10.1：一个签名方案是一个满足下列条件的五元组�EMBEDEquation.3���：�EMBEDEquation.DSMT4���是由所有可能的消息组成的一个有限集合；�EMBEDEquation.DSMT4���是由所有可能的签名组成的一个有限集合；�EMBEDEquation.DSMT4���为密钥空间，它是由所有可能的密钥组成的一个有限集合；对每一个�EMBEDEquation.3���，有一个签名算法�EMBEDEquation.3���和一个相应的验证算法�EMBEDEquation.3���。对每一个消息�EMBEDEquation.3���和每一个签名�EMBEDEquation.3���，每一个�EMBEDEquation.3���和�EMBEDEquation.3���都是满足下列条件的函数：�EMBEDEquation.3���由�EMBEDEquation.3���和�EMBEDEquation.3���组成的数据对�EMBEDEquation.DSMT4���称为签名消息。_1094197718.unknown_1094197783.unknown_1094197806.unknown_1094197850.unknown_1094197940.unknown_1094197951.unknown_1094197931.unknown_1094197818.unknown_1094197795.unknown_1094197746.unknown_1094197758.unknown_1094197731.unknown_1094197630.unknown_1094197706.unknown_1090047118.unknown对每一个，和应该是多项式时间函数。是公开的函数，而是保密的。给定一个消息x，除了Alice之外，任何人去计算使的数字签名y应该计算上不可行（注意，对给定的x,可能存在不止一个y，这要看函数是如何定义的）。如果Oscar能够计算出使得成立的数据对，而x没有事先被Alice签名，则签名y称为伪造签名。非正式地，一个伪造的签名是由Alice之外的其他人产生的一个有效数字签名。_1094197964.unknown_1094197985.unknown_1094197999.unknown_1094198005.unknown_1094197978.unknown_1090047708.unknown_1094197931.unknown_1090047445.unknown对签名方案来讲，经常考虑下面的攻击模型：·唯密钥攻击：Oscar拥有Alice的公钥，即验证函数。·已知消息攻击：Oscar拥有一系列以前由Alice签名的消息，例如，其中是消息而是Alice对这些消息的签名（因此，）。·选择消息攻击：Oscar请求Alice对一个消息列表签名。因此他选择消息，并且Alice提供对这些消息的签名，它们分别是，。_1240909586.unknown_1240909617.unknown_1240909653.unknown_1240909662.unknown_1240909627.unknown_1240909596.unknown_1240909531.unknown_1240909550.unknown_1090071127.unknown下面考虑攻击者可能的几种目的：·完全破译：攻击者能够确定Alice的私钥，即签名函数。因此他能对任何消息产生有效的签名。·选择性伪造：攻击者能以某一不可忽略的概率对另外某个人选择的消息产生一个有效的签名。换句话说，如果给攻击者一个消息，那么他能（以某种概率）决定签名，使得。该消息不应该是以前Alice曾经签名的消息。·存在性伪造：攻击者至少能够为一则消息产生一个有效的签名。换句话说，攻击者能创建一个数对，其中是消息而。该消息不应该是以前Alice曾经签名的消息。_1090066273.unknown_1090075401.unknown_1090650592.unknown_1090075031.unknown_1090049662.unknown·RSA数字签名方案密码体制：RSA签名方案设�EMBEDEquation.3���，其中�EMBEDEquation.3���和�EMBEDEquation.3���是素数。设�EMBEDEquation.3���，并定义�EMBEDEquation.3���是素数，�EMBEDEquation.DSMT4���。值�EMBEDEquation.3���和�EMBEDEquation.3���为公钥，值�EMBEDEquation.3���、�EMBEDEquation.3���和�EMBEDEquation.3���为私钥。对�EMBEDEquation.DSMT4���，定义�EMBEDEquation.3���，�EMBEDEquation.3���，其中�EMBEDEquation.3���。_1090049103.unknown_1090648830.unknown_1271006199.unknown_1272177653.unknown_1272177779.unknown_1272177589.unknown_1240909167.unknown_1090049233.unknown_1090049551.unknown_1090049136.unknown_1090048637.unknown_1090049056.unknown_1090048616.unknownRSA的缺点：1.我们看到，通过选择一个签名并计算使得，Oscar能生成一个有效的签名。2.对RSA签名方案的另一种攻击是基于它的乘法特性。假设和是任意两个由Alice以前签名的消息，那么，因此Oscar能对消息产生有效的签名。_1090087326.unknown_1090087371.unknown_1090651371.unknown_1090651381.unknown_1090087364.unknown_1090066273.unknown_1090075031.unknown_1090049662.unknown3.还有另外一种变化。假定Oscar要对消息伪造一个签名。对Oscar来说很容易找到使。现在假设他请求Alice为和签名，签名结果分别是和。然后，象前面的攻击一样，是消息的签名。_1090087740.unknown_1090087834.unknown_1090087892.unknown_1090651702.unknown_1090087885.unknown_1090087821.unknown_1090087371.unknown_1090087695.unknown_1090049662.unknown·阻止以上攻击的一种方法是让消息具备足够的冗余，使使用这种方法获得的伪造签名对应一个有“意义”的消息的概率非常小。·另外，Hash函数与数字签名结合使用能阻止这种伪造（先Hash，再加密。密码Hash函数将在下一章作讨论）。_1090049662.unknown签名与公钥加密的结合：1、先签名后加密。假定Alice希望发送一个签名的加密消息给Bob。给定明文，Alice将计算她的签名，然后使用Bob的公开加密函数加密和，获得。密文将被传送至Bob。当Bob接收到后，他首先使用解密函数获得，然后使用Alice的公开验证算法来验证。_1090067688.unknown_1090067793.unknown_1090649857.unknown_1090649914.unknown_1090649820.unknown_1090067719.unknown_1090066273.unknown_1090067569.unknown_1090049662.unknown2、先加密后签名。如果Alice首先加密，然后对加密结果签名会怎样呢？那么她将计算和。Alice将把发送给Bob，Bob用来验证对的签名，然后解密，获得。这种方法一个潜在的问题是如果Oscar获得了，他能够用他自己的签名来替换Alice的签名。然后，如果Oscar将发送给Bob，Bob将用来验证Oscar的签名，Bob可能由此推断明文来自Oscar。因为这种潜在的危险（不能确定发送方身份），大多数人建议在加密之前签名。_1090068034.unknown_1090068144.unknown_1090069160.unknown_1090649987.unknown_1240909280.unknown_1090649967.unknown_1090069064.unknown_1090068091.unknown_1090066273.unknown_1090067923.unknown_1090049662.unknown·EIGamal签名方案·1985年人们提出了ElGamal签名方案，该方案的变型已被美国国家标准技术研究所采纳为数字签名算法（或DSA）。·与RSA密码体制既可以用于公钥又可以用于签名方案不一样，这种方案是为签名而专门设计的。·ElGamal签名方案是非确定性的（ElGamal公钥密码体制也是非确定性的）。这意味着对任何给定的消息有许多有效的签名，并且验证算法能够将它们中的任何一个作为可信的签名而接受。用到的符号：··表示从1到p-1与p互素的数·若p为素数，则为一乘法群·若p为素数，则是一个本原元EMBEDEquation.DSMT4（注：）_1271163645.unknown_1271163867.unknown_1271164011.unknown_1272178865.unknown_1271163876.unknown_1271163751.unknown_1271163167.unknown密码体制：ElGamal签名方案设�EMBEDEquation.3���是一个使得在�EMBEDEquation.3���上的离散对数问题是难处理的素数，设�EMBEDEquation.3���是一个本原元。设明文空间�EMBEDEquation.3���签名空间�EMBEDEquation.DSMT4���，定义密钥空间�EMBEDEquation.3���，值�EMBEDEquation.3���是公钥，�EMBEDEquation.3���是私钥。对�EMBEDEquation.3���和一个秘密的随机数�EMBEDEquation.3���，定义�EMBEDEquation.3���，其中�EMBEDEquation.3���，�EMBEDEquation.3���。对�EMBEDEquation.3���和�EMBEDEquation.3���，定义�EMBEDEquation.3���。_1090137185.unknown_1090137342.unknown_1090137627.unknown_1094211151.unknown_1271162891.unknown_1271162923.unknown_1090138004.unknown_1090137459.unknown_1090137583.unknown_1090137413.unknown_1090137253.unknown_1090137312.unknown_1090137221.unknown_1090133191.unknown_1090136948.unknown_1090133070.unknown注释：·p为大素数，且满足一些其它条件使得其上的离散对数问题难处理，比如要求p-1有大素因子等。·明文空间为，说明加密时每个分组数值一般不超过p-1。注意：在具体使用时一般对消息的Hash值进行签字·如果签名被正确地构造出来，那么验证将会成功，因为，其中。·Alice使用私钥和秘密随机数（用于一则消息）计算签名。仅仅利用公开的信息就能验证该签名_1090138338.unknown_1090150263.unknown_1090150365.unknown_1271163645.unknown_1090149572.unknown_1090138228.unknown例：假定选取，那么。若Alice要对消息签名，她取（注意）。那么并且任何人通过计算和来验证这个签名。因此，该签名是有效的。_1090150959.unknown_1090151216.unknown_1090565182.unknown_1090565415.unknown_1090151388.unknown_1090151022.unknown_1090150770.unknown_1090150800.unknown_1090150716.unknownElGamal签名方案的安全性一、伪造签名1、假定Oscar在不知道的情况下想对消息伪造签名。如果Oscar选择一个值，然后试图找出相应的，那么他必须计算离散对数。另一方面，如果他首先选择，然后试图找到，那么他必须“求解”等式以便获得这个“未知”的，这是一个还没有已知可行的办法来求解的方程。然而，它与象离散对数问题这样研究得比较透彻的问题似乎没有关系。也许仍然存在某种方法可同时计算和，使是一个签名。但是，没有人发现解这个问题的方法，也没有人能够证明不能解这个问题。_1090150263.unknown_1090150919.unknown_1090153742.unknown_1090154745.unknown_1090151817.unknown_1090150365.unknown_1090149644.unknown2、如果Oscar先选择和，然后去解，那么他又一次面临着求解离散对数问题的一个实例，也就是计算。因此，使用这种方法Oscar不能对给定的消息签名。3、然而，通过同时选择、和，存在一种方法使Oscar能对任意的消息签名。因此，在唯密钥攻击的情况下进行存在性伪造还是可能的（假定没有使用Hash函数）。我们对此作具体描述。_1090150365.unknown_1090150919.unknown_1090155105.unknown_1090149644.unknown（1）设和是满足的整数，假设的表达式为。那么验证条件是，等价于。如果且，则上式成立。给定和，在的条件下，很容易能够利用这两个模的等式求出和。我们得到如下的等式：，以及很显然，按照这种方法构造出来的是消息的有效签名。_1090155581.unknown_1090156608.unknown_1090157443.unknown_1090667097.unknown_1271245380.unknown_1272179938.unknown_1090667080.unknown_1090157237.unknown_1090157311.unknown_1090157097.unknown_1090156063.unknown_1090156497.unknown_1090155709.unknown_1090150365.unknown_1090155571.unknown_1090149644.unknown例：在前面的例子中，设。假定Oscar选择；则，他能求出：那么（117，41）是消息331的有效签名，这可从下面的式子得到验证：；。_1090157784.unknown_1271245717.unknown_1271245727.unknown_1271245736.unknown_1271245708.unknown_1090157653.unknown_1090157705.unknown_1090157599.unknown（2）下面介绍第二种伪造类型，采取这种伪造时，Oscar从Alice已签名的消息开始。它属于已知消息攻击的存在性伪造。假定是消息的有效签名，那么Oscar可利用它给其它的消息签名。设，和是整数，，且。计算，那么，验证条件显然成立。因此，是的有效签名。_1090157443.unknown_1090158930.unknown_1090159051.unknown_1090159314.unknown_1090159355.unknown_1090159188.unknown_1090158981.unknown_1090158798.unknown_1090158834.unknown_1090158760.unknown_1090155571.unknown_1090155581.unknown_1090150365.unknown这两种方法都是存在性伪造，但它们似乎还不能被修改成选择性伪造。因此，在使用安全Hash函数的情况下，这两种方法似乎对ElGamal签名方案的安全性不构成威胁。二、完全破译在ElGamal签名方案使用不仔细的情况下我们也能提出攻击它的一些方法。1、首先，在计算签名时所使用的随机值不能泄露。如果被泄露出去，则计算将是很容易的事情。一旦被泄露，那么系统就完全被破坏了，Oscar能随意地伪造签名了。2、系统的另外一个误用是对两个不同的消息签名时使用相同的值。这将使Oscar计算变得容易，因而攻破系统（见下页）。_1090160831.unknown_1090160924.unknown_1090160707.unknown具体做法如下：设是消息的签名，是消息的签名，那么我们有，，因此，。令，对未知的我们获得如下的等式：。该方程等价于：。设。因为和，所以有。定义，，，那么等式变为：。因为，我们可以计算出，那么由模决定的值为，这就产生了个候选的值：，其中。对于个候选的值，可通过等式检测出其中唯一正确的那一个。_1090161709.unknown_1090162397.unknown_1090162695.unknown_1090163195.unknown_1090668135.unknown_1090668225.unknown_1090668374.unknown_1090668177.unknown_1090668089.unknown_1090163011.unknown_1090162600.unknown_1090162633.unknown_1090162471.unknown_1090162165.unknown_1090162283.unknown_1090162342.unknown_1090162209.unknown_1090162060.unknown_1090162100.unknown_1090161988.unknown_1090161371.unknown_1090161560.unknown_1090161608.unknown_1090161379.unknown_1090161297.unknown_1090161340.unknown_1090160707.unknown·数字签名标准DSS·1991年美国国家标准技术研究所提出了数字签名算法DSA(DigitalSignatureAlgorithm)作为数字签字标准DSS(DigitalSignatureStandard)·DSS最初于1991年公布，在考虑了公众对其安全性的反馈意见后，于1993年公布了其修改版。·数字签名算法DSA·DSA是在ElGamal和Schnorr两个签名方案的基础上设计的，其安全性基于求离散对数的困难性。·算法描述如下：eq\o\ac(○,1)全局公开密钥p：满足的大素数，其中且L是64的倍数。q：p-1的素因子，满足，即q长为160比特。g：，其中h是满足1<h<p-1且使得的任一整数。_1108101768.unknown_1272133940.unknown_1272134008.unknown_1272133876.unknown_1041963386.unknowneq\o\ac(○,2)用户秘密钥xx是满足0<x<q的随机数或伪随机数。eq\o\ac(○,3)用户的公开钥y。eq\o\ac(○,4)用户为待签消息选取的秘密数kk是满足0<k<q的随机数或伪随机数。_1108101784.unknowneq\o\ac(○,5)签名过程用户对消息M的签名为(r,s)，,，H(M)是由SHA-1求出的杂凑值。eq\o\ac(○,6)验证过程设接收方收到的消息为，签名为。计算，，，。检查，若相等，则认为签名有效。这是因为若，则_1108101795.unknown_1108101810.unknown_1108101821.unknown_1108101869.unknown_1272134389.unknown_1108101827.unknown_1108101815.unknown_1108101802.unknown_1041963667.unknown_1041964326.unknown_1041963644.unknown·由于离散对数的困难性，敌手从r恢复k或从s恢复x都是不可行的。·还有一个问题值得注意，即签名产生过程中的运算主要是求r的模指数运算，而这一运算与待签的消息无关，因此能被预先计算。·事实上，用户可以预先计算出很多r和以备以后的签名使用，从而可大大加快产生签名的速度。_1041964689.unknown_1041964728.unknown·DSS的基本方式RSA签字与DSS签字的不同方式_1108473054.vsd·采用RSA签名时，将消息输入到一个杂凑函数以产生一个固定长度的安全杂凑值，再用发方的秘密钥加密杂凑值就形成了对消息的签名。·消息及其签名被一起发给收方，收方得到消息后再产生出消息的杂凑值，且使用发方的公开钥对收到的签名解密。·这样收方就得了两个杂凑值，如果两个杂凑值是一样的，则认为收到的签字是有效的。·DSS签字也利用杂凑函数产生消息的一个杂凑值，杂凑值连同随机数k一起作为签名函数的输入，签名函数还需使用发方的秘密钥和供所有用户使用的一族参数，称这一族参数为全局公开钥。·签名函数的两个输出s和r就构成了消息的签名(s,r)。接收方收到消息后再产生出消息的杂凑值，将杂凑值与收到的签名一起输入验证函数，验证函数还需输入全局公开钥和发方的公开钥。·验证函数的输出如果与收到的签名成份r相等，则验证了签字是有效的。_1105889543.unknown_1105889576.unknown_1041862750.unknownElGamal与DSA签名长度的比较：·ElGamal签名长度2048bits·DSA签名长度320bits·基于离散对数问题的一般数字签名体制ElGamal、DSA等签字体制都可归结为离散对数签字体制的特例。eq\o\ac(○,1)体制参数：大素数；：或的大素因子；：，且，其中表示g是从中随机选取的，其中；：用户A的秘密钥，；：用户A的公开钥，。_1032953836.unknown_1033593239.unknown_1108101989.unknown_1108473296.unknown_1108473300.unknown_1049980887.unknown_1033593170.unknown_1033593192.unknown_1033593096.unknown_1032953799.unknown_1032953808.unknown_1032017922.unknowneq\o\ac(○,2)签名的产生过程对于待签名的消息，A执行以下步骤：·计算的杂凑值；·选择随机数：，计算；·从签名方程中解出。方程的系数有许多种不同的选择方法，下表给出了这些可能的选择。以作为产生的数字签名。_1032730159.unknown_1033593631.unknown_1108102013.unknown_1108102019.unknown_1033593658.unknown_1033593438.unknown_1032729554.unknown_1032729694.unknown_1032728834.unknown参数可能的置换取值表 １１１１_1049981491.unknown_1049981600.unknown_1049981602.unknown_1049981603.unknown_1049981605.unknown_1049981601.unknown_1049981509.unknown_1049981517.unknown_1049981500.unknown_1049981447.unknown_1049981482.unknown_1032731586.unknowneq\o\ac(○,3)签名的验证过程收方在收到消息和签名后，可以按照以下验证方程检验：这样的方案数共有120种，其中安全的共有18种，ElGamal与DSA都是其中的一种情况。_1033593931.unknown_1108102032.unknown_1032730159.unknown·其它签名方案·一次签名：一个签名方案仅对一则消息签名时是安全的、但可以对签名进行任意次验证（一套密钥只能用一次，第二次签名时需要产生新的密钥）。·不可否认签名：签名消息的真伪只有经过签名者同意才能够被验证。例如软件公司发布软件时可以对每一份拷贝进行签名，用来保证不包含病毒。但公司只往往希望只有正版用户才能验证签名，而盗版用户不能。·群签名：只有某团体内的成员能够对消息签名；签名的接收者能够证实消息是该团体的有效签名；签名的接收者不能决定是该团体内哪一个成员的签名；当出现争议时，签名能够被“打开”，以揭示签名者的身份。例如公司各部门资源的管理问题。·多重签名：多个人对同一文件进行签名。往往是一级一级按顺序来签，每一级签名之前要验证上一级有没有签名。·代理签名：当需要签名的人不方便签名时（比如生病或者到一些不方便上网的地方出差），他可以让秘书代签，但前提是他不能把自己的私钥给秘书。一般要求代理签名和正常签名是可区分的。·盲签名：签名者看不到自己所签文件的内容，或者只看到所签的一部分信息。作业：在ElGamal签名方案中，设，是的本原元，选取，EMBEDEquation.DSMT4。公开，保密。假设要Alice对消息进行签名，其秘密选取，请计算出Alice对的签名，并写出接收方Bob对该签名的验证过程。_1146683717.unknown_1146683802.unknown_1146683909.unknown_1180381773.unknown_1180381793.unknown_1146683982.unknown_1146683855.unknown_1146683781.unknown_1146683625.unknown_1146683657.unknown_1146683615.unknown