5.6一次性签名

5.6一次性签名一次性签名是至多能签一个消息的签名方案。如果签多个消息，敌手就可以伪造签名。这里每签一个消息就需要一个新的公私钥对。一次性签名方案的签名和验证都十分有效。签名方案密钥生成单向函数LamportZYf:在Y中随机选取为私钥计算，及单向函数为公钥。,,,,1,20,21,10,1yyyy1,0,,kkyy)(,,jijiyfz1,0,1jki1,0,,,kkzz,,,,1,20,21,10,1zzzz签名算法对明文的签名是验证算法若包含在公钥中，则签名合法11xxxxkk},1|{,jxkiyiji}1),(|{,,,kiyfzzjijiji例如：素数p=7879,3是的本原元素。定义，令k=3.私钥公钥及7879Z7879mod3)(xxf58310,1y8030,2y42850,3y7351,1y24671,2y64491,3y20090,1z46720,2z2680,3z38101,1z47211,2z57311,3z7879mod3)(xxf对消息x=011的签名为（4285，2467，735）。对方验证时计算.它们都在公钥中，所以签名合法。对手虽然不能从求出，但是用这个方法对两个不同的消息签名时，对手就能伪造出另一个消息的签名。例如上例中对手知道011和101的签名分别是38107879mod373547217879mod324642687879mod34285jiz,jiy,),,(1,11,20,3yyy和，显然和分别是111和001的签名。),,(1,10,21,3yyy),,(1,10,20,3yyy),,(1,11,21,3yyy5.7失败—停止数字签名————Fail-stopFail-Stop数字签名最早是1990年由B.Pfitzmann&M.Waidner提出的。它允许实体A证明“声称是A的签名”实际上是伪造的签名。其做法是展示“该签名机制所基于的假设已受到威胁”。Fail-Stop数字签名的好处在于即使一个非常强的对手可能伪造一个签名，但可以察觉出是伪造的，与此同时不再使用该签名机制。所以称为“失败而后停止”更恰当一些。Fail-Stop数字签名应具有如下性质:(1)如果签名者依据该机制签署一个消息，则验证者能验证签名并接受它.(2)伪造者没有指数运算能力就不可能构造“能通过验证算法的一批签名。(3)如果伪造者以高概率成功地构造出一个能通过验证算法的签名，那么真正的签名者可以给出“该签名是伪造的”的证明。(4)签名者不能自己构造出一些签名，而后又断言他们是伪造的。以次保证接收者的安全Fail-Stop数字签名由签名算法、验证算法、“伪造”证明算法组成。其中“伪造”证明算法是对伪造签名的一种证明。1992年E.Heyst&T.P.Pedersen提出的Fail-Stop数字签名算法，它是一次性签名，即一个密钥只能用来签名一次。该数字签名的基本思想是：每个可能的公钥有许多私钥与之对应，然而签名者只知道其中之一，并用它作签名。窃听者搜集被签名的信息，试图从中发现签名者的私钥。由于私钥很多，所以成功的概率可以忽略不计。窃听者使用他自己生成的密钥伪造一个信息的签名，这个签名与签名者的签名不同。可信中心密钥生成p,q=(p-1)/2是素数，选择p使上的离散对数问题是难解问题。是q阶元中心选定并公开，由可信中心选定对任何人保密。pZ*pZ110qapamod0,,,qp由可信0a签名者的密钥生成对实体A选择为密钥，与其对应的公钥为，其中，2121,,,bbaa21,paamod211pbbmod212签名算法计算x的签名为验证算法验证成立，y是对信息x的合法签名伪造证明可信中心的密钥有以下基本事实qxbaymod)(111qxbaymod)(222),(21yyypyyxmod21210al具有相同公钥的私钥共有个，称这些私钥是等价的.证明：私钥与等价当且仅当且，21,2121,,,bbaa2q),,,(2121bbaa),,,(2121bbaapaaaamod21211pbbbbmod21212l1,,,02121qbbaaqaaaaaamod201201qbabbabmod201201确定，有q中选择。同样确定，也有q中选择。所以每个等价类有个私钥。l签名者用私钥k对明文x签名y能通过验证。与k等价的私钥都可以对该签名进行验证证明：私钥k=与等价，它们对消息x的签名不同，分别为:21,aa21,aa21,bb21,bb2qk),,,(2121bbaak),,,(2121bbaaqxbaymod111qxbaymod222qbxaymod111qbxaymod222签名验证通过，即。由私钥的定义知，容易证明=。用私钥也可以对该签名进行验证。pyyxmod211xx2121)(xyy2121x)(21kl只有q个不同且相互等价的私钥，它们对明文x的签名y都相同的。证明：已知公钥对应的私钥为，另一个私钥与之等价，即：21,),,,(2121bbaa),,,(2121vvuupcuuaamod121211quauaaacmod2012011pcvvbbmod221212qvavbabcmod2012012要求与对x的签名相同，即：),,,(2121vvuu),,,(2121bbaaqyxvuxbaymod~111111qyxvuxbaymod~2222222121212100010001000001yyccvvuuxxaa该方程组系数矩阵的秩为3，有q组解。),,,(2121vvuul只有q个不同私钥，它们对明文x的签名y都相同的。但用它们对另外的明文的签名则两两互不相同证明方法同上，从略。结论：已知对x的签名为y和另一个明文，敌手O猜中对x’的签名y’的概率是。xxq1证明：假设与签名者私钥等价的q个私钥为,它们对x的签名都是y，并且对x’的签名两两互不相同。所以敌手猜中私钥对签名的概率为。现假设敌手O能够对x’伪造一个合法签名并能通过验证。面对这个合法伪造签名，真正的签名者可以从他自己对明文x’的签名显然能通过验证。qkkk,,,21q1),(21yyy),(21yyy有得出的概率为，即存在的概率可以计算出的概率为真正的签名者以作为该签名的伪造证明提交给可信中心。pyyyyxmod212121qyayyaymod201201qyymod022q1122)(yyq11qyyyyamod))((121110q110a注意：这里假设签名者只有多项式时间计算能力，不能从计算出。现在签名者能够计算出，仲裁人接受签名者的“伪造证明”。若签名者用一个私钥签了两个不同消息，签名分别是。可以求出签名者的私钥，同理。所以该方案是一次性数字签名方案。,0a),,,(2121bbaa0axx~,)~,~(),,(2121yyyy111xbya)~()~(1111yyxxb)~()~(2212yyxxb222xbya