信息安全原理與技術(shù)之消息認證與數(shù)字簽名

信息安全原理與技術(shù)郭亞軍宋建華李莉清華大學出版社2024/8/201Ch5-消息認證與數(shù)字簽名第5章消息認證與數(shù)字簽名主要知識點：

--認證

--認證碼

--散列函數(shù)

--MD5

--SHA-512

--數(shù)字簽名2024/8/202Ch5-消息認證與數(shù)字簽名認證認證則是防止主動攻擊的重要技術(shù)，可以防止如下一些攻擊：偽裝：攻擊者生成一個消息并聲稱這條消息是來自某合法實體，或者攻擊者冒充消息接收方向消息發(fā)送方發(fā)送的關(guān)于收到或未收到消息的欺詐應(yīng)答。內(nèi)容修改：對消息內(nèi)容的修改，包括插入、刪除、轉(zhuǎn)換和修改。順序修改：對通信雙方消息順序的修改，包括插入、刪除和重新排序。計時修改：對消息的延遲和重放。在面向連接的應(yīng)用中，攻擊者可能延遲或重放以前某合法會話中的消息序列，也可能會延遲或重放是消息序列中的某一條消息。2024/8/203Ch5-消息認證與數(shù)字簽名認證的目的第一，驗證消息的發(fā)送者是合法的，不是冒充的，這稱為實體認證，包括對信源、信宿等的認證和識別；第二，驗證信息本身的完整性，這稱為消息認證，驗證數(shù)據(jù)在傳送或存儲過程中沒有被篡改、重放或延遲等。2024/8/204Ch5-消息認證與數(shù)字簽名認證的目的可提供認證功能的認證碼的函數(shù)可分為三類：加密函數(shù)：使用消息發(fā)送方和消息接收方共享的密鑰對整個消息進行加密，則整個消息的密文作為認證符。消息認證碼：它是消息和密鑰的函數(shù)，產(chǎn)生定長度值，該值作為消息的認證符。散列函數(shù)：它是將任意長的消息映射為定長的hash值的函數(shù)，以該hash值作為認證符。2024/8/205Ch5-消息認證與數(shù)字簽名基本的認證系統(tǒng)模型2024/8/206Ch5-消息認證與數(shù)字簽名消息認證碼消息認證碼，簡稱MAC(MessageAuthenticationCode)，是一種使用密鑰的認證技術(shù)，它利用密鑰來生成一個固定長度的短數(shù)據(jù)塊，并將該數(shù)據(jù)塊附加在消息之后。在這種方法中假定通信雙方A和B共享密鑰K。若A向B發(fā)送消息M時，則A使用消息M和密鑰K，計算MAC＝C(K,M)2024/8/207Ch5-消息認證與數(shù)字簽名消息認證碼的使用2024/8/208Ch5-消息認證與數(shù)字簽名消息認證碼的使用（續(xù)）2024/8/209Ch5-消息認證與數(shù)字簽名MAC的安全要求MAC中使用了密鑰，這點和對稱密鑰加密一樣，如果密鑰泄漏了或者被攻擊了，則MAC的安全性則無法保證。在基于算法的加密函數(shù)中，攻擊者可以嘗試所有可能的密鑰以進行窮舉攻擊，一般對k位的密鑰，窮舉攻擊需要2(k-1)步。2024/8/2010Ch5-消息認證與數(shù)字簽名對MAC的攻擊

第一輪

·給定M1,MAC1＝CK(M1) ·對所有2k個密鑰判斷MACi＝CKi(M1) ·匹配數(shù)

2(k-n)

。

第二輪

·給定M2,MAC2＝CK(M2) ·對循環(huán)1中找到的2(k-n)個密鑰判斷MACi＝CKi(M2) ·匹配數(shù)

2(k-2n)

。攻擊者可以按此方法不斷對密鑰進行測試，直到將匹配數(shù)縮寫到足夠小的范圍。平均來講，若k=a

n,則需a次循環(huán)2024/8/2011Ch5-消息認證與數(shù)字簽名針對MAC算法的攻擊攻擊者針對下面的MAC算法，則不需要使用窮舉攻擊即可獲得密鑰信息。設(shè)消息M＝(X1||X2||…||Xm)，即由64位分組Xi聯(lián)結(jié)而成。定義

Δ(M)＝X1

X2

…

Xm

Ck(M)=EK[Δ(M)]攻擊者可以用任何期望的Y1至Ym-1替代X1至Xm-1，用Ym替代Xm來進行攻擊，其中Ym如下計算的：

Ym＝Y(jié)1

Y2

…

Ym-1

Δ(M)攻擊者可以將Y1至Ym-1與原來的MAC連結(jié)成一個新的消息M’，接收方收到(M’,Ck(M))時，由于Δ(M’)=Y1

Y2

…

Ym=Δ(M)，因此Ck(M)=EK[Δ(M’)]，接受者會認為該消息是真實。用這種辦法，攻擊者可以隨意插入任意的長為64

(m-1)位的消息。2024/8/2012Ch5-消息認證與數(shù)字簽名MAC的性質(zhì)一個安全的MAC函數(shù)應(yīng)具有下列性質(zhì)：若攻擊者知道M和Ck(M)，則他構(gòu)造滿足Ck(M’)=Ck(M)的消息M’在計算上是不可行的。Ck(M)應(yīng)是均勻分布的，即對任何隨機選擇的消息M和M’,Ck(M)=Ck(M’)的概率是2-n,其中n是MAC的位數(shù)。設(shè)M’是M的某個已知的變換，即M’=f(M)，則Ck(M)=Ck(M’)的概率為2-n。2024/8/2013Ch5-消息認證與數(shù)字簽名基于DES的消息認證碼2024/8/2014Ch5-消息認證與數(shù)字簽名Hash函數(shù)Hash函數(shù)(也稱散列函數(shù)或雜湊函數(shù))是將任意長的輸入消息作為輸入生成一個固定長的輸出串的函數(shù)，即h=H(M)。這個輸出串h稱為該消息的散列值（或消息摘要，或雜湊值）。2024/8/2015Ch5-消息認證與數(shù)字簽名安全的Hash函數(shù)的要求H可以應(yīng)用于任意長度的數(shù)據(jù)塊，產(chǎn)生固定長度的散列值；對每一個給定的輸入m，計算H(m)是很容易的；給定Hash函數(shù)的描述，對于給定的散列值h，找到滿足H(m)=h的m在計算上是不可行的；給定Hash函數(shù)的描述，對于給定的消息m1，找到滿足m2

m1且H(m2)=H(m1)的m2在計算上是不可行的；找到任何滿足H(m1)=H(m2)且m1

m2的消息對(m1,m2)在計算上是不可行的。2024/8/2016Ch5-消息認證與數(shù)字簽名安全的Hash函數(shù)的要求H可以應(yīng)用于任意長度的數(shù)據(jù)塊，產(chǎn)生固定長度的散列值；對每一個給定的輸入m，計算H(m)是很容易的；給定Hash函數(shù)的描述，對于給定的散列值h，找到滿足H(m)=h的m在計算上是不可行的；給定Hash函數(shù)的描述，對于給定的消息m1，找到滿足m2

m1且H(m2)=H(m1)的m2在計算上是不可行的；找到任何滿足H(m1)=H(m2)且m1

m2的消息對(m1,m2)在計算上是不可行的。2024/8/2017Ch5-消息認證與數(shù)字簽名Hash的一般結(jié)構(gòu)2024/8/2018Ch5-消息認證與數(shù)字簽名2024/8/2019Ch5-消息認證與數(shù)字簽名Hash函數(shù)的安全要求1．單向性：對任何給定的散列碼h，找到滿足H(x)＝h的x在計算上是不可行的。2．抗弱碰撞性：對任何給定的消息x，找到滿足y≠x且H(x)=H(y)的y在計算上是不可行的。3．抗強碰撞性：找到任何滿足H(x)=H(y)的偶對(x,y)在計算上是不可行的。2024/8/2020Ch5-消息認證與數(shù)字簽名生日攻擊（BirthdayAttack）如果攻擊者希望偽造消息M的簽名來欺騙接收者，則他需要找到滿足H(M’)=H(M)的M’來替代M。對于生成64位散列值的散列函數(shù)，平均需要嘗試263次以找到M’。但是建立在生日悖論上的生日攻擊法，則會更有效。對于上述問題換種說法：假設(shè)一個函數(shù)有n個函數(shù)值，且已知一個函數(shù)值H(x)。任選k個任意數(shù)作為函數(shù)的輸入值，則k必須為多大才能保證至少找到一個輸入值y且H(x)=H(y)的概率大于0.5?2024/8/2021Ch5-消息認證與數(shù)字簽名生日悖論我們可以如下描述這類問題：k為多大時，在k個人中至少找到兩個人的生日相同的概率大于0.5？不考慮二月二十九日并且假定每個生日出現(xiàn)的概率相同。2024/8/2022Ch5-消息認證與數(shù)字簽名首先k個人的生日排列的總數(shù)目是365k。這樣，k個人有不同生日的排列數(shù)為：

因此，k個人有不同生日的概率為不重復(fù)的排列數(shù)除以總數(shù)目，得到：

則，k個人中，至少找到兩個人同日出生的概率是：

2024/8/2023Ch5-消息認證與數(shù)字簽名Yuval的生日攻擊(1)合法的簽名方對于其認為合法的消息愿意使用自己的私鑰對該消息生成的m位的散列值進行數(shù)字簽名。(2)攻擊者為了偽造一份有(1)中的簽名者簽名的消息，首先產(chǎn)生一份簽名方將會同意簽名的消息，再產(chǎn)生出該消息的2m/2種不同的變化，且每一種變化表達相同的意義（如：在文字中加入空格、換行字符）。然后，攻擊者再偽造一條具有不同意義的新的消息，并產(chǎn)生出該偽造消息的2m/2種變化。2024/8/2024Ch5-消息認證與數(shù)字簽名Yuval的生日攻擊（續(xù)）(3)攻擊者在上述兩個消息集合中找出可以產(chǎn)生相同散列值的一對消息。根據(jù)“生日悖論”理論，能找到這樣一對消息的概率是非常大的。如果找不到這樣的消息，攻擊者再產(chǎn)生一條有效的消息和偽造的消息，并增加每組中的明文數(shù)目，直至成功為止。(4)攻擊者用第一組中找到的明文提供給簽名方要求簽名，這樣，這個簽名就可以被用來偽造第二組中找到的明文的數(shù)字簽名。這樣，即使攻擊者不知道簽名私鑰也能偽造簽名。2024/8/2025Ch5-消息認證與數(shù)字簽名中間相遇攻擊法（MeetintheMiddleAttack）(1)根據(jù)已知數(shù)字簽名的明文，先產(chǎn)生散列函數(shù)值h。(2)再根據(jù)意圖偽造簽名的明文，將其分成每個64位長的明文分組：Q1,Q2,…,QN-2。Hash函數(shù)的壓縮算法為：hi=EQi[hi-1]，1

i

N-2。(3)任意產(chǎn)生232個不同的X，對每個X計算EX[hN-2]。同樣的，任意產(chǎn)生232個不同的Y，對每個Y計算DY[G]，D是相對應(yīng)E的解密函數(shù)。2024/8/2026Ch5-消息認證與數(shù)字簽名中間相遇攻擊法（MeetintheMiddleAttack）-續(xù)(4)根據(jù)“生日悖論”，有很大的概率可以找到一堆X及Y滿足EX[hN-2]=DY[G]。(5)如果找到了這樣的X和Y，攻擊者重新構(gòu)造一個明文：Q1,Q2,…,QN-2,X,Y。這個新的明文的散列值也為h，因此攻擊者可以使用已知的數(shù)字簽名為這個構(gòu)造的明文偽造新的明文的簽名。2024/8/2027Ch5-消息認證與數(shù)字簽名MD5MD5（Message-Digest

Algorithm

5）是由Ronald

L.

Rivest（RSA算法中的“R”）這90年代初開發(fā)出來的，經(jīng)MD2、MD3和MD4發(fā)展而來。它比MD4復(fù)雜，但設(shè)計思想類似，同樣生成一個128位的信息散列值。其中，MD2是為8位機器做過設(shè)計優(yōu)化的，而MD4和MD5卻是面向32位的計算機。2004年8月，在美國召開的國際密碼學會議（Crypto’2004）上，王小云教授給出破解MD5、HAVAL-128、MD4和RIPEMD算法的報告。給出了一個非常高效的尋找碰撞的方法，可以在數(shù)個小時內(nèi)找到MD5的碰撞。2024/8/2028Ch5-消息認證與數(shù)字簽名MD5算法步驟1）填充消息：任意長度的消息首先需要進行填充處理，使得填充后的消息總長度與448模512同余（即填充后的消息長度

448mod512）。填充的方法是在消息后面添加一位“1”，后續(xù)都是“0”。2）添加原始消息長度：在填充后的消息后面再添加一個64位的二進制整數(shù)表示填充前原始消息的長度。這時經(jīng)過處理后的消息長度正好是512位的倍數(shù)。3）初始值（IV）的初始化：MD5中有四個32位緩沖區(qū)，用（A,B,C,D）表示，用來存儲散列計算的中間結(jié)果和最終結(jié)果，緩沖區(qū)中的值被稱為鏈接變量。首先將其分別初始化為為：A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210。2024/8/2029Ch5-消息認證與數(shù)字簽名MD5算法步驟-續(xù)4）以512位的分組為單位對消息進行循環(huán)散列計算：經(jīng)過處理的消息，以512位為單位，分成N個分組，用Y0，Y1，…，YN-1。MD5對每個分組進行散列處理。每一輪的處理會對（A，B，C，D）進行更新。5）輸出散列值：所有的N個分組消息都處理完后，最后一輪得到的四個緩沖區(qū)的值即為整個消息的散列值。2024/8/2030Ch5-消息認證與數(shù)字簽名MD5算法步驟-續(xù)2024/8/2031Ch5-消息認證與數(shù)字簽名MD5應(yīng)用舉例利用給出的MD5程序?qū)Α癶elloworld!”進行處理，計算它的HASH值。微軟的系統(tǒng)軟件都有MD5驗證，嘗試查找軟件的MD5值。在WINDOWS操作系統(tǒng)中，可以通過開始—>運行—>sigverif命令，利用數(shù)字簽名查找驗證非WINDOWS的系統(tǒng)軟件。2024/8/2032Ch5-消息認證與數(shù)字簽名SHA-512算法步驟對消息進行填充：對原始消息進行填充使其長度與896模1024同余(即填充后的消息長度

896mod1024)。即使原始消息已經(jīng)滿足上述長度要求，仍然需要進行填充，因此填充位數(shù)在1到1024之間。填充部分由一個1和后續(xù)的0組成。添加消息長度信息：在填充后的消息后添加一個128位的塊，用來說明填充前消息的長度，表示為一個無符號整數(shù)(最高有效字節(jié)在前)。至此，產(chǎn)生了一個長度為1024整數(shù)倍的擴展消息。2024/8/2033Ch5-消息認證與數(shù)字簽名SHA-512算法步驟初始化Hash緩沖區(qū)：Hash函數(shù)計算的中間結(jié)果和最終結(jié)果保存在512位的緩沖區(qū)中，分別用64比特的寄存器(A,B,C,D,E,F,G,H)表示，并將這些寄存器初始化為下列64位的整數(shù)(十六進制值)：A＝0x6A09E667F3BCC908 B＝0xBB67AE8584CAA73BC＝0x3C6EF372FE94F82B D＝0xA54FF53A5F1D36F1 E=0x510E527FADE682D1F=0x9B05688C2B3E6C1FG=0x1F83D9ABFB41BD6BH=0x5BE0CD19137E21792024/8/2034Ch5-消息認證與數(shù)字簽名SHA-512算法步驟-續(xù)以1024位分組（16個字）為單位處理消息：處理算法的核心是需要進行80輪運算的模塊。輸出：所有的N個1024位分組都處理完以后，最后輸出的即是512位的消息散列值。2024/8/2035Ch5-消息認證與數(shù)字簽名SHA-512算法步驟-續(xù)2024/8/2036Ch5-消息認證與數(shù)字簽名

SHA-512每一步的核心處理2024/8/2037Ch5-消息認證與數(shù)字簽名HMACHMAC的設(shè)計目標包括：

可以直接使用現(xiàn)有的Hash函數(shù)；

不針對于某一個Hash函數(shù)，可以根據(jù)需要更換Hash函數(shù)模塊；

可保持Hash函數(shù)的原有性能，不能過分降低其性能；

對密鑰的使用和處理應(yīng)較簡單；

如果已知嵌入的Hash函數(shù)的強度，則可以知道認證機制抵抗密碼分析的強度。2024/8/2038Ch5-消息認證與數(shù)字簽名HMAC的結(jié)構(gòu)2024/8/2039Ch5-消息認證與數(shù)字簽名HMAC的實現(xiàn)方案2024/8/2040Ch5-消息認證與數(shù)字簽名數(shù)字簽名數(shù)字簽名也是一種認證機制，它是公鑰密碼學發(fā)展過程中的一個重要組成部分，是公鑰密碼算法的典型應(yīng)用。數(shù)字簽名的應(yīng)用過程是，數(shù)據(jù)源發(fā)送方使用自己的私鑰對數(shù)據(jù)校驗和或其他與數(shù)據(jù)內(nèi)容有關(guān)的信息進行處理，完成對數(shù)據(jù)的合法“簽名”，數(shù)據(jù)接收方則利用發(fā)送方的公鑰來驗證收到的消息上的“數(shù)字簽名”，以確認簽名的合法性。2024/8/2041Ch5-消息認證與數(shù)字簽名數(shù)字簽名數(shù)字簽名需要滿足以下條件：簽名的結(jié)果必須是與被簽名的消息相關(guān)的二進制位串；簽名必須使用發(fā)送方某些獨有的信息（發(fā)送者的私鑰），以防偽造和否認；產(chǎn)生數(shù)字簽名比較容易；識別和驗證簽名比較容易；給定數(shù)字簽名和被簽名的消息，偽造數(shù)字簽名在計算上是不可行的。保存數(shù)字簽名的拷貝，并由第三方進行仲裁是可行的。2024/8/2042Ch5-消息認證與數(shù)字簽名數(shù)字簽名的典型使用(1)消息發(fā)送方式與散列函數(shù)對消息進行計算，得到消息的散列值。(2)發(fā)送方使用自己的私鑰對消息散列值進行計算，得到一個較短的數(shù)字簽名串。(3)這個數(shù)字簽名將和消息一起發(fā)送給接收方。(4)接收方首先從接收到的消息中用同樣的散列函數(shù)計算出一個消息摘要，然后使用這個消息摘要、發(fā)送者的公鑰以及收到的數(shù)字簽名，進行數(shù)字簽名合法性的驗證。2024/8/2043Ch5-消息認證與數(shù)字簽名Schnorr數(shù)字簽名系統(tǒng)參數(shù)的選擇p，q：滿足q|p-1，q

2160，q

2512g：g

Zp，滿足gq=1modp，g

1H：散列函數(shù)x：用戶的私鑰，1<x<qy：用戶的公鑰，y=gxmodp2024/8/2044Ch5-消息認證與數(shù)字簽名Schnorr數(shù)字簽名簽名設(shè)要簽名的消息為M，0<M<p。簽名者隨機選擇一整數(shù)k，1<k<q，并計算：e=H(r,M)s=k–xemodq(e,s)即為M的簽名。簽名者將M連同(r,s)一起存放，或發(fā)送給驗證者。2024/8/2045Ch5-消息認證與數(shù)字簽名Schnorr數(shù)字簽名驗證驗證者獲得M和(e,s)，需要驗證(e,s)是否是M的簽名。計算：r’=gsremodp檢查H(r’,M)=e是否正確，若是，則(e,s)為M的合法簽名。2024/8/2046Ch5-消息認證與數(shù)字簽名DSSDSA的系統(tǒng)參數(shù)選擇如下：p：512的素數(shù)，其中2L-1<p<2L，512

L

1024，且L是64的倍數(shù)，即L的位長在512至1024之間并且其增量為64位。q：160位的素數(shù)且q|p-1。g：滿足g=h(p-1)/qmodpH：為散列函數(shù)x：用戶的私鑰，0<x<qy：用戶的公鑰，y=gxmodpp、q、g為系統(tǒng)發(fā)布的公共參數(shù)，與公鑰y公開；私鑰x保密。2024/8/2047Ch5-消息認證與數(shù)字簽名DSS簽名設(shè)要簽名的消息為M，0<M<p。簽名者隨機選擇一整數(shù)k，0<k<q，并計算：r=(gkmodp)modqs=[k-1(H(M)+xr)]modq(r,s)即為M的簽名。簽名者將M連同(r,s)一起存放，或發(fā)送給驗證者。2024/8/2048Ch5-消息認證與數(shù)字簽名DSS驗證驗證者獲得M和(r,s)，需要驗證(r,s)是否是M的簽名。首先檢查r和s是否屬于[0,q]，若不是，則(r,s)不是簽名值。否則，計算：w=s-1modqu1=(H(M)w)modqu2=rwmodqv=((gu1yu2)modp)modq如果v=r，則所獲得的(r,s)是M的合法簽名。2024/8/2049Ch5-消息認證與數(shù)字簽名仲裁數(shù)字簽名

仲裁簽名中除了通信雙方外，還有一個仲裁方發(fā)送方A發(fā)送給B的每條簽名的消息都先發(fā)送給仲裁者T，T對消息及其簽名進行檢查以驗證消息源及其內(nèi)容，檢查無誤后給消息加上日期再發(fā)送給B，同時指明該消息已通過仲裁者的檢驗。仲裁數(shù)字簽名實際上涉及到多余一步的處理，仲裁者的加入使得對于消息的驗證具有了實時性。2024/8/2050Ch5-消息認證與數(shù)字簽名仲裁數(shù)字簽名

(1)A

T：M||EKAT[IDA||H(M)](2)T

B：EKTB[IDA||M||EKAT[IDA||H(M)]||T](1)A

T：IDA||EPRA[IDA||EPUB(EPRA[M])](2)T

B：EPRT[IDA||EPUB[EPRA[M]]||T]2024/8/2051Ch5-消息認證與數(shù)字簽名盲簽名盲簽名是Chaum在1982年首次提出的，并利用盲簽名技術(shù)提出了第一個電子現(xiàn)金方案。盲簽名因為具有盲性這一特點，可以有效的保護所簽名的消息的具體內(nèi)容，所以在電子商務(wù)等領(lǐng)域有著廣泛的應(yīng)用。盲簽名允許消息發(fā)送者先將消息盲化，而后讓簽名者對盲化的消息進行簽名，最后消息擁有者對簽名除去盲因子，得到簽名者關(guān)于原消息的簽名。2024/8/2052Ch5-消息認證與數(shù)字簽名盲簽名的性質(zhì)它除了滿足一般的數(shù)字簽名條件外，還必須滿足下面的兩條性質(zhì)：1.簽名者不知道其所簽名的消息的具體內(nèi)容。2.簽名消息不可追蹤，即當簽名消息被公布后，簽名者無法知道這是他哪次的簽署的。2024/8/2053Ch5-消息認證與數(shù)字簽名盲簽名的步驟A期望獲得對消息m的簽名，B對消息m的盲簽名的實現(xiàn)描述如下：盲化：A對于消息進行處理，使用盲因子合成新的消息M并發(fā)生給B；簽名：B對消息M簽名后，將簽名(M,sign(M))返回給給A；去盲：A去掉盲因子，從對M的簽名中得到B對m的簽名。2024/8/2054Ch5-消息認證與數(shù)字簽名好的盲簽名的性質(zhì)不可偽造性：除了簽名者本人外，任何人都不能以他的名義生成有效的盲簽名。不可抵賴性：簽名者一旦簽署了某個消息，他無法否認自己對消息的簽名。盲性：簽名者雖然對某個消息進行了簽名，但他不可能得到消息的具體內(nèi)容。不可跟蹤性：一旦消息的簽名公開后，簽名者不能確定