第5章散列函數(shù)和消息鑒別1

第1章密碼學(xué)概述 第2章古典密碼技術(shù) 第3章分組密碼第4章公鑰密碼體制第5章散列函數(shù)與消息鑒別第6章數(shù)字簽名技術(shù)

第7章密鑰管理技術(shù)第8章身份鑒別技術(shù)第9章序列密碼第10章密碼技術(shù)應(yīng)用附錄課程主要內(nèi)容第5章散列函數(shù)與消息鑒別本章主要內(nèi)容

散列函數(shù)的概念

散列函數(shù)的構(gòu)造與設(shè)計 安全散列算法SHA對散列函數(shù)的攻擊消息鑒別

第5章散列函數(shù)與消息鑒別5.1散列函數(shù)的概念

密碼學(xué)中的散列函數(shù)又稱為哈希函數(shù)（Hash函數(shù)）、雜湊函數(shù)，它是一種單向密碼體制，是一個從明文到密文的不可逆映射，只有加密過程，不能解密。

散列函數(shù)的性質(zhì)設(shè)散列函數(shù)為h(m)，具有以下基本特性：

（1）h(m)算法公開，不需要密鑰。（2）具有數(shù)據(jù)壓縮功能，可將任意長度的輸入數(shù)據(jù)轉(zhuǎn)換成一個固定長度的輸出。（3）對任何給定的m，h(m)易于計算。散列函數(shù)必須滿足以下安全性要求：（1）具有單向性。給定消息的散列值h(m)，要得到消息m在計算上不可行；（2）具有弱抗碰撞性（Weakcollisionresistance）。對任何給定的消息m，尋找與m不同的消息m’，使得它們的散列值相同，即h(m’)＝h(m)，在計算上不可行。（3）具有強抗碰撞性（Strongcollisionresistance)。尋找任意兩個不同的消息m和m’，使得h(m)＝h(m’)在計算上不可行。第5章散列函數(shù)與消息鑒別散列函數(shù)的應(yīng)用散列函數(shù)的主要應(yīng)用有以下三個方面：

1）保證數(shù)據(jù)的完整性

2）單向數(shù)據(jù)加密

3）數(shù)字簽名應(yīng)用散列函數(shù)實現(xiàn)數(shù)據(jù)完整性保護的模型：

注：實際應(yīng)用中，未必一定是如h(m‖k)的計算方式，明文與密鑰k的組合方式因不同的實現(xiàn)可以不同。第5章散列函數(shù)與消息鑒別

算法中重復(fù)使用一個函數(shù)f

。函數(shù)f的輸入有兩項，一項是上一輪（第i-1輪）的輸出CVi-1，稱為鏈接變量，另一項是算法在本輪（第i輪）b位的輸入分組mi。5.2散列函數(shù)的構(gòu)造與設(shè)計

迭代型散列函數(shù)的一般結(jié)構(gòu)整個散列函數(shù)的邏輯關(guān)系可表示為：CV0=IV；CVi=f（CVi-1，mi）；1≤i≤t；h（M）=CVt第5章散列函數(shù)與消息鑒別雖然在合理的假設(shè)下，可以證明這類散列函數(shù)是安全的，由于它的計算效率太低，所以這一類散列函數(shù)并沒有什么實用價值。

散列函數(shù)的基本設(shè)計方法有：基于公開密鑰密碼算法的設(shè)計、基于對稱分組密碼算法的設(shè)計以及直接設(shè)計法。1.基于公開密鑰密碼算法設(shè)計散列函數(shù)散列函數(shù)的設(shè)計方法以CBC模式利用公開密鑰算法，使用公鑰PK以及初始變量IV對消息分組進行加密，并輸出最后一個密文分組ct作為散列函數(shù)輸出值，如圖5.3所示。第5章散列函數(shù)與消息鑒別

基于分組密碼的CBC工作模式和CFB工作模式的散列函數(shù)中，密鑰k不能公開。如果密鑰k公開，則會使得攻擊者構(gòu)造消息碰撞十分容易。

通常，可以使用對稱密鑰分組密碼算法的CBC模式或CFB模式來產(chǎn)生散列值，如圖5.4、圖5.5所示。2.基于對稱分組密碼算法設(shè)計散列函數(shù)第5章散列函數(shù)與消息鑒別3.直接設(shè)計散列函數(shù)這類散列函數(shù)并不基于任何假設(shè)和密碼體制，它是通過直接構(gòu)造復(fù)雜的非線性關(guān)系達到單向性要求來設(shè)計單向散列函數(shù)。這類散列算法典型的有：MD2、MD4、MD5、SHA-1等算法。5.3安全散列算法SHA

1.SHA-1SHA-1是數(shù)字簽名標(biāo)準(zhǔn)DSS（DigtialSignatureStandard）中使用的散列算法。它能夠處理最大長度為2^{64}位的輸入數(shù)據(jù)，輸出為160位的散列函數(shù)值。

Ⅰ.基本操作和元素:(1)逐位邏輯運算(2)加法運算(3)移位操作f1,K,W[0…19]20stepsf2,K,W[20…39]20stepsf3,K,W[40…59]20stepsf4,K,W[60…79]20steps++++ABCEAEAEAEH(i-1)16032Xi512H(i)160SHA-1Processingofasingle512-bitblock+ismod232DBCDBCDBCD+Step FunctionName FunctionValue(0t19) ft=f(t,B,C,D) (BC)(￢BD)(20t39) f2=f(t,B,C,D) BCD(40t59) f3=f(t,B,C,D) (BC)(BD)(CD)(60t79) f4=f(t,B,C,D) BCDWt=(Wt-16

Wt-14Wt-8Wt-3)<<<1Yq512bitsW0W1W15W16

S1XORW0W2W8W13Wt

S1XORWt-16Wt-14Wt-8Wt-3W79

S1XORW63W65W71W76第5章散列函數(shù)與消息鑒別(1)消息分割與填充(2)初始化緩沖區(qū)(3)處理第i個數(shù)據(jù)塊xi(4)4輪循環(huán)，80步操作完成后，保存散列中間結(jié)果，再與第一輪的輸入相加（模2^{32}）(5)然后，以H0(i)

，H1(i)

，H2(i)

，H3(i)

，H4(i)作為寄存器初值，用于對分組xi+1進行散列處理。SHA-1壓縮函數(shù)操作過程，如圖5.9所示(下頁)，是處理一個512位分組的4次循環(huán)中每一循環(huán)的基本壓縮操作流程。Ⅱ.SHA的散列過程Ⅲ.SHA-1的壓縮操作第5章散列函數(shù)與消息鑒別Ⅳ.示例

【例5.1】計算字符串“abc”的SHA-1散列值。字符串“abc”的二進制表示為：011000010110001001100011，共有24位的長度。按照SHA-1的填充要求，應(yīng)該填充一個“1”(界符)和423個“0”，最后有兩個字“0000000000000018”(十六進制)，表明原始消息的長度為24位。本例中共只有一個分組。第5章散列函數(shù)與消息鑒別初始五個寄存器的初始值為：

H0(0)=67452301，H1(0)=EFCDAB89，H2(0)=98BADCFE，H3(0)=10325476，H4(0)=C3D2E1F0進行迭代計算，前16個32位字的值剛好取自這個分組的所有字，即：

W0=61626380(即01100001011000100110001110000000)，

W1=W2=……=W14=00000000，W15=00000018。對t=0～79計算得到各個寄存器中的值。最后得到結(jié)果為：H0=67452301+42541B35=A9993E36，H1=EFCDAB89+5738D5E1=4706816A，H2=98BADCFE+21834873=BA3E2571，H3=10325476+681E6DF6=7850C26C，H4=C3D2E1F0+D8FDF6AD=9CD0D89D。于是：SHA-1(“abc”)=A9993E364706816ABA3E25717850C26C9CD0D89D，共160位，20個字節(jié)。

第5章散列函數(shù)與消息鑒別Ⅴ.其他SHA算法2002年，NIST在FIPSl80-1的基礎(chǔ)上做了修改，發(fā)布了推薦的修訂版本FIPS180-2。在這個標(biāo)準(zhǔn)中，除了SHA-1外，還新增了SHA-256、SHA-398和SHA-512三個散列算法標(biāo)準(zhǔn)，它們的消息摘要長度分別為256位、398位和512位，以便與AES的使用相匹配。SHA系列散列算法的基本運算結(jié)構(gòu)有很大的相似性。

SHA-1，SHA-256的數(shù)據(jù)分組都是512位。SHA-384，SHA-512的數(shù)據(jù)分組則是1024位。SHA-1，SHA-256，SHA-384，SHA-512的比較表5.4是它們基本參數(shù)的比較：第5章散列函數(shù)與消息鑒別目前對于散列函數(shù)的攻擊方法可以分為兩類：對散列函數(shù)的攻擊是指攻擊者尋找一對產(chǎn)生碰撞的消息的過程。評價散列函數(shù)的有效方法就是看一個攻擊者找到一對產(chǎn)生碰撞的消息所花的代價有多高。第一類稱為窮舉攻擊（或暴力攻擊），它能對任何類型的散列函數(shù)進行攻擊，其中最典型的方法就是“生日攻擊”。第二類稱為密碼分析法，這類攻擊方法依賴于對散列函數(shù)的結(jié)構(gòu)和代數(shù)性質(zhì)分析，采用針對散列函數(shù)弱性質(zhì)的方法進行攻擊。這類攻擊方法有中間相遇攻擊、差分分析等。生日悖論

我們來考慮這樣一個有趣的問題：在一個教室中最少應(yīng)有多少學(xué)生才使得至少有兩個學(xué)生的生日在同一天的概率大于0.5？計算與此相關(guān)的概率被稱為生日悖論問題。5.4對散列函數(shù)的攻擊第5章散列函數(shù)與消息鑒別生日攻擊與散列函數(shù)相關(guān)的類似問題可表述如下：給定一個散列函數(shù)h的輸出長度為m位，共有2m個可能的散列值輸出，如果讓散列函數(shù)h接收k個隨機輸入產(chǎn)生集合X，再使用另外k個隨機輸入產(chǎn)生集合Y，問k必須為多大才能使兩個集合產(chǎn)生相同散列值輸出的概率大于0.5？這種尋找散列函數(shù)h的具有相同輸出的兩個任意輸入的攻擊方式稱為生日攻擊。5.5消息鑒別消息鑒別是一個過程，用以驗證接收消息的真實性（的確是由它所聲稱的實體發(fā)來的）和完整性（未被篡改、插入、刪除），同時還用于驗證消息的順序性和時間性（未被重排、重放、延遲等）。消息鑒別對于開放的網(wǎng)絡(luò)中的各種信息系統(tǒng)的安全性具有重要作用。大體來說，實現(xiàn)消息鑒別的手段可以分為兩類：基于加密技術(shù)的消息鑒別和基于散列函數(shù)的消息鑒別。第5章散列函數(shù)與消息鑒別基于加密技術(shù)的消息鑒別從消息鑒別的目的出發(fā)，無論是對稱密碼體制，還是公鑰密碼體制，對于消息本身的加密都可以看作是一種鑒別的手段。（1）利用對稱加密體制實現(xiàn)消息鑒別如圖5.10所示，發(fā)送方A和接收方B共享密鑰k。A用密鑰k對消息M加密后通過公開信道傳送給B。B接收到密文消息之后，通過是否能用密鑰k將其恢復(fù)成合法明文，來判斷消息是否來自A，信息是否完整。第5章散列函數(shù)與消息鑒別該方法的特點是：1）它能提供機密性：只有A和B知道密鑰k；2）提供鑒別：只能發(fā)自A，傳輸中未被改變；3）不能提供數(shù)字簽名：接收方可以偽造消息，發(fā)送方可以抵賴消息的發(fā)送。（2）利用公鑰密碼體制實現(xiàn)消息鑒別①提供消息鑒別如圖5.11所示，發(fā)送方A用自己的私鑰SKA對消息進行加密運算（但并不能提供機密性保護，請思考為什么？），再通過公開信道傳送給接收方B。接收方B用A的公鑰PKA對得到的消息進行解密運算并完成鑒別。第5章散列函數(shù)與消息鑒別這種方法的特點是：能實現(xiàn)數(shù)字簽名的功能，可以抗抵賴，并提供鑒別。②提供消息鑒別和機密性保護如圖5.12所示，在發(fā)送方A用自己的私鑰SKA進行加密運算（實現(xiàn)數(shù)字簽名）之后，還要用接收方B的公鑰PKB進行加密，從而實現(xiàn)機密性。缺點：一次完整的通信需要執(zhí)行公鑰算法的加密、解密操作各兩次。優(yōu)點：提供機密性、數(shù)字簽名和鑒別。第5章散列函數(shù)與消息鑒別(1)消息鑒別碼的概念基于散列函數(shù)的消息鑒別消息鑒別碼(MAC，MessageAuthenticationCode)或報文鑒別碼，是用于提供數(shù)據(jù)原發(fā)鑒別和數(shù)據(jù)完整性的密碼校驗值。MAC是使用一個特定的密鑰將消息通過一種鑒別算法處理所得出的一串代碼。一個MAC算法是由一個秘密密鑰k和參數(shù)化的一簇函數(shù)hk構(gòu)成。這簇函數(shù)具有如下特性：a)容易計算——對于一個已知函數(shù)h，給定一個值k和一個輸入x，hk(x)是容易計算的。這個計算的結(jié)果被稱為消息鑒別碼值或消息鑒別碼。b)壓縮——hk把任意具有有限長度（比特數(shù)）的一個輸入x映射成一個具有固定長度的輸出hk(x)。c)強抗碰撞性——要找到兩個不同消息x和y，使得hk(x)=hk(y)是計算上不可行的。第5章散列函數(shù)與消息鑒別①提供消息鑒別的方法（圖5.13）：②提供消息鑒別和機密性的方法（圖5.14，圖5.15）：第5章散列函數(shù)與消息鑒別（2）基于散列函數(shù)的消息鑒別散列函數(shù)具有以下特點：輸入是可變大小的消息M，輸出固定長度的散列值(即消息摘要)；計算簡單，不需要使用密鑰，具有強抗碰撞性?；谏⒘泻瘮?shù)的消息鑒別方法如圖5.16所示，有以下幾種情況：（1）用對稱密碼體制加密消息及其散列值，如圖5.16(a)。（2）用對稱密碼體制只對消息的散列值進行加密，如圖5.16(b)。（3）用公鑰密碼體制只對散列值進行加密運算，如圖5.16(c)。第5章散列函數(shù)與消息鑒別（4）結(jié)合使用公鑰密碼體制和對稱密碼體制，這種方法用發(fā)送方的私鑰對散列值進行數(shù)字簽名，用對稱密碼體制加密消息M和得到的數(shù)字簽名，如圖5.16(d)。（5）這種方法使用了散列算法，但未使用加密算法。（6）在方法(5)的基礎(chǔ)上，使用對稱密碼體制對消息M和生成的散列值進行保護，如圖5.16(f)。第5章散列函數(shù)與消息鑒別第5章散列函數(shù)與消息鑒別HMAC算法基于散列函數(shù)的消息鑒別碼構(gòu)造的基本思想就是將某個散列函數(shù)嵌入到消息鑒別碼的構(gòu)造過程中。HMAC作為這種構(gòu)造方法的代表，已經(jīng)作為RFC2104公布，并在IPSec和其他網(wǎng)絡(luò)協(xié)議(如SSL)中得到應(yīng)用。1.HMAC算法的設(shè)計要求：按照RFC2104，HMAC希望達到以下的設(shè)計要求：（1）——可不經(jīng)修改而使用現(xiàn)有的散列函數(shù)，特別是那些易于軟件實現(xiàn)的、源代碼可方便獲取且免費使用的散列函數(shù)。（2）——其中嵌入的散列函數(shù)可以易于替換為更快或更安全的散列函數(shù)，以適應(yīng)不同的安全需求。（3）——保持嵌入的散列函數(shù)的原有性能，不因用于HAMC而使其性能降低。（4）——密鑰的使用和處理簡單方便。（5）——以嵌入的散列函數(shù)安全假設(shè)為基礎(chǔ)，易于分析HMAC用于鑒別時的安全強度。第5章散列函數(shù)與消息鑒別

2.HMAC算法描述圖5.17是HMAC算法的實現(xiàn)框圖。其中h為嵌入的散列函數(shù)(如MD5、SHA-1);輸入消息M=(Y0，Y1，……，YL-1)，

Yi(0≤i≤L-1)是b位的一個分組，M包含了散列函數(shù)的填充位。

n為嵌入的散列函數(shù)輸出值的長度，