MD5快速碰撞算法之研究.pdf

1、MD5是一種散列算法，該算法與數(shù)字簽名密切相關(guān)。研究MD5算法在信息安全領(lǐng)域有著十分重要的意義。
　　 搜索MD5碰撞是指找出一對(duì)報(bào)文M0和M1使得MD5(M0)=MD5(M1)。
　　 王小云等提出的報(bào)文修改法實(shí)現(xiàn)了MD5碰撞研究的突破，但是該方法的搜索效率很低，用個(gè)人計(jì)算機(jī)無(wú)法在短時(shí)間內(nèi)得到搜索結(jié)果。
　　 單報(bào)文修改法通過(guò)修改m[0]至m[15]使得M0滿(mǎn)足第一條差分路徑中P[1]至P[16]這16個(gè)點(diǎn)的條

2、件。而多報(bào)文修改法通過(guò)修改報(bào)文最遠(yuǎn)可以到達(dá)P[24]這個(gè)點(diǎn)。到達(dá)P[24]點(diǎn)后，m[0]至m[15]已全部確定，接下去我們只能通過(guò)驗(yàn)證M0來(lái)判斷它是否滿(mǎn)足P[25]至P[64]各點(diǎn)的條件。如果發(fā)現(xiàn)M0不滿(mǎn)足P[25]至P[64]中任何一點(diǎn)的條件，則需要重新隨機(jī)產(chǎn)生一個(gè)新的M0，再重復(fù)前面做過(guò)的報(bào)文修改步驟到達(dá)P[24]點(diǎn)。很明顯，要使得P[25]至P[64]各點(diǎn)條件全部滿(mǎn)足的概率達(dá)到1，則要求到達(dá)P[24]點(diǎn)的Mo有237個(gè)。
　

3、　 由于報(bào)文修改法不能重復(fù)利用已滿(mǎn)足P[1]到P[24]點(diǎn)條件的M0，從而造成計(jì)算復(fù)雜度過(guò)高，因此我們以Klima的“隧道法”為基礎(chǔ)，提出了一種稱(chēng)為自由位跨步驗(yàn)證法的MD5碰撞搜索方法。
　　 所謂自由點(diǎn)是指在P[1]至P[24]中的某幾個(gè)點(diǎn)，當(dāng)我們改變這些點(diǎn)的某些位時(shí)，并不會(huì)造成這些點(diǎn)條件的改變。自由點(diǎn)中可以改變的位則稱(chēng)為自由位。
　　 對(duì)于某個(gè)已經(jīng)到達(dá)P[24]點(diǎn)的M0來(lái)說(shuō)，如果它不滿(mǎn)足P[24]點(diǎn)后面某一點(diǎn)的條件