1、2020/9/23,1,第7章 數(shù)字簽字和密碼協(xié)議,郝艷華 漳州師范學院計算機科學與工程系,2020/9/23,2,7.1 數(shù)字簽字的基本概念 7.2 數(shù)字簽字標準 7.3 其他簽字方案 7.4 認證協(xié)議 7.5 身份證明技術 7.6 其他密碼協(xié)議,2020/9/23,3,數(shù)字簽字由公鑰密碼發(fā)展而來，它在網(wǎng)絡安全，包括身份認證、數(shù)據(jù)完整性、不可否認性以及匿名性等方面有著重要應用。 本章首先介紹數(shù)字簽字的基本概念和一些常用的數(shù)字簽字算法，然后介紹身份認證協(xié)議、身份證明技術以及其他一些常用的密碼協(xié)議。,2020/9/23,4,7.1 數(shù)字簽字的基本概念,7.1.1 數(shù)字簽字應滿足的要求 上一章介紹

2、的消息認證其作用是保護通信雙方以防第三方的攻擊，然而卻不能保護通信雙方中的一方防止另一方的欺騙或偽造。 通信雙方之間也可能有多種形式的欺騙，例如通信雙方A和B（設A為發(fā)方，B為收方）使用圖6.1所示的消息認證碼的基本方式通信，則可能發(fā)生以下欺騙：,2020/9/23,5,2020/9/23,6, B偽造一個消息并使用與A共享的密鑰產生該消息的認證碼，然后聲稱該消息來自于A。 由于B有可能偽造A發(fā)來的消息，所以A就可以對自己發(fā)過的消息予以否認。 這兩種欺騙在實際的網(wǎng)絡安全應用中都有可能發(fā)生，例如在電子資金傳輸中，收方增加收到的資金數(shù)，并聲稱這一數(shù)目來自發(fā)方。又如用戶通過電子郵件向其證券經紀人發(fā)送

3、對某筆業(yè)務的指令，以后這筆業(yè)務賠錢了，用戶就可否認曾發(fā)送過相應的指令。,2020/9/23,7,因此在收發(fā)雙方未建立起完全的信任關系且存在利害沖突的情況下，單純的消息認證就顯得不夠。數(shù)字簽字技術則可有效解決這一問題。類似于手書簽字，數(shù)字簽字應具有以下性質： 能夠驗證簽字產生者的身份，以及產生簽字的日期和時間。 能用于證實被簽消息的內容。 數(shù)字簽字可由第三方驗證，從而能夠解決通信雙方的爭議。,2020/9/23,8,由此可見，數(shù)字簽字具有認證功能。為實現(xiàn)上述3條性質，數(shù)字簽字應滿足以下要求： 簽字的產生必須使用發(fā)方獨有的一些信息以防偽造和否認。 簽字的產生應較為容易。 簽字的識別和驗證應較為容易

4、。 對已知的數(shù)字簽字構造一新的消息或對已知的消息構造一假冒的數(shù)字簽字在計算上都是不可行的。,2020/9/23,9,7.1.2 數(shù)字簽字的產生方式,數(shù)字簽字的產生可用加密算法或特定的簽字算法。 1. 由加密算法產生數(shù)字簽字 利用加密算法產生數(shù)字簽字是指將消息或消息的摘要加密后的密文作為對該消息的數(shù)字簽字，其用法又根據(jù)是單鑰加密還是公鑰加密而有所不同。,2020/9/23,10,(1) 單鑰加密 發(fā)送方A根據(jù)單鑰加密算法以與接收方B共享的密鑰K對消息M加密后的密文作為對M的數(shù)字簽字發(fā)往B。該系統(tǒng)能向B保證所收到的消息的確來自A，因為只有A知道密鑰K。再者B恢復出M后，可相信M未被篡改，因為敵手不

5、知道K就不知如何通過修改密文而修改明文。具體來說，就是B執(zhí)行解密運算Y=DK(X)，如果X是合法消息M加密后的密文，則B得到的Y就是明文消息M，否則Y將是無意義的比特序列。,2020/9/23,11,圖7.1 消息加密產生數(shù)字簽字的基本方式,2020/9/23,12,(2) 公鑰加密 發(fā)送方A使用自己的秘密鑰SKA對消息M加密后的密文作為對M的數(shù)字簽字，B使用A的公開鑰PKA對消息解密，由于只有A才擁有加密密鑰SKA，因此可使B相信自己收到的消息的確來自A。然而由于任何人都可使用A的公開鑰解密密文，所以這種方案不提供保密性。為提供保密性，A可用B的公開鑰再一次加密,2020/9/23,13,下

6、面以RSA簽字體制為例說明數(shù)字簽字的產生過程。 體制參數(shù)。 選兩個保密的大素數(shù)p和q，計算n=pq，(n)=(p-1)(q-1)；選一整數(shù)e，滿足1e(n)，且gcd(n),e)=1；計算d，滿足de1 mod (n)；以e,n為公開鑰,d,n為秘密鑰。 簽字過程。 設消息為M，對其簽字為SMd mod n,2020/9/23,14, 驗證過程。 接收方在收到消息M和簽字S后，驗證 是否成立，若成立，則發(fā)送方的簽字有效。 實際應用時，數(shù)字簽字是對消息摘要加密產生，而不是直接對消息加密產生，如圖6.3(a)圖6.3(d)所示。,2020/9/23,15,2020/9/23,16,由加密算法產生數(shù)

7、字簽字又分為 外部保密方式 內部保密方式 外部保密方式是指數(shù)字簽字是直接對需要簽字的消息生成而不是對已加密的消息生成，否則稱為內部保密方式。 外部保密方式便于解決爭議，因為第3方在處理爭議時，需得到明文消息及其簽字。但如果采用內部保密方式，第3方必須得到消息的解密密鑰后才能得到明文消息。 如果采用外部保密方式，接收方就可將明文消息及其數(shù)字簽字存儲下來以備以后萬一出現(xiàn)爭議時使用。,2020/9/23,17,2. 由簽字算法產生數(shù)字簽字 簽字算法的輸入是明文消息M和密鑰x，輸出是對M的數(shù)字簽字，表示為S=Sigx(M)。相應于簽字算法，有一驗證算法，表示為Verx(S,M)，其取值為 算法的安全性

8、在于從M和S難以推出密鑰x或偽造一個消息M使M和S可被驗證為真。,2020/9/23,18,7.1.3 數(shù)字簽字的執(zhí)行方式,數(shù)字簽字的執(zhí)行方式有兩類： 直接方式 具有仲裁的方式。 1. 直接方式 直接方式是指數(shù)字簽字的執(zhí)行過程只有通信雙方參與，并假定雙方有共享的秘密鑰或接收一方知道發(fā)方的公開鑰。,2020/9/23,19,直接方式的數(shù)字簽字有一公共弱點，即方案的有效性取決于發(fā)方秘密鑰的安全性。 如果發(fā)方想對已發(fā)出的消息予以否認，就可聲稱自己的秘密鑰已丟失或被竊，因此自己的簽字是他人偽造的。 可采取某些行政手段，雖然不能完全避免但可在某種程度上減弱這種威脅。例如，要求每一被簽字的消息都包含有一個

9、時戳（日期和時間）并要求密鑰丟失后立即向管理機構報告。 這種方式的數(shù)字簽字還存在發(fā)方的秘密鑰真的被偷的危險，例如敵手在時刻T偷得發(fā)方的秘密鑰，然后可偽造一消息，用偷得的秘密鑰為其簽字并加上T以前的時刻作為時戳。,2020/9/23,20,2. 具有仲裁方式的數(shù)字簽字 上述直接方式的數(shù)字簽字所具有的缺陷都可通過使用仲裁者得以解決。 和直接方式的數(shù)字簽字一樣，具有仲裁方式的數(shù)字簽字也有很多實現(xiàn)方案，這些方案都按以下方式運行： 發(fā)方X對發(fā)往收方Y的消息簽字后，將消息及其簽字先發(fā)給仲裁者A，A對消息及其簽字驗證完后，再連同一個表示已通過驗證的指令一起發(fā)往收方Y。此時由于A的存在，X無法對自己發(fā)出的消息

10、予以否認。在這種方式中，仲裁者起著重要的作用并應取得所有用戶的信任。,2020/9/23,21,以下是具有仲裁方式數(shù)字簽字的幾個實例，其中 X表示發(fā)方 Y表示收方 A是仲裁者 M是消息 XY：M 表示X給Y發(fā)送一消息M。,2020/9/23,22,例7.1 簽字過程如下： XA：MEKXAIDXH(M)。 AY：EKAYIDXMEKXAIDXH(M)T。 其中 E是單鑰加密算法 KXA和KAY分別是X與A共享的密鑰和A與Y共享的密鑰 H(M)是M的雜湊值 T是時戳 IDX是X的身份。,2020/9/23,23,在中，X以EKXAIDXH(M)作為自己對M的簽字，將M及簽字發(fā)往A。 在中A將從X

11、收到的內容和IDX、T一起加密后發(fā)往Y，其中的T用于向Y表示所發(fā)的消息不是舊消息的重放。Y對收到的內容解密后,將解密結果存儲起來以備出現(xiàn)爭議時使用。 如果出現(xiàn)爭議，Y可聲稱自己收到的M的確來自X，并將 EKAYIDXMEKXAIDXH(M) 發(fā)給A，由A仲裁，A由KAY解密后，再用KXA對EKXAIDXH(M)解密，并對H(M)加以驗證，從而驗證了X的簽字。,2020/9/23,24,以上過程中，由于Y不知KXA，因此不能直接檢查X的簽字，但Y認為消息來自于A因而是可信的。所以在整個過程中，A必須取得X和Y的高度信任： X相信A不會泄露KXA，并且不會偽造X的簽字; Y相信A只有在對 EKAY

12、IDXMEKXAIDXH(M) 中的雜湊值及X的簽字驗證無誤后才將之發(fā)給Y; X，Y都相信A可公正地解決爭議。 如果A已取得各方的信任，則X就能相信沒有人能偽造自己的簽字，Y就可相信X不能對自己的簽字予以否認。,2020/9/23,25,本例中消息M是以明文形式發(fā)送的，因此未提供保密性，下面兩個例子可提供保密性。 例7.2 簽字過程如下： XA: IDXEKXYMEKXAIDXH(EKXYM)。 AY: EKAYIDXEKXYMEKXAIDXH(EKXYM)T。 其中KXY是X，Y共享的密鑰，其他符號與例7.1相同。X以EKXAIDXH(EKXYM)作為對M的簽字，與由KXY加密的消息M一起發(fā)

13、給A。A對EKXAIDXH(EKXYM)解密后通過驗證雜湊值以驗證X的簽字，但始終未能讀取明文M。A驗證完X的簽字后，對X發(fā)來的消息加一時戳，再用KAY加密后發(fā)往Y。解決爭議的方法與例7.1一樣。,2020/9/23,26,本例雖然提供了保密性，但還存在與上例相同的一個問題，即仲裁者可和發(fā)方共謀以否認發(fā)方曾發(fā)過的消息，也可和收方共謀以偽造發(fā)方的簽字。這一問題可通過下例所示的采用公鑰加密技術的方法得以解決。,2020/9/23,27,例7.3 簽字過程如下： XA：IDXESKXIDXEPKYESKXM。 AY：ESKAIDXEPKYESKXMT。 其中SKA和SKX分別是A和X的秘密鑰，PKY

14、是Y的公開鑰，其他符號與前兩例相同。 第步中，X用自己的秘密鑰SKX和Y的公開鑰PKY對消息加密后作為對M的簽字，以這種方式使得任何第3方（包括A）都不能得到M的明文消息。A收到X發(fā)來的內容后，用X的公開鑰可對ESKXIDXEPKYESKXM解密，并將解密得到的IDX與收到的IDX加以比較，從而可確信這一消息是來自于X的（因只有X有SKX）。 第步，A將X的身份IDX和X對M的簽字加上一時戳后，再用自己的秘密鑰加密發(fā)往Y。,2020/9/23,28,與前兩種方案相比，第3種方案有很多優(yōu)點。 首先，在協(xié)議執(zhí)行以前，各方都不必有共享的信息，從而可防止共謀。 第二，只要仲裁者的秘密鑰不被泄露，任何人

15、包括發(fā)方就不能發(fā)送重放的消息。 最后，對任何第三方（包括A）來說，X發(fā)往Y的消息都是保密的。,2020/9/23,29,7.2 數(shù)字簽名標準,數(shù)字簽字標準DSS(Digital Signature Standard)是由美國NIST公布的聯(lián)邦信息處理標準FIPS PUB 186，其中采用了上一章介紹的SHA和一新的簽字技術，稱為DSA(Digital Signature Algorithm)。 DSS最初于1991年公布，在考慮了公眾對其安全性的反饋意見后，于1993年公布了其修改版。,2020/9/23,30,7.2.1 DSS的基本方式,首先將DSS與RSA的簽字方式做一比較。RSA算法既

16、能用于加密和簽字，又能用于密鑰交換。與此不同，DSS使用的算法只能提供數(shù)字簽字功能。 采用RSA簽字時，將消息輸入到一個雜湊函數(shù)以產生一個固定長度的安全雜湊值，再用發(fā)方的秘密鑰加密雜湊值就形成了對消息的簽字。消息及其簽字被一起發(fā)給收方，收方得到消息后再產生出消息的雜湊值，且使用發(fā)方的公開鑰對收到的簽字解密。這樣收方就得了兩個雜湊值，如果兩個雜湊值是一樣的，則認為收到的簽字是有效的。,2020/9/23,31,DSS簽字也利用一雜湊函數(shù)產生消息的一個雜湊值，雜湊值連同一隨機數(shù)k一起作為簽字函數(shù)的輸入，簽字函數(shù)還需使用發(fā)送方的秘密鑰SKA和供所有用戶使用的一族參數(shù)，稱這一族參數(shù)為全局公開鑰PKG。

17、簽字函數(shù)的兩個輸出s和r就構成了消息的簽字(s，r)。 接收方收到消息后再產生出消息的雜湊值，將雜湊值與收到的簽字一起輸入驗證函數(shù)，驗證函數(shù)還需輸入全局公開鑰PKG和發(fā)送方的公開鑰PKA。驗證函數(shù)的輸出如果與收到的簽字成分r相等，則驗證了簽字是有效的。,2020/9/23,32,圖7.2 RSA簽字與DSS簽字的不同方式,2020/9/23,33,7.2.2 數(shù)字簽字算法DSA,DSA是在ElGamal和Schnorr兩個簽字方案的基礎上設計的，其安全性基于求離散對數(shù)的困難性。 算法描述如下： (1) 全局公開鑰 p：滿足2L-11的任一整數(shù)。,2020/9/23,34,(2) 用戶秘密鑰x

18、x是滿足0xq的隨機數(shù)或偽隨機數(shù)。 (3) 用戶的公開鑰y ygx mod p。 (4) 用戶為待簽消息選取的秘密數(shù)k k是滿足0kq的隨機數(shù)或偽隨機數(shù)。 (5) 簽字過程 用戶對消息M的簽字為(r, s)， 其中r(gk mod p) mod q,sk-1(H(M)+xr) mod q，H(M)是由SHA求出的雜湊值。,2020/9/23,35,(6) 驗證過程 設接收方收到的消息為M，簽字為(r,s)。計算 w(s)-1 mod q,u1H(M)w mod q u2r w mod q,v(gu1yu2) mod p mod q 檢查 ，若相等，則認為簽字有效。這是因為若(M,r,s)=(M

19、,r,s)，則,2020/9/23,36,圖7.3 DSA的框圖,2020/9/23,37,其中的4個函數(shù)分別為 sf1H(M),k,x,r,qk-1(H(M)+xr) mod q r =f2(k,p,q,g)(gk mod p) mod q w =f3(s,q)(s)-1 mod q v =f4(y,q,g,H(M),w,r) (g(H(M)w) mod qyrw mod q) mod p mod q 由于離散對數(shù)的困難性，敵手從r恢復k或從s恢復x都是不可行的。,2020/9/23,38,還有一個問題值得注意，即簽字產生過程中的運算主要是求r的模指數(shù)運算r=(gk mod p) mod q

20、，而這一運算與待簽的消息無關，因此能被預先計算。事實上，用戶可以預先計算出很多r和k-1以備以后的簽字使用，從而可大大加快產生簽字的速度。,2020/9/23,39,7.3 其他簽字方案,7.3.1 基于離散對數(shù)問題的數(shù)字簽字體制 基于離散對數(shù)問題的數(shù)字簽字體制是數(shù)字簽字體制中最為常用的一類，其中包括 ElGamal簽字體制 DSA簽字體制 Okamoto簽字體制等。,2020/9/23,40,1. 離散對數(shù)簽字體制 ElGamal、DSA、Okamoto等簽字體制都可歸結為離散對數(shù)簽字體制的特例。 (1) 體制參數(shù) p：大素數(shù)； q：p-1或p-1的大素因子； g：gRZ*p，且gq1(mo

21、d p)，其中gR Z*p表示g是從Z*p中隨機選取的，其中Z*p=Zp-0； x：用戶A的秘密鑰，1xq； y：用戶A的公開鑰，ygx(mod p)。,2020/9/23,41,(2) 簽字的產生過程 對于待簽字的消息m，A執(zhí)行以下步驟： 計算m的雜湊值H(m)。 選擇隨機數(shù)k：1kq，計算rgk(mod p)。 從簽字方程akb+cx(mod q)中解出s。方程的系數(shù)a、b、c有許多種不同的選擇方法，表7.1給出了這些可能選擇中的一小部分，以(r, s)作為產生的數(shù)字簽字。,2020/9/23,42,(3) 簽字的驗證過程 接收方在收到消息m和簽字(r, s)后，可以按照以下驗證方程檢驗：

22、,2020/9/23,43,2. ElGamal簽字體制 (1) 體制參數(shù) p：大素數(shù)； g：Z*p的一個生成元； x：用戶A的秘密鑰，xRZ*p； y：用戶A的公開鑰，ygx(mod p)。,2020/9/23,44,(2) 簽字的產生過程 對于待簽字的消息m，A執(zhí)行以下步驟： 計算m的雜湊值H(m)。 選擇隨機數(shù)k：kZ*p，計算rgk(mod p)。 計算s(H(m)-xr)k-1(mod p-1)。 以(r,s)作為產生的數(shù)字簽字。,2020/9/23,45,(3) 簽字驗證過程 接收方在收到消息m和數(shù)字簽字(r, s)后，先計算H(m)，并按下式驗證： 正確性可由下式證明：,2020

23、/9/23,46,3. Schnorr簽字體制 (1) 體制參數(shù) p：大素數(shù)，p2512； q：大素數(shù)，q|(p-1)，q2160； g：gRZ*p,且gq1(mod p)； x：用戶A的秘密鑰，1xq； y：用戶A的公開鑰，ygx(mod p)。,2020/9/23,47,(2) 簽字的產生過程 對于待簽字的消息m，A執(zhí)行以下步驟： 選擇隨機數(shù)k：1kq，計算rgk(mod p)。 計算e=H(r, m)。 計算sxe+k(mod q)。 以(e, s)作為產生的數(shù)字簽字。,2020/9/23,48,(3) 簽字驗證過程 接收方在收到消息m和數(shù)字簽字(e, s)后，先計算rgsy-e(mod

24、 p)，然后計算H(r,m)，并按下式驗證 其正確性可由下式證明：,2020/9/23,49,4. Neberg-Rueppel簽字體制 該體制是一個消息恢復式簽字體制，即驗證人可從簽字中恢復出原始消息，因此簽字人不需要將被簽消息發(fā)送給驗證人。 (1) 體制參數(shù) p：大素數(shù)； q：大素數(shù)，q|(p-1)； g：gRZ*p，且gq1(mod p)； x：用戶A的秘密鑰，xRZ*p； y：用戶A的公開鑰，ygx(mod p)。,2020/9/23,50,(2) 簽字的產生過程 對于待簽字的消息m，A執(zhí)行以下步驟： 計算出 ，其中R是一個單一映射，并且容易求逆，稱為冗余函數(shù)。 選擇一個隨機數(shù)k(0k

25、q)，計算rg-k mod p。 計算 。 計算sxe+k(mod q)。 以(e, s)作為對m的數(shù)字簽字。,2020/9/23,51,(3) 簽字的驗證過程 接收方收到數(shù)字簽字(e, s)后，通過以下步驟來驗證簽字的有效性： 驗證是否0ep。 驗證是否0sq。 計算vgsy-e(mod p)。 計算mve(mod p)。 驗證是否mR(m)，其中R(m)表示R的值域。 恢復出m=R-1(m)。 這個簽字體制的正確性可以由以下等式證明：,2020/9/23,52,5. Okamoto簽字體制 (1) 體制參數(shù) p：大素數(shù)，且p2512; q：大素數(shù)，q|(p-1)，且q2140； g1, g

26、2：兩個與q同長的隨機數(shù)； x1, x2：用戶A的秘密鑰，兩個小于q的隨機數(shù)； y：用戶A的公開鑰，yg-x11g-x22(mod p)。,2020/9/23,53,(2) 簽字的產生過程 對于待簽字的消息m，A執(zhí)行以下步驟： 選擇兩個小于q的隨機數(shù)k1,k2RZ*q。 計算雜湊值：eH(gk11gk22(mod p),m)。 計算：s1(k1+ex1)(mod q)。 計算：s2(k2+ex2)(mod q)。 以(e, s1, s2)作為對m的數(shù)字簽字。,2020/9/23,54,(3) 簽字的驗證過程 接收方在收到消息m和數(shù)字簽字(e, s1, s2)后，通過以下步驟來驗證簽字的有效性：

27、 計算vgs11gs22ye(mod p)。 計算e=H(v,m)。 驗證： 其正確性可通過下式證明：,2020/9/23,55,7.3.2 基于大數(shù)分解問題的數(shù)字簽字體制,設n是一個大合數(shù)，找出n的所有素因子是一個困難問題，稱之為大數(shù)分解問題。下面介紹的兩個數(shù)字簽字體制都基于這個問題的困難性。,2020/9/23,56,1. Fiat-Shamir簽字體制 (1) 體制參數(shù) n：n=pq，其中p和q是兩個保密的大素數(shù)； k：固定的正整數(shù)； y1,y2,yk：用戶A的公開鑰，對任何i(1ik)，yi都是模n的平方剩余； x1,x2,xk：用戶A的秘密鑰，對任何i(1ik)， 。,2020/9/

28、23,57,(2) 簽字的產生過程 對于待簽字的消息m，A執(zhí)行以下步驟： 隨機選取一個正整數(shù)t。 隨機選取t個介于1和n之間的數(shù)r1,r2,rt，并對任何j(1jt)，計算Rjr2j(mod n)。 計算雜湊值H(m,R1,R2,Rt)，并依次取出H(m,R1,R2,Rt)的前kt個比特值b11,b1t,b21,b2t,bk1,bkt。 對任何j(1jt)，計算 。 以(b11,b1t,b21,b2t,bk1,bkt),(s1,st)作為對m的數(shù)字簽字。,2020/9/23,58,(3) 簽字的驗證過程 收方在收到消息m和簽字(b11,b1t,b21，,b2t,bk1,bkt),(s1,st)

29、后，用以下步驟來驗證： 對任何j(1jt)，計算 。 計算H(m,R1,R2,Rt)。 驗證b11,b1t,b21,b2t,bk1,bkt是否依次是H(m,R1,R2,Rt)的前kt個比特。如果是，則以上數(shù)字簽字是有效的。 正確性可以由以下算式證明：,2020/9/23,59,2. Guillou-Quisquater簽字體制 (1) 體制參數(shù) n：n=pq，p和q是兩個保密的大素數(shù)； v：gcd(v,(p-1)(q-1)=1； x：用戶A的秘密鑰，xRZ*n； y：用戶A的公開鑰，yZ*n，且xvy1(mod n)。,2020/9/23,60,(2) 簽字的產生過程 對于待簽消息m，A進行以

30、下步驟： 隨機選擇一個數(shù)kZ*n，計算Tkv(mod n)。 計算雜湊值： e=H(m,T)，且使1ev；否則，返回步驟。 計算skxe mod n。 以(e, s)作為對m的簽字。,2020/9/23,61,(3) 簽字的驗證過程 接收方在收到消息m和數(shù)字簽字(e, s)后，用以下步驟來驗證： 計算出Tsvye(mod n)。 計算出e=H(m,T)。 驗證： 正確性可由以下算式證明：,2020/9/23,62,7.3.3 基于身份的數(shù)字簽字體制,ElGamal簽名機制 （1）體制參數(shù) 體制參數(shù)與4.8.3節(jié)相同。設q是大素數(shù)，G1，G2分別是階為q的加法群和乘法群，e: G1G1G2是一個

31、雙線性映射，H1:0,1* G1*和H2:G20,1n是兩個雜湊函數(shù)，sZq*是系統(tǒng)的主密鑰，P是G1的一個生成元。用戶ID的公開鑰和秘密鑰分別是QID=H1(ID)G1*和dID=sQID,2020/9/23,63,(2)簽字的產生過程 對于待簽字的消息m，A執(zhí)行以下步驟： 選擇隨機數(shù)k:kZq* 計算R=kP=(xR,yR) 計算S=(H2(m)P+xRdID)k-1 以（R,S）作為產生的數(shù)字簽字 (3)簽證的驗證過程 接收方在收到消息m和數(shù)字簽字(R,S)后，先計 算H2(m)，并按下式驗證： 正確性可由下式證明：,2020/9/23,64,2.Schnorr簽字體制 （1）體制參數(shù)

32、體制參數(shù)與上述ElGamal簽字體制的參數(shù)相同 （2）簽字的產生過程 對于待簽字的消息m，A執(zhí)行以下步驟： 選擇隨機數(shù)k:kZq*，計算r=e(QID,kP)= e(QID,P)k 計算c=H2(r,m) 計算S=cdID+kQID=(cs+k)QID 以（c,S)作為產生的數(shù)字簽字,2020/9/23,65,（3）簽字的驗證過程 接收方在收到消息m和數(shù)字簽字（c,S) 后，先計算 然后計算 ，并按下式驗證 其正確性可由下式證明：,2020/9/23,66,7.4 認證協(xié)議,6.1節(jié)介紹過消息認證的基本概念，事實上安全可靠的通信除需進行消息的認證外，還需建立一些規(guī)范的協(xié)議對數(shù)據(jù)來源的可靠性、通

33、信實體的真實性加以認證，以防止欺騙、偽裝等攻擊。 本節(jié)以網(wǎng)絡通信的一個基本問題的解決引出認證協(xié)議的基本意義，這一基本問題陳述如下： A和B是網(wǎng)絡的兩個用戶，他們想通過網(wǎng)絡先建立安全的共享密鑰再進行保密通信。那么A(B)如何確信自己正在和B(A)通信而不是和C通信呢？這種通信方式為雙向通信，因此，此時的認證稱為相互認證。類似地，對于單向通信來說，認證稱為單向認證。,2020/9/23,67,7.4.1 相互認證,A、B兩個用戶在建立共享密鑰時需要考慮的核心問題是保密性和實時性。 為了防止會話密鑰的偽造或泄露，會話密鑰在通信雙方之間交換時應為密文形式，所以通信雙方事先就應有密鑰或公開鑰。 第2個問

34、題實時性則對防止消息的重放攻擊極為重要，實現(xiàn)實時性的一種方法是對交換的每一條消息都加上一個序列號，一個新消息僅當它有正確的序列號時才被接收。但這種方法的困難性是要求每個用戶分別記錄與其他每一用戶交換的消息的序列號，從而增加了用戶的負擔，所以序列號方法一般不用于認證和密鑰交換。,2020/9/23,68,保證消息的實時性常用以下兩種方法： 時戳如果A收到的消息包括一時戳，且在A看來這一時戳充分接近自己的當前時刻， A才認為收到的消息是新的并接受之。這種方案要求所有各方的時鐘是同步的。 詢問-應答用戶A向B發(fā)出一個一次性隨機數(shù)作為詢問，如果收到B發(fā)來的消息（應答）也包含一正確的一次性隨機數(shù)，A就認

35、為B發(fā)來的消息是新的并接受之。,2020/9/23,69,其中時戳法不能用于面向連接的應用過程，這是由于時戳法在實現(xiàn)時固有的困難性。 首先是需要在不同的處理器時鐘之間保持同步，那么所用的協(xié)議必須是容錯的以處理網(wǎng)絡錯誤，并且是安全的以對付惡意攻擊。 第二，如果協(xié)議中任一方的時鐘出現(xiàn)錯誤而暫時地失去了同步，則將使敵手攻擊成功的可能性增加。 最后還由于網(wǎng)絡本身存在著延遲，因此不能期望協(xié)議的各方能保持精確的同步。所以任何基于時戳的處理過程、協(xié)議等都必須允許同步有一個誤差范圍。考慮到網(wǎng)絡本身的延遲，誤差范圍應足夠大；考慮到可能存在的攻擊，誤差范圍又應足夠小。,2020/9/23,70,而詢問-應答方式則

36、不適合于無連接的應用過程，這是因為在無連接傳輸以前需經詢問應答這一額外的握手過程，這與無連接應用過程的本質特性不符。 對無連接的應用程序來說，利用某種安全的時間服務器保持各方時鐘同步是防止重放攻擊最好的方法。 通信雙方建立共享密鑰時可采用單鑰加密體制和公鑰加密體制。,2020/9/23,71,1. 單鑰加密體制 采用單鑰加密體制為通信雙方建立共享的密鑰時，需要有一個可信的密鑰分配中心KDC，網(wǎng)絡中每一用戶都與KDC有一共享的密鑰，稱為主密鑰。KDC為通信雙方建立一個短期內使用的密鑰，稱為會話密鑰，并用主密鑰加密會話密鑰后分配給兩個用戶。這種分配密鑰的方式在實際應用中較為普遍采用，如下一章介紹的

37、Kerberos系統(tǒng)采用的就是這種方式。,2020/9/23,72,(1) Needham-Schroeder協(xié)議 KDC的密鑰分配過程，可用以下協(xié)議（稱為Needham-Schroeder協(xié)議）來描述： AKDC：IDAIDBN1 KDCA： EKAKSIDBN1EKBKSIDA AB：EKBKSIDA -弱點 BA：EKSN2 AB：EKSf(N2),2020/9/23,73,式中KA、KB分別是A、B與KDC共享的主密鑰。 協(xié)議的目的是由KDC為A、B安全地分配會話密鑰KS，A在第步安全地獲得了KS，而第步的消息僅能被B解讀，因此B在第步安全地獲得了KS ，第步中B向A示意自己已掌握KS

38、，N2用于向A詢問自己在第步收到的KS是否為一新會話密鑰，第步A對B的詢問作出應答，一方面表示自己已掌握KS，另一方面由f(N2)回答了KS的新鮮性?？梢姷凇刹接糜诜乐挂环N類型的重放攻擊，比如敵手在前一次執(zhí)行協(xié)議時截獲第步的消息，然后在這次執(zhí)行協(xié)議時重放，如果雙方沒有第、兩步的握手過程的話，B就無法檢查出自己得到的KS是重放的舊密鑰。,2020/9/23,74,然而以上協(xié)議卻易遭受另一種重放攻擊，假定敵手能獲取舊會話密鑰，則冒充A向B重放第步的消息后，就可欺騙B使用舊會話密鑰。敵手進一步截獲第步B發(fā)出的詢問后，可假冒A作出第步的應答。進而，敵手就可冒充A使用經認證過的會話密鑰向B發(fā)送假消息。

39、,2020/9/23,75,(2) Needham-Schroeder協(xié)議的改進方案之一 為克服以上弱點，可在第步和第步加上一時戳，改進后的協(xié)議如下： AKDC：IDAIDB KDCA： EKAKSIDBTEKBKSIDAT AB：EKBKSIDAT BA：EKSN1 AB：EKSf(N1),2020/9/23,76,其中T是時戳，用以向A、B雙方保證KS的新鮮性。A和B可通過下式檢查T的實時性： |Clock-T|t1+t2 其中Clock為用戶（A或B）本地的時鐘，t1是用戶本地時鐘和KDC時鐘誤差的估計值，t2是網(wǎng)絡的延遲時間。 以上協(xié)議中由于T是經主密鑰加密的，所以敵手即使知道舊會話密

40、鑰，并在協(xié)議的過去執(zhí)行期間截獲第步的結果，也無法成功地重放給B，因B對收到的消息可通過時戳檢查其是否為新的。,2020/9/23,77,以上改進還存在以下問題： 方案主要依賴網(wǎng)絡中各方時鐘的同步，這種同步可能會由于系統(tǒng)故障或計時誤差而被破壞。如果發(fā)送方的時鐘超前于接收方的時鐘，敵手就可截獲發(fā)送方發(fā)出的消息，等待消息中時戳接近于接收方的時鐘時，再重發(fā)這個消息。這種攻擊稱為等待重放攻擊。 抗擊等待重放攻擊的一種方法是要求網(wǎng)絡中各方以KDC的時鐘為基準定期檢查并調整自己的時鐘，另一種方法是使用一次性隨機數(shù)的握手協(xié)議，因為接收方向發(fā)送方發(fā)出詢問的隨機數(shù)是他人無法事先預測的，所以敵手即使實施等待重放攻擊

41、，也可被下面的握手協(xié)議檢查出來。,2020/9/23,78,(3) Needham-Schroeder協(xié)議的改進方案之二 下面的協(xié)議可解決Needham-Schroeder協(xié)議以及改進方案一可能遭受的攻擊： AB：IDANA BKDC：IDBNBEKBIDANATB KDCA：EKAIDBNAKSTBEKBIDAKSTBNB AB：EKBIDAKSTBEKSNB,2020/9/23,79,協(xié)議的具體含義如下： A將新產生的一次性隨機數(shù)NA與自己的身份IDA一起以明文形式發(fā)往B， NA以后將與會話密鑰KS一起以加密形式返回給A，以保證A收到的會話密鑰的新鮮性。 B向KDC發(fā)出與A建立會話密鑰的請

42、求，表示請求的消息包括B的身份、一次性隨機數(shù)NB以及由B與KDC共享的主密鑰加密的數(shù)據(jù)項。其中NB以后將與會話密鑰一起以加密形式返回給B以向B保證會話密鑰的新鮮性，請求中由主密鑰加密的數(shù)據(jù)項用于指示KDC向A發(fā)出一個證書，其中的數(shù)據(jù)項有證書接收者A的身份、B建議的證書截止時間TB、B從A收到的一次性隨機數(shù)。,2020/9/23,80, KDC將B產生的NB連同由KDC與B共享的密鑰KB加密的IDAKSTB一起發(fā)給A，其中KS是KDC分配的會話密鑰，EKBIDAKSTB由A當作票據(jù)用于以后的認證。KDC向A發(fā)出的消息還包括由KDC與A共享的主密鑰加密的IDBNAKSTB，A用這一消息可驗證B已收

43、到第步發(fā)出的消息（通過IDB），A還能驗證這一步收到的消息是新的（通過NA），這一消息中還包括KDC分配的會話密鑰KS以及會話密鑰的截止時間TB。,2020/9/23,81, A將票據(jù)EKBIDAKSTB連同由會話密鑰加密的一次性隨機數(shù)NB發(fā)往B，B由票據(jù)得到會話密鑰KS，并由KS得NB。NB由會話密鑰加密的目的是B認證了自己收到的消息不是一個重放,而的確是來自于A。,2020/9/23,82,以上協(xié)議為A、B雙方建立共享的會話密鑰提供了一個安全有效的手段。再者，如果A保留由協(xié)議得到的票據(jù)，就可在有效時間范圍內不再求助于認證服務器而由以下方式實現(xiàn)雙方的新認證： AB：EKBIDAKSTB,NA

44、 BA：NB，EKSNA AB：EKSNB B在第步收到票據(jù)后，可通過TB檢驗票據(jù)是否過時，而新產生的一次性隨機數(shù)NA、NB則向雙方保證了沒有重放攻擊。 以上協(xié)議中時間期限TB是B根據(jù)自己的時鐘定的，因此不要求各方之間的同步。,2020/9/23,83,2. 公鑰加密體制 第5章曾介紹過使用公鑰加密體制分配會話密鑰的方法，下面的協(xié)議也用于這個目的。 AAS： IDAIDB ASA：ESKASIDAPKATESKASIDBPKBT AB：ESKASIDAPKATESKASIDBPKBTEPKBESKAKST,2020/9/23,84,其中SKAS、SKA 分別是AS和A的秘密鑰，PKA、PKB分

45、別是A和B的公開鑰，E為公鑰加密算法，AS是認證服務器。 第步，A將自己的身份及欲通信的對方的身份發(fā)送給AS。 第步，AS發(fā)給A的兩個鏈接的數(shù)據(jù)項都是由自己的秘密鑰加密（即由AS簽字），分別作為發(fā)放給通信雙方的公鑰證書。 第步，A選取會話密鑰并經自己的秘密鑰和B的公開鑰加密后連同兩個公鑰證書一起發(fā)往B。因會話密鑰是由A選取，并以密文形式發(fā)送給B，因此包括AS在內的任何第3者都無法得到會話密鑰。時戳T用以防止重放攻擊，所以需要各方的時鐘是同步的。,2020/9/23,85,下一協(xié)議使用一次性隨機數(shù)，因此不需要時鐘的同步： AKDC：IDAIDB KDCA：ESKAUIDBPKB AB：EPKBN

46、AIDA BKDC：IDBIDAEPKAUNA KDCB：ESKAUIDAPKAEPKBESKAUNAKSIDB BA：EPKAESKAUNAKSIDBNB AB：EKSNB,2020/9/23,86,其中SKAU和PKAU分別是KDC的秘密鑰和公開鑰。 第步，A通知KDC他想和B建立安全連接。 第步，KDC將B的公鑰證書發(fā)給A，公鑰證書包括經KDC簽字的B的身份和公鑰。 第步，A告訴B想與他通信，并將自己選擇的一次性隨機數(shù)NA發(fā)給B。 第步，B向KDC發(fā)出得到A的公鑰證書和會話密鑰的請求，請求中由KDC的公開鑰加密的NA用于讓KDC將建立的會話密鑰與NA聯(lián)系起來，以保證會話密鑰的新鮮性。,2

47、020/9/23,87,第步，KDC向B發(fā)出A的公鑰證書以及由自己的秘密鑰和B的公開鑰加密的三元組NA,KS,IDB。三元組由KDC的秘密鑰加密可使B驗證三元組的確是由KDC發(fā)來的，由B的公開鑰加密是防止他人得到三元組后假冒B建立與A的連接。 第步，B新產生一個一次性隨機數(shù)NB,連同上一步收到的由KDC的秘密鑰加密的三元組一起經A的公開鑰加密后發(fā)往A。 第步，A取出會話密鑰，再由會話密鑰加密NB后發(fā)往B，以使B知道A已掌握會話密鑰。,2020/9/23,88,以上協(xié)議可進一步做如下改進： 在第、兩步出現(xiàn)NA的地方加上IDA，以說明NA的確是由A產生的而不是其他人產生的，這時IDA，NA就可惟一

48、地識別A發(fā)出的連接請求。,2020/9/23,89,7.4.2 單向認證,電子郵件等網(wǎng)絡應用有一個最大的優(yōu)點就是不要求收發(fā)雙方同時在線，發(fā)送方將郵件發(fā)往接收方的信箱，郵件在信箱中存著，直到接收方閱讀時才打開。 郵件消息的報頭必須是明文形式以使SMTP（simple mail transfer protocol-簡單郵件傳輸協(xié)議）或X.400等存儲-轉發(fā)協(xié)議能夠處理。然而通常都不希望郵件處理協(xié)議要求郵件的消息本身是明文形式，否則就要求用戶對郵件處理機制的信任。,2020/9/23,90,所以用戶在進行保密通信時，需對郵件消息進行加密以使包括郵件處理系統(tǒng)在內的任何第3者都不能讀取郵件的內容。再者郵

49、件接收者還希望對郵件的來源即發(fā)方的身份進行認證，以防他人的假冒。與雙向認證一樣，在此仍分為單鑰加密和公鑰加密兩種情況來考慮。,2020/9/23,91,1. 單鑰加密 對諸如電子郵件等單向通信來說，圖5.2所示的無中心的密鑰分配情況不適用。因為該方案要求發(fā)送方給接收方發(fā)送一請求，并等到接收方發(fā)回一個包含會話密鑰的應答后，才向接收方發(fā)送消息，所以本方案與接收方和發(fā)送方不必同時在線的要求不符。在圖5.1所示的情況中去掉第步和第步就可滿足單向通信的兩個要求。協(xié)議如下： AKDC：IDAIDBN1 KDCA：EKAKSIDBN1EKBKSIDA AB：EKBKSIDAEKSM,2020/9/23,92

50、,本協(xié)議不要求B同時在線，但保證了只有B能解讀消息，同時還提供了對消息的發(fā)方A的認證。然而本協(xié)議不能防止重放攻擊，為此需在消息中加上時戳，但由于電子郵件處理中的延遲，時戳的作用極為有限。,2020/9/23,93,2. 公鑰加密 公鑰加密算法可對發(fā)送的消息提供保密性、認證性或既提供保密性又提供認證性，為此要求 發(fā)送方知道接收方的公開鑰（保密性） 或要求接收方知道發(fā)送方的公開鑰（認證性） 或要求每一方都知道另一方的公開鑰。,2020/9/23,94,如果主要關心保密性，則可使用以下方式： AB：EPKBKSEKSM 其中A用B的公開鑰加密一次性會話密鑰，用一次性會話密鑰加密消息。只有B能夠使用相

51、應的秘密鑰得到一次性會話密鑰，再用一次性會話密鑰得到消息。這種方案比簡單地用B的公開鑰加密整個消息要有效得多。,2020/9/23,95,如果主要關心認證性，則可使用以下方式： AB：MESKAH(M) 這種方式可實現(xiàn)對A的認證，但不提供對M的保密性。 如果既要提供保密性又要提供認證性，可使用以下方式： AB：EPKBMESKAH(M),2020/9/23,96,后兩種情況要求B知道A的公開鑰并確信公開鑰的真實性。為此A還需同時向B發(fā)送自己的公鑰證書，表示為 AB：MESKAH(M)ESKASTIDAPKA 或AB：EPKBMESKAH(M)ESKASTIDAPKA 其中ESKASTIDAPK

52、A是認證服務器AS為A簽署的公鑰證書。,2020/9/23,97,7.5 身份證明技術,在很多情況下，用戶都需證明自己的身份，如登錄計算機系統(tǒng)、存取電子銀行中的賬目數(shù)據(jù)庫、從自動出納機ATM取款等。 傳統(tǒng)的方法是使用通行字或個人身份識別號PIN(personal identification number)來證明自己的身份，這些方法的缺點是檢驗用戶通行字或PIN的人或系統(tǒng)可使用用戶的通行字或PIN冒充用戶。 本節(jié)介紹的身份的零知識證明技術，可使用戶在不泄露自己的通行字或PIN的情況下向他人證實自己的身份。,2020/9/23,98,7.5.1 交互證明系統(tǒng),交互證明系統(tǒng)由兩方參與，分別稱為證明

53、者（prover，簡記為P）和驗證者（verifier，簡記為V），其中P知道某一秘密（如公鑰密碼體制的秘密鑰或一平方剩余x的平方根），P希望使V相信自己的確掌握這一秘密。 交互證明由若干輪組成，在每一輪，P和V可能需根據(jù)從對方收到的消息和自己計算的某個結果向對方發(fā)送消息。比較典型的方式是在每輪V都向P發(fā)出一詢問，P向V做出一應答。所有輪執(zhí)行完后，V根據(jù)P是否在每一輪對自己發(fā)出的詢問都能正確應答，以決定是否接受P的證明。,2020/9/23,99,交互證明和數(shù)學證明的區(qū)別是：數(shù)學證明的證明者可自己獨立地完成證明，而交互證明是由P產生證明、V驗證證明的有效性來實現(xiàn)，因此雙方之間通過某種信道的通信

54、是必需的。 交互證明系統(tǒng)須滿足以下要求： 完備性: 如果P知道某一秘密，V將接受P的證明。 正確性: 如果P能以一定的概率使V相信P的證明，則P知道相應的秘密。,2020/9/23,100,7.5.2 簡化的Fiat-Shamir身份識別方案,1. 協(xié)議及原理 設n=pq，其中p和q是兩個不同的大素數(shù)，x是模n的平方剩余，y是x的平方根。又設n和x是公開的，而p、q和y是保密的。證明者P以y作為自己的秘密。4.1.9節(jié)已證明，求解方程y2x mod n與分解n是等價的。因此他人不知n的兩個素因子p、q而計算y是困難的。P和驗證者V通過交互證明協(xié)議，P向V證明自己掌握秘密y，從而證明了自己的身份

55、。,2020/9/23,101,協(xié)議如下： P隨機選r(0rn)，計算ar2 mod n，將a發(fā)送給V。 V隨機選e0,1，將e發(fā)送給P。 P計算brye mod n，即e=0時，b=r；e=1時，b=ry mod n。將b發(fā)送給V。 若b2axe mod n，V接受P的證明。 在協(xié)議的前3步，P和V之間共交換了3個消息，這3個消息的作用分別是： 第1個消息是P用來聲稱自己知道a的平方根； 第2個消息e是V的詢問，如果e=0，P必須展示a的平方根，即r，如果e=1，P必須展示被加密的秘密，即ry mod n； 第3個消息b是P對V詢問的應答。,2020/9/23,102,2. 協(xié)議的完備性、正

56、確性和安全性 (1) 完備性 如果P和V遵守協(xié)議，且P知道y，則應答brye mod n應是模n下axe的平方根，在協(xié)議的第步V接受P的證明，所以協(xié)議是完備的。,2020/9/23,103,(2) 正確性 假冒的證明者E可按以下方式以1/2的概率騙得V接受自己的證明： E隨機選r(0rn)和 ，計算 將a發(fā)送給V。 V隨機選e0,1，將e發(fā)送給E。 E將r發(fā)送給V。,2020/9/23,104,根據(jù)協(xié)議的第步，V的驗證方程是 ，當 時，驗證方程成立，V接受E的證明，即E欺騙成功。因 的概率是1/2，所以E欺騙成功的概率是1/2。另一方面，1/2是E能成功欺騙的最好概率，否則假設E以大于1/2的

57、概率使V相信自己的證明，那么E知道一個a，對這個a他可正確地應答V的兩個詢問e=0和e=1，意味著E能計算b21a mod n和b22ax mod n，即 ，因此E由 即可求得x 的平方根y，矛盾。,2020/9/23,105,(3) 安全性 協(xié)議的安全性可分別從證明者P和驗證者V的角度來考慮。 根據(jù)上面的討論，假冒的證明者E欺騙V成功的概率是1/2，對V來說，這個概率太大了。為減小這個概率，可將協(xié)議重復執(zhí)行多次，設執(zhí)行t次，則欺騙者欺騙成功的概率將減小到2-t。 下面考慮P的安全性。因為V的詢問是在很小的集合0,1中選取的，V沒有機會產生其他信息，而P發(fā)送給V的信息僅為P知道x的平方根這一事

58、實，因此V無法得知x的平方根。,2020/9/23,106,7.5.3 零知識證明,零知識證明起源于最小泄露證明。 在交互證明系統(tǒng)中，設P知道某一秘密，并向V證明自己掌握這一秘密，但又不向V泄露這一秘密，這就是最小泄露證明。 進一步，如果V除了知道P能證明某一事實外，不能得到其他任何信息，則稱P實現(xiàn)了零知識證明，相應的協(xié)議稱為零知識證明協(xié)議。,2020/9/23,107,例7.4 圖7.4表示一個簡單的迷宮，C與D之間有一道門，需要知道秘密口令才能將其打開。P向V證明自己能打開這道門，但又不愿向V泄露秘密口令?？刹捎萌缦聟f(xié)議： V在協(xié)議開始時停留在位置A。 P一直走到迷宮深處，隨機選擇位置C或

59、位置D。 P消失后，V走到位置B，然后命令P從某個出口返回位置B。 P服從V的命令，必要時利用秘密口令打開C與D之間的門。 P和V重復以上過程n次。,2020/9/23,108,圖7.4 零知識證明協(xié)議示例,2020/9/23,109,協(xié)議中，如果P不知道秘密口令，就只能從來路返回B，而不能走另外一條路。 此外，P每次猜對V要求走哪一條路的概率是1/2，因此每一輪中P能夠欺騙V的概率是1/2。假定n取16，則執(zhí)行16輪后，P成功欺騙V的概率是1/216=1/65536。于是，如果P16次都能按V的要求返回，V即能證明P確實知道秘密口令。 還可以看出，V無法從上述證明過程中獲取絲毫關于P的秘密口令的信息，所以這是一個零知識證明協(xié)議。,2020/9/23,110,例7.5 哈密爾頓（Hamilton）回路 圖中的回路是指始點和終點相重合的路徑，若回路通過圖的每個頂點一次且僅