Hash函數與消息認證一、Hash函數概述二、Hash函數MD5三、安全Hash算法SHA四、基于分組密碼與離散對數的Hash函數五、消息認證

2023/2/31一、Hash函數概述

Hash函數單向函數函數f(x):A→B若滿足下面兩個條件，則稱為單向函數對于任意x*∈A計算y=f(x)是容易的，其中y∈B。對于x∈A，求y∈B使滿足y=f(x)是計算上不可能的。2023/2/33

Hash函數Hash函數設H：將A*映射到An，H滿足：H是單向函數。已知x,找x*∈A*，使H(x)=H(x*)在計算上是不可能的。找一對x

和x*，x≠x*，使H(x)=H(x*)在計算上也是不可能的。H稱為安全的Hash函數。

2023/2/34

Hash函數Hash函數的分類根據安全水平：弱無碰撞：散列函數H稱為是弱無碰撞的，是指對給定消息，在計算上幾乎找不到異于x的x*使H(x)=H(x*)。?強無碰撞：散列函數H被稱為是強無碰撞的,是指在計算上幾乎不可能找到相異的x

，x*使得H(x)=H(x*)。2023/2/35

Hash函數Hash函數的分類根據是否使用密鑰帶秘密密鑰的Hash函數:消息的散列值由只有通信雙方知道的秘密密鑰K來控制。此時Hash值稱作MAC。不帶秘密密鑰的Hash函數：消息的散列值的產生無需使用密鑰。此時Hash值稱作MDC。2023/2/36

Hash函數Hash函數的用途?消息的完整性檢測?數字簽名2023/2/37Hash函數hh發送者對h(x)進行加密接收者對y進行解密不安全信道不安全信道xxyxyh(x)h(x)h(x)相等？2023/2/38Hash函數使用Hash函數進行數字簽名的好處?提高數字簽名的速度。?無需泄露簽名所對應的消息，可將簽名泄露，如對消息x的簽名是Sig(x)，其z=H(x)可將(z,y)公開，而保密x。?可將簽名變換和加密變換分開，可以在OSI的不同層提供消息的完整性和機密性。2023/2/39Hash函數

Hash函數的安全性：Hash函數的安全性取決于其抗擊各種攻擊的能力，對手的目標是找到兩個不同消息映射為同一雜Hash值。一般假定對手知道Hash算法，采用選擇明文攻擊法。2023/2/310Hash函數對Hash函數的基本攻擊方法窮舉攻擊法：給定H=H(H0,M)，其中H0為初值，攻擊者在所有可能的M中尋求有利于攻擊者的M’，使H(H0,M’)=H(H0,M)，由于限定了目標H(H0,M)來尋找H(H0,M’)，這種攻擊法稱為目標攻擊。若對算法的初值H0不限定，使其H(H0,M)等于H(H0,M’)，則稱這種攻擊法為自由起始目標攻擊。2023/2/311Hash函數對Hash函數的基本攻擊方法

生日攻擊：這種攻擊法不涉及Hash算法的結構，可用于攻擊任何Hash算法。強無碰撞函數正是基于生日悖論一類的攻擊法定義的。窮舉和生日攻擊都屬選擇明文攻擊。生日攻擊給定初值H0尋找MM’，使H(H0,M’)=H(H0,M)，也可對初始值H0不加限制，即尋找H0’,M’使滿足h(H0’,M’)=h(H0,M)。2023/2/312Hash函數生日悖論在一個會場參加會議的人中，找一個與某人生日相同的概率超過0.5時，所需參會人員為183人。但要問使參會人員中至少有兩個同日生的概率超過0.5的參會人數僅為23人。這是因為，對于與某個已知生日的人同日生的概率為1/365，若房中有t人，則至少找到一人與此人同日生的概率為。易于解出當t183時可使p>0.5。

2023/2/313

Hash函數Hash函數的迭代構造將不限定長度的輸入數據壓縮成定長輸出的Hash值過程：將輸入數字串劃分成固定長的段如m比特段將此m比特映射成n比特，稱完成此映射的函數為迭代函數。對一段m比特輸入做類似映射，以此類推，直到全部輸入數字串完全做完，以最后的輸出值作為整個輸入的Hash值。2023/2/314

Hash函數將mbit到nbit的分組映射或迭代函數的三種選擇

m>n。有數據壓縮，例如：MD4、MD5SHA等算法。是不可逆映射。

m=n。無數據壓縮，亦無數據擴展，通常分組密碼采用這類。

m<n。有數據擴展的映射。認證碼屬于此類。

2023/2/315

Hash函數迭代函數以E表示，一般E又都是通過基本輪函數的多輪迭代實現的，因此，輪函數的設計是Hash函數設計的核心。迭代Hash函數的構造方法安全迭代函數E消息M劃分成組M1,M2,…,Mi,…,Mt選定密鑰為K，H0為初始向量IV，2023/2/316

Hash函數Rabin法：

H0=IV；Hi=E(Mi,Hi-1)i=1,…,t；H(M)=Ht。密碼分組鏈接(CBC)法：

H0=IV；Hi=E(K,MiHi-1)i=1,2,…,t；H(M)=Ht。密碼反饋(CFB)法：

Hi=E(K,Hi-1Mi)，i=1,2,…,t；H(M)=Ht

2023/2/317

Hash函數組合明/密文鏈接法：

Mt+1=IV；Hi=E(K,MiMi-1Hi-1)i=1,2,…,t；H(M)=Ht+1。修正Daveis-Meyer法：

H0=IV；Hi=E(Hi-1,Mi,Hi-1)(Hi和Mi共同作為密鑰)

2023/2/318

Hash函數

B.Preneel總結的下述12種基本方式構造的分組迭代Hash函數。令E是迭代函數，它可以是一種分組加密算法，E(K,X)，K是密鑰，X是輸入數據組或某種壓縮算法。令消息分組為M1,…,Mi,…,H0=I為初始值。

Hi=E(Mi,Hi-1)Hi-1Hi=E(Hi-1,Mi)MiHi-1

Hi=E(Hi-1,MiHi-1)Mi

2023/2/319

Hash函數Hi=E(Hi-1,MiHi-1)MiHi-1Hi=E(Hi-1,Mi)MiHi=E(Mi,MiHi-1)MiHi-1Hi=E(Mi,Hi-1)MiHi-1

Hi=E(Mi,MiHi-1)Hi-1Hi=E(MiHi-1,Mi)MiHi=E(MiHi-1,Hi-1,)Hi-1[Brown等1990]Hi=E(MiHi-1,Mi)Hi-1Hi=E(MiHi-1,Hi-1)Mi

2023/2/320二、Hash函數MD5Hash函數MD5設計目標：

MD5是R.Rivest在MIT開發研究的Hash函數輸入：任意長度的消息輸出：128位消息摘要處理：以512位輸入數據塊為單位2023/2/322Hash函數MD5

MD5算法對明文輸入按512bit分組，最后要填充使其成為512bit的整數倍，且最后一組的后64bit用來表示消息長在mod264下的值K，故填充位數為1～512

bit，填充數字圖樣為(100…0)，得Y0,Y1,…，YL-1。其中，Yl為512

bit，即16個長為32bit的字，按字計消息長為N=L×16。。2023/2/323Hash函數MD5

MD5算法每輪輸出為128bit，可用下述4個32

bits字表示：A，B，C，D。其初始存數以十六制表示為：

A=01234567B=89ABCDEFC=FEDCBA98D=76543210。2023/2/324Hash函數MD5MD5算法HMD5的運算，對512bit(16-字)組進行運算，Yq表示輸入的第q組512

bit數據，在各輪中參加運算。T[1,…,64]為64個元素表，分四組參與不同輪的計算。T[i]為232×abs(Sine(i))的整數部分，i是弧度。T[i]可用32bit二元數表示，T是32bit隨機數源。

2023/2/325Hash函數MD5

MD5是四輪運算，各輪邏輯函數不同。每輪又要進行16步迭代運算，4輪共需64步完成。每步完成

ab＋CLSS(a＋g(B,C,D)＋X[k]＋T[i])其中a,b,c,d=緩存器中的四個字，按特定次序變化。g=基本邏輯函數F,G,H,I中之一，算法的每一輪用其中之一。2023/2/326ABCD＂fI(ABCD,Yq,T[49…64])++++ABCD＂fF(ABCD,Yq,T[1…16])ABCD＂fH(ABCD,Yq,T[33…48])ABCD＂fH(ABCD,Yq,T[33…48])MDq,128ABCDABCDABCDABCDYq512MDq+1,1282023/2/327+gabcd+++CLSSX[k]T[i]2023/2/328

Hash函數CLSs：32-bit存數循環左移s位。X[k]=M[q×16＋k]：消息的第q-512-bit組的第k個32-bit字T[i]：232×abs(sin(i))的整數部分。＋：模232加法。

T[i]由sin函數構造。每個輸入的32bit字被采用4次，每輪用一次，而T[i]中每個元素恰只用一次。每一次，ABCD中只有4個字節更新，共更新16次，在最后第17次產生此組的最后輸出。2023/2/329Hash函數表-1各輪的邏輯函數2023/2/330Hash函數表-2邏輯函數的真值表bcdFGHI000000100110100100110011100110000111010101110110011111102023/2/331

Hash函數

MD0=IV（ABCD緩存器的初始矢量）

MDq+1=MDq+fI[Yq,fH[Yq,fG[Yq,fF[Yq,MDq]]]]MD=MDL—1（最終輸出值）。

2023/2/332

Hash函數

MD5的安全性：求具有相同Hash值的兩個消息在計算上是不可行的。MD-5的輸出為128-bit，若采用純強力攻擊尋找一個消息具有給定Hash值的計算困難性為2128。若采用生日攻擊法，尋找有相同Hash值的兩個消息需要試驗264個消息。差分攻擊對MD5的安全性不構成威脅。

2023/2/333

Hash函數

MD5的安全性：對單輪MD5已有攻擊結果。與Snefru比較，兩者均為32bits字運算。Snefru采用S-BOX，XOR函數，MD5用mod232加。最近山東大學的王小云教授利用用差分分析的方法研究MD5，得到了比較好的算法使MD5能夠產生碰撞。因此MD5的安全性還需要進一步提高。2023/2/334三、安全Hash算法SHA安全Hash算法SHA

SHA是美國NIST和NSA設計的一種標準算法SHA(SecureHashAlgorithm)，用于數字簽字標準算法DSS(DigitalSignatureStandard)，亦可用于其它需要用Hash算法的情況。SHA具有較高的安全性。輸入消息長度小于264bit輸出壓縮值為160bit2023/2/336安全Hash算法SHA

SHA的描述輸入長度少于264比特，輸出160比特。輸入分成512比特塊。附加信息位使長度mod512與448同余。一組64比特附在后面，看作是64比特的整數，包含原來未加附加位的信息長度。2023/2/337安全Hash算法SHA

SHA的描述MD緩沖器初始化。緩沖區分為５個寄存器(A,B,C,D,E)，每個32比特，初始值分別為：

A=67453210B=EFCDAB89C=98BADCFED=10325476E=C3D2E1F0

2023/2/338安全Hash算法SHA對512比特組的信息的處理：算法的核心是４輪操作，每輪20步，每輪的結構類似但是邏輯函數不同，分別為f1,f2,f3,f4

每輪輸入512比特，輸出160比特。

2023/2/339安全Hash算法SHA對512比特組的信息的處理：

ABCDE,每輪用的常數Kt,,0≤t≤79,其實只有4個不同的常數

5A8279990≤t≤196ED9EBA120≤t≤39Kt＝8F1BDBDC40≤t≤59CA62C1D660≤t≤79當L組運算結束后，由第L步的輸出160比特作H(m)。2023/2/340＋＋＋＋＋P1,K,W[0…19]P2,K,W[20…39]P3,K,W[40…59]P4,K,W[60…79]51216032ACDBEACDBEACDBEACDBE1602023/2/341安全Hash算法SHASHA每一步是如下計算的：(A,B,C,D,E)←((E+f(t,B,C,D))+S5(A)+Wt),A,S30(B),C,D)t為步數，f(t,B,C,D)為第t步的邏輯函數。Sk為左旋轉移位k位。Wt為由512比特的輸入組導出32比特的第t塊。Kt為附加的常數。+為mod232的加法。2023/2/342AEDCBAEDCBfS5S30++++WtKt2023/2/343安全Hash算法SHA

每個函數的輸入為32比特，輸出是一個32比特字，有一系列邏輯運算而得到的。輸出的第n位為BCD3輸入第n位的函數。

(B∧C)∨(B∧D)0≤t≤19BCD20≤t≤39f(t,B,C,D)=(B∧C)∨(B∧D)∨(C∧D)40≤t≤59BCD60≤t≤792023/2/344安全Hash算法SHA

SHA與MD5的比較最主要不同點，SHA比MD5長了32比特，如果采用強行攻擊，SHA顯然比MD5抗攻擊能力強。MD5已有了密碼分析的攻擊方法，顧較脆弱。MD5效率比SHA高。兩者都比較容易實現。R.L.Rivest公開了MD-5的設計決策，但SHA的設計者則不愿公開。2023/2/345四、基于分組密碼與離散對數的Hash函數基于分組密碼的Hash函數利用DES構造Hash函數我們將介紹利用DES構造Hash函數的若干模式，實際上也是利用和DES類似的明文、密文長度和密鑰長度一樣的分組密碼來構造Hash函數的模式。設m=m1m2…ml,m=m1m2…ml

都是64比特的明文塊，k是密鑰，也是64比特。2023/2/347基于分組密碼的Hash函數第1種構造模式S1:i←1,K←k;S2:K←DESk(mi),i←i+1;S3:若i≤l,則轉S2,否則作Hk(m)←KkDESDESDESm1m2ml…Hk(m)2023/2/348基于分組密碼的Hash函數第2種構造模式S1:i←1,S←S0;S2:mi←miS,S←DESk(mi),S3:若i≤l;則轉S2,否則作Hk(m)←SS0DESDESDESm1m2ml…kkk2023/2/349基于分組密碼的Hash函數第3種構造模式S1:i←1,mi←0,H0←0,mh+1←V;S2:H0←DESk(mi

mi-1

Hi-1),i←i+1；S3:若i≤l+1;則轉S2,否則作Hk(m)←Hi+1；其中V為和k類似的參數，H0

和M0

都取為零2023/2/350基于分組密碼的Hash函數DESDESDESm1m2ml…kkk…2023/2/351基于離散對數的Hash函數

2023/2/352五、消息認證消息認證認證目的：驗證信息的發送者是真的、而不是冒充的，此為實體認證，包括信源、信宿等的認證和識別；驗證信息的完整性，此為消息認證，驗證數據在傳送或存儲過程中未被竄改、重放或延遲等。認證的理論與技術：認證和認證系統、Hash函數、數字簽名、身份證明、認證協議。2023/2/354消息認證認證系統一個純認證系統的模型如圖所示。在這個系統中的發送者通過一個公開信道將消息送給接收者，接收者不僅想收到消息本身，而且還要驗證消息是否來自合法的發送者及消息是否經過竄改。系統中的密碼分析者不僅要截收和分析信道中傳送的密報，而且可偽造密文送給接收者進行欺詐，稱其為系統的干擾者(Tamper)更加貼切。實際認證系統可能還要防止收、發之間的相互欺詐。2023/2/355消息認證信道干擾者認證編碼器認證譯碼器信源信宿密鑰源認證信道純認證系統模型2023/2/356消息認證認證系統的組成鑒別編碼器和鑒別譯碼器可抽象為鑒別函數。