新編密碼學 課件 第6章 Hash函數

6.1Hash函數的基本概念

6.2迭代的Hash函數

6.3MD5算法與SHA-1算法

6.4SM3算法6.1Hash函數的基本概念數據的完整性是指數據從發(fā)送方產生,經過傳輸或存儲以后,沒有被以未授權的方式修改的性質。密碼學中的Hash函數在現代密碼學中扮演著重要的角色,該函數雖然與計算機應用領域中的Hash函數有關,但兩者之間存在著重要的差別。計算機應用領域中的Hash函數(也稱散列函數)是一個將任意長度的消息序列映射為較短的、固定長度的值的函數。密碼學上的Hash函數能夠保障數據的完整性,它通常被用來構造數據的“指紋”(即函數值),當被檢驗的數據發(fā)生改變時,對應的“指紋”信息也發(fā)生變化。這樣,即使數據被存儲在不安全的地方,我們也可以通過數據的“指紋”信息來檢測數據的完整性。設H是一個Hash函數,x是消息,不妨假設x是任意長度的二元序列,相應的“指紋”定義為y=H(x),Hash函數值通常也稱為消息摘要(MessageDigest)。一般要求消息摘要是固定長度的二元序列。如果消息x被修改為x',則可以通過計算消息摘要y'=H(x'),并且驗證y'=y是否成立來確認數據x是否被修改。如果y'≠y,則說明消息x被修改,從而達到檢驗消息完整性的目的。對于Hash函數的安全要求,通常用下面3個問題進行判斷。如果一個Hash函數對這3個問題都是難解的,則認為該Hash函數是安全的。用X表示所有消息的集合(有限集或無限集),Y表示所有消息摘要構成的有限集合。(1)原像問題(PreimageProblem):設H:X→Y是一個Hash函數,y∈Y,是否能夠找到x∈X,使得H(x)=y。如果對于給定的消息摘要y,原像問題能夠解決,則(x,y)是有效的。不能有效解決原像問題的Hash函數稱為單向的或原像穩(wěn)固的。(2)第二原像問題(SecondPreimageProblem):設H:X→Y是一個Hash函數,x∈X,是否能夠找到x'∈X,使得x'≠x,且H(x')=H(x)。如果第二原像問題能夠解決,則(x',H(x))是有效的二元組。不能有效解決第二原像問題的Hash函數稱為第二原像穩(wěn)固的。(3)碰撞問題(CollisionProblem):設H:X→Y是一個Hash函數,是否能夠找到x,x'∈X,使得x'≠x,且H(x')=H(x)。對于碰撞問題的有效解決并不能直接產生有效的二元組,但是,如果(x,y)是有效的二元組,且x',x是碰撞問題的解,則(x',y)也是一個有效的二元組。不能有效解決碰撞問題的Hash函數稱為碰撞穩(wěn)固的。實際應用中的Hash函數可分為簡單的Hash函數和帶密鑰的Hash函數。一個帶密鑰的Hash函數通常作為消息認證碼。假定Alice和Bob有一個共享的密鑰k,通過該密鑰可以產生一個Hash函數Hk。對于消息x,Alice和Bob都能夠計算出相應的消息摘要y=Hk(x)。Alice通過公共通信信道將二元組(x,y)發(fā)送給Bob,Bob接收到(x,y)后,通過檢驗y=Hk(x)是否成立來確定消息x的完整性。如果y=Hk(x)成立,說明消息x和消息摘要y都沒有被篡改。一個帶密鑰的Hash函數族包括以下構成要素:(1)X:所有消息的集合(有限集或無限集)。(2)Y:所有消息摘要構成的有限集合。(3)K:密鑰空間,是所有密鑰的有限集合。(4)對任意的k∈K,都存在一個Hash函數Hk∈H,Hk:X→Y。如果Hk(x)=y,則稱二元組(x,y)∈X×Y在密鑰k下是有效的。Hash函數的目的是為文件、報文或其他分組數據提供完整性檢驗,要實現這個目的,設計的Hash函數H必須具備以下條件:(1)H能夠用于任何大小的數據分組。(2)H產生定長的輸出。(3)對任意給定的消息x,H(x)要易于計算,便于軟件和硬件實現。(4)對任意給定的消息摘要y,尋找x使得y=H(x)在計算上是不可行的。(5)對任意給定的消息x,尋找x',x'≠x,使得H(x)=H(x')在計算上是不可行的。(6)尋找任意的(x,x'),使得H(x)=H(x')在計算上是不可行的。以上6個條件中,前3個條件是Hash函數能夠用于消息認證的基本要求,第4個條件是指Hash函數具有單向性,第5個條件用于消息摘要被加密時防止攻擊者的偽造(即能夠抵抗弱碰撞),第6個條件用于防止生日攻擊(即能夠抵抗強碰撞)。條件(4)(5)和(6)意味著Hash函數具有3個一般特性:抗原像特性、抗第二原像特性、碰撞特性。Hash函數的目的是確定消息是否被修改。因此,對Hash函數攻擊的目標是生成這樣的修改后消息:其Hash函數值與原始消息的Hash函數值相等。例如,如果Oscar找到了一對消息M1

和M2,使得H(M1)=H(M2),而消息M1

是Alice發(fā)送的,那么Oscar就可以用M2

來替換M1,從而達到攻擊的目的。Oscar的問題是如何找到具有相同Hash函數值,并使Alice接受其中一條而反對另外一條的兩條消息。這可以采取窮舉搜索的方式。Oscar可以構造一組可接受的消息和一組不可接受的消息,之后計算每個消息的Hash函數值,尋找具有相同Hash函數值的消息對。這種類型攻擊法的可行性基于生日問題的解決。生日攻擊的思想來源于概率論中一個著名的問題———生日問題。該問題是:一個班級中至少要有多少個學生,才使得兩個學生生日相同的概率大于1/2,其答案是23,即只要班級中的學生人數大于23,則班上有兩個人生日相同的概率大于1/2?；谏諉栴}的生日攻擊意味著,要保證消息摘要對碰撞問題是安全的,則安全消息摘要的長度就有一個下界。如果消息摘要的長度為m位,則總的消息數為2m,因此需要檢查大約

個消息,使得兩條消息具有相同Hash函數值的概率大于50%。例如,長度為40位的消息摘要是非常不安全的,因為僅僅在220(大約為一百萬)個隨機Hash函數值中就有50%的概率發(fā)現一個碰撞。舉例來說,如果Alice使用了一個生成16位Hash函數值的Hash函數,那么Oscar所需要做的工作是構造Alice可以接受的28=256條消息和構造Alice不能接受的另外256條消息。存在50∶50的機會,使得這些消息中有兩條消息生成相同的Hash函數值。這可以通過生成8個字不同的類似消息來達到目的。6.2迭代的Hash函數本節(jié)討論一種可以將有限定義域上的Hash函數延拓到具有無限定義域上的Hash函數的方法———迭代Hash函數。1979年,Merkle基于數據壓縮函數compress建議了一個Hash函數的通用模式。壓縮函數compress接受兩個輸入:m位長度的壓縮值和t位的數據值y,并生成一個m位的輸出。Merkle建議的內容是:數據值由消息分組組成,對所有數據分組進行迭代處理。在本節(jié)中,我們假設Hash函數的輸入和輸出都是位串。我們把位串的長度記為|x|,把位串x和y的串聯記為x‖y。下面給出一種構造無限定義域上Hash函數H的方式,該方式將一個已知的壓縮函數compress:{0,1}m+1→{0,1}m(m≥1,t≥1)擴展為具有無限長度輸入的Hash函數H。通過這種方法構造的Hash函數稱為迭代Hash函數。其系統(tǒng)結構如圖6-1所示?；趬嚎s函數compress構造迭代Hash函數包括以下3個步驟:(1)預處理:輸入一個消息x,其中|x|≥m+t+1,基于x構造相應的位串y(|y|≡0modt)的過程如下:y=y1‖y2‖…‖yr

其中,|yi|=t(1≤i≤r),r為消息分組的個數。(2)迭代壓縮:設z0是一個公開的初始位串,|z0|=m。具體的迭代過程如下:最終得到長度是m的位串zr。(3)后處理:設g:{0,1}m

→{0,1}t

是一個公開函數,定義H(x)=g(zr)。則有在上述預處理過程中常采用以下方式實現:其中,pad(x)是填充函數,一個典型的填充函數是在消息x后填入|x|的值,并填充一些額外的位,使得所得到的位串y是t的整數倍。在預處理階段,必須保證映射xy是單射(如果映射xy是一一對應的,就可能找到x≠x'使得y=y',則有H(x)=H(x'),從而設計的H將不是碰撞穩(wěn)固的),同時保證|x‖pad(x)|是t的整數倍?；趬嚎s函數compress構造迭代Hash函數的核心技術是設計一種無碰撞的壓縮函數compress,而攻擊者對算法的攻擊重點也是compress的內部結構。由于迭代Hash函數和分組密碼一樣,是由壓縮函數compress對消息x進行若干輪壓縮處理過程組成的,所以對compress的攻擊須分析各輪之間的位模式,分析過程常常需要先找到compress的碰撞。由于compress是壓縮函數,其碰撞是不可避免的,因此在設計compress時就應保證找出其碰撞在計算上是不可行的。6.3MD5算法與SHA-1算法6.3.1MD5算法的描述MD(MessageDigest,消息摘要)算法由RonRivest在1990年10月提出,1992年4月,RonRivest公布了相應的改進算法。人們通常把RonRivest在1990年提出的算法稱為MD4,把相應的改進算法稱為MD5。MD5接收任意長度的消息作為輸入,并生成128位的消息摘要作為輸出。MD5以512位的分組長度來處理消息,每一個分組又被劃分為16個32位的子分組。算法的輸出由4個32位的分組組成,它們串聯成一個128位的消息摘要。MD5的算法框圖如圖6-2所示。對于給定長度的消息x,MD5算法的具體過程需要如下3個步驟:(1)在消息x末尾添加一些額外位來填充消息,使其長度恰好比512的整數倍小64。(2)在其后附上用64位表示的消息長度信息,得到的結果序列長度恰好是512的整數倍。(3)將初始輸入A=01234567,B=89abcdef,C=fedcba98,D=76543210放在4個32位寄存器A,B,C,D里(其中0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f表示一個十六進制的數字或一個長度為4的二進制序列),MD5對每個512位的分組進行4輪處理。在完成所有4輪處理后,A,B,C,D的初值加到A,B,C,D的新值上,生成相應的消息分組的輸出。這個輸出用作處理下一個消息分組的輸入,待最后一個消息分組處理完后,寄存器A,B,C,D中保存的128位內容就是所處理消息的Hash函數值。下面分別敘述每個步驟的細節(jié)。(1)填充是絕大多數Hash函數的通用特性,正確的填充能夠增加算法的安全性。對MD5中的消息進行填充,使其長度等于448mod512,填充是由一個1后跟足夠個數的0組成的,以達到所要求的長度。這里應強調的是,即使原消息的長度達到了所要求的長度,也要進行填充因此,填充的位數大于等于1而小于等于512。(2)附加消息的長度,用上一步留出的64位來表示消息被填充前的長度。例如,原始消息的長度為704位,其二進制值為1011000000,將這個二進制值寫為64位(在開始位置添加54個0),并把它添加到消息的末尾,其結果是一個具有960+64=1024位的消息。(3)MD5的初始輸出放在4個32位寄存器A,B,C,D中,這些寄存器隨后將用于保存Hash函數的中間結果和最終結果。將4個寄存器的值賦給相應的變量AA,BB,CC,DD。然后對512位的消息分組序列應用主循環(huán),循環(huán)的次數是消息中按512位分組的分組數。每一次的主循環(huán)都有4輪操作,而且這4輪操作都很相似。每一輪進行16次操作,每次操作對AA,BB,CC,DD中的3個作一次非線性的函數g運算,g是基本邏輯函數FF,GG,HH,II之一。然后將得到的結果加上第4個變量,再加上消息的一個子分組Mj和一個常數tj(0≤j≤15),再將所得結果循環(huán)左移一個不定的數s,并加上AA,BB,CC,DD中的一個。最后用得到的結果取代AA,BB,CC,DD中的一個。MD5的分組處理框圖如圖6-3所示,壓縮函數中的單步迭代示意圖如圖6-4所示。單步基本操作定義為:AA=BB+((AA+g(BB,CC,DD)+Mj+tj)<<s)上述過程涉及4個非線性函數FF,GG,HH,II,子分組Mj,常數tj,循環(huán)左移數s,這里分別對它們進行解釋:(1)4個非線性函數FF,GG,HH,II接受3個32位字作為輸入,并按照位邏輯運算產生32位輸出。FF,GG,HH,II分別定義為FF,GG,HH,II的函數真值表如表6-1所示。(2)子分組Mj:將512位的消息分成16個子分組,每個子分組32位,共有16個組,Mj表示第j個組。Mj的使用過程為:在第1輪16個組中Mj正好被用上一次;從第2輪到第4輪則依次通過下面的置換實現:例如,第3輪ρ3(j)≡(5+3j)mod16的結果依次為5,8,11,14,1,4,7,10,13,0,3,6,9,12,15,2。(3)常

數tj:每

輪

處

理

過

程

中

需

要

加

上

常

數T(見

圖65)中

的16個

元

素tj,tj為232×abs(sinj)的整數部分,這里j以弧度為單位。圖中tj由32位的字表示。(4)循環(huán)左移數s:每輪中每步左循環(huán)移位的位數按表6-2執(zhí)行。接下來我們詳細介紹主循環(huán)中4輪操作的具體內容。第1輪操作(共包含16次操作):第2輪操作(共包含16次操作):第3輪操作(共包含16次操作):第4輪操作(共包含16次操作):在此基礎上,令A=A+AA,B=B+BB,C=C+CC,D=D+DD,輸

出H(x)=A‖B‖C‖D,得到128位的消息摘要。MD5算法具有的性質是:Hash函數的每一位均是輸入消息序列中每一位的函數。該性質保證了在Hash函數計算過程中產生基于消息x的混合重復,從而使得生成的Hash函數結果混合得非常理想,也就是說,隨機選取兩組有著相似規(guī)律性的消息序列,也很難產生相同的Hash函數值。目前,MD5算法被廣泛應用于各種領域,從密碼分析的角度看,MD5仍然被認為是一種易受到攻擊的算法,而且近年來對MD5攻擊的相關研究已取得了很大的進展。2004年,我國學者王小云給出了一種解決MD5碰撞問題的算法。因此,有必要用一個具有更長消息摘要和更能抵御已知密碼分析攻擊的Hash函數來代替目前被廣泛使用的MD5算法。下面介紹的安全Hash算法,即SHA-1算法。6.《漢語大字典》《漢語大字典》(徐中舒主編，四川辭書出版社、湖北辭書出版社1986～1990年聯合出版)共收錄單字約56000個，是目前為止收錄漢字最多、單字釋義最全的字典。所有古今文獻中出現過的漢字，幾乎都可以在該書中查到。該書對每個漢字的音、形、義都作了歷史的、全面的反映。書中系統(tǒng)整理了古今楷書漢字，并收列能反映形體演變關系的甲骨文、金文、篆書和隸書形體。除用漢語拼音字母注明字的現代讀音外，書中還收列了中古的反切，標注了上古的韻部。該書義項完備，書證豐富，詳釋字的本義、派生義、通假義，釋義比較準確。全書共8卷，按部首編排，共200個部首，同部首的按漢字筆畫從少到多排列。每分卷都附有檢字表，第8卷為“附錄和索引”，列有“筆畫檢字表”，從該表能快速查到字典所收的任何一個漢字所在的卷、頁。6.3.2SHA-1算法的描述SHA-1(SecurityHashAlgorithm,安全Hash算法)是一個產生160位消息摘要的迭代Hash函數,該算法由美國國家標準和技術協會提出,于1993年公布并作為聯邦信息處理標準。SHA-1的設計基于MD4算法,并且它在設計方面也很大程度上模仿MD4算法。2002年,NIST在SHA-1的基礎上,進一步推出了SHA-256、SHA-394、SHA-512三個版本的安全Hash算法,它們的消息摘要長度分別為256位、394位和512位。這些改進算法不僅增強了Hash算法的安全性能,而且便于與AES算法相結合。這些改進算法的基本運算結構與SHA-1算法很相似,下面主要介紹SHA-1算法的基本原理和運算流程。SHA-1的算法框圖如圖6-6所示。SHA-1算法輸入消息的最大長度不超過264,輸入的消息按照512位的分組進行處理。算法的具體操作如下:(1)填充過程。設輸入的消息序列為x,|x|表示消息序列的長度。由于SHA-1算法要求輸入消息的最大長度不超過264位,所以|x|≤264-1。用和MD5類似的方式填充消息,填充過程對輸入的消息序列進行填充使得消息長度與448模512同余(即|x|mod512=448),填充的位數范圍是1~512,填充位串的最高位為1,其余各位均為0。(2)在填充的結果序列后附加序列。用和MD5類似的方式附加消息的長度,將一個64位的序列附加到填充的結果序列后面,填充序列的值等于初始序列位串的長度值,從而得到長度是512位的分組序列。(3)對給定的5個32位的寄存器A,B,C,D,E賦初值,即其中,0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f表示一個十六進制的數字或一個長度為4的二進制序列。這5個寄存器隨后將用于保存Hash函數的中間結果和最終結果。(4)將寄存器的值賦給相應的變量AA,BB,CC,DD,EE。然后對512位的消息分組序列應用主循環(huán),循環(huán)的次數是消息中按512位進行分組的分組數。每一次的主循環(huán)都有4輪操作,并且這4輪操作都很相似。每一輪進行20次操作,每次操作對AA,BB,CC,DD,EE中的3個作一次非線性的函數Ft運算,Ft是基本邏輯函數F1,F2,F3,F4之一。然后進行與MD5算法類似的移位運算(一個5位的循環(huán)移位和一個30位的循環(huán)移位)和加運算。最后用得到的結果取代AA,BB,CC,DD中的一個。SHA-1的分組處理框圖如圖6-7所示,壓縮函數中的單步迭代示意圖如圖6-8所示。主循環(huán)包括:當0≤t≤79時,(1)A=A+AA,B=B+BB,C=C+CC,D=D+DD,E=E+EE。(2)輸出H(x)=A‖B‖C‖D‖E,得到160位的消息摘要。SHA-1算法中的非線性函數定義為函數F1,F2,F3,F4的真值表如表63所示。與MD5使用64個常量不同,SHA-1在各個階段只加了4個常量值,分別為設y=M0‖M1‖…‖M15,其中每一個消息分組Mi都是長度為32位的字。用以下方法將消息分組從16個32位的字變成80個32位的字:SHA-1分組處理所需的80個字的產生過程如圖6-9所示。6.3.3MD5與SHA-1的比較由于MD5與SHA-1都是由MD4演化來的,所以兩個算法極為相似。下面給出MD5和SHA-1之間的比較分析。(1)抗窮舉搜索攻擊的強度:MD5與SHA-1的消息摘要長度分別為128位和160位,由于SHA-1生成的消息摘要長度比MD5算法生成的消息摘要長度要長32位,所以用窮舉搜索攻擊尋找具有給定消息摘要的消息分別需要做O(2128)和O(2160)次運算,而窮舉搜索攻擊找到具有相同消息摘要的兩個不同消息分別需要做O(264)和O(280)次運算,因此SHA-1抗擊窮舉搜索攻擊的強度高于MD5抗擊窮舉搜索攻擊的強度。一般認為,SHA-1是抗密碼分析的,而MD5算法可能是易于受到攻擊的。(2)速度:由于MD5與SHA-1的主要運算都是模232加法,因此都易在32位結構上實現。但比較起來,SHA-1的迭代步數(80步)多于MD5的迭代步數(64步),所用的緩沖區(qū)(160位)大于MD5使用的緩沖區(qū)(128位),因此在相同硬件上實現時,SHA-1的速度要比MD5的速度慢。(3)簡潔與緊致性:MD5與SHA-1描述起來都較為簡單,實現起來也較為簡單,均不需要較大的程序和代換表。6.4SM3算法6.4.1SM3算法的描述2012年,國家商用密碼管理辦公室發(fā)布了SM3密碼雜湊算法,并將其作為密碼行業(yè)標準(GM/T0004—2012)。2016年,國家標準化委員會公布了SM3密碼雜湊算法為國家標準(GB/T32905—2016)。目前,SM3密碼雜湊算法已經提交ISO國際標準化組織。SM3密碼雜湊算法的消息分組長度為512位,輸出摘要長度為256位。壓縮函數的狀態(tài)有256位,共64步操作。1.SM3密碼雜湊算法的初始化(1)SM3密碼雜湊算法中用到的初始向量IV共256位,由8個32位的字串聯組成,具體值為(2)SM3雜湊算法需要用到的常量定義如下:(3)SM3雜湊算法使用的布爾函數定義為(4)SM3雜湊算法使用的置換函數定義為(5)對于長度為l位的消息m,SM3密碼雜湊算法首先將位“1”添加到消息的末尾,然后再添加k個“0”位,其中k是滿足l+k+1≡448mod512的最小非負整數,最后添加一個64位的位串,該位串是消息長度l的二進制表示。填充后的消息m'的位長為512的倍數。2.SM3密碼雜湊算法的迭代過程將填充后的消息m'按照512位為一組進行消息分組其中,n=(l+k+1)/512。對消息分組進行多輪迭代其中,CF是SM3的壓縮函數,初始值V(0)為256位的初始向量IV,B(i)為填充后的消息分組。迭代過程輸出的結果為V(n)。3.SM3密碼雜湊算法的壓縮函數SM3密碼雜湊算法的核心是壓縮函數CF。壓縮函數由消息擴展過程和狀態(tài)更新過程組成。具體描述如下:1)消息擴展過程將消息分組B(i)按照以下方式擴展生成132個字,并用于壓縮函數CF。(1)將消息分組B(i)劃分成16個字W0,W1,…,W15。(2)循環(huán)52次生成52個字,即(3)循環(huán)64次生成最后64個字,即SM3密碼雜湊算法的消息擴展過程如圖6-10所示。2)狀態(tài)更新過程設A,B,C,D,E,F,G,H為寄存器,