第5章數(shù)字簽名5.1數(shù)字簽名的基本概念5.2RSA數(shù)字簽名5.3ElGamal數(shù)字簽名5.4數(shù)字簽名標準DSS5.5其他數(shù)字簽名5.5.1基于離散對數(shù)問題的數(shù)字簽名

5.5.2基于大整數(shù)分解問題的數(shù)字簽名

5.5.3具有特殊用途的數(shù)字簽名現(xiàn)代密碼學電子科技大學精選5.1數(shù)字簽名的基本概念數(shù)字簽名應(yīng)具有以下特性：（1）不可偽造性除了簽名者外，任何人都不能偽造簽名者的合法簽名。（2）認證性接收者相信這份簽名來自簽名者。（3）不可重復使用性一個消息的簽名不能用于其他消息。（4）不可修改性一個消息在簽名后不能被修改。（5）不可否認性簽名者事后不能否認自己的簽名。現(xiàn)代密碼學電子科技大學精選一個數(shù)字簽名體制（也稱為數(shù)字簽名方案）一般有兩個組成部分，即簽名算法（signaturealgorithm）和驗證算法（verificationalgorithm）。簽名算法的輸入是消息m和密鑰k，輸出是對m的數(shù)字簽名，記為s=（m）。驗證算法輸入的是消息m和簽名s，輸出是真或偽，記為：算法的安全性在于從m和s難以推出密鑰k或偽造一個消息使和s可被驗證為真。現(xiàn)代密碼學電子科技大學精選數(shù)字簽名可按以下幾種方式進行分類：①按用途來分，數(shù)字簽名可分為普通數(shù)字簽名和具有特殊用途的數(shù)字簽名[如盲簽名（blindsignature）、不可否認簽名（undeniablesignature）、群簽名（groupsignature）、代理簽名（proxysignature）等]?，F(xiàn)代密碼學電子科技大學數(shù)字簽名的分類精選②按是否具有消息恢復功能來分，數(shù)字簽名可分為具有消息恢復功能的數(shù)字簽名和不具有消息恢復功能的數(shù)字簽名。③按是否使用隨機數(shù)來分，數(shù)字簽名可分為確定性數(shù)字簽名和隨機化數(shù)字簽名（randomizeddigitalsignature）精選1．參數(shù)與密鑰生成（1）選取兩個保密的大素數(shù)p和q。（2）計算n=pq,，其中是n的歐拉函數(shù)值。（3）隨機選取整數(shù)e，1＜e＜，滿足。（4）計算d，滿足。（5）公鑰為(e,n)，私鑰為d。

5.2RSA數(shù)字簽名現(xiàn)代密碼學電子科技大學精選2．簽名對于消息m∈，簽名為：3．驗證對于消息簽名對(m,s)，如果：

則s是m的有效簽名?，F(xiàn)代密碼學電子科技大學5.2RSA數(shù)字簽名精選RSA數(shù)字簽名方案存在以下缺陷：①任何人都可以偽造某簽名者對于隨機消息m的簽名s。其方法是先選取s，再用該簽名者的公鑰(e,n)計算。s就是該簽名者對消息m的簽名?，F(xiàn)代密碼學電子科技大學精選②如果敵手知道消息和的簽名分別是和，則敵手可以偽造的簽名，這是因為在RSA簽名方案中，存在以下性質(zhì)：精選③由于在RSA簽名方案中，要簽名的消息，所以每次只能對位長的消息進行簽名。然而，實際需要簽名的消息可能比n大，解決的辦法是先對消息進行分組，然后對每組消息分別進行簽名。這樣做的缺點是簽名長度變長，運算量增大。精選克服上述缺陷的方法之一是在對消息進行簽名前先對消息做Hash變換，然后對變換后的消息進行簽名。即簽名為：

驗證時，先計算h（m），再檢查等式：

是否成立?，F(xiàn)代密碼學電子科技大學精選5.3ElGamal數(shù)字簽名現(xiàn)代密碼學電子科技大學精選5.3ElGamal數(shù)字簽名算法1．參數(shù)與密鑰生成①選取大素數(shù)p,是一個本原元。p和g公開。②隨機選取整數(shù)x,1≤x≤p2，計算③公鑰為y，私鑰為x。現(xiàn)代密碼學電子科技大學精選2．簽名對于消息m，首先隨機選取一個整數(shù)k,1≤k≤p2，然后計算：

則m的簽名為(r,s)，其中h為Hash函數(shù)。5.3ElGamal數(shù)字簽名算法精選3．驗證對于消息簽名對(m,(r,s))，如果：

則(r,s)是m的有效簽名。5.3ElGamal數(shù)字簽名算法精選5.4DSS數(shù)字簽名標準現(xiàn)代密碼學電子科技大學精選5.4DSS數(shù)字簽名標準1．參數(shù)與密鑰生成①選取大素數(shù)p，滿足＜p＜，其中512≤L≤1024且L是64的倍數(shù)。顯然，p是L位長的素數(shù)，L從512到1024且是64的倍數(shù)。②選取大素數(shù)q，q是p1的一個素因子且，即q是160位的素數(shù)且是p1的素因子。現(xiàn)代密碼學電子科技大學精選1．參數(shù)與密鑰生成③選取一個生成元，其中h是一個整數(shù)，滿足1＜h＜p1并且。④隨機選取整數(shù)x，0＜x＜q，計算。⑤p、q和g是公開參數(shù)，y為公鑰，x為私鑰。5.4DSS數(shù)字簽名標準精選2．簽名

對于消息m，首先隨機選取一個整數(shù)k,0＜k＜q，然后計算：則m的簽名為(r,s)，其中h為Hash函數(shù)，DSS規(guī)定Hash函數(shù)為SHA-1?，F(xiàn)代密碼學電子科技大學5.4DSS數(shù)字簽名標準精選3．驗證對于消息簽名對(m,(r,s))，首先計算：然后驗證：如果等式成立，則(r,s)是m的有效簽名；否則簽名無效。精選DSS的框圖下圖所示，其中的4個函數(shù)分別為：現(xiàn)代密碼學電子科技大學精選5.5其他數(shù)字簽名

5.5.1基于離散對數(shù)問題的數(shù)字簽名現(xiàn)代密碼學電子科技大學精選1．離散對數(shù)簽名方案ElGamal簽名方案、DSA簽名方案、Schnorr簽名方案都可以歸結(jié)為離散對數(shù)簽名方案的特例?，F(xiàn)代密碼學電子科技大學精選1．離散對數(shù)簽名方案（1）參數(shù)與密鑰生成

p：大素數(shù)。q：p1或p1的大素因子。g：，且，其中表示g是從中隨機選取的，這里的。x：用戶A的私鑰，1＜x＜q。y：用戶A的公鑰，y

gx

modp。精選1．離散對數(shù)簽名方案（2）簽名對于消息m，A執(zhí)行以下步驟：①計算的m的Hash值h(m)。②隨機選擇整數(shù)k,1＜k＜q。③計算r

gk

modp。④從簽名方程：ak

(b+cx)mod

q中解出s，其中方程的系數(shù)a、b、c有多種選擇，表5-1給出了一部分可能的選擇。對消息m的簽名為(r,s)?，F(xiàn)代密碼學電子科技大學精選表5-1參數(shù)a、b、c可能的選擇1111注：表中?，F(xiàn)代密碼學電子科技大學精選1．離散對數(shù)簽名方案（3）驗證接收者在收到消息m和簽名(r,s)后，可以按照以下驗證方程檢查簽名的合法性：現(xiàn)代密碼學電子科技大學精選2．Schnorr簽名方案（1）參數(shù)與密鑰生成p：大素數(shù)且p≥2512

。q：大素數(shù)且q|（p1）,q≥2160

。g：，且gq

1modp。x：用戶A的私鑰，1＜x＜q。y：用戶A的公鑰，y

gx

modp。現(xiàn)代密碼學電子科技大學精選（2）簽名對于消息m，A執(zhí)行以下步驟：①隨機選擇整數(shù)k,1＜k＜q。②計算r

gk

modp。③計算e=h（r,m）。④計算s（xe+k）modq。對消息m的簽名為（e,s）。現(xiàn)代密碼學電子科技大學2．Schnorr簽名方案精選（3）驗證接收者在收到消息m和簽名（e,s）后，通過以下步驟來檢驗簽名的合法性：①計算。②按照以下方程進行驗證：Schnorr簽名的正確性可由下式證明：現(xiàn)代密碼學電子科技大學2．Schnorr簽名方案精選3．Nyberg-Rueppel簽名方案（1）參數(shù)與密鑰生成p：大素數(shù)。q：大素數(shù)且q|（p1）。g：，且gq

1modp。x：用戶A的私鑰，1＜x＜q。y：用戶A的公鑰，y

gx

modp

現(xiàn)代密碼學電子科技大學精選（2）簽名對于消息m，A執(zhí)行以下步驟：①計算，其中R是從消息空間到簽名空間的一個單一映射，并且容易求逆，稱為冗余函數(shù)。②隨機選擇整數(shù)k，1≤k≤q1。③計算r

g-k

modp。④計算。⑤計算s（xe+k）modq。對消息m的簽名為（e,s）。精選（3）驗證接收者在收到消息m和簽名（e,s）后，通過以下步驟來驗證簽名的合法性：①驗證是否有0＜e＜p成立，如果不成立，拒絕該簽名。②驗證是否有0≤s＜p成立，如果不成立，拒絕該簽名?，F(xiàn)代密碼學電子科技大學精選③計算和。④驗證是否有，如果，拒絕該簽名，這里MR

表示R的值域。⑤恢復消息。下面證明Nyberg-Rueppel簽名方案的正確性。因為所以現(xiàn)代密碼學電子科技大學精選5.5.2基于大整數(shù)分解的數(shù)字簽名方案1．Feige-Fiat-Shamir簽名方案（1）參數(shù)與密鑰生成n：n=pq，其中p和q是兩個保密的大素數(shù)。k：固定的正整數(shù)。：用戶A的私鑰，。：用戶A的公鑰，現(xiàn)代密碼學電子科技大學精選（2）簽名對于消息m，A執(zhí)行以下步驟：①隨機選擇整數(shù)r,1≤r≤n1。②計算u

rmodn。③計算e=（e,e,…,e）=h（m,u），e∈{0,1}。④計算。對消息m的簽名為（e,s）。現(xiàn)代密碼學電子科技大學精選（3）驗證接收者在收到消息m和簽名（e,s）后，通過以下步驟來檢驗簽名的合法性：①計算。②按照以下方程進行驗證：

Feige-Fiat-Shamir簽名的正確性可由下式證明：現(xiàn)代密碼學電子科技大學精選2．Guillou-Quisquater簽名方案

（1）參數(shù)與密鑰生成n：n=pq，其中p和q是兩個保密的大素數(shù)。k：k∈{1,2,,n1}且x：用戶A的私鑰，。y：用戶A的公鑰，且。現(xiàn)代密碼學電子科技大學精選（2）簽名

對于消息m，A執(zhí)行以下步驟：①隨機選擇整數(shù)。②計算u

rk

modn。③計算e=h（m,u）。④計算s=rxe

modn。對消息m的簽名為（e,s）?，F(xiàn)代密碼學電子科技大學精選（3）驗證

接收者在收到消息m和簽名（e,s）后，通過以下步驟來驗證簽名的合法性：①計算。②按照以下方程進行驗證：

Guillou-Quisquater簽名的正確性可由下式證明：現(xiàn)代密碼學電子科技大學精選群簽名具有以下特點：只有群體中的合法成員才能代表整個群體進行簽名。接收者可以用群公鑰驗證群簽名的合法性，但不知道該群簽名是由群體中的哪個成員所簽。在發(fā)生爭議時，群管理員（權(quán)威機構(gòu)）可以識別出實際的簽名者。現(xiàn)代密碼學電子科技大學5.5.3具有特殊用途的數(shù)字簽名

1．群簽名精選一個群簽名方案由以下幾個部分組成：（1）建立（setup）一個用以產(chǎn)生群公鑰和私鑰的多項式概率算法。（2）加入（join）一個用戶和群管理員之間的交互式協(xié)議。執(zhí)行該協(xié)議可以使用戶成為群成員，群管理員得到群成員的秘密的成員管理密鑰，并產(chǎn)生群成員的私鑰和成員證書。現(xiàn)代密碼學電子科技大學

1．群簽名精選（3）簽名（sign）一個概率算法，當輸入一個消息、一個群成員的私鑰和一個群公鑰后，輸出對該消息的簽名。（4）驗證（verify）給定一個消息的簽名和一個群公鑰后，判斷該簽名相對于該群公鑰是否有效。（5）打開（open）給定一個簽名、群公鑰和群私鑰的條件下確定簽名者的身份。

群簽名精選一個好的群簽名方案應(yīng)該滿足以下幾條性質(zhì)：①正確性（correctness）②不可偽造性（unforgeability）③匿名性（anonymity）④不可關(guān)聯(lián)性（unlinkability）⑤可跟蹤性（traceability）⑥可開脫性（exculpability）⑦抗聯(lián)合攻擊（coalition-resistance）現(xiàn)代密碼學電子科技大學電子科技大學

群簽名精選2．代理簽名一個代理簽名方案由以下幾個部分組成：系統(tǒng)建立選定代理簽名方案的系統(tǒng)參數(shù)，用戶的密鑰等。簽名權(quán)力的委托原始簽名者將自己的簽名權(quán)力委托給代理簽名者。代理簽名的產(chǎn)生代理簽名者代表原始簽名者產(chǎn)生代理簽名。代理簽名的驗證驗證人驗證代理簽名的有效性。現(xiàn)代密碼學電子科技大學精選根據(jù)簽名權(quán)力委托的方式不同，代理簽名可以分為以下幾類：（1）完全代理（fulldelegation）（2）部分代理（partialdelegation）（3）具有證書的代理（delegationbywarrant）（4）具有證書的部分代理（partialdelegationwithwarrant）現(xiàn)代密碼學電子科技大學2．代理簽名精選根據(jù)原始簽名者能否產(chǎn)生同代理簽名者一樣的簽名，代理簽名又可分為兩類：1）代理非保護（proxy-unprotected）原始簽名者能夠產(chǎn)生有效的代理簽名。2）代理保護（proxy-protected）原始簽名者不能夠產(chǎn)生有效的代理簽名。現(xiàn)代密碼學電子科技大學2．代理簽名精選一個強代理簽名方案應(yīng)滿足以下幾條性質(zhì)：①可區(qū)分性（distinguishability）②可驗證性（verifiability）③強不可偽造性（strongunforgeability）④強可識別性（strongidentifiability）⑤強不可否認性（strongundeniability）⑥