現(xiàn)代密碼學(xué)-Hash函數(shù)與消息認(rèn)證-1110市公開課一等獎(jiǎng)省名師優(yōu)質(zhì)課賽課一等獎(jiǎng)?wù)n件

當(dāng)代密碼學(xué)二十一世紀(jì)高等學(xué)校計(jì)算機(jī)規(guī)劃教材Modern

Cryptography彭代淵信息科學(xué)與技術(shù)學(xué)院dypeng@.9-.1作者：何大可彭代淵唐小虎何明星梅其祥出版社：人民郵電出版社1當(dāng)代密碼學(xué)

Modern

Cryptography彭代淵信息科學(xué)與技術(shù)學(xué)院dypeng@11月第5章Hash函數(shù)與消息認(rèn)證

2第5章Hash函數(shù)與消息認(rèn)證5.1Hash函數(shù)概述5.2Hash函數(shù)MD55.3安全Hash算法SHA15.4基于分組密碼與離散對數(shù)Hash函數(shù)5.5消息認(rèn)證35.1Hash函數(shù)概述5.1.1Hash函數(shù)定義5.1.2Hash函數(shù)安全性5.1.3Hash函數(shù)迭代結(jié)構(gòu)法45.1.1Hash函數(shù)定義數(shù)據(jù)安全機(jī)密性完整性認(rèn)證性密碼技術(shù)主要確保數(shù)據(jù)機(jī)密性Hash函數(shù)能確保數(shù)據(jù)完整性和認(rèn)證性55.1.1Hash函數(shù)定義Hash函數(shù)定義：Hash函數(shù)是一個(gè)將任意長度消息（message）映射成固定長度消息函數(shù)。將h稱為一個(gè)Hash函數(shù)（hashfunction），或稱為哈希函數(shù)、散列函數(shù)。對于任何消息x，將h(x)稱為xHash值、散列值、消息摘要（messagedigest）。65.1.1Hash函數(shù)定義Hash函數(shù)碰撞（collision）

設(shè)x、x’是兩個(gè)不一樣消息，假如h(x)=h(x’)則稱x和x’是Hash函數(shù)h一個(gè)（對）碰撞.75.1.1Hash函數(shù)定義Hash函數(shù)分類單向Hash函數(shù)（oneway）給定一個(gè)Hash值y，假如尋找一個(gè)消息x，使得y=h(x)是計(jì)算上不可行，則稱h是單向Hash函數(shù).弱抗碰撞Hash函數(shù)（weaklycollisionfree）任給一個(gè)消息x，假如尋找另一個(gè)不一樣消息x’，使得h(x)=h(x’)是計(jì)算上不可行，則稱h是弱抗碰撞Hash函數(shù).強(qiáng)抗碰撞Hash函數(shù)（stronglycollisionfree）假如尋找兩個(gè)不一樣消息x和x’，使得h(x)=h(x’)是計(jì)算上不可行，則稱h是強(qiáng)抗碰撞Hash函數(shù).85.1.1Hash函數(shù)定義安全Hash函數(shù)h應(yīng)含有以下性質(zhì)：對任意消息x，計(jì)算h(x)是輕易；

h是單向；

h是弱抗碰撞，或是強(qiáng)抗碰撞。95.1Hash函數(shù)概述5.1.1Hash函數(shù)定義5.1.2Hash函數(shù)安全性5.1.3Hash函數(shù)迭代結(jié)構(gòu)法105.1.2Hash函數(shù)安全性對Hash函數(shù)攻擊是指尋找一對碰撞消息過程生日悖論（birthdayparadox）生日問題：假設(shè)每個(gè)人生日是等概率，每年有365天，在k個(gè)人中最少有兩個(gè)人生日相同概率大于1/2，問k最小應(yīng)是多少？k人生日都不一樣概率是：有P(365,23)=0.5073。即在23個(gè)人中，最少有兩個(gè)人生日相同概率大于0.5，這個(gè)數(shù)字比人們直觀猜測結(jié)果小得多，因而稱為生日悖論。11生日攻擊法生日悖論原理能夠用于結(jié)構(gòu)對Hash函數(shù)攻擊設(shè)Hash函數(shù)值有n個(gè)比特，m是真消息，M是偽造假消息，分別把消息m和M表示成r和R個(gè)變形消息。消息與其變形消息含有不一樣形式，但有相同含義。將消息表示成變形消息方法很多，比如增加空格、使用縮寫、使用意義相同單詞、去掉無須要單詞等。5.1.2Hash函數(shù)安全性125.1.2Hash函數(shù)安全性生日攻擊法分別把消息m和M表示成r和R個(gè)變形消息13生日攻擊法計(jì)算真消息m變形與假消息M變形發(fā)生碰撞概率

因?yàn)閚比專長散列值共有2n個(gè)，所以對于給定m變形mi和M變形Mj，mi與Mj不碰撞概率是1-1/2n。因?yàn)镸共有R個(gè)變形，所以M全部變形都不與mi碰撞概率是：

因?yàn)橄共有r個(gè)變形，所以m變形與M變形都不碰撞概率是：m變形與M變形發(fā)生碰撞概率是：5.1.2Hash函數(shù)安全性14生日攻擊法

當(dāng)r=R=2n/2時(shí)，P(n)=1e10.63。對于Hash值長度為64比特Hash函數(shù)，生日攻擊時(shí)間復(fù)雜度約為232，所以是不安全。為了抵抗生日攻擊，提議Hash值長度最少為128比特.5.1.2Hash函數(shù)安全性15中間相遇攻擊（in-the-middleattack）用于攻擊一類含有特殊結(jié)構(gòu)Hash函數(shù)分析Hash函數(shù)運(yùn)算中間值相等概率討論一類利用加密變換結(jié)構(gòu)Hash函數(shù)設(shè)加密體制為：

對于消息m=(m1,m2)，其散列值計(jì)算分以下兩步：（1）h1=EK(m1,IV)；（2）d=h(m)=EK(m2,h1)，其中IV是加密變換初始值。這類Hash函數(shù)將遭受中間相遇攻擊。5.1.2Hash函數(shù)安全性16中間相遇攻擊（in-the-middleattack）用于攻擊一類含有特殊結(jié)構(gòu)Hash函數(shù)分析Hash函數(shù)運(yùn)算中間值相等概率討論一類利用加密變換結(jié)構(gòu)Hash函數(shù)攻擊方式:假設(shè)攻擊者要找出一個(gè)假消息M=(M1,M2)，使得M與m是一個(gè)碰撞。設(shè)m散列值都為d。攻擊者首先產(chǎn)生消息M1r個(gè)變形，消息M2R個(gè)變形.5.1.2Hash函數(shù)安全性17中間值集合假消息第1部分M1變形M1,1EKM1,2EKM1,rEKIVM2,2DKM2,RDK假消息第2部分M2M2,1DKd目標(biāo)摘要5.1.2Hash函數(shù)安全性h1=EK(m1,IV)d=h(m)=EK(m2,h1)

185.1.2Hash函數(shù)安全性

這里DK是解密變換。假設(shè)加密變換EK是隨機(jī)，那么能夠使用生日攻擊法來分析集合H1和H2中出現(xiàn)相同元素概率。假如集合H1與H2有相同元素，比如h1,i=h2,j=DK(M2,j,d)，則有d=EK(M2,

j,h1,i

)，即M與m有相同散列值d。h1=EK(m1,IV)d=h(m)=EK(m2,h1)

195.1Hash函數(shù)概述5.1.1Hash函數(shù)定義5.1.2Hash函數(shù)安全性5.1.3Hash函數(shù)迭代結(jié)構(gòu)法205.1.3Hash函數(shù)迭代結(jié)構(gòu)法壓縮函數(shù)（compressionfunction）迭代技術(shù)

設(shè)x是一個(gè)長度為L比特串。重復(fù)應(yīng)用壓縮函數(shù)f，對消息x進(jìn)行屢次壓縮，最終得到x散列值215.1.3Hash函數(shù)迭代結(jié)構(gòu)法

計(jì)算消息x散列值h(x)步驟預(yù)處理:用一個(gè)公開算法在消息x右方添加若干比特，得到比特串y，使得y長度為t倍數(shù)。即有y=x||pad(x)=y1||y

2||…||yr

,其中|yi|=t(i=1,2,…,r)，pad(x)稱為填充函數(shù)。經(jīng)典填充函數(shù)是先添加x長度|x|值，再添加若干比特（比如0）。迭代過程:設(shè)H0=IV是一個(gè)長度為m初始比特串，重復(fù)使用壓縮函數(shù)f，依次計(jì)算Hi=f(Hi1||yi)(i=1,2,…,r).輸出變換:設(shè)g:{0,1}m{0,1}t是一個(gè)公開函數(shù)，令h(x)=g(Hr).225.1.3Hash函數(shù)迭代結(jié)構(gòu)法

用上述方法結(jié)構(gòu)Hash函數(shù)稱為迭代Hash函數(shù)。大多數(shù)實(shí)用Hash函數(shù)都是迭代Hash函數(shù)在預(yù)處理階段，必須確保變換xy是單射。因?yàn)榧偃珙A(yù)處理變換xy不是單射，則存在xx’使得y=y’，從而h(x)=h(x’)，即能夠找到h碰撞。對于任意無碰撞壓縮函數(shù)，都能夠使用迭代技術(shù)結(jié)構(gòu)一個(gè)無碰撞Hash函數(shù)。23第5章Hash函數(shù)與消息認(rèn)證5.1Hash函數(shù)概述5.2Hash函數(shù)MD55.3安全Hash算法SHA15.4基于分組密碼與離散對數(shù)Hash函數(shù)5.5消息認(rèn)證245.2Hash函數(shù)MD5MD5(MD:messagedigest,消息摘要)1990年10月,著名密碼學(xué)家R.L.Rivest在MIT(MassachusettsInstituteofTechnology)提出了一個(gè)Hash函數(shù),作為RFC1320(RFC:互聯(lián)網(wǎng)研究和開發(fā)機(jī)構(gòu)工作統(tǒng)計(jì))公開發(fā)表,稱為MD4.MD5是MD4改進(jìn)版本,于1992年4月作為RFC1321公開發(fā)表.MD5特征直接結(jié)構(gòu)法:不依賴任何密碼系統(tǒng)和假設(shè)條件算法簡練計(jì)算速度快尤其適合32位計(jì)算機(jī)軟件實(shí)現(xiàn)傾向于使用低端結(jié)構(gòu).255.2.1MD5算法

MD5算法輸入能夠是任意長度消息x，對輸入消息按512位分組為單位進(jìn)行處理，輸出128位散列值MD(x)。整個(gè)算法分為五個(gè)步驟。步驟1:增加填充位在消息x右邊增加若干比特，使其長度與448模512同余。也就是說，填充后消息長度比512某個(gè)倍數(shù)少64位。即使消息本身已經(jīng)滿足上述長度要求，依然需要進(jìn)行填充。比如，若消息長為448，則仍需要填充512位使其長度為960位。填充位數(shù)在1到512之間。填充比特第一位是1，其它均為0。265.2.1MD5算法

步驟2:附加消息長度值

用64位表示原始消息x長度，并將其附加在步驟1所得結(jié)果之。若填充前消息長度大于264，則只使用其低64位。填充方法是把64比特長度分成兩個(gè)32比特字，低32比特字先填充，高32比特字后填充。步驟1與步驟2一起稱為消息預(yù)處理

經(jīng)預(yù)處理后，原消息長度變?yōu)?12倍數(shù)設(shè)原消息x經(jīng)預(yù)處理后變?yōu)橄?/p>

Y=Y0Y1…YL1，其中Yi（i=0,1,…,L1）是512比特在后面步驟中，將對512比特分組Yi進(jìn)行處理275.2.1MD5算法例5.1假設(shè)消息為:

x=“abcde”=0110000101100010011000110110010001100101=(6162636465)16,|x|=40=(28)16.步驟1在x右邊填充1個(gè)“1”和407個(gè)“0”，將x變成448比特x1:x1=x||1||0(407個(gè))=x||800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.=6162636465800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.285.2.1MD5算法例5.1假設(shè)消息為:

x=“abcde”=0110000101100010011000110110010001100101=(6162636465)16,|x|=40=(28)16.經(jīng)步驟2處理后比特串為（16進(jìn)制表示）：x2=x1||28(64位)=61626364658000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002800000000000000.295.2.1MD5算法步驟3:初始化MD緩沖區(qū)

MD5算法中間結(jié)果和最終止果都保留在128位緩沖區(qū)里，緩沖區(qū)用4個(gè)32位存放器表示。4個(gè)緩沖區(qū)記為A、B、C、D，其初始值為以下32位整數(shù)（16進(jìn)制表示）：A=67452301,B=EFCDAB89,C=98BADCFE,D=10325476.上述初始值以小端格式存放(字最低有效字節(jié)存放在低地址位置)為：字A=01234567,字B=89ABCDEF,字C=FEDCBA98,字D=76543210.305.2.1MD5算法步驟4:以512位分組(16個(gè)字)為單位處理消息

MD5是迭代Hash函數(shù),其壓縮函數(shù)為:步驟4是MD5算法主循環(huán)，它以512比特作為分組，重復(fù)應(yīng)用壓縮函數(shù)HMD5，從消息Y第一個(gè)分組Y1開始，依次對每個(gè)分組Yi進(jìn)行壓縮，直至最終分組YL1，然后輸出消息xHash值?？梢?，MD5循環(huán)次數(shù)等于消息Y中512比特分組數(shù)目L。31MD5壓縮函數(shù)HMD5

HMD5由四輪處理組成加法是指緩沖區(qū)中4個(gè)字與CVi中對應(yīng)4個(gè)字分別模232相加32MD5壓縮函數(shù)HMD5

HMD5四輪處理過程算法結(jié)構(gòu)相同，每一輪要對緩沖區(qū)ABCD進(jìn)行16次迭代，每次迭代運(yùn)算形式為:

其中a、b、c、d分別為緩沖區(qū)A、B、C、D中字，運(yùn)算結(jié)束后再將（a、b、c、d）循環(huán)右移一個(gè)字。33MD5壓縮函數(shù)HMD5

HMD5基本邏輯函數(shù)g每一輪使用一個(gè)基本邏輯函數(shù)g，每個(gè)基本邏輯函數(shù)輸入是三個(gè)32位字，輸出是一個(gè)32位字，它執(zhí)行位邏輯運(yùn)算，即輸出第n位是其三個(gè)輸入第n位函數(shù)基本邏輯函數(shù)g定義符號、、和分別表示邏輯操作AND、OR、NOT和XOR34MD5壓縮函數(shù)HMD5

HMD5基本邏輯函數(shù)g基本邏輯函數(shù)g真值表bcdFGHI0000010100111001011101110001101001101001001101011100111035MD5壓縮函數(shù)HMD5

字組X

把當(dāng)前處理512比特分組Yi依次分成16個(gè)32比特字,分別記為X[0,1,…,15].在每一輪16步迭代中,每一步迭代使用一個(gè)字,迭代步數(shù)不一樣使用字也不相同.所以,16步迭代恰好用完16個(gè)字.36MD5壓縮函數(shù)HMD5

對于不一樣輪處理過程,使用16個(gè)字次序不一樣.第一輪中，使用次序?yàn)閄[0,1,…,15]。第二輪中使用次序由以下置換確定:2(i)=(1+5i)mod16第三輪中使用次序由以下置換確定:3(i)=(5+3i)mod16第四輪中使用次序由以下置換確定:4(i)=7imod16.比如:第三輪處理過程第i步迭代使用字X[3(i)]=X[(5+3i)mod16];第8步迭代使用字X[3(8)]=X[(5+38)]=X[29]=X[23].37MD5壓縮函數(shù)HMD5

T[1]=D76AA478T[2]=E8C7B756T[3]=242070DBT[4]=C1BDCEEET[5]=F57C0FAFT[6]=4787C62AT[7]=A8304613T[8]=FD469501T[9]=698098D8T[10]=8B44F7AFT[11]=FFFF5BB1T[12]=895CD7BET[13]=6B901122T[14]=FD987193T[15]=A679438ET[16]=49B40821T[17]=F61E2562T[18]=C040B340T[19]=265E5A51T[20]=E9B6C7AAT[21]=D62F105DT[22]=02441453T[23]=D8A1E681T[24]=E7D3FBC8T[25]=21E1CDE6T[26]=C33707D6T[27]=F4D50D87T[28]=455A14EDT[29]=A9E3E905T[30]=FCEFA3F8T[31]=676F02D9T[32]=8D2A4C8AT[33]=FFFA3942T[34]=8771F681T[35]=699D6122T[36]=FDE5380CT[37]=A4BEEA44T[38]=4BDECFA9T[39]=F6BB4B60T[40]=BEBFBC70T[41]=289B7EC6T[42]=EAA127FAT[43]=D4EF3085T[44]=04881D05T[45]=D9D4D039T[46]=E6DB99E5T[47]=1FA27CF8T[48]=C4AC5665T[49]=F4292244T[50]=432AFF97T[51]=AB9423A7T[52]=FC93A039T[53]=655B59C3T[54]=8F0CCC92T[55]=FFEFF47DT[56]=85845DD1T[57]=6FA87E4FT[58]=FE2CE6E0T[59]=A3014314T[60]=4E0811A1T[61]=F7537E82T[62]=BD3AF235T[63]=2AD7D2BBT[64]=EB86D391常數(shù)表T：64個(gè)32位常數(shù)T[i]=232abs(sin(i))整數(shù)部分(i=1,2,…,64).38MD5壓縮函數(shù)HMD5

常數(shù)表T：64個(gè)32位常數(shù)

T[i]=232abs(sin(i))整數(shù)部分(i=1,2,…,64).常數(shù)表T作用是“隨機(jī)化”32位輸入數(shù)據(jù)，即消除輸入數(shù)據(jù)規(guī)律性。HMD5第k輪處理過程使用常數(shù)表T元素T[16(k1)+1,16(k1)+2,…,16k](k=1,2,3,4)，

第k輪第i次迭代使用元素

T[16(k1)+i](i=1,2,…,16).39MD5壓縮函數(shù)HMD5

循環(huán)左移位數(shù)s

Ls(v)表示對32位變量v循環(huán)左移s位。s值與輪數(shù)和迭代步數(shù)相關(guān)。步數(shù)輪數(shù)123456789101112131415161234754612911101714161522202321754612911101714161522202321754612911101714161522202321754612911101714161522202321405.2.1MD5算法

步驟5:輸出

依次對消息L個(gè)512比特分組進(jìn)行處理，第L個(gè)分組處理后輸出值即是消息x散列值MD(x)?？蓪D5處理過程歸納以下：CV0=IVCVi+1=SUM32[CVi,RFI(Yi,RFH

(Yi,RFG(Yi,RFF(Yi,CVi))))](i=0,1,…,L1)MD=CVL1.IV=第三步定義緩沖區(qū)ABCD初值L=消息經(jīng)第一步和第二步處理后分組個(gè)數(shù)Yi

=消息第i個(gè)512位分組RFu

=使用基本邏輯函數(shù)u輪函數(shù)SUM32=對輸入字模232相加MD=散列值.415.2.2MD5安全性

Rivest猜測，MD5可能是128位Hash函數(shù)中強(qiáng)度最大。當(dāng)前，對MD5攻擊已取得以下結(jié)果：T.Berson（1992）已經(jīng)證實(shí)，對單輪MD5算法，利用差分密碼分析，能夠在合理時(shí)間內(nèi)找出散列值相同兩條消息。這一結(jié)果對MD5四輪運(yùn)算每一輪都成立。不過，當(dāng)前尚不能將這種攻擊推廣到含有四輪運(yùn)算MD5上.B.Boer和A.Bosselaers（1993）說明了怎樣找到消息分組和MD5兩個(gè)不一樣初始值,使它們產(chǎn)生相同輸出.也就是說,對一個(gè)512位分組,MD5壓縮函數(shù)對緩沖區(qū)ABCD不一樣值產(chǎn)生相同輸出,這種情況稱為偽碰撞（pseudo-collision）.當(dāng)前尚不能用該方法成功攻擊MD5算法.425.2.2MD5安全性

H.Dobbertin（1996）找到了MD5無初始值碰撞(pseudo-collision).給定一個(gè)512位分組,能夠找到另一個(gè)512位分組,對于選擇初始值IV0,它們MD5運(yùn)算結(jié)果相同.到當(dāng)前為止,尚不能用這種方法對使用MD5初始值IV整個(gè)消息進(jìn)行攻擊.我國山東大學(xué)王小云教授（）提出攻擊對MD5最具威脅。對于MD5初始值IV，王小云找到了許多512位分組對，它們MD5值相同.國際密碼學(xué)家Lenstra利用王小云等提供MD5碰撞，偽造了符合X.509標(biāo)準(zhǔn)數(shù)字證書.MD5算法抗密碼分析能力較弱,對MD5生日攻擊所需代價(jià)為264數(shù)量級.所以,必須設(shè)計(jì)新Hash算法,使其與MD5相比含有更長散列值和更高安全性.43第5章Hash函數(shù)與消息認(rèn)證5.1Hash函數(shù)概述5.2Hash函數(shù)MD55.3安全Hash算法SHA1

5.4基于分組密碼與離散對數(shù)Hash函數(shù)5.5消息認(rèn)證445.3安全Hash算法SHA1安全Hash算法SHA（securehashalgorithm）由美國家標(biāo)準(zhǔn)準(zhǔn)與技術(shù)研究所（NIST）設(shè)計(jì)并于1993年作為聯(lián)邦信息處理標(biāo)準(zhǔn)（FIPS180）公布修改版于1995年公布（FIPS1801），通常稱之為SHA1。該標(biāo)準(zhǔn)稱為安全Hash函數(shù)。RFC3174也給出了SHA1，它基本上是復(fù)制FIPS1801內(nèi)容，但增加了C代碼實(shí)現(xiàn)。SHA1算法輸入是長度小于264任意消息x，輸出160位散列值。455.3.1SHA1算法步驟SHA1處理消息過程與MD5類似，對輸入消息按512位分組為單位進(jìn)行處理，整個(gè)算法分為五個(gè)步驟步驟1:增加填充位

在消息右邊增加若干比特，使其長度與448模512同余。即使消息本身已經(jīng)滿足上述長度要求，依然需要進(jìn)行填充。填充位數(shù)在1到512之間。填充比特第一位是“1”，其它均為“0”。步驟2:附加消息長度值

用64位表示原始消息x長度，并將其附加在步驟1所得結(jié)果之后。步驟1與步驟2一起稱為消息預(yù)處理

經(jīng)預(yù)處理后，原消息長度變?yōu)?12倍數(shù)。設(shè)原消息x經(jīng)預(yù)處理后變?yōu)橄=Y0Y1…YL1，其中Yi（i=0,1,…,L1）是512比特。在后面步驟中，將對512比特分組Yi進(jìn)行處理。465.3.1SHA1算法步驟步驟3:初始化緩沖區(qū)SHA1算法中間結(jié)果和最終止果保留在160位緩沖區(qū)里，緩沖區(qū)用5個(gè)32位存放器表示。5個(gè)緩沖區(qū)記為A、B、C、D、E，其初始值為以下32位整數(shù)（16進(jìn)制表示）：A=67452301,B=EFCDAB89,C=98BADCFE,D=10325476,E=C3D2E1F0.其中，前4個(gè)初始值與MD5初始值相同。SHA1以大端格式存放緩沖區(qū)值，即字最高有效字節(jié)存于低地址字節(jié)位置。所以，上述初始值存放為（十六進(jìn)制）：字A=67452301,字B=EFCDAB89,字C=98BADCFE,字D=10325476,字E=C3D2E1F0.475.3.1SHA1算法步驟步驟4:以512位分組（16個(gè)字）為單位處理消息SHA1是迭代Hash函數(shù)，其壓縮函數(shù)為：步驟4是SHA1算法主循環(huán)，它以512比特作為分組，重復(fù)應(yīng)用壓縮函數(shù)HSHA，從消息Y第一個(gè)分組Y1開始，依次對每個(gè)分組Yi進(jìn)行壓縮，直至最終分組YL1，然后輸出消息xHash值。SHA1循環(huán)次數(shù)等于消息Y中512比特分組數(shù)目L。48SHA1

壓縮函數(shù)HSHA

由四輪處理組成加法是模232相加CVi(160)Yi(512)BCDAEf4,K,W[60,61,…,79],20步BCDAEf2,K,W[20,21,…,39],20步BCDAEf3,K,W[40,41,…,59],20步BCDAEf1,K,W[0,1,…,19],20步+++++CVi+1

(160)49SHA1壓縮函數(shù)HSHA

壓縮函數(shù)HSHA四輪處理過程算法結(jié)構(gòu)相同，每一輪要對緩沖區(qū)ABCDE進(jìn)行20次迭代，每次迭代運(yùn)算形式為ABCDEABCDE+

+f+Wt+KtL30L5其中A、B、C、D、E分別為五個(gè)緩沖區(qū)中字，運(yùn)算結(jié)束后再將（A、B、C、D、E）循環(huán)右移一個(gè)字。50SHA1壓縮函數(shù)HSHA

基本邏輯函數(shù)f每一輪使用一個(gè)基本邏輯函數(shù)f，每個(gè)基本邏輯函數(shù)輸入是三個(gè)32位字，輸出是一個(gè)32位字，它執(zhí)行位邏輯運(yùn)算，即輸出第n位是其三個(gè)輸入第n位函數(shù)。輪數(shù)基本邏輯函數(shù)ff(B,C,D)1234f1(B,C,D)f2(B,C,D)f3(B,C,D)f4(B,C,D)51SHA1壓縮函數(shù)HSHA

基本邏輯函數(shù)f基本邏輯函數(shù)f真值表BCDf1f2f3f40000010100111001011101110000110101011010010100101010111152SHA1壓縮函數(shù)HSHA

字組Wt

t（0≤t≤79）代表迭代步數(shù)，依次表示第一、二、三、四輪處理過程進(jìn)行迭代次序Wt(0≤t≤79)是32比特字，它前面16個(gè)字W0,W1,…,W15依次取自當(dāng)前輸入分組Yi，其余字為加法常數(shù)表Kt迭代步數(shù)十六進(jìn)制十進(jìn)制0t1920t3940t5960t795A8279996ED9EBA18F1BBCDCCA62C1D6535.3.1SHA1算法步驟步驟5:輸出第L個(gè)分組處理后輸出值即是消息x散列值MD(x)SHA1處理過程歸納以下：CV0=IVCVi+1=SUM32(CVi,

ABCDEi)(i=0,1,…,L1)MD=CVL1其中：IV=第三步定義緩沖區(qū)ABCDE初值A(chǔ)BCDEi=處理第i個(gè)消息分組時(shí)最終一輪輸出L=消息經(jīng)第一步和第二步處理后分組個(gè)數(shù)SUM32=對輸入字模232相加MD=散列值.545.3.2SHA1和MD5比較SHA1與MD5算法類似，所以它們性質(zhì)極為相同抗窮舉攻擊能力SHA1抗窮舉攻擊能力比MD5強(qiáng)用窮舉攻擊方法產(chǎn)生含有給定散列值消息MD5需要代價(jià)為2128數(shù)量級SHA1需要代價(jià)為2160數(shù)量級用窮舉攻擊方法產(chǎn)生兩個(gè)含有相同散列值消息MD5需要代價(jià)為264數(shù)量級SHA1需要代價(jià)為280數(shù)量級抗密碼分析能力MD5算法抗密碼分析能力較弱SHA1算法抗密碼分析能力似乎并不弱555.3.2SHA1和MD5比較速度SHA1執(zhí)行速度比MD5速度慢得多簡練性SHA1和MD5兩種算法都易于描述和實(shí)現(xiàn)，不需要使用大程序和置換表數(shù)據(jù)存放方式MD5使用littleendian方式，SHA1使用bigendian方式。這兩種方式?jīng)]有本質(zhì)差異56第5章Hash函數(shù)與消息認(rèn)證5.1Hash函數(shù)概述5.2Hash函數(shù)MD55.3安全Hash算法SHA1

5.4基于分組密碼與離散對數(shù)Hash函數(shù)5.5消息認(rèn)證575.4基于分組密碼與離散對數(shù)Hash函數(shù)Hash函數(shù)間接結(jié)構(gòu)法利用已經(jīng)有密碼算法結(jié)構(gòu)Hash函數(shù)假如密碼算法是安全，那么利用它所結(jié)構(gòu)Hash函數(shù)也是安全585.4.1利用分組密碼算法結(jié)構(gòu)Hash函數(shù)已知條件設(shè)Ek是一個(gè)分組長度為n分組密碼加密算法，密鑰為k，對于任意消息x，首先對x進(jìn)行分組，每組長度為n。設(shè)消息x為:x=x1x2…xL,其中xi

GF(2)n（1i

L）.595.4.1利用分組密碼算法結(jié)構(gòu)Hash函數(shù)基于分組密碼CBC工作模式結(jié)構(gòu)Hash函數(shù)首先選取一個(gè)初始值:y0=IVGF(2)n，然后依次計(jì)算:

最終定義Hash值為:hCBC(x)=yL.IV=y0x1Eky1x2Eky2xLEkyL=hCBC(x)60基于分組密碼CFB工作模式結(jié)構(gòu)Hash函數(shù)首先選取一個(gè)初始值:y0=IVGF(2)n，然后依次計(jì)算:

最終定義Hash值為:hCFB(x)=yL.5.4.1利用分組密碼算法結(jié)構(gòu)Hash函數(shù)IV=y0x1y1Ekx2y2EkyL=hCFB(x)xLEk在密鑰公開情況下，基于分組密碼CBC工作模式和CFB工作模式結(jié)構(gòu)Hash函數(shù)是不安全，它們甚至不是弱無碰撞.61基于一些困難數(shù)學(xué)問題，諸如離散對數(shù)問題、因子分解問題、背包問題等能夠結(jié)構(gòu)出一些Hash函數(shù)，這些Hash函數(shù)安全性依賴于對應(yīng)數(shù)學(xué)問題困難性Chaum、Heijst和Pfitzmann（1992年）提出基于離散對數(shù)問題結(jié)構(gòu)Hash函數(shù)運(yùn)行速度不是很快能夠證實(shí)是安全.ChaumHeijstPfitzmannHash函數(shù)結(jié)構(gòu)

設(shè)p是一個(gè)大素?cái)?shù)，q=(p1)/2是一個(gè)素?cái)?shù)，

和

是Zp兩個(gè)本原元。假設(shè)離散對數(shù)log是計(jì)算上不可行。定義Hash函數(shù)h為：5.4.2基于離散對數(shù)問題Hash函數(shù)

62ChaumHeijstPfitzmannHash函數(shù)是強(qiáng)抗碰撞用反證法，假如Hash函數(shù)h有一對碰撞，那么能夠證實(shí)離散對數(shù)log能被有效計(jì)算.設(shè)(x1,x2)，(x3,x4)是h一對碰撞消息，即(x1,x2)(x3,x4)，h(x1,x2)=h(x3,x4)，那么5.4.2基于離散對數(shù)問題Hash函數(shù)

記d=gcd(x4x2,p1)。因?yàn)閜1=2q，且q是一個(gè)素?cái)?shù)，所以d{1,2,q,p1}。下面對d四個(gè)取值分別進(jìn)行討論。63ChaumHeijstPitzmannHash函數(shù)是強(qiáng)抗碰撞

5.4.2基于離散對數(shù)問題Hash函數(shù)

情況1：d=1此時(shí)x4x2關(guān)于模p1有逆，設(shè)y=(x4x2)1mod(p1)，則存在整數(shù)k，使得(x4x2)y=1+(p1)k，則有所以，可計(jì)算離散對數(shù)645.4.2基于離散對數(shù)問題Hash函數(shù)

情況2：d=2因?yàn)閜1=2q,且q是奇數(shù),所以gcd(x4x2,q)=1.設(shè)y=(x4x2)1modq，則存在整數(shù)k，使得(x4x2)y=1+qk,有因?yàn)閝=1modp，所以輕易檢驗(yàn)二式中哪一個(gè)成立.即離散對數(shù)log能被有效計(jì)算.655.4.2基于離散對數(shù)問題Hash函數(shù)

情況3：d=q

因?yàn)?≤x2≤q1,0≤x4≤q1

(q1)≤x4x2≤q1gcd(x4x2,q1)=q不成立.

情況3不存在.情況4：d=p1這種情況只有在x2=x4時(shí)才可能發(fā)生。這么就有所以x1=x3，(x1,x2)=(x3,x4)，與已知矛盾!即情況4也不存在.66第5章Hash函數(shù)與消息認(rèn)證5.1Hash函數(shù)概述5.2Hash函數(shù)MD55.3安全Hash算法SHA15.4基于分組密碼與離散對數(shù)Hash函數(shù)5.5消息認(rèn)證675.5消息認(rèn)證認(rèn)證（authentication）是預(yù)防網(wǎng)絡(luò)系統(tǒng)遭受主動(dòng)攻擊主要技術(shù)認(rèn)證主要目標(biāo)有兩個(gè)第一，驗(yàn)證消息發(fā)送者是真，而不是冒充，稱為實(shí)體認(rèn)證，包含信源、信宿等認(rèn)證和識別。第二，驗(yàn)證信息完整性，即驗(yàn)證數(shù)據(jù)在傳送或存放過程中未被篡改、重放或延遲，稱為消息認(rèn)證。685.5.1消息認(rèn)證碼帶密鑰Hash函數(shù)稱為消息認(rèn)證碼(MAC：messageauthenticationcode).消息認(rèn)證碼是實(shí)現(xiàn)消息認(rèn)證主要工具.MAC有兩個(gè)不一樣輸入，一個(gè)是消息x，另一個(gè)是密鑰K.MAC產(chǎn)生定長輸出.實(shí)例:某一個(gè)大企業(yè)A想給它客戶公布一個(gè)新產(chǎn)品廣告,A希望不對廣告內(nèi)容加密,但又希望其它企業(yè)不能修改廣告內(nèi)容或冒充企業(yè)A公布一樣廣告,或者當(dāng)廣告內(nèi)容被修改后能夠發(fā)覺.假如使用不帶密鑰Hash函數(shù),因?yàn)槠渌髽I(yè)可能在修改廣告內(nèi)容后產(chǎn)生新散列值,從而使A無法確認(rèn)原廣告是否被修改.

設(shè)計(jì)MAC算法要求在不知道密鑰情況下，難以找到兩個(gè)不一樣消息含有相同輸出。695.5.1消息認(rèn)證碼基于分組密碼CBC工作模式結(jié)構(gòu)MAC基于分組密碼CBC工作模式結(jié)構(gòu)MAC算法已經(jīng)成為ISO/IEC9797標(biāo)準(zhǔn)，它使用密文鏈接和雙密鑰三重加密技術(shù)。設(shè)EK表示以K為密鑰加密算法，設(shè)K’是一個(gè)與K不一樣密鑰，消息分組長度為n。首先把消息x分成L個(gè)n位塊x=x1x2…xL，計(jì)算：hK是一個(gè)n位MAC.記為CBC-MAC.705.5.1消息認(rèn)證碼基于Hash函數(shù)結(jié)構(gòu)MAC設(shè)h是一個(gè)（不帶密鑰）Hash函數(shù)，K是密鑰，x是消息，則定義消息認(rèn)證碼hK以下：基于MD5算法直接結(jié)構(gòu)消息認(rèn)證碼MD5-MACMD5-MAC算法使用96字節(jié)常數(shù)其中下標(biāo)加法運(yùn)算是模3相加.假如密鑰K長度小于128位，則經(jīng)過屢次自行鏈接，最終截取左邊128位作為以下算法中使用密鑰K。715.5.1消息認(rèn)證碼將密鑰K擴(kuò)展成3個(gè)16字節(jié)子密鑰K0，K1，K2，其中把K0，K1分成4個(gè)32位子串Kj[i]（j=0,1,i=0,1,2,3）對MD5進(jìn)行修改：用K0代替MD54個(gè)32位存放器ABCD.把K1[i]與MD5第i+1遍中每個(gè)常數(shù)232sin(j)進(jìn)行模232加法.將512位分組鏈接到消息x右邊，再按MD5要求進(jìn)行填充.

將上一步結(jié)果輸入到修改后MD5中，取其輸出前二分之一（64位）作為消息x消息認(rèn)證碼MD5-MAC(x).MD5-MAC軟件實(shí)現(xiàn)比較輕易，其運(yùn)算速度與MD5大致相近.725.5.2HMAC算法

消息認(rèn)證碼HMAC（keyed-hashingformessageauthenticationcode）是Bellare等人于1996年提出，1997年作為RFC2104發(fā)表，成為實(shí)際上Internet標(biāo)準(zhǔn)，包含IPSec協(xié)議在內(nèi)一些安全協(xié)議都使用了HMAC算法。HMAC算法利用已經(jīng)有Hash函數(shù)，關(guān)鍵問題是怎樣使用密鑰。使用不一樣Hash函數(shù)，就能夠得到不一樣HMAC。選取MD5時(shí)HMAC記為HMAC-MD5，選取SHA-1時(shí)HMAC記為HMAC-SHA1。735.5.2HMAC算法

HMAC算法描述設(shè)HMAC使用Hash函數(shù)為h，每次處理輸入分組長度為b比特（使用MD5與SHA-1時(shí)，b=512），最終輸出長度為l比特（使用MD5時(shí)，l=128；使用SHA-1時(shí)，l=160）。假如HMAC輸入消息為x，則x=x1x2…xL，其中每一個(gè)分組xi（1≤i≤L）長度為b比特。令HMAC使用密鑰為K，密鑰K能夠是任意、長度不超出b比特比特串（HMAC算法推薦密鑰最小長度為l比特）。當(dāng)密鑰K長度超出b比特時(shí)，使用Hash函數(shù)h對K進(jìn)行壓縮，把K作為h輸入，并將輸出l比特作為密鑰K。745.5.2HMAC算法

HMAC算法流程圖

x2

x1

Si

xL…KipadSo

h(Si||x)KopadHMAC(x)Hash函數(shù)hHash函數(shù)h755.5.2HMAC算法

HMAC算法詳細(xì)執(zhí)行步驟(1)假如密鑰K長度小于b比特，則在其右邊填充一些“0”，使其成為長度為b比特比特串，仍記為K。(2)計(jì)算Si=Kipad，其中ipad是HMAC算法中要求一個(gè)長度為b比特比特模式串，它等于將00110110重復(fù)b/8次后得到比特串。(3)把HMAC輸入消息x=x1x2…xL附加在Si右端，得到Si||x=Si||x1x2…xL，將該比特串作為Hash函數(shù)h輸入，得到l比特輸出h(Si||x)。(4)計(jì)算So=Kopad，其中opad是HMAC算法中要求另一個(gè)長度為b比特比特模式串，它等于將01011010重復(fù)b/8次后得到比特串。(5)將第(3)步得到h(Si||x)附加在So右端，并以該比特串作為Hash函數(shù)h輸入，得到l比特輸出。(6)將第(5)步輸出作為HMAC