第03章 數(shù)據(jù)完整性機(jī)制

第3章數(shù)據(jù)完整性機(jī)制主要內(nèi)容3.1網(wǎng)絡(luò)安全中數(shù)據(jù)完整性概述3.2數(shù)據(jù)完整性機(jī)制的評價(jià)標(biāo)準(zhǔn)3.3網(wǎng)絡(luò)安全中數(shù)據(jù)完整性驗(yàn)證機(jī)制與評價(jià)3.4MD5消息摘要計(jì)算算法與評價(jià)3.5MD5算法在數(shù)據(jù)安全方面的應(yīng)用實(shí)例3.1網(wǎng)絡(luò)安全中數(shù)據(jù)完整性概述數(shù)據(jù)完整性驗(yàn)證：驗(yàn)證收到的數(shù)據(jù)是否與原來數(shù)據(jù)之間保持完全一致的證明手段稱為數(shù)據(jù)完整性驗(yàn)證。數(shù)據(jù)的完整性驗(yàn)證是用來抗擊主動攻擊的篡改等行為。數(shù)據(jù)完整性數(shù)據(jù)完整性數(shù)據(jù)完整性是防止非法實(shí)體對交換數(shù)據(jù)的修改、插入、替換和刪除，或者如果被修改、插入、替換和刪除時(shí)可以被檢測出來。數(shù)據(jù)完整性可以通過消息認(rèn)證模式來保證。基本思路增加信息驗(yàn)證碼對數(shù)據(jù)完整性進(jìn)行驗(yàn)證（1）發(fā)送方根據(jù)要發(fā)送的原信息M0，利用驗(yàn)證碼函數(shù)產(chǎn)生與M0密切相關(guān)的信息驗(yàn)證碼C0；（2）發(fā)送方把原始信息M0和信息驗(yàn)證碼C0合在一起，并通過網(wǎng)絡(luò)發(fā)送給接收方；基本思路（3）接收方對所收到的原信息和驗(yàn)證碼進(jìn)行分離，假設(shè)分別為M1和C1，因?yàn)檫@兩個(gè)信息可能已被被篡改；（4）接收方使用與原始信息相同的信息驗(yàn)證碼函數(shù)（雙方事先約定好的）對收到的信息部分M1計(jì)算其自己的信息驗(yàn)證碼C2；基本思路（5）接收方將自己計(jì)算的接收方信息驗(yàn)證碼C2同分離出來的信息驗(yàn)證碼C1進(jìn)行對比，如果相等，接收方斷定收到的信息M1與用戶發(fā)送的信息M0是相同的，如果不相等，則接收方知道原始信息已經(jīng)被篡改過。基本思路模型圖3.2數(shù)據(jù)完整性機(jī)制的評價(jià)標(biāo)準(zhǔn)完整性驗(yàn)證的安全性驗(yàn)證碼的主要功能：實(shí)現(xiàn)數(shù)據(jù)完整性的驗(yàn)證安全達(dá)到防偽造、防篡改目的。碰撞性：對于兩個(gè)不同的消息m1和m2，如果它們的驗(yàn)證碼值相同，則就發(fā)生了碰撞完整性驗(yàn)證的安全性驗(yàn)證碼函數(shù)要求滿足的條件抗弱碰撞性：對于給定的消息m1和其驗(yàn)證碼H（m1），找到滿足m2≠m1，且H（m2）＝H（m1）的m2在計(jì)算上不可行抗強(qiáng)碰撞性：找到任何滿足H（m1）＝H（m2）且m2≠m1的消息對（m1，m2）在計(jì)算上是不可行的完整性驗(yàn)證的安全性在數(shù)據(jù)完整性的驗(yàn)證中可能受到的攻擊有：對截獲的部分消息進(jìn)行了增刪改；攻擊者不能分離信息和驗(yàn)證碼，直接用自己的信息整體替換所有的發(fā)送信息；攻擊者可以分析信息和驗(yàn)證碼，用自己的信息只替換信息部分，但無法替換驗(yàn)證碼攻擊者不僅用自己的信息替換信息部分，同時(shí)重新計(jì)算驗(yàn)證碼并替換之。完整性驗(yàn)證中加密的安全數(shù)據(jù)完整性驗(yàn)證的一些機(jī)制需要對其中的內(nèi)容進(jìn)行加密，如對驗(yàn)證碼的加密等，因此密鑰的分發(fā)，密鑰空間的大小，加密算法的選取直接影響完整性驗(yàn)證的性能和安全性。完整性驗(yàn)證算法的性能數(shù)據(jù)完整性驗(yàn)證包括發(fā)送方計(jì)算驗(yàn)證碼，加密，接收方重新計(jì)算驗(yàn)證碼，解密，驗(yàn)證碼比較等。影響性能的主要因素是計(jì)算驗(yàn)證碼和加解密，實(shí)際情況時(shí)要對完整性驗(yàn)證的安全性和性能進(jìn)行折中考慮。數(shù)據(jù)完整性驗(yàn)證的信息有效率數(shù)據(jù)完整性驗(yàn)證的有效率是指原信息部分長度與合并后總信息（包括原消息和驗(yàn)證碼）的長度之比。過長：增加額外的網(wǎng)絡(luò)通信量過短：影響完整性驗(yàn)證的準(zhǔn)確率和安全性3.3網(wǎng)絡(luò)安全中數(shù)據(jù)完整性驗(yàn)證機(jī)制與評價(jià)3.3.1基于數(shù)據(jù)校驗(yàn)的完整性驗(yàn)證機(jī)制與評價(jià)在計(jì)算機(jī)網(wǎng)絡(luò)原理中的循環(huán)冗余校驗(yàn)的檢錯(cuò)技術(shù)，目的就是防止計(jì)算機(jī)網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)幀出現(xiàn)錯(cuò)誤，導(dǎo)致發(fā)送的數(shù)據(jù)幀與接收的數(shù)據(jù)幀不一致網(wǎng)絡(luò)安全中的數(shù)據(jù)完整性驗(yàn)證機(jī)制與計(jì)算機(jī)網(wǎng)絡(luò)原理中的檢錯(cuò)技術(shù)類似。參照CRC冗余碼基于數(shù)據(jù)校驗(yàn)的完整性驗(yàn)證機(jī)制步驟1：A計(jì)算數(shù)據(jù)M0的冗余碼N0；步驟2：A將M0和N0合在一起，通過網(wǎng)絡(luò)發(fā)送給B；步驟3：B收到合并的信息后，將二者分開，設(shè)為M1和N1；基于數(shù)據(jù)校驗(yàn)的完整性驗(yàn)證機(jī)制步驟4：B用與原始信息相同的循環(huán)冗余方法重新計(jì)算信息M1的冗余碼N2；步驟5：B將計(jì)算的冗余碼N2同分離的冗余碼N1進(jìn)行對比，如果相等，B斷定信息是完整的，如果不相等，則B斷定信息是不完整的?；跀?shù)據(jù)校驗(yàn)的完整性驗(yàn)證機(jī)制機(jī)制評價(jià)優(yōu)點(diǎn)：該機(jī)制可以對網(wǎng)絡(luò)系統(tǒng)造成的數(shù)據(jù)不一致進(jìn)行驗(yàn)證，特別是在實(shí)現(xiàn)對數(shù)據(jù)鏈路層每個(gè)幀的數(shù)據(jù)差錯(cuò)檢驗(yàn)中取得了很好的效果。數(shù)據(jù)校驗(yàn)和完整性驗(yàn)證的區(qū)別？數(shù)據(jù)校驗(yàn)和完整性驗(yàn)證的區(qū)別數(shù)據(jù)校驗(yàn)是為了檢查出因?yàn)榫W(wǎng)絡(luò)自身的原因?qū)е碌臄?shù)據(jù)不一致，是由網(wǎng)絡(luò)系統(tǒng)隨機(jī)產(chǎn)生的數(shù)據(jù)完整性驗(yàn)證是為了檢查出可能的惡意主動攻擊者造成的數(shù)據(jù)不一致，后者會處心積慮地避開完整性驗(yàn)證的校驗(yàn)。缺點(diǎn)與改進(jìn)CRC冗余碼長度短計(jì)算方法需改進(jìn)，使得信息的每一位都與冗余碼密切相關(guān)目前常見得新的計(jì)算冗余碼的方法：MD5、SHA-1，冗余碼更名為消息摘要，長度分別為128、160位3.3.2基于消息摘要的完整性驗(yàn)證機(jī)制消息摘要也稱為消息的指紋消息摘要一般通過摘要函數(shù)H生成，摘要函數(shù)是單向函數(shù)，不是一種加密，使用摘要函數(shù)從消息生成摘要很容易，但是通過摘要來還原消息卻很難。哈希函數(shù)是常用算法，也稱為雜湊函數(shù)、散列函數(shù)、hash函數(shù)等基于消息摘要的完整性驗(yàn)證機(jī)制常用算法：MD4、MD5、SHA-1消息摘要使用散列函數(shù)把一段任意長度的消息M映射到一個(gè)短的固定長的數(shù)據(jù)MD雪崩效應(yīng)：消息摘要的每一位與原消息的每一位都關(guān)聯(lián)。實(shí)現(xiàn)機(jī)制步驟1：A根據(jù)要發(fā)送的消息M0，利用MD5、SHA-1等哈希函數(shù)H（雙方事先商定好的）產(chǎn)生消息摘要MD0；步驟2：A通過網(wǎng)絡(luò)將M0和MD0一起發(fā)送到B實(shí)現(xiàn)機(jī)制步驟3：B收到的信息設(shè)為M1，摘要設(shè)為MD1，B重新用A使用的產(chǎn)生摘要的函數(shù)H計(jì)算消息摘要，設(shè)為MD2步驟4：B比較MD2和MD1是否相同，如果相等，B斷定數(shù)據(jù)是完整的，如果不相等，則B斷定數(shù)據(jù)遭到篡改。評價(jià)優(yōu)點(diǎn)：雙方不需要共享密鑰；消息摘要與信息密切關(guān)聯(lián)，若驗(yàn)證成功，接收者確信信息未被更改過；信息的有效率高。消息摘要算法通常產(chǎn)生長度為128位或160位的消息摘要，即任何兩個(gè)消息摘要相同的概率分別為2128或2160分之一，顯然，這在實(shí)際上沖突的可能性極小。評價(jià)如果攻擊者同時(shí)修改信息及其摘要，接收者就無法判斷其完整性將摘要與加密結(jié)合如何解決？消息摘要舉例摘要類似于縱向冗余校驗(yàn)(LRC，LongitudinalRedundancyCheck)和循環(huán)冗余校驗(yàn)(CRC，CyclicRedundancyCheck)

消息摘要下圖顯示了發(fā)送方的LRC計(jì)算。LRC將位塊組成列表(行)，例如，如果要發(fā)送32位，則把其排成四行，然后計(jì)算每個(gè)列(共8列)有多少個(gè)1位如果1位為奇數(shù)，則稱為奇性，在陰影LRC行中用一個(gè)1位表示；相反，如果1位為偶數(shù)，則稱為偶性，在陰影LRC行中用一個(gè)0位表示)。消息摘要例子消息摘要舉例每列計(jì)算奇偶位，生成一個(gè)新行，共八個(gè)奇偶位，成為整個(gè)塊的奇偶位。這樣，LRC實(shí)際上是原消息的消息摘要。

計(jì)算結(jié)束后將數(shù)據(jù)和LRC發(fā)送給接收方。接收方把數(shù)據(jù)和LRC分開，對數(shù)據(jù)塊重新執(zhí)行LRC運(yùn)算，然后將得到的LRC值與從發(fā)送方收到的LRC值比較。如果兩個(gè)LRC值相同，則可以相信發(fā)送方發(fā)來的信息沒有在中途發(fā)生改變。

消息摘要的思想

消息摘要采用類似原理，但范圍更大一些例如，假設(shè)數(shù)字4000要用4除，得到1000。則4可以作為4000的摘要。

一個(gè)要點(diǎn)是：將4000除以4總是得到1000。如果改變4000，則結(jié)果不再是4，即原消息改了，則摘要一定會改變。消息摘要的思想

另一個(gè)要點(diǎn)是：如果只給出數(shù)字4而不給出更多信息，則無法追溯原來的公式4×1000=4000。即消息的摘要(這里是數(shù)字4)沒有暴露原消息的任何信息(這里是數(shù)字4000)，不能逆向返回（單向函數(shù)，與加密不同，不能解密）

消息摘要的思想假設(shè)要計(jì)算數(shù)字7391743的消息摘要，則可以將數(shù)字中每個(gè)位與下一個(gè)位相乘(是0時(shí)排除)，忽略乘積中的第一位。這樣，我們對數(shù)據(jù)塊進(jìn)行散列運(yùn)算(或消息摘要算法)，得到其散列或消息摘要要比原消息小得多。

一個(gè)簡單消息摘要簡例兩個(gè)消息摘要相同的概率前面考慮的是非常簡單的消息摘要。例如，如果前兩位篡改為99，則摘要的結(jié)果不變，即兩個(gè)不同的消息有相同的摘要，而且很容易求出實(shí)際上，消息摘要的計(jì)算沒有這么簡單。消息摘要通常占128位以上，選擇這么長的消息摘要是有目的的，是為了減少兩個(gè)消息摘要相同的范圍。消息摘要要求

(1)給定某個(gè)消息，消息摘要應(yīng)該相同。即同一個(gè)消息不能有不同的摘要。(2)兩個(gè)不同的原消息很難求出相同的摘要(3)給定消息摘要，應(yīng)該很難求出原先的消息，即，消息摘要不能反向求出（單向函數(shù)），否則就會出現(xiàn)通過摘要暴露原消息的情況消息摘要要求沖突的概念如果兩個(gè)消息得到相同的消息摘要，則會違背上述原則，稱為沖突(collision)。如果兩個(gè)消息摘要發(fā)生沖突，則表示其摘要相同。消息摘要算法通常產(chǎn)生長度為128位或160位的消息摘要，即任何兩個(gè)消息摘要相同的概率分別為2128或2160分之一，顯然，這在實(shí)際上可能性極小。3.3.3基于消息摘要與對稱密鑰加密的完整性驗(yàn)證機(jī)制A用消息摘要算法H計(jì)算信息M0的消息摘要MD0A將M0和MD0和在一起，并使用K加密合并的消息，并通過網(wǎng)絡(luò)發(fā)送給BB收到加密的消息后，用同一密鑰K把密文解密，并將二者分開，分別設(shè)為M1和MD1基于消息摘要與對稱密鑰加密的完整性驗(yàn)證機(jī)制B用與原始信息相同的消息摘要計(jì)算方法H重新計(jì)算M1的消息摘要MD2B將計(jì)算的消息摘要MD2與分離出來的消息摘要MD1進(jìn)行對比，如果相等，B斷定信息是完整的；如果不相等，B就斷定信息遭到篡改機(jī)制評價(jià)優(yōu)點(diǎn)：防止攻擊者篡改消息防止攻擊者同時(shí)把信息部分和消息摘要部分替換并同時(shí)保持它們之間的匹配關(guān)系的攻擊機(jī)制評價(jià)缺點(diǎn)：雙方需共享密鑰K，存在密鑰的發(fā)布問題如何改進(jìn)？3.3.4基于非對稱密鑰和對稱密鑰結(jié)合的完整性驗(yàn)證機(jī)制步驟1：A計(jì)算信息M0的消息摘要（MD0）步驟2：A選定一次性對稱密鑰K1，用完即放棄，防止重放攻擊；步驟3：A取一次性對稱密鑰(K1)，用B的公鑰(K2)加密K1，結(jié)果設(shè)為Bk2(K1)。這個(gè)過程稱為對稱密鑰的密鑰包裝(keywrapping)；基于非對稱密鑰和對稱密鑰結(jié)合的完整性驗(yàn)證機(jī)制步驟4A將M0和MD0合在一起，并使用對稱密鑰(K1)加密合并后的數(shù)據(jù)，結(jié)果設(shè)為：Ak1(M0+MD0)，并通過網(wǎng)絡(luò)將Bk2(K1)+Ak1(M0+MD0)發(fā)送給B；步驟5：B用A所用的非對稱密鑰算法和自己的私鑰(K3)解密Bk2(K1)，這個(gè)過程的輸出是對稱密鑰K1；基于非對稱密鑰和對稱密鑰結(jié)合的完整性驗(yàn)證機(jī)制步驟6：B用A所用的對稱密鑰算法和對稱密鑰K1解密Ak1（M0+MD0），并將二者分開，設(shè)為M1和MD1；步驟7：B用與原始信息相同的消息摘要計(jì)算方法重新計(jì)算信息M1的的消息摘要MD2基于非對稱密鑰和對稱密鑰結(jié)合的完整性驗(yàn)證機(jī)制步驟8：B將計(jì)算的的消息摘要MD2同分離的消息摘要MD1進(jìn)行對比，如果相等，B斷定信息是完整的，如果不相等，則B斷定信息遭到篡改。機(jī)制評價(jià)優(yōu)點(diǎn)：這個(gè)機(jī)制防止了攻擊者替換和篡改信息的攻擊外，解決了密鑰的發(fā)布問題，A隨機(jī)選定一次性對稱密鑰K1，用完即放棄，防止了重放攻擊。機(jī)制評價(jià)缺點(diǎn)：需要保證公鑰的真實(shí)可信性是需要計(jì)算信息摘要，可以簡化驗(yàn)證的步驟，不用計(jì)算信息摘要，一個(gè)最直接的方法是直接用加密方法實(shí)現(xiàn)數(shù)據(jù)完整性驗(yàn)證3.3.5基于對稱密鑰直接加密原消息的完整性驗(yàn)證機(jī)制與評價(jià)加密本身提供一種消息完整性驗(yàn)證方法，假設(shè)A、B雙方共享密鑰K，并且發(fā)送的是有意義的消息，則直接加密原消息也可以起到完整性驗(yàn)證的作用。由于攻擊者不知道密鑰K，因此攻擊者就不知道如何改變密文中的消息位才能在明文中產(chǎn)生預(yù)期的改變。接收方可以根據(jù)解密后的明文是否有意義來進(jìn)行完整性驗(yàn)證。實(shí)現(xiàn)機(jī)制A使用對稱密鑰機(jī)密機(jī)制加密M0，并通過網(wǎng)絡(luò)發(fā)送給BB收到加密的信息后，用同一密鑰解密B根據(jù)解密后的明文是否有意義來判斷消息是否完整，如果有意義，B認(rèn)為數(shù)據(jù)是完整的，如果是無意義的亂碼，B就認(rèn)為數(shù)據(jù)遭到篡改。機(jī)制評價(jià)優(yōu)點(diǎn)：不增加額外的驗(yàn)證碼，數(shù)據(jù)完整性的信息有效率高具有保密性和完整性驗(yàn)證的雙重功能缺點(diǎn)：密鑰的發(fā)布問題改進(jìn)：與非對稱密鑰加密體制結(jié)合來解決密鑰的發(fā)布3.3.6基于RSA數(shù)字簽名的完整性驗(yàn)證機(jī)制步驟1：A用自己的私鑰加密消息M，用EA私(M）表示；步驟2：把加密的消息發(fā)送給B；步驟3：B接收到加密的消息后用A的公鑰解密，用公式DA公(EA私(M）)表示；3.3.6基于RSA數(shù)字簽名的完整性驗(yàn)證機(jī)制步驟4：B根據(jù)解密后的明文是否有意義來進(jìn)行消息完整性驗(yàn)證，如果有意義，B認(rèn)為數(shù)據(jù)是完整的，如果是無意義的亂碼，則B認(rèn)為的數(shù)據(jù)遭到篡改。機(jī)制評價(jià)優(yōu)點(diǎn)：在本機(jī)制中，參照物的依據(jù)就是解密后的信息是否有意義。解決了密鑰的分發(fā)問題。在完整性驗(yàn)證方面，即使攻擊者C在中途截獲了加密消息，能夠用A的公鑰解密消息，然后篡改消息，也沒法達(dá)到任何目的機(jī)制評價(jià)缺點(diǎn)：加密的速度慢；第二個(gè)缺點(diǎn)是發(fā)送的明文必須是有意義的明文，在某些場合下，有意義的明文并不好判斷。因此二進(jìn)制文件需要通過增加額外驗(yàn)證碼來進(jìn)行完整性驗(yàn)證。由于A的公鑰是公開的，任何人都可以解密A加密的消息，因此該機(jī)制不具有保密作用。3.3.7加密原消息作為驗(yàn)證碼的完整性驗(yàn)證機(jī)制A使用對稱密鑰加密機(jī)制加密M0，設(shè)為EK(M0)，作為驗(yàn)證碼A將M0和EK(M0)合在一起，并通過網(wǎng)絡(luò)發(fā)送給BB收到數(shù)據(jù)后，將兩者分開，設(shè)原消息為M1(可能已被篡改)，用同一密鑰K解密驗(yàn)證碼，解密的結(jié)果設(shè)為M2B將M2與M1進(jìn)行對比，如果相等，B斷定信息是完整的；如果不相等，B就斷定信息遭到篡改。機(jī)制評價(jià)優(yōu)點(diǎn)：不需要額外算法去產(chǎn)生驗(yàn)證碼，只需把加密的原消息作為驗(yàn)證碼(篡改、替換)缺點(diǎn)：驗(yàn)證碼太大沒有保密作用3.3.8基于消息認(rèn)證碼的數(shù)據(jù)完整性驗(yàn)證機(jī)制如果攻擊者同時(shí)修改摘要及信息，并使他們相匹配，則接收者無法判斷其完整性，為此將摘要與加密結(jié)合，這種技術(shù)稱為消息鑒別碼（MessageAuthenticationCode,MAC）基于消息認(rèn)證碼的數(shù)據(jù)完整性驗(yàn)證機(jī)制實(shí)現(xiàn)機(jī)制步驟1：A根據(jù)要發(fā)送的消息M0，利用密鑰K通過MAC產(chǎn)生函數(shù)C產(chǎn)生MAC0=Ck(M0)；步驟2：A將M0和MAC0合在一起，并通過網(wǎng)絡(luò)發(fā)送到B；步驟3：B收到信息后，并將二者分開，設(shè)為M1和MAC1；基于消息認(rèn)證碼的數(shù)據(jù)完整性驗(yàn)證機(jī)制步驟4：B利用密鑰K對收到的信息M1用與A相同的MAC產(chǎn)生函數(shù)C重新計(jì)算M1的驗(yàn)證碼，設(shè)為MAC2步驟5：B比較MAC2和MAC1是否相同，如果相等，B斷定數(shù)據(jù)是完整的，如果不相等，則B斷定數(shù)據(jù)遭到篡改。機(jī)制評價(jià)優(yōu)點(diǎn)：這種機(jī)制使接收者確信信息未被更改過防止消息被整體替換，因?yàn)楣粽咛鎿Q了消息，并計(jì)算自己的MAC，由于不知道K，無法再次生成正確的MAC。具有身份鑒別的作用，其他人不能假冒信息有效率高消息認(rèn)證碼（MAC）的計(jì)算眼熟么？取左邊n位消息認(rèn)證碼（MAC）的計(jì)算典型的鑒別碼生成算法主要基于DES的認(rèn)證算法，該算法采用CBC模式。最后一輪迭代結(jié)束后，取結(jié)果的左邊n位作為鑒別碼。信息的有效率為m/L，其中m為信息長度，n為鑒別碼長度，L=m+n缺點(diǎn)是：驗(yàn)證過程需要加密。機(jī)制評價(jià)缺點(diǎn)：沒有保密作用，只有完整性驗(yàn)證作用密鑰的發(fā)布問題（共享密鑰K）算法改進(jìn)對于密鑰的發(fā)布問題，可以采用基于哈希函數(shù)的完整性驗(yàn)證機(jī)制來改進(jìn)哈希函數(shù)的計(jì)算類似MAC，但不需要雙方共享密鑰hash與MAC的區(qū)別MAC在產(chǎn)生消息認(rèn)證碼時(shí)需要對全部數(shù)據(jù)進(jìn)行加密，速度慢；Hash是一種直接產(chǎn)生認(rèn)證碼的方法，不需要雙方共享密鑰Hash可以用于數(shù)字簽名MAC函數(shù)與加密函數(shù)的聯(lián)系與區(qū)別MAC函數(shù)與加密函數(shù)類似，需要明文、密鑰和算法的參與MAC算法不要求可逆性，而加密算法必須是可逆的。復(fù)習(xí)簡述基于數(shù)據(jù)校驗(yàn)的完整性驗(yàn)證機(jī)制簡述基于消息摘要與對稱密鑰加密的完整性驗(yàn)證機(jī)制簡述基于非對稱密鑰和對稱密鑰結(jié)合的完整性性驗(yàn)證機(jī)制3.4MD5消息摘要計(jì)算算法與評價(jià)

消息摘要能夠完成完整性驗(yàn)證必須滿足的要求：兩個(gè)不同的原消息很難求出相同的摘要給定消息摘要，很難求出原來的消息3.4.1MD5概述

MD5消息摘要算法是90年代初由RonRivest開發(fā)的。MD5的全稱是message-digestalgorithm5（信息-摘要算法），作用是把一個(gè)隨機(jī)長度的信息變化產(chǎn)生一個(gè)128位的信息摘要。MD5概述

MD5根源于一系列消息摘要算法，都是由RonRivest開發(fā)的。原先的消息摘要算法稱為MD，很快進(jìn)入下一版MD2，但很脆弱。RonRivest開始開發(fā)MD3，結(jié)果失敗了(因此沒有發(fā)布)。后來，RonRivest開發(fā)了MD4，但很快發(fā)現(xiàn)其還是不理想，因此最終推出了MD5。

MD2簡介Rivest在1989年開發(fā)出MD2算法。在這個(gè)算法中，首先對信息進(jìn)行數(shù)據(jù)補(bǔ)位，使信息的字節(jié)長度是16的倍數(shù)。然后，以一個(gè)16位的檢驗(yàn)和追加到信息末尾，并且根據(jù)這個(gè)新產(chǎn)生的信息計(jì)算出散列值。后來，Rogier和Chauvaud發(fā)現(xiàn)如果忽略了檢驗(yàn)將和MD2產(chǎn)生沖突。MD2算法加密后結(jié)果是唯一的。

MD4簡介Rivest在1990年又開發(fā)出MD4算法。Denboer和Bosselaers以及其他人很快的發(fā)現(xiàn)了攻擊MD4版本中第一步和第三步的漏洞。Dobbertin向大家演示了如何利用一部普通的個(gè)人電腦在幾分鐘內(nèi)找到MD4完整版本中的沖突。毫無疑問，MD4就此被淘汰掉了。盡管MD4算法在安全上有個(gè)這么大的漏洞，但它對在其后才被開發(fā)出來的好幾種信息安全加密算法的出現(xiàn)卻有著不可忽視的引導(dǎo)作用。MD5簡介1991年，Rivest開發(fā)出技術(shù)上更為趨近成熟的md5算法。它在MD4的基礎(chǔ)上增加了“安全-帶子”（safety-belts）的概念。雖然MD5比MD4復(fù)雜度大一些，但卻更為安全。這個(gè)算法很明顯的由四個(gè)和MD4設(shè)計(jì)有少許不同的步驟組成在MD5算法中，信息-摘要的大小和填充的必要條件與MD4完全相同。Denboer和Bosselaers曾發(fā)現(xiàn)MD5算法中的假沖突（pseudo-collisions），但除此之外就沒有其他被發(fā)現(xiàn)的加密后結(jié)果了。

MD5算法的目的在驗(yàn)證數(shù)據(jù)完整性方面是安全的：找到兩個(gè)具有相同摘要的消息在計(jì)算上是不可行的（不是理論上不可行）。直接安全性：算法不基于任何安全性假設(shè)，例如因子分解難度。算法有效率高：算法基于32位的簡單操作，適于高速軟件實(shí)現(xiàn)。算法簡單：算法中沒有大型數(shù)據(jù)結(jié)構(gòu)和復(fù)雜的程序?；靖攀鯩D5以512位分組來處理輸入的信息，且每一分組又被劃分為16個(gè)32位子分組經(jīng)過了一系列的處理后，算法的輸出由四個(gè)32位分組組成，將這四個(gè)32位分組連接后將生成一個(gè)128位消息摘要。

每組：512

128,位數(shù)是原來的1/4，不是指所有信息的長度，是指每組的512位被縮減到原來的1/4，原消息額可以任意長。MD5工作的第1步：填充MD5的第1步是在原消息中增加填充位，目的是使原消息長度等于一個(gè)值，即比512的倍數(shù)少64位（64位留下來放原消息的長度）例如，如果原消息長度為1000位，則要填充多少位？512*3-64-1000=472MD5工作的第1步：填充填充對是由一個(gè)1和多個(gè)0組成的位串。注意填充總是增加，即使消息長度已經(jīng)是比512的倍數(shù)少64。因此，如果消息長度已經(jīng)是448，則要填充512位，使長度變成960位。因此，填充長度為1——512的值。填充過程第2步：添加長度增加填充位后，下一步要計(jì)算消息原長，這個(gè)消息原長表示為64位值，添加到加進(jìn)填充后的消息末尾。先計(jì)算消息長度，不包括填充位(即增加填充位前的長度)。例如，如果原消息為1000位，則填充472位，但長度為1000，而不是1472。第2步：添加長度注意：如果消息長度超過264位(即64位無法表示，因?yàn)橄⑻L)，則只用長度的低64位，即等于計(jì)算lengthmod264。我們看到，這時(shí)消息長度為512的倍數(shù)。第2步：添加長度第3步：將輸入分成512位的塊第4步：初始化鏈接變量A，B，C，D都是32位的鏈接變量（ChainingVariable），實(shí)際是常量， A=0x01234567， B=0x89abcdef， C=0xfedcba98， D=0x76543210。第5步：處理塊預(yù)處理結(jié)束后，開始實(shí)際的計(jì)算，對消息中的每個(gè)512位塊計(jì)算4輪，在每一輪中每個(gè)小塊按不同的順序參與運(yùn)算4輪的第一步進(jìn)行不同的P處理，其他步驟相同。第5步：處理塊1、將四個(gè)鏈接變量復(fù)制到四個(gè)變量中使a=A，b=B，c=C，d=D，實(shí)際上，這個(gè)算法將a、b、c、d組合成128位寄存器(abcd)，寄存器(abcd)在實(shí)際算法運(yùn)算中保存中間結(jié)果和最終結(jié)果。第5步：處理塊2、將當(dāng)前512位塊分解為16個(gè)子塊，每個(gè)子塊為32位3、四輪的每一輪有16次迭代（共64次迭代），每一次迭代處理一個(gè)塊中的16個(gè)子塊。第5步：處理塊每一輪（16次迭代）的輸入如下：(a)16個(gè)子塊(32位)M[0]，M[1]，…，M[15]

(b)變量a,b,c,d（每個(gè)32位）(c)常量t（16/64個(gè)，每個(gè)32位）表示為t[k]，其中k為1～64。由于有四輪，因此每一輪用64個(gè)t值中的16個(gè)(d)S(循環(huán)左移S位)常量數(shù)組t的構(gòu)成常量數(shù)組t的構(gòu)成是：t[i]=int(232xabs(sin(i)))=int(4294967296

xabs(sin(i)))為32位整型數(shù)。函數(shù)sin(i)中i取弧度。其作用是隨機(jī)化32位整型量，消除輸入數(shù)據(jù)的規(guī)律性。每一輪的輸入第1輪的輸入內(nèi)容變量a、b、c、d參加16個(gè)子塊的運(yùn)算的順序按子塊序號的遞增順序參加，即：M[1]、M[2]、……M[16]64個(gè)常量數(shù)組元素的前16個(gè)元素參加運(yùn)算，即：t[1]、t[2]、……t[16]第1輪的輸入內(nèi)容每一輪的每次運(yùn)算結(jié)果循環(huán)左移S位，S在不斷變化，分別是7、12、17、22，重復(fù)四次，一共是16次。每一次新的操作前a、b、c、d循環(huán)右移一位見P66，表3-9第1輪輸入的內(nèi)容第2輪的輸入內(nèi)容變量a、b、c、d參加16個(gè)子塊參加的運(yùn)算的順序按近似遞增等差數(shù)列參加，公差為5，下標(biāo)為：1,6,11,0,5,10,15,4,9,14,3,8,13,2,7,1264個(gè)常量數(shù)組元素的第2組16個(gè)元素參加運(yùn)算，即：t[17]、t[18]、……t[32]第2輪的輸入內(nèi)容第二輪的每次運(yùn)算結(jié)果循環(huán)左移S位，S在不斷變化，分別是5、9、14、20，重復(fù)四次，一共是16次。每一次新的操作前a、b、c、d循環(huán)右移一位見P67，表3-10第2輪的輸入內(nèi)容第3輪的輸入內(nèi)容變量a、b、c、d參加16個(gè)子塊參加的運(yùn)算的順序按近似遞增等差數(shù)列參加，公差為3，下標(biāo)為：5,8,11,14,1,4,7,10,13,0,3,6,9,12,15,264個(gè)常量數(shù)組元素的第三組16個(gè)元素參加運(yùn)算，即：t[33]、t[34]、……t[48]第3輪的輸入內(nèi)容每一輪的每次運(yùn)算結(jié)果循環(huán)左移S位，S在不斷變化，分別是4、11、16、23，重復(fù)四次，一共是16次。每一次新的操作前a、b、c、d循環(huán)右移一位見P68，表3-11第3輪的輸入內(nèi)容第4輪的輸入內(nèi)容變量a、b、c、d參加16個(gè)子塊參加，運(yùn)算的順序按近似遞增等差數(shù)列參加，公差為7，下標(biāo)為：0,7,14,5,12,3,10,1,8,15,6,13,4,11,2,964個(gè)常量數(shù)組元素的第四組16個(gè)元素參加運(yùn)算，即：t[49]、t[50]、……t[64]第4輪的輸入內(nèi)容每一輪的每次運(yùn)算結(jié)果循環(huán)左移S位，S在不斷變化，分別是6、10、15、21，重復(fù)四次，一共是16次。每一次新的操作前a、b、c、d循環(huán)右移一位見P69，表3-12第4輪的輸入內(nèi)容每一輪的操作（壓縮操作）(1)處理P首先處理b、c、d，這個(gè)處理P在四輪中不同。（32位）(2)變量a加進(jìn)處理P的輸出(即寄存器abcd)。(3)消息子塊M[i]加進(jìn)第2步輸出。(4)常量t[k]加進(jìn)第3步輸出。每一輪的操作（壓縮操作）(5)第4步的輸出(即寄存器abcd內(nèi)容)循環(huán)左移S位(S值不斷改變)。(6)變量b加進(jìn)第5步輸出(即寄存器abcd)。(7)第6步的輸出(即寄存器abcd內(nèi)容)賦值給變量a(8)第7步的輸出成為下一步的新abcd。（128位）(9)新一輪迭代之前，abcd循環(huán)右移一位每一輪的操作處理P輪次處理P1（bANDc）OR(NOTb)AND(d))2（bANDd）OR(cAND(NOTd))3bXORcXORd4cXOR(bOR(NOTd))MD5算法評價(jià)該機(jī)制將要輸入的信息分割成等長的512的塊，每一塊計(jì)算出自己的摘要，并將每塊的摘要參與到下一塊摘要的計(jì)算中，這種鏈接模式使最后一塊的摘要(整個(gè)消息的摘要)跟原信息的每一塊都關(guān)聯(lián)，思路與CBC思路類似。MD5滿足的要求在驗(yàn)證數(shù)據(jù)完整性方面是安全的算法效率高算法簡單MD5算法的核心處理是重復(fù)進(jìn)行位邏輯運(yùn)算，使得最終輸出的摘要中每一位與輸入消息中所有位相關(guān)，因此達(dá)到很好的混淆效果，具有雪崩現(xiàn)象。MD5的破解在2004年8月17日美國加州圣巴巴拉召開的國際密碼學(xué)會議（Crypto’2004）上，來自中國山東大學(xué)的王小云教授做了破解MD5算法的報(bào)告。國內(nèi)有些媒體甚至認(rèn)為這一破解會導(dǎo)致數(shù)字簽名安全大廈的轟然倒塌。MD5的破解一個(gè)安全散列算法的安全性是基于這樣的假設(shè)：知道一個(gè)信息