第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è)計(jì) 安全散列算法SHA對散列函數(shù)的攻擊消息鑒別

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

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

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

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

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

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

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

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

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

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

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

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

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

通常，可以使用對稱密鑰分組密碼算法的CBC模式或CFB模式來產(chǎn)生散列值，如圖5.4、圖5.5所示。2.基于對稱分組密碼算法設(shè)計(jì)散列函數(shù)第5章散列函數(shù)與消息鑒別3.直接設(shè)計(jì)散列函數(shù)這類散列函數(shù)并不基于任何假設(shè)和密碼體制，它是通過直接構(gòu)造復(fù)雜的非線性關(guān)系達(dá)到單向性要求來設(shè)計(jì)單向散列函數(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)逐位邏輯運(yùn)算(2)加法運(yùn)算(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個(gè)數(shù)據(jù)塊xi(4)4輪循環(huán)，80步操作完成后，保存散列中間結(jié)果，再與第一輪的輸入相加（模2^{32}）(5)然后，以H0(i)

，H1(i)

，H2(i)

，H3(i)

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

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

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

W0=61626380(即01100001011000100110001110000000)，

W1=W2=……=W14=00000000，W15=00000018。對t=0～79計(jì)算得到各個(gè)寄存器中的值。最后得到結(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個(gè)字節(jié)。

第5章散列函數(shù)與消息鑒別Ⅴ.其他SHA算法2002年，NIST在FIPSl80-1的基礎(chǔ)上做了修改，發(fā)布了推薦的修訂版本FIPS180-2。在這個(gè)標(biāo)準(zhǔn)中，除了SHA-1外，還新增了SHA-256、SHA-398和SHA-512三個(gè)散列算法標(biāo)準(zhǔn)，它們的消息摘要長度分別為256位、398位和512位，以便與AES的使用相匹配。SHA系列散列算法的基本運(yùn)算結(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)生碰撞的消息的過程。評價(jià)散列函數(shù)的有效方法就是看一個(gè)攻擊者找到一對產(chǎn)生碰撞的消息所花的代價(jià)有多高。第一類稱為窮舉攻擊（或暴力攻擊），它能對任何類型的散列函數(shù)進(jìn)行攻擊，其中最典型的方法就是“生日攻擊”。第二類稱為密碼分析法，這類攻擊方法依賴于對散列函數(shù)的結(jié)構(gòu)和代數(shù)性質(zhì)分析，采用針對散列函數(shù)弱性質(zhì)的方法進(jìn)行攻擊。這類攻擊方法有中間相遇攻擊、差分分析等。生日悖論

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

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

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

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