消息認證與數(shù)字簽名

1、第五章 消息認證與數(shù)字簽名,,第五章 消息認證與數(shù)字簽名,公鑰密碼體制的一種最重要的應用是數(shù)字簽名。數(shù)字簽名通常需要與散列函數(shù)結(jié)合起來使用。本章先簡要介紹信息認證，然后介紹散列函數(shù)，最后介紹數(shù)字簽名。5.1 信息認證 前面所介紹的對稱密碼和公鑰密碼體制，都是圍繞著信息的保密性，即防止第三方獲取明文消息而展開，但信息的完整性和抗否認性也是信息安全的重要內(nèi)容。保證信息的完整性和抗否認性主要通過信息認證和數(shù)字簽名來實現(xiàn)。,,產(chǎn)

2、生認證符的方法可分以下三類：信息加密：將明文加密后以密文作為認證符；消息認證碼 MAC：用一個密鑰控制的公開函數(shù)作用后產(chǎn)生的固定長度的數(shù)值，也稱密碼校驗和。散列函數(shù)：一個將任意長度的消息映射為定長的散列值的函數(shù)，以散列值作為認證符。5.1.1 加密認證信息加密能夠提供一種認證措施，這里分對稱密碼體制加密認證和公鑰密碼體制加密認證。,,1. 對稱密碼體制加密認證 設(shè)想發(fā)送者A用只有他與接收者B知道的密鑰K加密信息發(fā)送給接收

3、者。因為A是除B以外惟一擁有密鑰K的一方，而攻擊者不知道如何改變密文來產(chǎn)生明文中所期望的變化，因此 B 知道解密得到的明文是否被改變。這樣對稱加密就提供了消息認證功能。 現(xiàn)在考慮如下情況：給定解密函數(shù)D和密鑰K，接收者將接受任何輸入X并產(chǎn)生輸出Y=Dk(X)，如果X是合法信息M的密文，則Y是信息M的明文，否則 Y將是毫無意義的二進制比特序列。接收方需要某些自動化措施，以確定Y是否是合法的明文。,,假定信息M 的明文可以是任意比特的

4、組合。在這種情況下，接收方將沒有自動的方法來確定收到的 X 是否是合法信息的密文。因此，需要從所有可能的比特模式的一個子集中來考慮合法的信息，任何可疑的密文不可能產(chǎn)生合法的明文 。如考慮在106的組合中只有一種是合法的，則從中隨機選擇一個比特組合作為密文能夠產(chǎn)生合法的明文的概率為10-6 。為了實現(xiàn)用自動的方法來確定收到的 Y 是否是合法信息的密文，可以采用的一種方法是強制明文有某種結(jié)構(gòu)，這種結(jié)構(gòu)易于識別但不能復制并且不求助于加密。

5、例如，可以在加密以前對消息附加檢錯碼。,,2. 公鑰密碼體制加密認證 使用公開密鑰加密信息的明文只能提供保密而不能提供認證。為了提供認證，發(fā)送者 A用私鑰對信息的明文進行加密，任意接收者都可以用 A的公鑰解密。這種方式提供的認證措施與對稱密碼體制加密的情形在原理上是相同的。與前面的一樣，在明文中也要求有某種內(nèi)部結(jié)構(gòu)，因此，接收者能夠識別正常的明文和隨機的比特串。 采用這樣的結(jié)構(gòu)既可提供了認證，也可提供數(shù)字簽名。因為只有

6、A 能夠產(chǎn)生該密文，其它任何一方都不能產(chǎn)生該密文，從效果上看 A 已經(jīng)用私鑰對信息的明文進行了簽名。,,應當注意 只用私鑰加密不能提供保密性。因為任何人只要有A的公開密鑰，就能夠?qū)υ撁芪倪M行解密。5.1.2 消息認證碼 消息認證碼 MAC（或稱密碼檢驗和）是在個密鑰的控制下將任意長的消息映射到一個簡短的定長數(shù)據(jù)分組，并將它附加在消息后。設(shè)M 是變長的消息，K是僅由收發(fā)雙方共享的密鑰，則M的MAC由如下的函數(shù)C生成：MAC

7、 = CK ( M )這里CK ( M )是定長的。發(fā)送者每次將MAC附加到消息中。接收者通過重新計算MAC來對消息進行認證。,,如果收到的MAC與計算得出的MAC相同，則接收者可以認為：消息未被更改過。因為任意更改消息而沒有更改MAC的行為，都將導致收到的MAC與用更改過的消息計算出的MAC不相同。且由于使用的密鑰只有收發(fā)雙方知道，其它方無法更改MAC使之與更改后的消息對應。消息來自與他共享密鑰的發(fā)送者。由于使用的密鑰只有收

8、發(fā)雙方知道，其它方無法產(chǎn)生對應的MAC。 MAC函數(shù)類似于加密函數(shù)，主要區(qū)別在于MAC函數(shù)不需要可逆而加密函數(shù)必須是可逆的。因此，認證函數(shù)比加密函數(shù)更不易破解。,,應當注意，因收發(fā)雙方共享相同的密鑰，上述過程只提供認證而不提供保密，也不能提供數(shù)字簽名。 前面談到對稱密碼體制的加密能夠提供認證，為什么還要使用獨立的消息認證碼呢？主要理由如下：一些應用要求將相同的消息對許多終端進行廣播，僅使用一個終端負責消息的

9、認證，這種方法既經(jīng)濟又實用。負責認證的終端有相應的密鑰，并執(zhí)行認證操作。如果認證不正確，其它終端將收到它發(fā)來的警告。接收方有繁重的任務，無法負擔大量的解密任務，因此僅進行有選擇的認證，對消息進行隨機檢查。,,有一些應用，只關(guān)心信息的完整性而不需要保密性。認證與保密的分離能夠提供結(jié)構(gòu)上的靈活性。有些應用場合期望在超過接收時間后繼續(xù)延長保護期限，同時允許處理消息的內(nèi)容。如果使用加密，解密后保護就失效了，這樣，消息只能在傳輸過程中得到完

10、整性保護，但在目標系統(tǒng)中卻辦不到。,5.2 散列(Hash)函數(shù),散列函數(shù) (又稱雜湊函數(shù))是對不定長的輸入產(chǎn)生定長輸出的一種特殊函數(shù)：h= H ( M )其中M是變長的消息，h=H(M)是定長的散列值（或稱為消息摘要）。散列函數(shù)H 是公開的，散列值在信源處被附加在消息上，接收方通過重新計算散列值來保證消息未被篡改。由于函數(shù)本身公開，傳送過程中對散列值需要另外的加密保護（如果沒有對散列值的保護，篡改者可以在修改消息的同時修改散列值，

11、從而使散列值的認證功能失效）。,,5.2.1 散列函數(shù)的性質(zhì) 散列函數(shù)的目的是為文件、消息或其他的分組數(shù)據(jù)產(chǎn)生“指紋”。要用于消息認證的散列函數(shù)H必須具有如下性質(zhì)：H能用于任何大小的數(shù)據(jù)分組，能產(chǎn)生定長的輸出。對于任何給定的x，H(x)要相對易于計算。對任何給定的散列碼h，尋找x使得H(x)=h在計算上不可行（單向性）。對任何給定的分組x，尋找不等于x的y ，使得H(x)=H(y)在計算上不可行（弱抗沖突）。尋找任何的(x

12、,y)，使得H(x)=H(y)在計算上不可行（強抗沖突）。,,注意到前兩個性質(zhì)使得散列函數(shù)用于消息認證成為可能。第2和第3個性質(zhì)保證H的單向性，給定消息產(chǎn)生散列值很簡單，反過來由散列值產(chǎn)生消息計算上不可行。這保證了攻擊者無法通過散列值恢復消息。第 4個性質(zhì)保證了攻擊者無法在不修改散列值的情況下替換消息而不被察覺。第5個性質(zhì)比第4個性質(zhì)更強，保證了一種被稱為生日攻擊的方法無法奏效。 散列碼不同的使用方式可以提供不同要求的消息認證。這里

13、列出如下四種：,,使用對稱密碼體制對附加了散列碼的消息進行加密。這種方式與用對稱密碼體制加密附加檢錯碼的消息在結(jié)構(gòu)上是一致的。認證的原理也相同，而且這種方式也提供保密性。使用對稱密碼體制僅對附加的散列碼進行加密。在這種方式中，如果將散列函數(shù)與加密函數(shù)合并為一個整體函數(shù)實際上就是一個MAC函數(shù)。使用公鑰密碼體制，但發(fā)送方的私有密鑰僅對散列碼進行加密。這種方式與第二種方式一樣提供認證，而且還提供數(shù)字簽名。發(fā)送者將消息 M與通信各方共享

14、的一個秘密值S串接，然后計算出散列值，并將散列值附在消息M后發(fā)送出去。由于秘密值S 并不發(fā)送，攻擊者無法產(chǎn)生假消息。,,5.2.2 散列函數(shù)的結(jié)構(gòu) 為了對不定長的輸入產(chǎn)生定長的輸出，并且最后的結(jié)果要與所有的字節(jié)相關(guān)，大多數(shù)安全的散列函數(shù)都采用了分塊填充鏈接的模式，其結(jié)構(gòu)是迭代型的。這種散列函數(shù)模型最早由Merkle于1989年提出，在Ron Rivest于1990提出的MD4中也采用了這種模型。下面介紹這種模型的一般結(jié)構(gòu)。

15、這種散列函數(shù)將輸入數(shù)據(jù)分為L個固定長度為b比特的分組。輸入數(shù)據(jù)除了消息和附加的填充數(shù)據(jù)外，還附加了消息的長度值。附加的這個長度值將增加攻擊者攻擊的難度。對手要么找出兩個具有相同長度的消息，使得它們加上各自長度值后散列值相同；要么找出兩個不同長度的消息，這樣的消息加上各自的長度值后必須散列成相同的值。,,散列算法中重復使用一個壓縮函數(shù)f，f產(chǎn)生一個n比特的輸出。f有兩個輸入，一個是前一步的n比特輸出，稱為鏈接變量；另一個是b比特的分組

16、。算法開始時鏈接變量要指定一個初始值VI。最終的鏈接變量值便是散列值。通常有b>n，因此稱f為壓縮函數(shù)。該散列算法可以表達如下：CV0 = V ICVi = f (CVi ?1 ,Yi ?1 ) ,1≤ i ≤ Lh = H ( M ) = CVL這里M是由分組Y0 , Y1 ,……，YL ?1組成。如圖5. 1所示。,,,圖5. 1 迭代型散列函數(shù)的結(jié)構(gòu),,已經(jīng)證明如果壓縮函數(shù)是無碰撞的，則上述方法得到的H

17、ash函數(shù)也是無碰撞的。 因此，Hash函數(shù)的核心技術(shù)是設(shè)計無碰撞的壓縮函數(shù)。同樣，攻擊者對算法的攻擊重點也是對f 的內(nèi)部結(jié)構(gòu)的分析。與分組密碼一樣，f也是由若干輪處理過程組成，因而對f 的分析需要通過對各輪之間的比特模式的分析來進行，常常需要先找出f的碰撞。 由于f 是壓縮函數(shù)，因而一定存在碰撞。這就要求在設(shè)計f時盡量使找出f的碰撞在計算上是不可行的。5.2.1 安全散列算法（SHA） Ron Rivest于19

18、90 提出了一個稱為 MD4的散列函數(shù)。它的設(shè)計沒有基于任何假設(shè)和密碼體制，這種直接構(gòu)造方法受到人們的廣泛關(guān)注。不久，它的一些缺點也被提出。,,為了增強安全性和克服MD4的缺陷，Rivest于1991年對MD4 作了六點改進，并將改進后的算法稱為MD5。MD5曾經(jīng)是使用最普遍的安全散列算法。然而，隨著對MD5分析的深入，從密碼分析和強力攻擊的角度來看，MD5也被認為是易受攻擊的。因此，有必要用一個具有更長的散列碼和更能抗擊已知密碼分析攻

19、擊的散列函數(shù)來代替流行的MD5。已經(jīng)有兩個散列碼長為160 比特的替代者SHA-1和RIPEMD-160。本書只介紹SHA-1。 安全散列算法 SHA Secure Hash Algorithm 由美國國家標準和技術(shù)協(xié)會（NIST）提出，并作為聯(lián)邦信息處理標準（FIPS PUB 180）在1993年公布；1995年又發(fā)布了一個修訂版FIPS PUB 180-1，通常稱為SHA-1。SHA是基于MD4算法。,,1. SHA

20、-1描述 如圖5.2所示。SHA-1算法的輸入為不超過264比特長的任意消息，輸出為一個160比特長的消息摘要，輸入按512比特長的分組進行處理。處理過程如下： (1)對消息進行填充：在原始的消息后面附加填充比特串，使得數(shù)據(jù)長度（比特數(shù)）與 448模512同余。即使得填充后的數(shù)據(jù)長度為512的整數(shù)倍減去64。填充是必須的，即使消息長度已滿足要求，仍然需要填充。如消息長度為448比特，則需要填充512比特，

21、使其長度變?yōu)?60。因此，填充的比特數(shù)從1到512。規(guī)定填充比特串的第一位是1，其余各位均是0。,,,,(2) 附加消息的長度：用64比特的二進制數(shù)表示原始消息的長度，將所得的 64 比特數(shù)據(jù)附加在第1步所得的數(shù)據(jù)后面（高位字節(jié)優(yōu)先）。 (3) 初始化MD緩存：用一個160比特的緩存來存放該散列函數(shù)的中間及最終結(jié)果。該緩存可以表示為 5個32比特的寄存器(A, B,C, D, E)。這些寄存器被初始化為以下32比特長的整

22、數(shù)(十六進制表示）：A=67452301B=EFCDAB89C=98BADCFED=10325476E=C3D2E1F0,,注意這些值以高位字節(jié)優(yōu)先的方式存儲，因而初始化的值（十六進制表示）存儲如下：字A=67 45 23 01字B=EF CD AB 89字C=98 BA DC FE字D=10 32 54 76字E=C3 D2 E1 F0 (4)處理512比特分組序列：核心是一個包含四個循環(huán)的模塊，每個循環(huán)由2

23、0個處理步驟組成，如圖5.3所示。四個循環(huán)結(jié)構(gòu)相似，但使用不同的原始邏輯函數(shù)，分別為f1、f2、f3和f4。,,,,每個循環(huán)以當前處理的512比特分組Yq和160比特的緩存值A(chǔ)BCDE為輸入，然后更新緩存的內(nèi)容。每個循環(huán)也使用一個額外的常數(shù)值Kt ，其中0 ≤ t≤ 79。這些值用十六進制表示如表5. 1。,,第四個循環(huán)的輸出加到第一個循環(huán)的輸入(CVq)上產(chǎn)生CVq+1，這里的相加是緩存中的5個字分別與CVq中對應的5個字以模232相

24、加。(5)輸出：所有L個512比特的分組處理完成后，第L階段產(chǎn)生的輸出便是160比特的報文摘要。SHA-1的第三到第五步的操作總結(jié)如下：CV0=VICVq=SUM32 (CVq ,ABCDEq)MD=CVL其中VI是第三步定義的緩沖區(qū)ABCDE的初值，ABCDEq是第q個分組經(jīng)過四輪處理后的輸出，L是分組個數(shù)，SUM32是對應字模232的加法，MD是最終摘要值。,,5.2.2 SHA-1的壓縮函數(shù) 上面說過

25、，SHA-1 的壓縮函數(shù)由四次循環(huán)組成，每循環(huán)由20個處理步驟組成，每個處理步驟的形式為（參看圖5.4）：A, B, C, D, E ← ( E + f (t , B, C, D) + S5 ( A) + Wt + Kt ), A, S 30 ( B),C, D,,其中A、B、C、D、E是上面提到的緩存中的5個字， f (t , B, C, D)是步驟t 的原始邏輯函數(shù)， Sk為32比特的參數(shù)循環(huán)左移k 位，Wt是由當前512比特分

26、組導出的一個32比特字（導出方式見表5.2）， Kt如表5.1的定義。 每個基本邏輯函數(shù)有3個32比特字輸入并產(chǎn)生一個32比特字輸出。每個函數(shù)執(zhí)行一組按位的邏輯操作，即第n位的輸出是這三個輸入中第n 個比特的一個函數(shù)。函數(shù)的定義如表5.2所示。,,邏輯運算與、或、非、異或分別用符號∧、∨ 、—、⊕表示。函數(shù)的真值表如表5.3所示。,,32比特字 Wt的值是通過如下過程由 512比特的分組中導出的：Wt的前16個字的值直接

27、取自當前分組中的前16個字的值，余下的字定義如下：Wt = S1(Wt ?16 ⊕ Wt?14 ⊕ Wt?8 ⊕ W t?3 ) 因此，在前16步處理中Wt的值等于分組中對應字的值。余下的64 步中Wt 的值由四個前面的Wt值異或之后再循環(huán)左移一位得出，如圖5.5所示。SHA-1將16個分組字擴展為80個字以供壓縮函數(shù)使用，這將使尋找碰撞非常困難。,,,,5.2.4 與MD5和RIPEMD-160的比較SH

28、A-1在許多方面都與MD5和RIPEMD-160相似，因為這三個算法都是由MD4導出。表5.4展示了它們的異同。,表5.4 SHA-1與MD5和RIPEMD-160的對比,,從上面的設(shè)計指標和目前的分析結(jié)果來看，它們的優(yōu)缺點比較如下： (1) 抗強力攻擊的能力：對于弱碰撞攻擊，這三個算法都是無懈可擊的。MD5 很容易遭遇強碰撞的生日攻擊，而SHA-1和RIPEMD-160目前是安全的。 (2)抗密碼分析攻

29、擊的能力：對MD5的密碼分析已經(jīng)取得了很大的進展。RIPEMD-160 設(shè)計時就考慮了抗已知密碼分析攻擊。 SHA-1也有很高的抗密碼分析攻擊的能力。RIPEMD-160 應該比SHA-1有更強的抗密碼分析攻擊的能力。,,(3)計算速度：三個算法的主要運算都是模232加法和按位邏輯運算，因而都易于在32 位的結(jié)構(gòu)上實現(xiàn)，但SHA-1和RIPEMD-160的迭代次數(shù)較多，復雜性較高，因此速度較MD5慢些。 (4)存儲方式：

30、低位字節(jié)優(yōu)先與高位字節(jié)優(yōu)先都沒有明顯優(yōu)勢。5.3 數(shù)字簽名體制 前面介紹的消息認證能保護通信雙方以防止第三方的攻擊，然而卻無法防止通信雙方的一方對另一方的欺騙。如通信雙方A和B使用消息認證碼通信，則可能發(fā)生如下欺騙：,,A 偽造一個消息并使用與B 共享的密鑰產(chǎn)生該消息的認證碼，然后聲稱該消息來自于B；由于這個原因，B也可以對自己發(fā)送給A的消息予以否認。因此除了認證之外還需要其它機制來防止通信雙方的抵賴行為，最常見的解決方

31、案就是采用數(shù)字簽名。5.3.1數(shù)字簽名原理數(shù)字簽名體制是以電子形式簽名存儲消息的方法，所簽名的消息能夠在通信網(wǎng)中傳送。數(shù)字簽名與傳統(tǒng)的手寫簽名有如下不同： (1)簽名：手寫簽名是被簽文件的物理組成部分；而數(shù)字簽名不是被簽消息的物理部分，因而需要將簽名連接到被簽消息上。,,(2)驗證：手寫簽名是通過將它與其它真實的簽名進行比較來驗證；而數(shù)字簽名是利用已經(jīng)公開的驗證算法來驗證。 (3)簽名數(shù)字消息的復制品

32、與其本身是一樣的，而手寫簽名紙質(zhì)文件的復制品與原品是不同的。 與手寫簽名類似，一個數(shù)字簽名至少應滿足以下三個基本條件： (1)簽名者不能否認自己的簽名； (2)接受者能夠驗證簽名，而其他任何人都不能偽造簽名； (3)當關(guān)于簽名的真?zhèn)伟l(fā)生爭執(zhí)時，存在一個仲裁機構(gòu)或第三方能夠解決爭執(zhí)。 在這些性質(zhì)的基礎(chǔ)上，結(jié)合手寫簽名與數(shù)字簽名的區(qū)別，可歸納出如下數(shù)字簽名的需求：,,(1

33、)依賴性：數(shù)字簽名必須依賴于要簽名報文的比特模式，類似于筆跡簽名與被簽文件的不可分離性。 (2)惟一性：數(shù)字簽名必須使用對簽名者來說是惟一的信息，以防偽造和否認，類似筆跡簽名的獨特性。 (3)可驗證：數(shù)字簽名必須是在算法上可驗證的。 (4)抗偽造：偽造一個數(shù)字簽名在計算上不可行，無論是通過以后的數(shù)字簽名來構(gòu)造新報文，還是對給定的報文構(gòu)造一個虛假的數(shù)字簽名，類似筆跡簽名不可模仿性。

34、 (5)可用性：數(shù)字簽名的產(chǎn)生、識別和證實必須相對簡單，并且其備份在存儲上是可實現(xiàn)的，顯然簽名不能太長。 目前已經(jīng)提出了許多數(shù)字簽名體制，但可以分成兩類：直接數(shù)字簽名和需仲裁的數(shù)字簽名。,,直接數(shù)字簽名 直接數(shù)字簽名僅涉及通信方。它假定收方知道發(fā)方的公開密鑰。數(shù)字簽名通過使用發(fā)方的私有密鑰對整個消息進行加密或使用發(fā)方的私有密鑰對消息的散列碼進行加密來產(chǎn)生。目前，所有的直接數(shù)字簽名體制都有一個共

35、同的弱點：方案的有效性依賴于發(fā)方私有密鑰的安全性。如果發(fā)方隨后想否認發(fā)送過某個簽名消息，發(fā)方可以聲稱簽名的私鑰丟失或被盜用，并偽造了他的簽名。如果A的私鑰真的被盜，盜用者便能夠發(fā)送帶有A的簽名的消息，并附加上盜用前的任何時刻作為時間戳。,,需仲裁的數(shù)字簽名為了解決直接數(shù)字簽名中存在的問題 我們可以引入仲裁者。需仲裁的數(shù)字簽名體制一般流程如下：發(fā)方A對發(fā)給收方 B 的消息簽名后，將附有簽名的消息發(fā)給仲裁者C ， C對其驗證后，連同一個

36、通過驗證的證明發(fā)送給收方B。在這個方案中，A無法對自己發(fā)出的消息予以否認，但仲裁者必須是得到所有用戶信任的負責任者。,,5.3.2 RSA數(shù)字簽名體制 用RSA實現(xiàn)數(shù)字簽名的方法中，要簽名的報文作為一個散列函數(shù)的輸入，產(chǎn)生一個定長的安全散列碼。使用簽名者的私有密鑰對這個散列碼進行加密就形成簽名，然后，將簽名附在報文后。驗證者根據(jù)報文產(chǎn)生一個散列碼，同時使用簽名者的公開密鑰對簽名進行解密。如果計算得出的散列碼與解密后的簽名匹配，那么

37、簽名就是有效的。因為只有簽名者知道私有密鑰，因此只有簽名者才能產(chǎn)生有效的簽名。其簽名與驗證的過程如圖5.6所示。,,,,對照數(shù)字簽名的各項要求： (1)散列函數(shù)取得報文的信息摘要，從而使對之進行加密產(chǎn)生的簽名依賴于消息； (2) RSA私鑰的保密性使得簽名是唯一的； (3)信息摘要的字節(jié)數(shù)很少（如SHA的160字節(jié)），因而Hash函數(shù)的輸出產(chǎn)生簽名相對簡單，同樣地，簽名的識別與證實相對簡單；

38、 (4)散列函數(shù)的單向性與抗沖突性，還有RSA私鑰的保密性，使得偽造數(shù)字簽名不可行。 可以看出，散列函數(shù)在數(shù)字簽名中發(fā)揮了產(chǎn)生消息摘要、減少簽名與認證工作量的作用。,,5.3.3 ElGamal數(shù)字簽名體制ElGamal于1985年基于離散對數(shù)問題提出了一個數(shù)字簽名體制，通常稱為 ElGamal數(shù)字簽名體制。它像ElGamal密碼體制一樣都是非確定性的，即一個確定的消息可能有許多合法的簽名。這里介紹一個更一般

39、的數(shù)字簽名體制，稱它為ElGamal型數(shù)字簽名體制。設(shè)計一個ElGamal型數(shù)字簽名體制的過程如下： (1)選擇足夠大的素數(shù)p使得求解離散對數(shù)問題在Zp上是困難的，q是p-1的大素因子或者q=p。,,(2)隨機選擇Zp*中一個階為q的元素α；當q=p時，在Zp*中隨機選擇一個本原元α。 (3)隨機選擇整數(shù)a，使得0≤a ≤ p?2，并計算β=αa mod p。 (4)對每個密鑰k=(p,

40、q, α,a ,β)，定義簽名變換 Sigk(x,r)=(γ, δ)， 這里r是每次簽名前隨機選擇的隨機數(shù)，γ=( α r mod p) mod q 。 δ 的取值如下：當q < p時， δ滿足方程rf (γ, x,δ ) + ag(γ, x,δ ) +h (γ, x,δ ) ≡ 0 mod p；當q=p時，δ滿足方程rf (γ, x,δ ) + ag(γ, x,δ ) +h (γ, x,δ ) ≡ 0 mod(p-1)，這里

41、的f,g,h是公開知道的函數(shù)，并且使得從方程中求解δ是容易的。 (5)對x ∈ Zp* ,γ ∈ Zq* ,δ ∈ Zq ，定義驗證函數(shù)為Ver ( x , γ , δ ) = T，當且僅當γf (γ, x,δ ).βg(γ, x,δ ).αh (γ, x,δ ) ≡ (1mod p) mod q。 (6)以{p,q, α,β}為公開密鑰，a為私有密鑰。,,這樣就建立了ElGamal型數(shù)字簽名體制：其消息

42、空間P = Zp*，簽名空間S = Z q * × Zq (q < p)或S = Z q * ×Zp?1(q = p)，密鑰空間為K ={(p,q, α,a ,β)：β=αa mod p}(q<p)或K={(p,q, α,a ,β)：β=αa mod p}(q=p)。其中p是大素數(shù)，q=p或者q 是p-1的大素數(shù)因子，α是Z p *的一個本原元(取q=p)或Zp *中一個階為q的元素(取q<p)

43、， 0≤a ≤ p?2， β=αa mod p。 如果簽名是正確構(gòu)造的則驗證將是成功的，因為(γf (γ, x,δ ).βg(γ, x,δ ).αh (γ, x,δ ) mod p) mod q= αrf (γ, x,δ ) + αag(γ, x,δ ) +αh (γ, x,δ ) mod p) mod q=1，當f,g,h取不同的函數(shù)時，就能得到不同的數(shù)字簽名體制。 在上面的簽名體制中，取q=p時，得到

44、的就是ElGamal數(shù)字簽名體制。此時，簽名算法為Sigk(x,r)=(γ, δ)， γ=( α r mod p) ， δ=(x-aγ)r-1 mod (p-1)；而驗證算法為Ver ( x , γ , δ ) = T，當且僅當γδ.βγ ≡ αxmod p，x, γ ∈ Zp* , δ ∈Zp-1 。,,5.3.3 數(shù)字簽名標準DSS DSS數(shù)字簽名標準由美國國家標準技術(shù)研究所 NIST于1991年提出，在1994年

45、公布的聯(lián)邦信息處理標準FIPSPUB 186中采用為數(shù)字簽名標準，它利用了前面介紹的安全散列算法SHA并提出了一種新的數(shù)字簽名技術(shù)，即數(shù)字簽名算法DSA。 在DSS數(shù)字簽名方法中，簽名方先利用安全散列算法產(chǎn)生報文的信息摘要，然后將信息摘要和一個專用于該簽名的隨機數(shù) k 作為簽名函數(shù)的輸入，該簽名函數(shù)還依賴于簽名方的私有密鑰(KRa)和一個全局公開密鑰(KUG ，事實上是一組相關(guān)聯(lián)的參數(shù))。簽名由兩個分量組成，記為s和r。

46、驗證方計算報文的散列碼，該散列碼和簽名做為驗證函數(shù)的輸入。驗證函數(shù)同時還依賴于全局公開密鑰和與簽名方的私鑰配對的驗證方的公鑰。如果簽名是有效的，驗證函數(shù)的輸出等于簽名分量r，其工作流程如圖5.7所示。,,,,簽名算法DSA是基于Zp *上求解離散對數(shù)問題的難度，是ElGamal型數(shù)字簽名體制的變形。在ElGamal型數(shù)字簽名體制中，當q<p，f ( γ , x , δ ) = δ，g (γ , x , δ ) = ? γ，h(γ

47、, x, δ ) = ? H ( x)時，就成為數(shù)字簽名算法DSA，其中H是一個散列算法。在DSA中，稱公鑰 {p,q, α, β}中的{p,q, α}為全局公鑰分量， β為用戶公鑰。 設(shè)計一個DSA算法的步驟如下： (1)全局公鑰的選擇：首先選擇一個160比特的素數(shù)q，接著選擇一個長度在512到 1024比特之間的素數(shù) p，使得 p-1 能被q整除，最后選擇g=h(p-1)/q mod p，其中h是大于1小于p

48、-1的整數(shù)，從而使g大于1。,,(2)選擇用戶私鑰公鑰對：選擇1到之間p-1的隨機數(shù)或者偽隨機數(shù) x 作為用戶私鑰，計算y=gx mod p作為公鑰。 (3)生成簽名：用戶選擇隨機整數(shù)k，對消息M，計算兩個分量r與s產(chǎn)生簽名(r,s)：r = f2 (k, p, q, g) = ( gk mod p) modqs = f1( H( M ), k, x, r, q) = (k ?1( H( M ) + xr) )modq

49、 (4)驗證簽名：接收方先根據(jù)收到的消息M’、簽名(r’,s’)、公鑰y、p、q、g等值計算 w = f3 (s' , q) = (s' )?1 modqv = f4 ( y, q, g, H( M' ), w, r' ) = ((g( H ( M ') w )modq yr 'w modq mod p) modq 將v與r進行比較，若相等則接受簽名。簽名和