第八章 數(shù)字簽名

1,上講的主要內(nèi)容,數(shù)字簽名的簡介基于RSA數(shù)字簽名基于ElGamal數(shù)字簽名Schnorr數(shù)字簽名基于ECC數(shù)字簽名,第八章數(shù)字簽名續(xù),主講人：馬秀文,Email：maxiuwen2001,3,數(shù)字簽名的擴展,指定驗證者（不可否認）簽名盲簽名多重簽名群簽名代理簽名,4,前言,在數(shù)字簽字的實際應用當中，一些特殊的場合往往有特殊的要求。因此需要在基本數(shù)字簽名技術的基礎上進行擴展，以滿足這些要求。例如，為了保護信息擁有者的隱私，產(chǎn)生了盲簽名；為了實現(xiàn)簽名權的安全傳遞，產(chǎn)生了代理簽名；為了實現(xiàn)多人對同一消息的簽名，產(chǎn)生了多重簽名等等。正是這些實際應用的特殊需求，使得各種各樣的特殊數(shù)字簽名的研究一直是數(shù)字簽名研究領域非?；钴S的部分并產(chǎn)生很多分支。,5,不可否認簽名簡介,普通數(shù)字簽字，可以精確地對其進行復制，這對于如公開聲明之類文件的散發(fā)是必須的，但對另一些文件如個人或公司信件、特別是有價值文件的簽字，如果也可隨意復制和散發(fā)，就會造成災難。這時就需要不可否認簽名。,6,不可否認簽名簡介,這類簽名有一些特殊性質，其中最本質的是在無簽字者合作條件下不可能驗證簽字，從而可以防止復制或散布他所簽文件的可能性，這一性質使產(chǎn)權擁有者可以控制產(chǎn)品的散發(fā)，在電子出版系統(tǒng)知識產(chǎn)權保護中將有用場。特點：在得不到簽名者配合的情況下其他人不能正確進行簽名驗證，即驗證時，需由驗證者與簽名者合作才可證明其正確性。這樣的簽名是不允許使用者任意復制的。,7,不可否認簽名的組成,不可否認簽名方案由三部分組成：數(shù)字簽名算法、驗證協(xié)議、否認協(xié)議。否認協(xié)議(DisavowalProtocol)：在簽字者合作下才能驗證簽字，這會給簽字者一種機會，在不利于他時他“拒絕”合作以達到否認他曾簽署的文件。為了防止此類事件而引入。構成簽字算法的第三個組成部分，簽字者可利用否認協(xié)議向法庭或公眾證明一個偽造的簽字確是假的；如果簽字者拒絕參與執(zhí)行否認協(xié)議，就表明簽字事實上是真的由他簽署的。,8,不可否認簽名的算法（初始化）,S為簽名者；V為簽名的驗證者；p和q是滿足安全的大素數(shù)，q是p-1的大因子，g是域GF(p)的本原元；S擁有公私鑰對(x,y)，其中y=gxmodp；m為待簽名的文件；h是安全的哈希函數(shù)；,9,不可否認簽名的算法（簽名）,簽名者S進行如下計算：1.2.消息m的不可否認簽名是3.簽名者的驗證：,10,不可否認簽名的算法（驗證）,驗證者V簽名者S,11,如果不成立，這個簽名是有效的（簽名者沒有配合），否則，這個簽名是無效的。,不可否認簽名的算法（不可否認）,如果上面驗證沒通過，驗證者V做如下運算：,12,盲簽名,盲數(shù)字簽名是一種特殊的數(shù)字簽名，當用戶A發(fā)送消息m給簽名者B時，一方面要求B對消息簽名，另一方面又不讓B知道消息的內(nèi)容，也就是簽名者B所簽的消息是經(jīng)過盲化處理的。,13,盲簽名,盲簽名除具有一般數(shù)字簽名的特點外，還有下面兩個特征：(1)簽名者無法知道所簽消息的具體內(nèi)容，雖然他為這個消息簽了名。（匿名性）(2)即使后來簽名者見到這個簽名時，也不能將之與盲消息對應起來。（不可跟蹤性）,14,盲簽名的實現(xiàn)過程,注：將盲變換看作是信封，盲化文件是對文件加個信封，而去掉盲因子過程是打開信封。文件在信封中時無人可讀它，而在盲文件上簽字相當于在復寫紙信封上簽字，從而得到了對真文件(信封內(nèi))的簽字。,15,盲簽字協(xié)議,(a)A取一文件并以一隨機值乘之，稱此隨機值為盲因子（盲化處理）。(b)A將此盲文件送給B。(c)B對盲文件簽字。(d)A以盲因子除之，得到B對原文件的簽字。若簽字函數(shù)和乘法函數(shù)是可換的，則上述作法成立。否則要采用其它方法(而不是乘法)修改原文件。,16,盲簽字協(xié)議-安全性討論,B可以欺詐嗎？是否可以獲取有關文件的信息？若盲因子完全隨機，則可保證B不能由(b)中所看到的盲文件得出原文件的信息。即使B將(c)中所簽盲文件復制，他也不能(對任何人)證明在此協(xié)議中所簽的真正文件，而只是知道其簽字成立，并可證實其簽字。即使他簽了100萬個文件，也無從得到所簽文件的信息。,17,盲簽名存在問題（舉例）,反間諜組織的成員的身份必須保密，甚至連反間諜機構也不知道他是誰。反間機構的頭頭要給每個成員一個簽字的文件，文件上注明：持此簽署文件人(將成員的掩蔽名字寫于此)有充分外交豁免權。每個成員都有他自己的掩蔽名單。成員們不想將他們的掩蔽名單送給反間諜機構，敵人也可能會破壞反間諜機構的計算機。另一方面，反間機構也不會對成員給他的任何文件都進行盲簽字，例如，一個聰明的成員可能用“成員(名字)已退休，并每年發(fā)給100萬退休金”進行消息代換后，請總統(tǒng)先生簽字。此情況下，盲簽字可能有用。,18,盲簽名實現(xiàn)的方法（舉例）,假定每個成員可有10個可能的掩護名字，他們可以自行選用，別人不知道。假定成員們并不關心在那個掩護名字下他們得到了外交豁免，并假定機構的計算機為AgencysIntelligentComputingEngine，簡記為ALICE。則可利用下述協(xié)議實現(xiàn)：(a)每個成員準備10份文件，各用不同的掩護名字，以得到外交豁免權。(b)成員以不同的盲因子盲化每個文件。(c)成員將10個盲文件送給ALICE。(d)ALICE隨機選擇9個，并詢問成員每個文件的盲因子。(e)成員將適當?shù)拿ひ蜃铀徒oALICE。(f)ALICE從9個文件中移去盲因子，確信其正確性。(g)ALICE將所簽署10個文件送給成員。(f)成員移去盲因子，并讀出他的新掩護名字：“TheCrimsonStreak”，在該名字下這份簽署的文件給了他外交豁免權。,19,盲簽名的安全性分析,這一協(xié)議在抗反間成員欺詐上是安全的，他必須知道哪個文件不被檢驗才可進行欺詐，其機會只有10%。(當然他可以送更多的文件)ALICE對所簽第10個文件比較有信心，雖然未曾檢驗。這具有盲簽性，保存了所有匿名性。反間成員可以按下述方法進行欺詐，他生成兩個不同的文件，ALICE只愿簽其中之一，B找兩個不同的盲因子將每個文件變成同樣的盲文件。這樣若ALICE要求檢驗文件，B將原文件的盲因子給他；若ALICE不要求看文件并簽字，則可用盲因子轉換成另一蓄意制造的文件。以特殊的數(shù)學算法可以將兩個盲文件做得幾乎一樣，顯然，這僅在理論上是可能的。,20,盲簽名的分類及過程,由于具有匿名性和不可追蹤性的特點，盲簽名能滿足實際應用的許多需求，并已成為當前研究的熱點。目前根據(jù)“盲”程度不同，盲簽名方案通常分為強盲簽名、弱盲簽名兩類。其中強盲簽名方案應用最廣，大部分場合都趨向于強盲簽名的實現(xiàn)，弱盲簽名主要立足于特殊應用需求，是強盲簽名的重要補充，下面將對這兩類方案進行簡單的介紹。其中符號含義為：R(m)：為了文件m的內(nèi)容不被泄漏而進行盲化過程得到的盲文件。Sign(R(m)：盲文件R(m)的簽名。Sign(m)：去盲后得到的真實文件m的簽名。,21,強盲簽名,強盲簽名又稱為完全盲簽名，它的原始定義是指簽名者在文件上簽名是有效的，但不能把簽署文件的行為與簽署了的文件相關聯(lián)，即無法建立Sign(R(m)到Sign(m)的聯(lián)系。正是這些特點實現(xiàn)了不可追蹤性(untraceable)和匿名性（anonymous），也是盲簽名的重要特色。它主要應用于電子商務中，諸如電子現(xiàn)金的使用和電子投票等有匿名性要求的領域。完全盲簽名的研究已經(jīng)比較成熟，如盲RSA簽名和盲Schnorr簽名方案是主要的實現(xiàn)方案。下面以最早的RSA盲簽名實現(xiàn)方案為例，介紹強盲簽名方案。,22,強盲簽名(RSA),設簽名人S有公鑰(e,n)，私鑰d，要對用戶U的文件m進行完全盲簽名。(1)U選取隨機整數(shù)k1,n，盲化m為：t=mkemodn，并將t發(fā)給S。(2)S簽名t：。(3)U對t去盲：。s是文件m最終的簽名，易證，所以。s的效果相當于簽名人S直接對m簽名，但S不知道m(xù)的內(nèi)容。這個協(xié)議中，由于S不知道k，不能從td得到s，從而得不到m。,23,強盲簽名(DSA),設U簽名的接受者，S為簽名者，其擁有公私鑰對(x,y)，其中y=gxmodp，m為待簽名的文件，U和S的簽名過程如下：US簽名請求r,24,強盲簽名(DSA)（正確性）,25,弱盲簽名,所謂弱盲簽名方案是指簽名者S僅知道Sign(R(m)而不知道Sign(m)，但一旦公開Sign(m),S可以建立兩者間的聯(lián)系，即S能把盲簽名Sign(R(m)的行為與文件m的內(nèi)容關聯(lián)起來。如果把文件m看作是一個電子現(xiàn)金，則用戶U使用這個電子現(xiàn)金支付給商家，再由商家到銀行兌付時，銀行就可以從簽名Sign(m)中了解是U消費的，從而可以追蹤U的行為，這顯然不滿足不可跟蹤性。但是從另一角度看，這種方案可以用于遺囑、合同等電子公證，在一段時間內(nèi)保護信息秘密，在合適的場合公布有關內(nèi)容及用戶身份。,26,弱盲簽名(舉例),設U簽名的接受者，S為簽名者，其擁有公私鑰對(x,y)，其中y=gxmodp，m為待簽名的文件，U和S的簽名過程如下：US簽名請求r,27,弱盲簽名(舉例)（正確性）,28,盲簽名在電子投票中的應用,29,群(組)簽名,1991年，Chaum和Heyst首次提出群簽名方案（GroupSignature）。群簽名方案允許組中合法用戶以用戶組的名義簽名，具有簽名者匿名、只有權威者才能辨認簽名者等多種特點，在實際中有廣泛的應用。,30,群(組)簽名特點,只有組中成員才能代表組為消息簽名，簽名為群簽名。消息接收者可以驗證群簽名的有效性，但不能辨別簽名者。一旦發(fā)生爭論，從消息的群簽名權威（組長）可以辨別簽名者。,31,群簽名方案(初始化),組中每一用戶Ui隨機選擇xi1,q-1,i=1,2,t，并計算yi=gximodp,那么用戶Ui的私鑰為xi和公鑰為yi，同樣，GC（組長）隨機選擇xT1,q-1,并計算yT=gxTmodp，GC的私鑰為xT和公鑰為yT。對于組中每一用戶Ui，GC隨機選擇ki1,q-1,計算：,32,群簽名方案,GC將(ri,si)發(fā)送到組中用戶Ui，Ui收到(ri,si)，驗證等式：,如果等式成立，(ri,si)是GC對用戶Ui身份的有效簽名。,對于組中每一用戶Ui，GC存儲(ri,si，ai，yi),其中：,33,群簽名方案(簽名),為了對消息m進行簽名，用戶Ui隨機選擇t1,q-1,計算:,那么,用戶Ui生成的群簽名值為(r,s),(ri,si),34,群簽名方案(驗證),接受方在收到消息m和群簽名值(r,s),(ri,si)后，驗證以下方程是否成立：如果等式成立，接受簽名，否則簽名無效。,35,群簽名方案(正確性),36,群簽名方案(揭示簽名者),(1)GC使用消息m和群簽名值(r,s),(ri,si)驗證這個群簽名是否有效，若有效進入下一步。(2)GC根據(jù)簽名值中的(ri，si),在GC初始化過程中保存的(ri，si，ai，yi)中查找匹配項，若存在，根據(jù)yi能確定用戶身份。(3)若成立，證明yi的用戶身份。,37,多重數(shù)字簽名的簡介,在數(shù)字簽名應用中，有時需要多個用戶對同一文件進行簽名和認證，比如，一個公司發(fā)表的聲明涉及到財務部、開發(fā)部、銷售部、售后服務部等部門，需要這些部門簽名認可，那么，需要這些部門對這個聲明文件進行簽名。能夠實現(xiàn)多個用戶對同一文件進行簽名的數(shù)字簽名方案稱為多重數(shù)字簽名（DigitalMulti-signature）方案。,38,多重數(shù)字簽名的簡介,根據(jù)不同的簽名過程，多重數(shù)字簽名方案可分兩類：有序多重數(shù)字簽名（SequentialMultisignature）和廣播多重數(shù)字簽名（BroadcastingMultisignature）。無論是有序多重簽名方案，還是廣播多重簽名方案，都包括文件發(fā)送者（Issuer）、文件簽名者（Signers）和文件驗證者（Verifier）。在廣播多重簽名方案中還包括簽名收集者（Collector）。,39,有序多重簽名方案的簡介,文件發(fā)送者規(guī)定文件簽名順序，然后將文件發(fā)送到第一個簽名者，除了第一個簽名者外，每一位簽名者收到簽名文件后，首先驗證上一簽名的有效性，如果簽名有效，繼續(xù)簽名，然后將簽名文件發(fā)送到下一個簽名者；如果簽名無效，拒絕對文件簽名，終止整個簽名過程。當簽名驗證者收到簽名文件后，驗證簽名的有效性，如果有效，多重數(shù)字簽名有效；否則，多重數(shù)字簽名無效。下圖描述了有序多重數(shù)字簽名方案。,40,Elgamal有序多重簽名方案(初始化),設UI為消息發(fā)送者，UV為簽名驗證者，U1,U2,Ut為消息的簽名者。p和q是滿足安全的大素數(shù)，q是p-1的大因子，g是域GF(p)的本原元，每一個簽名者Ui都擁有公私鑰對(xi,yi)，其中yi=gximodp。消息發(fā)送者UI預先設計一種簽名順序(U1,U2,Ut)并將這種簽名順序發(fā)送給每一位簽名者。,41,Elgamal有序多重簽名方案(簽名),UI將消息m發(fā)送給第一個簽名者U1。設s0=0，那么每一位簽名者Ui收(i2)到上一個簽名者Ui-1的簽名值(m,si-1)后，做如下操作：(1)驗證等式是否成立，如果成立，Ui認為U1,U2,Ui-1對消息m的簽名有效，否則認為簽名無效，拒絕繼續(xù)對消息簽名。(2)Ui隨機選擇ki1,q,計算ri=gkimodp和si=si-1+h(m)xi-rikimodq。(3)將(m,si)發(fā)送到下一個簽名者Ui+1，ri將分別發(fā)送到Ui以后的簽名者。,42,Elgamal有序多重簽名方案(驗證),消息m的有序多重簽名值(m,st,r1,r2,rt)。簽名驗證者UV驗證式：是否成立，如果成立，UV認為U1,U2,Ut對消息m進行的多重簽名有效，否則認為簽名無效。,43,Elgamal有序多重簽名方案(正確性),因此，Elgamal有序多重數(shù)字簽名方案是正確的。,44,廣播多重簽名方案的簡介,在廣播多重數(shù)字簽名方案中，文件發(fā)送者同時將文件發(fā)送給每一位簽名者進行簽名，然后簽名者將簽名文件發(fā)送到簽名收集者，由收集者對簽名文件進行整理并發(fā)送給簽名驗證者，簽名驗證者驗證多重簽名的有效性。下圖描述了廣播多重數(shù)字簽名方案。,45,Elgamal廣播多重簽名方案(初始化),設UI為消息發(fā)送者，UV為簽名驗證者，U1,U2,Ut為消息的簽名者，UC為消息收集者。p和q是滿足安全的大素數(shù)，q是p-1的大因子，g是域GF(p)的本原元，每一個簽名者Ui都擁有公私鑰對(xi,yi)，其中yi=gximodp。UI將消息m同時發(fā)送到Ui(i=1,2,t)進行簽名，Ui將簽名信息發(fā)送給簽名收集者UC，UC收到簽名信息后驗證其簽名的有效性，然后對簽名進行整理并產(chǎn)生多重簽名，然后將這個多重簽名發(fā)送到UV進行驗證。,46,Elgamal廣播多重簽名方案(簽名),UI將消息m發(fā)送給每一個簽名者Ui(i=1,2,t)，Ui和UC收到消息后做如下操作：(1)Ui隨機選擇ki1,q,計算ri=gkimodp，將ri發(fā)送到簽名接收者UC。(2)UC收到ri(i=1,2,t)后，計算，然后UC將R發(fā)送到其余每一個簽名者Ui(i=1,2,t)。(3)對于消息m，Ui(i=1,2,t)計算si=h(m,R)xi-rikimodq,然后將簽名消息(m,si,ri)發(fā)送到UC。(4)當UC收到(m,si,ri)后，其中i=1,2,t，計算，然后將(m,S,R)發(fā)送給UV。,47,Elgamal廣播多重簽名方案(驗證),當簽名驗證者UV收到多重簽名值(m，S，R)后，UV進行如下驗證：是否成立，如果成立，UV認為U1,U2,Ut對消息m進行的多重簽名有效，否則認為簽名無效。,48,Elgamal廣播多重簽名方案(正確性),因此，Elgamal廣播多重數(shù)字簽名方案是正確的。,49,代理簽名的簡介,代理簽名是指原始簽名者把他的簽名權授給代理者，代理者代表原始簽名者行使他的簽名權。當驗證者驗證代理簽名時，驗證者既能驗證這個簽名的有效性，也能確信這個簽名是原始簽名者認可的簽名。,50,代理簽名的發(fā)展過程,代理簽名的思想最早出現(xiàn)于1991年1996年第一次系統(tǒng)地闡述了代理簽名概念全代理授權部分代理授權授權書代理授權門限代理簽名、代理盲簽名、指定驗證者的代理簽名、一次代理簽名、匿名代理者的代理簽名、代理多重簽名等分布式計算、電子投票、電子付費、網(wǎng)格計算、移動代理等,51,代理簽名的定義,設A、B分別是某個代理數(shù)字簽名體制的兩個用戶，他們的公私鑰對分別是(xA,yA)和(xB,yB)。如果以下條件成立：A利用他的私鑰xA計算出一個數(shù)，并將秘密地交給B。任何人（包括B）在試圖求出xA時，不會對它有任何幫助。利用（可能包括xB）生成一個新的簽名密鑰，即代理私鑰xP。,52,代理簽名的定義（續(xù)）,存在一個公開的通用簽名算法Sign，對被簽名的文件m，有s=Sign(xP,m)，其中s是代理簽名。存在一個與簽名算法Sign相對應的驗證算法Ver，驗證等式Ver(yP,s,m)=True是否成立。任何人在試圖求出xA、xB、或xP時，任何數(shù)字簽名值s都不會對它產(chǎn)生幫助；那么就稱用戶A將他的（部分）數(shù)字簽名權利委托給了用戶B，并且稱A為B的原始簽名者，稱B為A的代理簽名者，稱為委托代理密鑰，xP稱為代理簽名密鑰，稱以xP作為簽名密鑰對消息m生成的數(shù)字簽名s為A的代理簽名。,53,代理簽名的性質,可驗證性可區(qū)分性不可偽造性可識別性不可否認性可控性,54,代理簽名的組成,代理密鑰對生成算法：它的輸入值是A和B，分別由原始簽名者A和代理簽名者B生成的，其輸出是代理密鑰對(xP,yP)，它的實現(xiàn)是由原始簽名者A和代理簽名者B經(jīng)過交互來完成的。代理簽名算法：代理簽名者B使用代理私鑰xP對文件m簽名，其輸入值為xP和m，輸出值是代理簽名值sP.代理簽名驗證算法：驗證者V對代理簽名進行驗證，其輸入值為代理簽名(sP,m,yP)，輸出是一個布爾值，要么是真，要么是假.,55,代理簽名的分類,完全授權型（Fulldelegation）部分授權型（Partialdelegation）非保護代理者的代理簽名（proxy-unprotectedproxysignature）保護代理者的代理簽名（proxy-protectedproxysignature）帶授權書型（Delegationwithwarrant）,56,非保護代理者的代理簽名(PH的方案),原始簽名者A,代理簽名者B,代理授權階段,57,PH的方案(續(xù)),代理簽名算法利用通用的簽名生成算法Sign，B使用代理私鑰xP代表原始簽名者A對文件m進行簽名s=Sign(xP,m)，有效的代理簽名值為(m,s,r,yA,IDB)，其中IDB表示代理簽名者的標識。代理驗證算法為了驗證代理簽名s，驗證者首先利用代理簽名值(m,s,r,yA,IDB)計算代理公鑰，然后利用與Sign相對應的通用簽名驗證算法Ver，驗證者使用yp驗證代理簽名的有效性，即Ver(yP,s,m)=True，如果等式成立，說明這個代理簽名是原始簽名者認可的且是有效的。,，,58,保護代理者的代理簽名(MUO的方案),原始簽名者A,代理簽名者B,代理授權階段,59,MUO的方案(續(xù)),代理簽名算法利用通用的簽名生成算法Sign，B使用代理私鑰xP代表原始簽名者A對文件m進行簽名s=Sign(xP,m)，有效的代理簽名值為(m,s,r,yA,yB)。代理驗證算法為了驗證代理簽名s，驗證者首先利用代理簽名值(m,s,r,yA,yB)計算代理公鑰，然后利用與Sign相對應的通用簽名驗證算法Ver，驗證者使用yp驗證代理簽名的有效性，即Ver(yP,s,m)=True，如果等式成立，說明這個代理簽名是原始簽名者認可的且是有效的。,，,60,帶授權書的代理簽名(KPW的方案),通過在代理簽名中添加授權書，Kim等人提出一種新形式部分授權的代理簽名方案，其主要思想是代理簽名者利用自己