2025/8/1216.3.2SHA-1散列算法

NIST在1993年發(fā)布了一個(gè)哈希算法稱為安全HASH算法，1995年修改，修改后的版本是SHA-1，這個(gè)版本是當(dāng)前使用最廣泛的哈希算法。SHA-1接受輸入消息的最大長(zhǎng)度為264-1bits，生成160bits的消息摘要。SHA-1算法操作首先對(duì)輸入消息劃分為512-bit塊，若最后一個(gè)數(shù)據(jù)塊不滿足長(zhǎng)度要求，按照一定規(guī)則進(jìn)行填充為512-bit塊。然后每個(gè)512-bit塊重復(fù)使用分塊處理函數(shù)，最終輸出160bits哈希值。1）SHA-1算法預(yù)處理

8/12/20255（1）消息由704位二進(jìn)制組成。先劃分第一個(gè)分組：704-512=192第二個(gè)分組填充：先填充一個(gè)“1”，填充“0”的個(gè)數(shù)位：

448-1-192=255最后64個(gè)比特填充消息的二進(jìn)制長(zhǎng)度。（2）消息由448位二進(jìn)制組成。已經(jīng)448bits了，又必須填充1，故填充后消息為2個(gè)分組。故先填充一個(gè)“1”，然后用“0”把第1個(gè)分組填滿。再把第2個(gè)分組的前448比特然后用“0”填充，剩下最后64比特填充消息的二進(jìn)制長(zhǎng)度。如果消息長(zhǎng)度為480bits呢？8/12/20257實(shí)際上，在編程的時(shí)候應(yīng)當(dāng)分為2種情況：（1）消息的最后分組小于448比特，即56個(gè)字節(jié)，這種情況的填充方式容易理解；（2）消息的最后分組長(zhǎng)度大于等于448比特，這種情況會(huì)增加一個(gè)分組。另外，按照現(xiàn)在計(jì)算機(jī)的編碼方式，消息的長(zhǎng)度總是8的整數(shù)倍。編程時(shí)，先分組再算消息摘要，還是讀一組計(jì)算一組？文件很大呢？多線程？---內(nèi)存映射文件的方式

數(shù)據(jù)擴(kuò)展

2）SHA-1算法512-bit分塊處理過程SHA-1算法以512-bit分塊為單位進(jìn)行循環(huán)處理，處理過程為：第一個(gè)512-bit分塊與160-bit初始IV變量作為輸入，通過分塊處理壓縮函數(shù)，輸出160bits數(shù)據(jù)塊；然后，第二512-bit分塊和第一個(gè)分塊處理最后輸出160-bit數(shù)據(jù)塊作為輸入，通過分塊處理處理壓縮函數(shù)，輸出160bits數(shù)據(jù)塊；依次，直到最后一個(gè)512-bit子塊處理完成，最后輸出160bits數(shù)據(jù)塊為輸入原始消息的哈希值，如圖所示（1）邏輯函數(shù)(?)分塊處理中需要使用結(jié)構(gòu)相似的四個(gè)基本邏輯函數(shù)：f1，f2，f3，f4，每個(gè)回合使用不同的邏輯函數(shù)，f1，f2，f3，f4邏輯函數(shù)的定義如下所示：（4）壓縮函數(shù)寄存器A、B、C、D，E數(shù)據(jù)通過壓縮函數(shù)變換

回合步驟輸入常數(shù)取值方式(整數(shù))1Kt=5A827992Kt

=6ED9EBA13Kt

=8F1BBCDC4Kt

=CA62C1D63）SHA-1算法偽代碼

4.5Fort=0to79T=ROTL5(A)

+f1(B,C,D)+E+W[t]+K[t]E=D；D=C；

C=ROTL30

(B)；B=A；A=TEnd；EndFor5.return哈希值(H0||H1||H2||H3||H4)備注：偽代碼中"+"表示模

加2025/8/1223例:對(duì)字符串”abc”，運(yùn)用SHA-1求散列值首先”abc”二進(jìn)制表示為：011000010110001001100011，共24位長(zhǎng)度SHA-1算法：第一步：按照SHA-1要求，填充數(shù)據(jù)

512－64－24＝424（填充1位“1”，423位“0”，及1000…000)512位的輸入數(shù)據(jù)為(十六進(jìn)制表示）：6162638000000000，……,00000018故W0=61626380,W1=W2=…=W14=00000000,W15=00000018第二步：初始化A、B、C與

D緩存器，如下：A：67452301

B：EFCDAB89

C：98BADCFED：10325476

E：C3D2E1F0-實(shí)例2025/8/1224

第三步：進(jìn)入第一輪次運(yùn)算，執(zhí)行

20

回合：

A,B,C,D,E→(E+f1(t,B,C,D)+S5(A)+Wt+Kt),A,S30(B),C,D)求A,B,C,D的值。SHA-1散列算法后面的與步驟3類似計(jì)算。由標(biāo)準(zhǔn)可知，若輸入字符串”abc”，SHA-1算法160bits哈希值為：a9993e364706816aba3e25717850c26c9cd0d89d6.3.3SHA-256、SHA-384和SHA-512*在2002年，相繼對(duì)SHA系列算法進(jìn)行擴(kuò)展，提出SHA-256、SHA-384、SHA-512，并稱為SHA-2。SHA-256與SHA-1算法一樣，以512-bit分塊為基本處理單位，每分塊又劃分為16個(gè)32-bit字進(jìn)入哈希函數(shù)中處理操作。而SHA-384、SHA-512與SHA-1算法不同，是以1024-bit分塊為基本處理單位，每分塊是劃分為16個(gè)64-bit字進(jìn)入哈希函數(shù)中處理操作。-SHA參數(shù)比較：6.3.4SHA-3算法自2007年，NIST發(fā)起了SHA-3競(jìng)賽以征集新的Hash算法以來，截止到2010年10月，第二輪遴選結(jié)束，共有五種算法進(jìn)入最終輪遴選，入選的五個(gè)算法是：BLAKE、Gr?stl、JH、Keccak、Skein，到2012年，NIST最終選擇Keccak算法作為SHA-3標(biāo)準(zhǔn)(即美國(guó)的FIPSPUB202）。SHA-3為了與SHA-2完全兼容，SHA-3中也提出了4個(gè)Hash算法SHA3-224,SHA3-256,SHA3-384,SHA3-512，可完全替換SHA-2。Keccak算法是由GuidoBertoni，JoanDaemen，Micha?lPeeters，以及GillesVanAssche設(shè)計(jì)的。作為SHA家族最新的算法，其采用了不同于傳統(tǒng)MD結(jié)構(gòu)，而選擇了海綿構(gòu)造（sponge結(jié)構(gòu)）。通過采用這種結(jié)構(gòu)，常用于MD結(jié)構(gòu)的攻擊方法難以進(jìn)行，增加了其算法安全性。2025/8/12296.3.5

Hash散列算法的應(yīng)用（略）

Hash算列函數(shù)由于其單向性和隨機(jī)性的特點(diǎn),

主要運(yùn)用于提供數(shù)據(jù)完整性(包括數(shù)字簽名、以及與數(shù)字簽名聯(lián)系起來的數(shù)字指紋的應(yīng)用)知識(shí)證明、密鑰推導(dǎo)、偽隨機(jī)數(shù)生成等方面。1．生成程序或文檔的“數(shù)字指紋”-完整性驗(yàn)證2025/8/12302．用于安全存儲(chǔ)口令/CSDN2011/CSDN用戶信息泄露的背后2025/8/12316.4散列算法的攻擊現(xiàn)狀（略）

散列函數(shù)主要用于數(shù)據(jù)完整性驗(yàn)證，確定消息是否被修改，因此對(duì)散列函數(shù)攻擊的目標(biāo)是生成這樣的修改后的消息：其散列值與原有消息的散列值相等。對(duì)散列函數(shù)的攻擊可以分為如下幾類：

2025/8/12312025/8/1232目前，對(duì)散列函數(shù)的碰撞攻擊最重要的平凡攻擊是生日攻擊。生日攻擊的名字起源于所謂的生日悖論，嚴(yán)格來說，它并不是一個(gè)真正的悖論，只是一個(gè)令人吃驚的概率問題。生日攻擊方法沒有利用Hash函數(shù)的結(jié)構(gòu)和任何代數(shù)弱性質(zhì)，它只依賴于消息摘要的長(zhǎng)度，即Hash值的長(zhǎng)度。這種攻擊對(duì)Hash函數(shù)提出了一個(gè)必要的安全條件，即消息摘要必須足夠的長(zhǎng)。6.4.1生日悖論問題生日悖論是這樣一個(gè)問題：在k個(gè)人中至少有兩個(gè)人的生日相同的概率大于0.5時(shí)，k至少多大？絕大多數(shù)人回答這個(gè)問題時(shí)候會(huì)認(rèn)為是一個(gè)很大的數(shù)，事實(shí)上是非常小的一個(gè)數(shù)。為了回答這一問題，下面我們給出計(jì)算方法：2025/8/1233（1）對(duì)于進(jìn)入房間的第一個(gè)人來說，有365個(gè)不同的生日；

（2）對(duì)于第二個(gè)進(jìn)入房間時(shí)，有364個(gè)與第一個(gè)人不是同一天生日的可能，因此不匹配概率為364/365；

（3）對(duì)于第三個(gè)人進(jìn)入房間時(shí)，有363個(gè)與前兩個(gè)人不是一天生日，因此現(xiàn)在不匹配的概率為：

匹配概率為：

（4）但k個(gè)人進(jìn)入房間時(shí)，不匹配概率的一般公式為：

匹配概率為：

2025/8/1234（5）當(dāng)k=23時(shí)，概率為0.5073，即在23個(gè)人中至少有兩個(gè)人生日相同的概率大于0.5。若k取100，則概率0.9999997，即獲得如此大的概率。之所以稱這一問題是悖論是因?yàn)楫?dāng)人數(shù)k給定時(shí)，得到的至少有兩個(gè)人的生日相同的概率比想象的要大得多。這是因?yàn)樵趉個(gè)人中考慮的是任意兩個(gè)人的生日是否相同，在23個(gè)人中可能的情況數(shù)為。

將生日悖論推廣：已知一個(gè)在1到n之間均勻分布的整數(shù)型隨機(jī)變量，若該變量的k個(gè)取值中至少有兩個(gè)取值相同的概率大于0.5，則k至少多大？2025/8/12356.4.2生日攻擊

Yuval生日攻擊實(shí)例：假設(shè)用戶A采用散列函數(shù)作為簽名發(fā)送給B，A能夠利用Yuval生日攻擊欺騙B，具體過程如下：(1)設(shè)用戶A預(yù)先準(zhǔn)備了兩條不同的消息，例如一份合同的兩種不同版本，一種是對(duì)B有利的合同，另外一種將使B破產(chǎn)的合同；

(2)A對(duì)這兩種不同版本的合同每一份都作一些細(xì)微的改變(例如對(duì)文件，A可在文件的單詞之間插入很多“空格-退格-空格”字符對(duì)，然后將其中的某些字符對(duì)替換為“空格-退格-空格”就得到一個(gè)變形的消息)，并分別計(jì)算散列值；(4)A將對(duì)B有利的合同和散列值提交給B請(qǐng)求簽字，然后返回給A2025/8/1237上述攻擊中如果散列值的長(zhǎng)為64比特，則A攻擊成功所需的時(shí)間復(fù)雜度為O(232)，那么64位的散列函數(shù)對(duì)付生日攻擊顯然太小。大多數(shù)的單向散列函數(shù)產(chǎn)生128位的散列（如MD5），這樣試圖進(jìn)行生日的攻擊的攻擊者必須對(duì)264個(gè)隨機(jī)消息進(jìn)行散列運(yùn)算才能找到散列值相同的消息。目前NIST在其安全散列標(biāo)準(zhǔn)（SHS）中用的是160位的散列值（如SHA-1），這樣生日攻擊就更難進(jìn)行，需要對(duì)280個(gè)隨機(jī)消息進(jìn)行散列運(yùn)算。

-hash函數(shù)小結(jié)：6.5消息認(rèn)證6.5.1消息認(rèn)證的基本概念消息認(rèn)證是一個(gè)過程，用以驗(yàn)證接收消息的真實(shí)性（的確是由它所聲稱的實(shí)體發(fā)來的）和完整性（未被篡改、插入、刪除），同時(shí)還用于驗(yàn)證消息的順序性和時(shí)間性（未重排、重放、延遲）。消息認(rèn)證過程中檢驗(yàn)內(nèi)容應(yīng)包括：（1）證實(shí)消息的源和宿；（2）消息內(nèi)容是否曾受到偶然的或有意的篡改；（3）消息的序號(hào)和時(shí)間先后?？傊?，消息認(rèn)證使接收者能識(shí)別：消息的源，內(nèi)容的真?zhèn)?，時(shí)間性和信宿。這種認(rèn)證只在相應(yīng)通信的雙方之間進(jìn)行，而不允許第三者進(jìn)行上述認(rèn)證。認(rèn)證不一定是實(shí)時(shí)的，可用消息認(rèn)證碼MAC（MessageAuthenticationcode）對(duì)消息做認(rèn)證。消息認(rèn)證碼是指消息被一密鑰控制的公開函數(shù)作用后產(chǎn)生的，用作認(rèn)證符的固定長(zhǎng)度的數(shù)值，也稱為密碼校驗(yàn)和或者M(jìn)AC值。消息認(rèn)證碼目的是確認(rèn)完整性并進(jìn)行認(rèn)證技術(shù)。根據(jù)任意長(zhǎng)度消息輸出固定長(zhǎng)度的數(shù)據(jù)，這點(diǎn)與Hash函數(shù)類似，但是與Hash函數(shù)不同，計(jì)算MAC值必須持有共享密鑰，沒有共享密鑰的人無法計(jì)算MAC值。與Hash函數(shù)一樣，哪怕消息發(fā)送1bit的變化，MAC值也會(huì)產(chǎn)生變化，消息認(rèn)證碼利用這一特性來達(dá)到確認(rèn)完整性目的。因此，消息認(rèn)證碼也可以理解為上一種與密鑰相關(guān)聯(lián)的單向Hash函數(shù)。消息認(rèn)證碼主要包括基于分組密碼設(shè)計(jì)的MAC和基于Hash的MAC。1．基于分組密碼的MAC目前，大多數(shù)消息認(rèn)證碼都是基于分組密碼，它們有相對(duì)較短比特長(zhǎng)度或短密碼（如基于DES-CBC的MAC是56bits），MAC函數(shù)與加密算法類似，不同之處為MAC函數(shù)不必是可逆的，因此與加密算法相比更不易被攻破，提供足夠安全。CBC-MAC算法是最常用的一種基于分組的MAC算法，如圖所示?；诜纸M密碼的CBC-MAC算法，其初始變量取值為零，然后把需要認(rèn)證的數(shù)據(jù)進(jìn)行分組，分組的長(zhǎng)度由所選的分組密碼算法所決定，若最后一組數(shù)據(jù)不夠分組規(guī)定長(zhǎng)度，則需要進(jìn)行必要的填充，最簡(jiǎn)單填充方法在其后補(bǔ)零.注意虛線框2．基于Hash的MAC為了提供數(shù)據(jù)認(rèn)證和數(shù)據(jù)完整性保證，也常使用基于Hash的MAC算法產(chǎn)生MAC消息認(rèn)證碼。下面介紹一種基于MD5的MAC算法（MD5-MAC算法），如下圖所示。MD5-MAC算法的是由MD5算法經(jīng)過變換得到，記為MD5’，它的性能與MD5接近，在軟件實(shí)現(xiàn)中慢5%~20%，具體算法如下：3．消息認(rèn)證碼的使用方式基于消息認(rèn)證碼的認(rèn)證過程，前提條件是通信雙方共享一密鑰K。設(shè)Alice欲發(fā)送給Bob的消息是M，Alice首先計(jì)算MAC=CK(M)，其中CK(·)是密鑰控制的公開函數(shù)，然后向Bob發(fā)送M‖MAC，B收到后做與A相同的計(jì)算，求得一新MAC，并與收到的MAC做比較，如圖所示。如果僅收發(fā)雙方知道密鑰K，且Bob計(jì)算得到的MAC與接收到的MAC一致，則這一系統(tǒng)就實(shí)現(xiàn)了以下功能：（1）接收方Alice相信發(fā)送方Bob發(fā)來的消息未被篡改。（2）接收方Bob相信發(fā)送方Alice不是冒充的。上述過程中只提供認(rèn)證性而未提供保密性。為了提供認(rèn)證同時(shí)提供消息保密性，可在MAC函數(shù)作用之后，進(jìn)行一次加密，若采用對(duì)稱密碼算法，算法密鑰也需被收發(fā)雙方共享。

上圖中，M與MAC鏈接后再被整體加密，消息認(rèn)證與明文相關(guān)消息認(rèn)證與機(jī)密性（與明文相關(guān)）

上圖中，M先被加密再與MAC鏈接后發(fā)送，消息認(rèn)證與密文相關(guān)（與密文相關(guān)）6.5.2HMACHMAC是由H.Krawezyk，M.Bellare，R.Canetti于1996年提出的一種基于Hash函數(shù)和密鑰進(jìn)行消息認(rèn)證的方法，已作為RFC2104被公布，并在IPSec和其他網(wǎng)絡(luò)協(xié)議(如SSL)中得以應(yīng)用。HMAC所能提供的消息認(rèn)證包括兩方面內(nèi)容：（1）消息完整性認(rèn)證：能夠證明消息內(nèi)容在傳送過程沒有被修改。（2）信源身份認(rèn)證：因?yàn)橥ㄐ烹p方共享了認(rèn)證的