新版第5章-數(shù)字簽名課件

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

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

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

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

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

驗(yàn)證時(shí)，先計(jì)算h（m），再檢查等式：

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

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

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

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

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

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

gx

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

gk

modp。④從簽名方程：ak

(b+cx)mod

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

。q：大素?cái)?shù)且q|（p1）,q≥2160

。g：，且gq

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

gx

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

gk

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

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

gx

modp

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

g-k

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

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

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

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

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

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

rk

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

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

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

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

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

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

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

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