數(shù)字簽名與認(rèn)證協(xié)議

數(shù)字簽名與認(rèn)證協(xié)議第1頁，課件共21頁，創(chuàng)作于2023年2月M進(jìn)行簽名：SigK(x,k)=(,),其中，=k(modp),=(x-)k-1(modp-1)對(duì)x,Fp*和Zp-1,驗(yàn)證簽名定義為Ver(x,,)=真（true)x(modp)對(duì)EIGamal簽名方案安全性的討論：

若Oscar在不知道a的情況下企圖偽造一個(gè)給定消息x的簽名：Sigoscar(x,k)=(,)(1)Oscar先選定一個(gè)，然后企圖找，這樣，他就必須解一個(gè)關(guān)于未知數(shù)的方程：

x(modp)這個(gè)方程是一個(gè)已知無可行解法的難處理問題！第2頁，課件共21頁，創(chuàng)作于2023年2月(2)Oscar先選定一個(gè)，使其滿足：x(modp)，于是，

-x(modp)，這樣，他就必須計(jì)算離散對(duì)數(shù)log(-x)=?,這自然是難處理的問題！(3)若兩者,都被

Oscar首先選定,然后企圖解出一個(gè)隨機(jī)消息x,使得x(modp)，于是Oscar利用這種方式也不能偽造隨機(jī)消息的簽名。(4)Oscar同時(shí)選擇,和x來偽造簽名問題:假設(shè)i和j是整數(shù),0<=I<=p-2,0<=j<=p-2,且(j,p-1)=1,先完成下列計(jì)算:ij(modp)-j-1(modp-1)x=-ij-1(modp-1)(其中j-1是用模p-1來計(jì)算的)第3頁，課件共21頁，創(chuàng)作于2023年2月可以證實(shí)(,)是一個(gè)消息x的有效簽名:

例子:假設(shè)p=467,=2和=132,它們?yōu)锽ob公開的簽名方案中的參數(shù)。Oscar利用這些參數(shù)偽造對(duì)一隨機(jī)信息x的簽名：選擇i=99和j=179，那么j-1(modp-1)=151，計(jì)算出下列的x,,:

第4頁，課件共21頁，創(chuàng)作于2023年2月那么（117，41）是消息331的一個(gè)有效簽名。驗(yàn)證：因此，這個(gè)偽造的簽名有效！（5）其他類型的偽造簽名：Oscar依據(jù)Bob已簽名的消息來做偽簽名。假設(shè)(,)是一個(gè)消息x的有效簽名，那么Oscar可以用此來偽簽其它消息：設(shè)h,i,j為整數(shù),0<=h,i,j<=p-2且,計(jì)算第5頁，課件共21頁，創(chuàng)作于2023年2月（其中是模p-1算出）

然后可驗(yàn)證出因此，為假消息的一個(gè)有效簽名討論兩個(gè)問題：（1）用EIGamal方案計(jì)算一個(gè)簽名時(shí)，使用的隨機(jī)數(shù)k為什么不能泄露？（2）若Bob用相同的值來簽名不同的兩份消息，Oscar能否攻破這個(gè)體制？第6頁，課件共21頁，創(chuàng)作于2023年2月2數(shù)字簽名標(biāo)準(zhǔn)公布于1994年5月19日的聯(lián)邦記錄上，并于1994年12月1日采納為標(biāo)準(zhǔn)DSS。DSS為EIGamal簽名方案的改進(jìn)。DSS：p為512bit的素?cái)?shù)，q為160比特的素?cái)?shù)，且q|p-1,Fp*,且為模p的q次單位根。消息集合P=Fp*，簽名集合A=FqFq,定義K={（p,,a,)|=a(modp)},值p,q,和是公開的，a是保密的。取xP,對(duì)K=(p,q,,a,)和一個(gè)（秘密）隨機(jī)數(shù)k(1<=k<=q-1),定義SigK(x,k)=(,),其中，=k(modp)（modq),=(x+)k-1(modq)對(duì)xFp*和,Fq來說,按下述計(jì)算來驗(yàn)證簽名的真?zhèn)危旱?頁，課件共21頁，創(chuàng)作于2023年2月

注：1*.DSS的使用涉及到Smart卡的使用,要求短的簽名。DSS以一個(gè)巧妙的方法修改了EIGamal方案，使得簽名160bits消息產(chǎn)生一個(gè)320bit的簽名，但是計(jì)算使用了512比特的模p.2*.要求在整個(gè)簽名算法中，如果計(jì)算了一個(gè)值,程序自動(dòng)拒絕，并且產(chǎn)生一個(gè)新的隨機(jī)值計(jì)算新的簽名，事實(shí)上，的發(fā)生概率大約為2-160.

第8頁，課件共21頁，創(chuàng)作于2023年2月3*.DSS是一個(gè)產(chǎn)生簽名比驗(yàn)證簽名快得多的方案，驗(yàn)證簽名太慢！4*.Smart卡的應(yīng)用?。mart卡有有限的處理能力，但是能與計(jì)算機(jī)進(jìn)行通信。人們企圖設(shè)計(jì)一種讓Smart卡僅作小量運(yùn)算的簽名方案。該方案必須完成簽名、驗(yàn)證簽名兩部分，而且方便安全。用DSS簽名的例子：

假設(shè)取q=101，p=78*9+1=7879，3為F7879的一個(gè)本原元，所以能取=378（mod7879)=170為模p的q次單位根。假設(shè)a=75，那么a(mod7879)=4567.現(xiàn)在,假設(shè)Bob想簽名一個(gè)消息x=1234，且他選擇了隨機(jī)值k=50，可算得k-1(mod101)=99,簽名算出:=(17050(mod7879)(mod101)=2518(mod101)=94第9頁，課件共21頁，創(chuàng)作于2023年2月=(1234+75*94)99(mod101)=97簽名為（1234，94，97）。驗(yàn)證：-1=97-1（mod101)=25,e1=1234*25(mod101)=45,e2=94*25(mod101)=27(17045*456727(mod7879))(mod101)=2518(mod101)=94因此，該簽名是有效的。第10頁，課件共21頁，創(chuàng)作于2023年2月3一次簽名

任何單向函數(shù)都可用來構(gòu)造一次簽名方案。該簽名對(duì)一個(gè)消息來說，唯一對(duì)應(yīng)著一個(gè)確定的簽名。這樣的簽名可驗(yàn)證任意多次。Lamport方案：設(shè)k為一個(gè)正整數(shù)，P={0,1}K,設(shè)f:YZ是一個(gè)單向函數(shù)，簽名集合A=YK，對(duì)于1<=i<=k,j=0,1來說，yijY可隨機(jī)地選擇。選后，可算得Zij=f(yij)1<=i<=k,j=0,1密鑰K由2k個(gè)y值和2k個(gè)Z值組成，y值保密而Z值公開.消息x=x1x2….xk(kbit串）。對(duì)于K=（yij,Zij|1<=i<=k,j=0,1)第11頁，課件共21頁，創(chuàng)作于2023年2月定義其中，yixi=ai,f(ai)=Zixi驗(yàn)證：注：1*.待簽名的消息為一個(gè)二進(jìn)制元組,每一個(gè)都單獨(dú)簽名.這個(gè)特征決定了“一次簽名”

2*.驗(yàn)證是簡單的檢查:簽名結(jié)果的每一個(gè)元素是相應(yīng)公開鑰元素的愿象.例子:取單向函數(shù)f(x)=x(modp),設(shè)p=7879(素?cái)?shù)),3為F7879的本原元,定義f(x)=3x(mod7879)假設(shè)Bob想簽名3比特消息,他選擇了6個(gè)(秘密的)隨機(jī)數(shù):第12頁，課件共21頁，創(chuàng)作于2023年2月y10=5831,y11=735,y20=803,y21=2467,y30=4285,y31=6449在f的作用下計(jì)算y的像:z10=2009,z11=3810,z20=4672,z21=4721,z30=268,z31=5732將這些Z值公開?，F(xiàn)在Bob打算簽名消息x=(1,1,0),那么對(duì)的簽名為(y11,y21,y30)=(735,2467,4285).驗(yàn)證簽名:3735(mod7879)=381032467(mod7879)=472134285(mod7879)=268因此,該簽名有效。注：該方案，僅能用于簽一個(gè)消息！一次，無法偽造。第13頁，課件共21頁，創(chuàng)作于2023年2月4不可否認(rèn)的簽名（Chaum和VanAntwerprn1989年提出）該簽名的特征是：驗(yàn)證簽名者必須與簽名者合作。驗(yàn)證簽名是通過詢問------應(yīng)答協(xié)議來完成。這個(gè)協(xié)議可防止簽名者Bob否認(rèn)他以前做的簽名。一個(gè)不可否認(rèn)的簽名方案有三個(gè)部分組成：簽名算法、驗(yàn)證協(xié)議、否認(rèn)協(xié)議設(shè)p=2q+1是一個(gè)素?cái)?shù)，它滿足q為素?cái)?shù)，且Fp中的對(duì)數(shù)問題是難解的。,且階為q,取1<=a<=q-1,定義,G表示階為q的FP*的子群。易見G=<>,（事實(shí)上G由模p的二次剩余組成）設(shè)P=A=G，且定義K={（p,,a,)|=a(modp)},值p,和是公開的，a是保密的。第14頁，課件共21頁，創(chuàng)作于2023年2月對(duì)K=（p,,a,)和消息xG,定義y=SigK(x)=xa(modp)易見yG。按如下協(xié)議完成驗(yàn)證：（1）.Alice隨機(jī)選擇（2）Alice計(jì)算,且將C送給Bob.（3）Bob計(jì)算,且d將送給Alice.（4）Alice接受y作為一個(gè)有效簽名,當(dāng)且僅當(dāng)

對(duì)上述這個(gè)簽名方案，要證明以下兩點(diǎn)：1）Alice將回接受按如上方案的有效簽名2）Bob幾乎不可否認(rèn)經(jīng)Alice驗(yàn)證過的自己的簽名。證明(1)：(alice接受Bob的簽名)。下面計(jì)算的所有指數(shù)都已做到模q約簡.第15頁，課件共21頁，創(chuàng)作于2023年2月知代入上式得剛好與協(xié)議（4）相符，故Alice接受Bob的簽名。對(duì)于（2）Bob幾乎不可否認(rèn)經(jīng)Alice驗(yàn)證過的自己的簽名。相當(dāng)于證明下述定理。定理1：若,那么Alice以概率1/(q-1)接受y作為x的有效簽名.證明:Bob對(duì)x做了簽名y(=xa)給Alice后。Bob接受了Alice的一個(gè)詢問,這個(gè)詢問對(duì)應(yīng)于q-1個(gè)有序?qū)?e1,e2)。(原因是一旦固定，e2=f(e1)。然而，Bob不知Alice選擇了哪一對(duì)(e1,e2)來構(gòu)造出C。

第16頁，課件共21頁，創(chuàng)作于2023年2月如果,那么Bob能做的任何可能回答，剛好與q-1個(gè)可能的有序?qū)?e1,e2)中的一個(gè)相對(duì)應(yīng)。由G=<>,所以對(duì)C,d,x,y來說，可設(shè)C=

i,d=j,x=k,y=l,i,j,k,l,考慮同余式：寫出關(guān)于的指數(shù)表示：等價(jià)于下述方程組：

第17頁，課件共21頁，創(chuàng)作于2023年2月既然假設(shè)而y=2l，xa=(k)a=

ak,所以lak,相當(dāng)于說上述方程的系數(shù)行列式：知該方程組僅有唯一一組解。即對(duì)每一個(gè)dG,對(duì)于q-1個(gè)可能的有序?qū)χ校╡1,e2），剛好有一個(gè)是正確的回答，Bob給Alice的一個(gè)回答d，將被驗(yàn)證的概率剛好為1/（q-1）。定理得證！第18頁，課件共21頁，創(chuàng)作于2023年2月下面討論否認(rèn)協(xié)議：目的：（1）Bob能使Alice相信一個(gè)無效的簽名是偽造的.（2）Bob簽名有效，而導(dǎo)致Alice判決錯(cuò)誤的概率為小概率事件。否認(rèn)協(xié)議：(y?=xa)暫視為對(duì)的簽名1）Alice隨機(jī)選取2）Alice計(jì)算且將送給Bo