《數(shù)字簽名與認證協(xié)議.ppt》由會員分享，可在線閱讀，更多相關《數(shù)字簽名與認證協(xié)議.ppt（21頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、第十章 數(shù)字簽名與認證協(xié)議,1 EIGamal簽名方案 該方案是特別為簽名的目的而設計的。1985年提出，很大程度上為Diffe-Hellman密鑰交換算法的推廣和變形。這個方案的改進已被美國NIST（國家標準和技術(shù)研究所）采納作為數(shù)字簽名標準。 方案：P為素數(shù)，F(xiàn)P中的離散對數(shù)問題是難處理的。取本原元Fp*,消息集合M=Fp*，簽名集合A=Fp*Zp-1,定義K=（p,,a,)| = a(modp),值p,和是公開的，a是保密的。 對K=( p,,a,)和一個（秘密）隨機數(shù)k Zp-1*,對消息x,M進行簽名： SigK(x,k)=(,), 其中，=k(modp), =(x-
2、)k-1(modp-1) 對x, Fp*和Zp-1,驗證簽名定義為 Ver(x, ,)=真（true)x(modp) 對EIGamal簽名方案安全性的討論： 若Oscar在不知道a的情況下企圖偽造一個給定消息x的簽名： Sigoscar(x,k)=(,) (1)Oscar先選定一個，然后企圖找，這樣，他就必須解一個關于未知數(shù)的方程： x(modp) 這個方程是一個已知無可行解法的難處理問題！,(2)Oscar先選定一個 ，使其滿足： x(modp)，于是， -x(modp)，這樣，他就必須計算離散對數(shù) log(-x)=?,這自然是難處理的問題！ (3)若兩者, 都被 Oscar首先
3、選定,然后企圖解出一個隨機消息x,使得x(modp)，于是Oscar利用這種方式也不能偽造隨機消息的簽名。 (4) Oscar同時選擇, 和x來偽造簽名問題: 假設i和j是整數(shù),0<=I<=p-2,0<=j<=p-2,且(j,p-1)=1,先完成下列計算: ij(modp) -j-1(modp-1) x=-ij-1(modp-1) (其中j-1是用模p-1來計算的),可以證實(, )是一個消息x的有效簽名: 例子:假設p=467,=2和=132,它們?yōu)锽ob公開的簽名方案中的參數(shù)。Oscar利用這些參數(shù)偽造對一隨機信息x的簽名： 選擇i=99和j=179
4、，那么j-1(modp-1)=151，計算出下列的x,, :,那么（117，41）是消息331的一個有效簽名。驗證： 因此，這個偽造的簽名有效！ （5）其他類型的偽造簽名： Oscar依據(jù)Bob已簽名的消息來做偽簽名。假設(, ) 是一個消息x的有效簽名，那么Oscar可以用此來偽簽其它 消息： 設h,i,j為整數(shù),0<=h,i,j<=p-2且 ,計算,（其中 是模p-1算出） 然后可驗證出 因此 ， 為假消息 的一個有效簽名 討論兩個問題： （1）用EIGamal方案計算一個簽名時，使用的隨機數(shù)k為什么不能泄露？ （2）若Bob用相同的值來簽名不同的
5、兩份消息，Oscar能否攻破這個體制？,2 數(shù)字簽名標準,公布于1994年5月19日的聯(lián)邦記錄上，并于1994年12月1日采納為標準DSS。DSS為EIGamal簽名方案的改進。 DSS：p為512bit的素數(shù)，q為160比特的素數(shù)，且q|p-1, Fp*,且為模p的q次單位根。消息集合P=Fp*，簽名集合A=FqFq,定義K=（p,,a,)| = a(modp),值p,q,和是公開的，a是保密的。 取xP,對K=( p,q,,a,)和一個（秘密）隨機數(shù)k (1<=k<=q-1) ,定義 SigK(x,k)=(,), 其中，=k(modp)（modq), =(x+ )k-1(mod
6、q) 對xFp*和,Fq來說,按下述計算來驗證簽名的真?zhèn)危?注：1*.DSS的使用涉及到Smart卡的使用,要求短的簽名。DSS以一個巧妙的方法修改了EIGamal方案，使得簽名160bits消息產(chǎn)生一個320bit的簽名，但是計算使用了512比特的模p. 2*.要求 在整個簽名算法中，如果計算了一個值 ,程序自動拒絕，并且產(chǎn)生一個新的隨機值計算新的簽名，事實上， 的發(fā)生概率大約為2-160.,3*. DSS是一個產(chǎn)生簽名比驗證簽名快得多的方案，驗證簽名太慢！ 4*. Smart卡的應用??！Smart卡有有限的處理能力，但是能與計算機進行通信。人們企圖設計一種讓
7、Smart卡僅作小量運算的簽名方案。該方案必須完成簽名、驗證簽名兩部分，而且方便安全。 用DSS簽名的例子： 假設取q=101，p=78*9+1=7879，3為F7879的一個本原 元，所以能取=378（mod7879)=170為模p的q次單位根。 假設a=75，那么a(mod7879)=4567.現(xiàn)在, 假設Bob想簽 名一個消息x=1234，且他選擇了隨機值k=50，可算得 k-1(mod101)=99,簽名算出: =(17050(mod7879)(mod101) =2518(mod101)=94,=(1234+75*94)99(mod101)=97 簽名為（1234，94，97）。
8、 驗證： -1=97-1（mod101)=25 , e1=1234*25(mod101)=45,e2=94*25(mod101)=27 (17045*456727(mod7879))(mod101)=2518(mod101)=94 因此，該簽名是有效的。,3 一次簽名,任何單向函數(shù)都可用來構(gòu)造一次簽名方案。該簽名對一個消息來說，唯一對應著一個確定的簽名。這樣的簽名可驗證任意多次。 Lamport方案： 設k為一個正整數(shù)，P=0,1K,設f:YZ是一個單向函數(shù)，簽名集合A=YK，對于1<=i<=k, j=0,1來說，yijY可隨機地選擇。選后，可算得 Zij=f(yij)
9、1<=i<=k,j=0,1 密鑰K由2k個y值和2k個Z值組成，y值保密而Z值公開.消息x=x1x2.xk(kbit串）。對于K=（yij,Zij|1<=i<=k,j=0,1),定義 其中，yixi=ai,f(ai)=Zixi 驗證： 注：1*. 待簽名的消息為一個二進制 元組,每一個都單獨簽名.這個特征決定了 “一次簽名” 2*.驗證是簡單的檢查:簽名結(jié)果的每一個元素是相應公開鑰元素的愿象. 例子:取單向函數(shù)f(x)=x(modp),設p=7879(素數(shù)),3為F7879的本原元,定義f(x)=3x(mod7879) 假設Bob想簽名3比特消息,他選擇了6個(秘密的)隨機數(shù):,y10=5
10、831,y11=735,y20=803,y21=2467,y30=4285,y31=6449 在f的作用下計算y的像: z10=2009,z11=3810,z20=4672,z21=4721,z30=268,z31=5732 將這些Z值公開?，F(xiàn)在Bob打算簽名消息x=(1,1,0),那么對的簽名為(y11,y21,y30)=(735,2467,4285). 驗證簽名: 3735(mod7879)=3810 32467(mod7879)=4721 34285(mod7879)=268 因此,該簽名有效。 注：該方案，僅能用于簽一個消息！一次，無法偽造。,4 不可否認的簽名,（Chau
11、m和Van Antwerprn 1989年提出） 該簽名的特征是：驗證簽名者必須與簽名者合作。驗證簽名是通過詢問------應答協(xié)議來完成。這個協(xié)議可防止簽名者Bob否認他以前做的簽名。 一個不可否認的簽名方案有三個部分組成： 簽名算法、驗證協(xié)議、否認協(xié)議 設p=2q+1是一個素數(shù)，它滿足q為素數(shù)，且Fp中的對數(shù)問題是難解的。 ,且階為q,取1,（事實上G由模p的二次剩余組成） 設P=A=G，且定義K=（p,,a,)| = a(modp),值p,和是公開的，a是保密的。,對K=（p,,a,)和消息xG,定義y=SigK(x)=xa(modp) 易見y G 。按如下協(xié)議完成驗證：
12、（1）.Alice 隨機選擇 （2）Alice計算 , 且將C送給Bob. （3）Bob計算 , 且d將送給Alice. （4）Alice接受y作為一個有效簽名,當且僅當 對上述這個簽名方案，要證明以下兩點： 1）Alice將回接受按如上方案的有效簽名 2）Bob幾乎不可否認經(jīng)Alice 驗證過的自己的簽名。 證明(1)：(alice接受Bob的簽名)。下面計算的所有指數(shù)都已做到模q約簡.,知 代入上式得 剛好與協(xié)議（4）相符，故Alice接受Bob的簽名。對于（2） Bob幾乎不可否認經(jīng)Alice驗證過的自己的簽名。相當于證 明下述定 理。 定理1：若
13、 ,那么Alice以概率1/(q-1)接受y作 為x的有效簽名. 證明: Bob對x做了簽名y(=xa)給Alice后。Bob接受了Alice的 一個詢問 ,這個詢問對應于q-1個有序?qū)?(e1,e2)。( 原因是 一旦固定，e2=f(e1)。然而， Bob不知Alice選擇了哪一對(e1,e2)來構(gòu)造出C。,如果 ,那么Bob能做的任何可能回答 ， 剛好與q-1個可能的有序?qū)?e1,e2)中的一個相對應。 由 G=, 所以對C,d,x,y來說，可設 C= i,d= j,x= k,y= l,i,j,k,l ,
14、 考慮同余式： 寫出關于 的指數(shù)表示： 等價于下述方程組：,既然假設 而 y=2l，xa=(k)a= ak,所以lak, 相當于說上述方程的系數(shù)行列式： 知該方程組僅有唯一一組解。 即對每一個dG, 對于q-1個可能的有序?qū)χ校╡1,e2），剛好 有一個是正確的回答，Bob給Alice的一個回答d，將被驗證 的概率剛好為1/（q-1）。定理得證！,下面討論否認協(xié)議： 目的：（1）Bob能使Alice相信一個無效的簽名是偽造的. （2）Bob簽名有效，而導致Alice判決錯誤的概率為小概率事件。 否認協(xié)議：(y?=xa)暫視為對的簽名 1）Alice 隨機選取 2）Alice計算
15、 且將送給Bob, 3）Bob計算 ,且將他回送Alice 4）Alice驗證 5）Alice再隨機選取 6）Alice計算 ，且將他送給Bob 7）Bob計算 ，且將他回送給Alice 8）Alice驗證,9)Alice推出 y是偽造的 定理2：如果 yxa(modp) ,且Alice和Bob都遵守否認協(xié)議，那么 證明：注意, ， 而 又 ，從而有 進一步有,類似地，按如上方式推出 證畢。 注：我們不能假設遵守了否認協(xié)議，他可以想方設法構(gòu)造d,D,來達到否認自己簽過名的目的。然而，只要Alice嚴格遵守協(xié)議，Bob是無法否認的?？勺C。 定理3，假設yxa(modp) 且Alice遵守否認協(xié)議，如果 那么 成立的概率為1-1/(q-1)。,
數(shù)字簽名與認證協(xié)議.ppt
