Hash函數(shù)與消息認證

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

2023/2/31一、Hash函數(shù)概述

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

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

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

2023/2/34

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

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

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

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

Hash函數(shù)的安全性：Hash函數(shù)的安全性取決于其抗擊各種攻擊的能力，對手的目標是找到兩個不同消息映射為同一雜Hash值。一般假定對手知道Hash算法，采用選擇明文攻擊法。2023/2/310Hash函數(shù)對Hash函數(shù)的基本攻擊方法窮舉攻擊法：給定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函數(shù)對Hash函數(shù)的基本攻擊方法

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

2023/2/313

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

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

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

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

m<n。有數(shù)據(jù)擴展的映射。認證碼屬于此類。

2023/2/315

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

Hash函數(shù)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函數(shù)組合明/密文鏈接法：

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函數(shù)

B.Preneel總結(jié)的下述12種基本方式構(gòu)造的分組迭代Hash函數(shù)。令E是迭代函數(shù)，它可以是一種分組加密算法，E(K,X)，K是密鑰，X是輸入數(shù)據(jù)組或某種壓縮算法。令消息分組為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函數(shù)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函數(shù)MD5Hash函數(shù)MD5設(shè)計目標：

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

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

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

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

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

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

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

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

2023/2/325Hash函數(shù)MD5

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

ab＋CLSS(a＋g(B,C,D)＋X[k]＋T[i])其中a,b,c,d=緩存器中的四個字，按特定次序變化。g=基本邏輯函數(shù)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函數(shù)CLSs：32-bit存數(shù)循環(huán)左移s位。X[k]=M[q×16＋k]：消息的第q-512-bit組的第k個32-bit字T[i]：232×abs(sin(i))的整數(shù)部分。＋：模232加法。

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

Hash函數(shù)

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

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

2023/2/332

Hash函數(shù)

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

2023/2/333

Hash函數(shù)

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

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

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

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

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

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

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

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

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

5A8279990≤t≤196ED9EBA120≤t≤39Kt＝8F1BDBDC40≤t≤59CA62C1D660≤t≤79當L組運算結(jié)束后，由第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為步數(shù)，f(t,B,C,D)為第t步的邏輯函數(shù)。Sk為左旋轉(zhuǎn)移位k位。Wt為由512比特的輸入組導(dǎo)出32比特的第t塊。Kt為附加的常數(shù)。+為mod232的加法。2023/2/342AEDCBAEDCBfS5S30++++WtKt2023/2/343安全Hash算法SHA

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

(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高。兩者都比較容易實現(xiàn)。R.L.Rivest公開了MD-5的設(shè)計決策，但SHA的設(shè)計者則不愿公開。2023/2/345四、基于分組密碼與離散對數(shù)的Hash函數(shù)基于分組密碼的Hash函數(shù)利用DES構(gòu)造Hash函數(shù)我們將介紹利用DES構(gòu)造Hash函數(shù)的若干模式，實際上也是利用和DES類似的明文、密文長度和密鑰長度一樣的分組密碼來構(gòu)造Hash函數(shù)的模式。設(shè)m=m1m2…ml,m=m1m2…ml

都是64比特的明文塊，k是密鑰，也是64比特。2023/2/347基于分組密碼的Hash函數(shù)第1種構(gòu)造模式S1:i←1,K←k;S2:K←DESk(mi),i←i+1;S3:若i≤l,則轉(zhuǎn)S2,否則作Hk(m)←KkDESDESDESm1m2ml…Hk(m)2023/2/348基于分組密碼的Hash函數(shù)第2種構(gòu)造模式S1:i←1,S←S0;S2:mi←miS,S←DESk(mi),S3:若i≤l;則轉(zhuǎn)S2,否則作Hk(m)←SS0DESDESDESm1m2ml…kkk2023/2/349基于分組密碼的Hash函數(shù)第3種構(gòu)造模式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;則轉(zhuǎn)S2,否則作Hk(m)←Hi+1；其中V為和k類似的參數(shù)，H0

和M0

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

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