md5的全稱是message-digest algorithm 5（信息-摘要算法），在90年代初由mit laboratory for computer science和rsa data security inc的ronald l. rivest開發(fā)出來，經(jīng)md2、md3和md4發(fā)展而來。它的作用是讓大容量信息在用數(shù)字簽名軟件簽署私人密匙前被"壓縮"成一種保密的格式（就是把一個(gè)任意長(zhǎng)度的字節(jié)串變換成一定長(zhǎng)的大整數(shù)）。不管是md2、md4還是md5，它們都需要獲得一個(gè)隨機(jī)長(zhǎng)度的信息并產(chǎn)生一個(gè)128位的信息摘要。雖然這些算法的結(jié)構(gòu)或多或少有些相似，但md2的設(shè)計(jì)與md4和md5完全不同，那是因?yàn)閙d2是為8位機(jī)器做過設(shè)計(jì)優(yōu)化的，而md4和md5卻是面向32位的電腦。這三個(gè)算法的描述和c語言源代碼在internet rfcs 1321中有詳細(xì)的描述（http://www.ietf.org/rfc/rfc1321.txt），這是一份最權(quán)威的文檔，由ronald l. rivest在1992年8月向ieft提交。
rivest在1989年開發(fā)出md2算法。在這個(gè)算法中，首先對(duì)信息進(jìn)行數(shù)據(jù)補(bǔ)位，使信息的字節(jié)長(zhǎng)度是16的倍數(shù)。然后，以一個(gè)16位的檢驗(yàn)和追加到信息末尾。并且根據(jù)這個(gè)新產(chǎn)生的信息計(jì)算出散列值。后來，rogier和chauvaud發(fā)現(xiàn)如果忽略了檢驗(yàn)和將產(chǎn)生md2沖突。md2算法的加密后結(jié)果是唯一的--既沒有重復(fù)。
為了加強(qiáng)算法的安全性，rivest在1990年又開發(fā)出md4算法。md4算法同樣需要填補(bǔ)信息以確保信息的字節(jié)長(zhǎng)度加上448后能被512整除（信息字節(jié)長(zhǎng)度mod 512 = 448）。然后，一個(gè)以64位二進(jìn)制表示的信息的最初長(zhǎng)度被添加進(jìn)來。信息被處理成512位damg?rd/merkle迭代結(jié)構(gòu)的區(qū)塊，而且每個(gè)區(qū)塊要通過三個(gè)不同步驟的處理。den boer和bosselaers以及其他人很快的發(fā)現(xiàn)了攻擊md4版本中第一步和第三步的漏洞。dobbertin向大家演示了如何利用一部普通的個(gè)人電腦在幾分鐘內(nèi)找到md4完整版本中的沖突（這個(gè)沖突實(shí)際上是一種漏洞，它將導(dǎo)致對(duì)不同的內(nèi)容進(jìn)行加密卻可能得到相同的加密后結(jié)果）。毫無疑問，md4就此被淘汰掉了。
盡管md4算法在安全上有個(gè)這么大的漏洞，但它對(duì)在其后才被開發(fā)出來的好幾種信息安全加密算法的出現(xiàn)卻有著不可忽視的引導(dǎo)作用。除了md5以外，其中比較有名的還有sha-1、ripe-md以及haval等。
一年以后，即1991年，rivest開發(fā)出技術(shù)上更為趨近成熟的md5算法。它在md4的基礎(chǔ)上增加了"安全-帶子"（safety-belts）的概念。雖然md5比md4稍微慢一些，但卻更為安全。這個(gè)算法很明顯的由四個(gè)和md4設(shè)計(jì)有少許不同的步驟組成。在md5算法中，信息-摘要的大小和填充的必要條件與md4完全相同。den boer和bosselaers曾發(fā)現(xiàn)md5算法中的假?zèng)_突（pseudo-collisions），但除此之外就沒有其他被發(fā)現(xiàn)的加密后結(jié)果了。
van oorschot和wiener曾經(jīng)考慮過一個(gè)在散列中暴力搜尋沖突的函數(shù)（brute-force hash function），而且他們猜測(cè)一個(gè)被設(shè)計(jì)專門用來搜索md5沖突的機(jī)器（這臺(tái)機(jī)器在1994年的制造成本大約是一百萬美元）可以平均每24天就找到一個(gè)沖突。但單從1991年到2001年這10年間，竟沒有出現(xiàn)替代md5算法的md6或被叫做其他什么名字的新算法這一點(diǎn)，我們就可以看出這個(gè)瑕疵并沒有太多的影響md5的安全性。上面所有這些都不足以成為md5的在實(shí)際應(yīng)用中的問題。并且，由于md5算法的使用不需要支付任何版權(quán)費(fèi)用的，所以在一般的情況下（非絕密應(yīng)用領(lǐng)域。但即便是應(yīng)用在絕密領(lǐng)域內(nèi)，md5也不失為一種非常優(yōu)秀的中間技術(shù)），md5怎么都應(yīng)該算得上是非常安全的了。
算法的應(yīng)用
md5的典型應(yīng)用是對(duì)一段信息（message）產(chǎn)生信息摘要（message-digest），以防止被篡改。比如，在unix下有很多軟件在下載的時(shí)候都有一個(gè)文件名相同，文件擴(kuò)展名為.md5的文件，在這個(gè)文件中通常只有一行文本，大致結(jié)構(gòu)如：
md5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461
這就是tanajiya.tar.gz文件的數(shù)字簽名。md5將整個(gè)文件當(dāng)作一個(gè)大文本信息，通過其不可逆的字符串變換算法，產(chǎn)生了這個(gè)唯一的md5信息摘要。如果在以后傳播這個(gè)文件的過程中，無論文件的內(nèi)容發(fā)生了任何形式的改變（包括人為修改或者下載過程中線路不穩(wěn)定引起的傳輸錯(cuò)誤等），只要你對(duì)這個(gè)文件重新計(jì)算md5時(shí)就會(huì)發(fā)現(xiàn)信息摘要不相同，由此可以確定你得到的只是一個(gè)不正確的文件。如果再有一個(gè)第三方的認(rèn)證機(jī)構(gòu)，用md5還可以防止文件作者的"抵賴"，這就是所謂的數(shù)字簽名應(yīng)用。
md5還廣泛用于加密和解密技術(shù)上。比如在unix系統(tǒng)中用戶的密碼就是以md5（或其它類似的算法）經(jīng)加密后存儲(chǔ)在文件系統(tǒng)中。當(dāng)用戶登錄的時(shí)候，系統(tǒng)把用戶輸入的密碼計(jì)算成md5值，然后再去和保存在文件系統(tǒng)中的md5值進(jìn)行比較，進(jìn)而確定輸入的密碼是否正確。通過這樣的步驟，系統(tǒng)在并不知道用戶密碼的明碼的情況下就可以確定用戶登錄系統(tǒng)的合法性。這不但可以避免用戶的密碼被具有系統(tǒng)管理員權(quán)限的用戶知道，而且還在一定程度上增加了密碼被破解的難度。
正是因?yàn)檫@個(gè)原因，現(xiàn)在被黑客使用最多的一種破譯密碼的方法就是一種被稱為"跑字典"的方法。有兩種方法得到字典，一種是日常搜集的用做密碼的字符串表，另一種是用排列組合方法生成的，先用md5程序計(jì)算出這些字典項(xiàng)的md5值，然后再用目標(biāo)的md5值在這個(gè)字典中檢索。我們假設(shè)密碼的最大長(zhǎng)度為8位字節(jié)（8 bytes），同時(shí)密碼只能是字母和數(shù)字，共26+26+10=62個(gè)字符，排列組合出的字典的項(xiàng)數(shù)則是p(62,1)+p(62,2)….+p(62,8)，那也已經(jīng)是一個(gè)很天文的數(shù)字了，存儲(chǔ)這個(gè)字典就需要tb級(jí)的磁盤陣列，而且這種方法還有一個(gè)前提，就是能獲得目標(biāo)賬戶的密碼md5值的情況下才可以。這種加密技術(shù)被廣泛的應(yīng)用于unix系統(tǒng)中，這也是為什么unix系統(tǒng)比一般操作系統(tǒng)更為堅(jiān)固一個(gè)重要原因。
算法描述
對(duì)md5算法簡(jiǎn)要的敘述可以為：md5以512位分組來處理輸入的信息，且每一分組又被劃分為16個(gè)32位子分組，經(jīng)過了一系列的處理后，算法的輸出由四個(gè)32位分組組成，將這四個(gè)32位分組級(jí)聯(lián)后將生成一個(gè)128位散列值。
在md5算法中，首先需要對(duì)信息進(jìn)行填充，使其字節(jié)長(zhǎng)度對(duì)512求余的結(jié)果等于448。因此，信息的字節(jié)長(zhǎng)度（bits length）將被擴(kuò)展至n*512+448，即n*64+56個(gè)字節(jié)（bytes），n為一個(gè)正整數(shù)。填充的方法如下，在信息的后面填充一個(gè)1和無數(shù)個(gè)0，直到滿足上面的條件時(shí)才停止用0對(duì)信息的填充。然后，在在這個(gè)結(jié)果后面附加一個(gè)以64位二進(jìn)制表示的填充前信息長(zhǎng)度。經(jīng)過這兩步的處理，現(xiàn)在的信息字節(jié)長(zhǎng)度=n*512+448+64=(n+1)*512，即長(zhǎng)度恰好是512的整數(shù)倍。這樣做的原因是為滿足后面處理中對(duì)信息長(zhǎng)度的要求。
md5中有四個(gè)32位被稱作鏈接變量（chaining variable）的整數(shù)參數(shù)，他們分別為：a=0x01234567，b=0x89abcdef，c=0xfedcba98，d=0x76543210。
當(dāng)設(shè)置好這四個(gè)鏈接變量后，就開始進(jìn)入算法的四輪循環(huán)運(yùn)算。循環(huán)的次數(shù)是信息中512位信息分組的數(shù)目。
將上面四個(gè)鏈接變量復(fù)制到另外四個(gè)變量中：a到a，b到b，c到c，d到d。
主循環(huán)有四輪（md4只有三輪），每輪循環(huán)都很相似。第一輪進(jìn)行16次操作。每次操作對(duì)a、b、c和d中的其中三個(gè)作一次非線性函數(shù)運(yùn)算，然后將所得結(jié)果加上第四個(gè)變量，文本的一個(gè)子分組和一個(gè)常數(shù)。再將所得結(jié)果向右環(huán)移一個(gè)不定的數(shù)，并加上a、b、c或d中之一。最后用該結(jié)果取代a、b、c或d中之一。
以一下是每次操作中用到的四個(gè)非線性函數(shù)（每輪一個(gè)）。
f(x,y,z) =(x&y)|((~x)&z)
g(x,y,z) =(x&z)|(y&(~z))
h(x,y,z) =x^y^z
i(x,y,z)=y^(x|(~z))
?。?amp;是與，|是或，~是非，^是異或）
這四個(gè)函數(shù)的說明：如果x、y和z的對(duì)應(yīng)位是獨(dú)立和均勻的，那么結(jié)果的每一位也應(yīng)是獨(dú)立和均勻的。
f是一個(gè)逐位運(yùn)算的函數(shù)。即，如果x，那么y，否則z。函數(shù)h是逐位奇偶操作符。
假設(shè)mj表示消息的第j個(gè)子分組（從0到15），<<
ff(a,b,c,d,mj,s,ti)表示a=b+((a+(f(b,c,d)+mj+ti)<< gg(a,b,c,d,mj,s,ti)表示a=b+((a+(g(b,c,d)+mj+ti)<< hh(a,b,c,d,mj,s,ti)表示a=b+((a+(h(b,c,d)+mj+ti)<< ii(a,b,c,d,mj,s,ti)表示a=b+((a+(i(b,c,d)+mj+ti)<<
這四輪（64步）是：
第一輪
ff(a,b,c,d,m0,7,0xd76aa478)
ff(d,a,b,c,m1,12,0xe8c7b756)
ff(c,d,a,b,m2,17,0x242070db)
ff(b,c,d,a,m3,22,0xc1bdceee)
ff(a,b,c,d,m4,7,0xf57c0faf)
ff(d,a,b,c,m5,12,0x4787c62a)
ff(c,d,a,b,m6,17,0xa8304613)
ff(b,c,d,a,m7,22,0xfd469501)
ff(a,b,c,d,m8,7,0x698098d8)
ff(d,a,b,c,m9,12,0x8b44f7af)
ff(c,d,a,b,m10,17,0xffff5bb1)
ff(b,c,d,a,m11,22,0x895cd7be)
ff(a,b,c,d,m12,7,0x6b901122)
ff(d,a,b,c,m13,12,0xfd987193)
ff(c,d,a,b,m14,17,0xa679438e)
ff(b,c,d,a,m15,22,0x49b40821)
第二輪
gg(a,b,c,d,m1,5,0xf61e2562)
gg(d,a,b,c,m6,9,0xc040b340)
gg(c,d,a,b,m11,14,0x265e5a51)
gg(b,c,d,a,m0,20,0xe9b6c7aa)
gg(a,b,c,d,m5,5,0xd62f105d)
gg(d,a,b,c,m10,9,0x02441453)
gg(c,d,a,b,m15,14,0xd8a1e681)
gg(b,c,d,a,m4,20,0xe7d3fbc8)
gg(a,b,c,d,m9,5,0x21e1cde6)
gg(d,a,b,c,m14,9,0xc33707d6)
gg(c,d,a,b,m3,14,0xf4d50d87)
gg(b,c,d,a,m8,20,0x455a14ed)
gg(a,b,c,d,m13,5,0xa9e3e905)
gg(d,a,b,c,m2,9,0xfcefa3f8)
gg(c,d,a,b,m7,14,0x676f02d9)
gg(b,c,d,a,m12,20,0x8d2a4c8a)
第三輪
hh(a,b,c,d,m5,4,0xfffa3942)
hh(d,a,b,c,m8,11,0x8771f681)
hh(c,d,a,b,m11,16,0x6d9d6122)
hh(b,c,d,a,m14,23,0xfde5380c)
hh(a,b,c,d,m1,4,0xa4beea44)
hh(d,a,b,c,m4,11,0x4bdecfa9)
hh(c,d,a,b,m7,16,0xf6bb4b60)
hh(b,c,d,a,m10,23,0xbebfbc70)
hh(a,b,c,d,m13,4,0x289b7ec6)
hh(d,a,b,c,m0,11,0xeaa127fa)
hh(c,d,a,b,m3,16,0xd4ef3085)
hh(b,c,d,a,m6,23,0x04881d05)
hh(a,b,c,d,m9,4,0xd9d4d039)
hh(d,a,b,c,m12,11,0xe6db99e5)
hh(c,d,a,b,m15,16,0x1fa27cf8)
hh(b,c,d,a,m2,23,0xc4ac5665)
第四輪
ii(a,b,c,d,m0,6,0xf4292244)
ii(d,a,b,c,m7,10,0x432aff97)
ii(c,d,a,b,m14,15,0xab9423a7)
ii(b,c,d,a,m5,21,0xfc93a039)
ii(a,b,c,d,m12,6,0x655b59c3)
ii(d,a,b,c,m3,10,0x8f0ccc92)
ii(c,d,a,b,m10,15,0xffeff47d)
ii(b,c,d,a,m1,21,0x85845dd1)
ii(a,b,c,d,m8,6,0x6fa87e4f)
ii(d,a,b,c,m15,10,0xfe2ce6e0)
ii(c,d,a,b,m6,15,0xa3014314)
ii(b,c,d,a,m13,21,0x4e0811a1)
ii(a,b,c,d,m4,6,0xf7537e82)
ii(d,a,b,c,m11,10,0xbd3af235)
ii(c,d,a,b,m2,15,0x2ad7d2bb)
ii(b,c,d,a,m9,21,0xeb86d391)
常數(shù)ti可以如下選擇：
在第i步中，ti是4294967296*abs(sin(i))的整數(shù)部分，i的單位是弧度。(4294967296等于2的32次方)
所有這些完成之后，將a、b、c、d分別加上a、b、c、d。然后用下一分組數(shù)據(jù)繼續(xù)運(yùn)行算法，最后的輸出是a、b、c和d的級(jí)聯(lián)。
當(dāng)你按照我上面所說的方法實(shí)現(xiàn)md5算法以后，你可以用以下幾個(gè)信息對(duì)你做出來的程序作一個(gè)簡(jiǎn)單的測(cè)試，看看程序有沒有錯(cuò)誤。
md5 ("") = d41d8cd98f00b204e9800998ecf8427e
md5 ("a") = 0cc175b9c0f1b6a831c399e269772661
md5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
md5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
md5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
md5 ("abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz0123456789") =
d174ab98d277d9f5a5611c2c9f419d9f
md5 ("123456789012345678901234567890123456789012345678901234567890123456789
01234567890") = 57edf4a22be3c955ac49da2e2107b67a
如果你用上面的信息分別對(duì)你做的md5算法實(shí)例做測(cè)試，最后得出的結(jié)論和標(biāo)準(zhǔn)答案完全一樣，那我就要在這里象你道一聲祝賀了。要知道，我的程序在第一次編譯成功的時(shí)候是沒有得出和上面相同的結(jié)果的。
md5的安全性
md5相對(duì)md4所作的改進(jìn)：
1. 增加了第四輪；
2. 每一步均有唯一的加法常數(shù)；
3. 為減弱第二輪中函數(shù)g的對(duì)稱性從(x&y)|(x&z)|(y&z)變?yōu)?x&z)|(y&(~z))；
4. 第一步加上了上一步的結(jié)果，這將引起更快的雪崩效應(yīng)；
5. 改變了第二輪和第三輪中訪問消息子分組的次序，使其更不相似；
6. 近似優(yōu)化了每一輪中的循環(huán)左移位移量以實(shí)現(xiàn)更快的雪崩效應(yīng)。各輪的位移量互不相同。
[06/22-12:58:29]
加密算法之RSA算法
它是第一個(gè)既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。它易于理解和操作，也很流行。算法的名字以發(fā)明者的名字命名：Ron Rivest, Adi Shamir 和Leonard Adleman。但RSA的安全性一直未能得到理論上的證明。它經(jīng)歷了各種攻擊，至今未被完全攻破。
一、RSA算法 :
首先, 找出三個(gè)數(shù), p, q, r,
其中 p, q 是兩個(gè)相異的質(zhì)數(shù), r 是與 (p-1)(q-1) 互質(zhì)的數(shù)......
p, q, r 這三個(gè)數(shù)便是 private key
接著, 找出 m, 使得 rm == 1 mod (p-1)(q-1).....
這個(gè) m 一定存在, 因?yàn)?r 與 (p-1)(q-1) 互質(zhì), 用輾轉(zhuǎn)相除法就可以得到了.....
再來, 計(jì)算 n = pq.......
m, n 這兩個(gè)數(shù)便是 public key
編碼過程是, 若資料為 a, 將其看成是一個(gè)大整數(shù), 假設(shè) a < n....
如果 a >= n 的話, 就將 a 表成 s 進(jìn)位 (s <= n, 通常取 s = 2^t),
則每一位數(shù)均小於 n, 然後分段編碼......
接下來, 計(jì)算 b == a^m mod n, (0 <= b < n),
b 就是編碼後的資料......
解碼的過程是, 計(jì)算 c == b^r mod pq (0 <= c < pq),
於是乎, 解碼完畢...... 等會(huì)會(huì)證明 c 和 a 其實(shí)是相等的
如果第三者進(jìn)行竊聽時(shí), 他會(huì)得到幾個(gè)數(shù): m, n(=pq), b......
他如果要解碼的話, 必須想辦法得到 r......
所以, 他必須先對(duì) n 作質(zhì)因數(shù)分解.........
要防止他分解, 最有效的方法是找兩個(gè)非常的大質(zhì)數(shù) p, q,
使第三者作因數(shù)分解時(shí)發(fā)生困難.........
<定理>
若 p, q 是相異質(zhì)數(shù), rm == 1 mod (p-1)(q-1),
a 是任意一個(gè)正整數(shù), b == a^m mod pq, c == b^r mod pq,
則 c == a mod pq
證明的過程, 會(huì)用到費(fèi)馬小定理, 敘述如下:
m 是任一質(zhì)數(shù), n 是任一整數(shù), 則 n^m == n mod m
(換另一句話說, 如果 n 和 m 互質(zhì), 則 n^(m-1) == 1 mod m)
運(yùn)用一些基本的群論的知識(shí), 就可以很容易地證出費(fèi)馬小定理的........
<證明>
因?yàn)?rm == 1 mod (p-1)(q-1), 所以 rm = k(p-1)(q-1) + 1, 其中 k 是整數(shù)
因?yàn)樵?modulo 中是 preserve 乘法的
(x == y mod z and u == v mod z => xu == yv mod z),
所以, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1)+1) mod pq
1. 如果 a 不是 p 的倍數(shù), 也不是 q 的倍數(shù)時(shí),
則 a^(p-1) == 1 mod p (費(fèi)馬小定理) => a^(k(p-1)(q-1)) == 1 mod p
a^(q-1) == 1 mod q (費(fèi)馬小定理) => a^(k(p-1)(q-1)) == 1 mod q
所以 p, q 均能整除 a^(k(p-1)(q-1)) - 1 => pq | a^(k(p-1)(q-1)) - 1
即 a^(k(p-1)(q-1)) == 1 mod pq
=> c == a^(k(p-1)(q-1)+1) == a mod pq
2. 如果 a 是 p 的倍數(shù), 但不是 q 的倍數(shù)時(shí),
則 a^(q-1) == 1 mod q (費(fèi)馬小定理)
=> a^(k(p-1)(q-1)) == 1 mod q
=> c == a^(k(p-1)(q-1)+1) == a mod q
=> q | c - a
因 p | a
=> c == a^(k(p-1)(q-1)+1) == 0 mod p
=> p | c - a
所以, pq | c - a => c == a mod pq
3. 如果 a 是 q 的倍數(shù), 但不是 p 的倍數(shù)時(shí), 證明同上
4. 如果 a 同時(shí)是 p 和 q 的倍數(shù)時(shí),
則 pq | a
=> c == a^(k(p-1)(q-1)+1) == 0 mod pq
=> pq | c - a
=> c == a mod pq
Q.E.D.
這個(gè)定理說明 a 經(jīng)過編碼為 b 再經(jīng)過解碼為 c 時(shí), a == c mod n (n = pq)....
但我們?cè)谧鼍幋a解碼時(shí), 限制 0 <= a < n, 0 <= c < n,
所以這就是說 a 等於 c, 所以這個(gè)過程確實(shí)能做到編碼解碼的功能.....
二、RSA 的安全性
RSA的安全性依賴于大數(shù)分解，但是否等同于大數(shù)分解一直未能得到理論上的證明，因?yàn)闆]有證明破解 RSA就一定需要作大數(shù)分解。假設(shè)存在一種無須分解大數(shù)的算法，那它肯定可以修改成為大數(shù)分解算法。目前， RSA 的一些變種算法已被證明等價(jià)于大數(shù)分解。不管怎樣，分解n是最顯然的攻擊方法?，F(xiàn)在，人們已能分解多個(gè)十進(jìn)制位的大素?cái)?shù)。因此，模數(shù)n 必須選大一些，因具體適用情況而定。
三、RSA的速度
由于進(jìn)行的都是大數(shù)計(jì)算，使得RSA最快的情況也比DES慢上倍，無論是軟件還是硬件實(shí)現(xiàn)。速度一直是RSA的缺陷。一般來說只用于少量數(shù)據(jù)加密。
四、RSA的選擇密文攻擊
RSA在選擇密文攻擊面前很脆弱。一般攻擊者是將某一信息作一下偽裝( Blind)，讓擁有私鑰的實(shí)體簽署。然后，經(jīng)過計(jì)算就可得到它所想要的信息。實(shí)際上，攻擊利用的都是同一個(gè)弱點(diǎn)，即存在這樣一個(gè)事實(shí)：乘冪保留了輸入的乘法結(jié)構(gòu)：
( XM )^d = X^d *M^d mod n
前面已經(jīng)提到，這個(gè)固有的問題來自于公鑰密碼系統(tǒng)的最有用的特征--每個(gè)人都能使用公鑰。但從算法上無法解決這一問題，主要措施有兩條：一條是采用好的公鑰協(xié)議，保證工作過程中實(shí)體不對(duì)其他實(shí)體任意產(chǎn)生的信息解密，不對(duì)自己一無所知的信息簽名；另一條是決不對(duì)陌生人送來的隨機(jī)文檔簽名，簽名時(shí)首先使用One-Way HashFunction 對(duì)文檔作HASH處理，或同時(shí)使用不同的簽名算法。在中提到了幾種不同類型的攻擊方法。
五、RSA的公共模數(shù)攻擊
若系統(tǒng)中共有一個(gè)模數(shù)，只是不同的人擁有不同的e和d，系統(tǒng)將是危險(xiǎn)的。最普遍的情況是同一信息用不同的公鑰加密，這些公鑰共模而且互質(zhì)，那末該信息無需私鑰就可得到恢復(fù)。設(shè)P為信息明文，兩個(gè)加密密鑰為e1和e2，公共模數(shù)是n，則：
C1 = P^e1 mod n
C2 = P^e2 mod n
密碼分析者知道n、e1、e2、C1和C2，就能得到P。
因?yàn)閑1和e2互質(zhì)，故用Euclidean算法能找到r和s，滿足：
r * e1 + s * e2 = 1
假設(shè)r為負(fù)數(shù)，需再用Euclidean算法計(jì)算C1^(-1)，則
( C1^(-1) )^(-r) * C2^s = P mod n
另外，還有其它幾種利用公共模數(shù)攻擊的方法。總之，如果知道給定模數(shù)的一對(duì)e和d，一是有利于攻擊者分解模數(shù)，一是有利于攻擊者計(jì)算出其它成對(duì)的e’和d’，而無需分解模數(shù)。解決辦法只有一個(gè)，那就是不要共享模數(shù)n。
RSA的小指數(shù)攻擊。 有一種提高 RSA速度的建議是使公鑰e取較小的值，這樣會(huì)使加密變得易于實(shí)現(xiàn)，速度有
所提高。但這樣作是不安全的，對(duì)付辦法就是e和d都取較大的值。
RSA算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法，也易于理解和操作。RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。RSA的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價(jià)。即RSA的重大缺陷是無法從理論上把握它的保密性能如何，而且密碼學(xué)界多數(shù)人士?jī)A向于因子分解不是NPC問題。 RSA的缺點(diǎn)主要有：A)產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。B)分組長(zhǎng)度太大，為保證安全性，n 至少也要 600 bits 以上，使運(yùn)算代價(jià)很高，尤其是速度較慢，較對(duì)稱密碼算法慢幾個(gè)數(shù)量級(jí)；且隨著大數(shù)分解技術(shù)的發(fā)展，這個(gè)長(zhǎng)度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。目前，SET( Secure Electronic Transaction )協(xié)議中要求CA采用比特長(zhǎng)的密鑰，其他實(shí)體使用比特的密鑰。
[06/22-12:58:37]
DES算法
一、DES算法
美國(guó)國(guó)家標(biāo)準(zhǔn)局1973年開始研究除國(guó)防部外的其它部門的計(jì)算機(jī)系統(tǒng)的數(shù)據(jù)加密標(biāo)準(zhǔn)，于1973年5月15日和1974年8月27日先后兩次向公眾發(fā)出了征求加密算法的公告。加密算法要達(dá)到的目的（通常稱為DES 密碼算法要求）主要為以下四點(diǎn)： ☆提供高質(zhì)量的數(shù)據(jù)保護(hù)，防止數(shù)據(jù)未經(jīng)授權(quán)的泄露和未被察覺的修改；
☆具有相當(dāng)高的復(fù)雜性，使得破譯的開銷超過可能獲得的利益，同時(shí)又要便于理解和掌握；
☆DES密碼體制的安全性應(yīng)該不依賴于算法的保密，其安全性僅以加密密鑰的保密為基礎(chǔ)；
☆實(shí)現(xiàn)經(jīng)濟(jì)，運(yùn)行有效，并且適用于多種完全不同的應(yīng)用。
1977年1月，美國(guó)政府頒布：采納IBM公司設(shè)計(jì)的方案作為非機(jī)密數(shù)據(jù)的正式數(shù)據(jù)加密標(biāo)準(zhǔn)（DES棗Data Encryption Standard）。
目前在國(guó)內(nèi)，隨著三金工程尤其是金卡工程的啟動(dòng)，DES算法在POS、ATM、磁卡及智能卡（IC卡）、加油站、高速公路收費(fèi)站等領(lǐng)域被廣泛應(yīng)用，以此來實(shí)現(xiàn)關(guān)鍵數(shù)據(jù)的保密，如信用卡持卡人的PIN的加密傳輸，IC卡與POS間的雙向認(rèn)證、金融交易數(shù)據(jù)包的MAC校驗(yàn)等，均用到DES算法。
DES算法的入口參數(shù)有三個(gè)：Key、Data、Mode。其中Key為8個(gè)字節(jié)共64位，是DES算法的工作密鑰；Data也為8個(gè)字節(jié)64位，是要被加密或被解密的數(shù)據(jù)；Mode為DES的工作方式，有兩種：加密或解密。
DES算法是這樣工作的：如Mode為加密，則用Key 去把數(shù)據(jù)Data進(jìn)行加密， 生成Data的密碼形式（64位）作為DES的輸出結(jié)果；如Mode為解密，則用Key去把密碼形式的數(shù)據(jù)Data解密，還原為Data的明碼形式（64位）作為DES的輸出結(jié)果。在通信網(wǎng)絡(luò)的兩端，雙方約定一致的Key，在通信的源點(diǎn)用Key對(duì)核心數(shù)據(jù)進(jìn)行DES加密，然后以密碼形式在公共通信網(wǎng)（如電話網(wǎng)）中傳輸?shù)酵ㄐ啪W(wǎng)絡(luò)的終點(diǎn)，數(shù)據(jù)到達(dá)目的地后，用同樣的Key對(duì)密碼數(shù)據(jù)進(jìn)行解密，便再現(xiàn)了明碼形式的核心數(shù)據(jù)。這樣，便保證了核心數(shù)據(jù)（如PIN、MAC等）在公共通信網(wǎng)中傳輸?shù)陌踩院涂煽啃浴?
通過定期在通信網(wǎng)絡(luò)的源端和目的端同時(shí)改用新的Key，便能更進(jìn)一步提高數(shù)據(jù)的保密性，這正是現(xiàn)在金融交易網(wǎng)絡(luò)的流行做法。
DES算法詳述
DES算法把64位的明文輸入塊變?yōu)?4位的密文輸出塊，它所使用的密鑰也是64位，整個(gè)算法的主流程圖如下：
其功能是把輸入的64位數(shù)據(jù)塊按位重新組合，并把輸出分為L(zhǎng)0、R0兩部分，每部分各長(zhǎng)32位，其置換規(guī)則見下表：
58,50,12,34,26,18,10,2,60,52,44,36,28,20,12,4,
62,54,46,38,30,22,14,6,64,56,48,40,32,24,16,8,
57,49,41,33,25,17, 9,1,59,51,43,35,27,19,11,3,
61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,7,
即將輸入的第58位換到第一位，第50位換到第2位，...，依此類推，最后一位是原來的第7位。L0、R0則是換位輸出后的兩部分，L0是輸出的左32位，R0 是右32位，例：設(shè)置換前的輸入值為D1D2D3......D64，則經(jīng)過初始置換后的結(jié)果為：L0=D58D50...D8；R0=D57D49...D7。
經(jīng)過16次迭代運(yùn)算后。得到L16、R16，將此作為輸入，進(jìn)行逆置換，即得到密文輸出。逆置換正好是初始置的逆運(yùn)算，例如，第1位經(jīng)過初始置換后，處于第40位，而通過逆置換，又將第40位換回到第1位，其逆置換規(guī)則如下表所示：
40,8,48,16,56,24,64,32,39,7,47,15,55,23,63,31,
38,6,46,14,54,22,62,30,37,5,45,13,53,21,61,29,
36,4,44,12,52,20,60,28,35,3,43,11,51,19,59,27,
34,2,42,10,50,18,58 26,33,1,41, 9,49,17,57,25,
放大換位表
32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, 8, 9, 10,11,
12,13,12,13,14,15,16,17,16,17,18,19,20,21,20,21,
22,23,24,25,24,25,26,27,28,29,28,29,30,31,32, 1,
單純換位表
16,7,20,21,29,12,28,17, 1,15,23,26, 5,18,31,10,
2,8,24,14,32,27, 3, 9,19,13,30, 6,22,11, 4,25,
在f(Ri,Ki)算法描述圖中，S1,S2...S8為選擇函數(shù)，其功能是把6bit數(shù)據(jù)變?yōu)?bit數(shù)據(jù)。下面給出選擇函數(shù)Si(i=1,2......8)的功能表：
選擇函數(shù)Si
S1:
14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7,
0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8,
4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0,
15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13,
S2:
15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10,
3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5,
0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15,
13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9,
S3:
10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8,
13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1,
13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7,
1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12,
S4:
7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15,
13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9,
10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4,
3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14,
S5:
2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9,
14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6,
4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14,
11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3,
S6:
12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11,
10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8,
9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6,
4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13,
S7:
4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1,
13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6,
1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2,
6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12,
S8:
13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7,
1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2,
7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8,
2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11,
在此以S1為例說明其功能，我們可以看到：在S1中，共有4行數(shù)據(jù)，命名為0，1、2、3行；每行有16列，命名為0、1、2、3，......，14、15列。
現(xiàn)設(shè)輸入為： D＝D1D2D3D4D5D6
令：列＝D2D3D4D5
行＝D1D6
然后在S1表中查得對(duì)應(yīng)的數(shù)，以4位二進(jìn)制表示，此即為選擇函數(shù)S1的輸出。下面給出子密鑰Ki(48bit)的生成算法
從子密鑰Ki的生成算法描述圖中我們可以看到：初始Key值為64位，但DES算法規(guī)定，其中第8、16、......64位是奇偶校驗(yàn)位，不參與DES運(yùn)算。故Key 實(shí)際可用位數(shù)便只有56位。即：經(jīng)過縮小選擇換位表1的變換后，Key 的位數(shù)由64 位變成了56位，此56位分為C0、D0兩部分，各28位，然后分別進(jìn)行第1次循環(huán)左移，得到C1、D1，將C1（28位）、D1（28位）合并得到56位，再經(jīng)過縮小選擇換位2，從而便得到了密鑰K0（48位）。依此類推，便可得到K1、K2、......、K15，不過需要注意的是，16次循環(huán)左移對(duì)應(yīng)的左移位數(shù)要依據(jù)下述規(guī)則進(jìn)行：
循環(huán)左移位數(shù)
1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1
以上介紹了DES算法的加密過程。DES算法的解密過程是一樣的，區(qū)別僅僅在于第一次迭代時(shí)用子密鑰K15，第二次K14、......，最后一次用K0，算法本身并沒有任何變化。
二、DES算法理論圖解
DES的算法是對(duì)稱的，既可用于加密又可用于解密。下圖是它的算法粗框圖。其具體運(yùn)算過程有如下七步。
三、DES算法的應(yīng)用誤區(qū)
DES算法具有極高安全性，到目前為止，除了用窮舉搜索法對(duì)DES算法進(jìn)行攻擊外，還沒有發(fā)現(xiàn)更有效的辦法。而56位長(zhǎng)的密鑰的窮舉空間為256，這意味著如果一臺(tái)計(jì)算機(jī)的速度是每一秒種檢測(cè)一百萬個(gè)密鑰，則它搜索完全部密鑰就需要將近2285年的時(shí)間，可見，這是難以實(shí)現(xiàn)的，當(dāng)然，隨著科學(xué)技術(shù)的發(fā)展，當(dāng)出現(xiàn)超高速計(jì)算機(jī)后，我們可考慮把DES密鑰的長(zhǎng)度再增長(zhǎng)一些，以此來達(dá)到更高的保密程度。
由上述DES算法介紹我們可以看到：DES算法中只用到64位密鑰中的其中56位，而第8、16、24、......64位8個(gè)位并未參與DES運(yùn)算，這一點(diǎn)，向我們提出了一個(gè)應(yīng)用上的要求，即DES的安全性是基于除了8，16，24，......64位外的其余56位的組合變化256才得以保證的。因此，在實(shí)際應(yīng)用中，我們應(yīng)避開使用第8，16，24，......64位作為有效數(shù)據(jù)位，而使用其它的56位作為有效數(shù)據(jù)位，才能保證DES算法安全可靠地發(fā)揮作用。如果不了解這一點(diǎn)，把密鑰Key的8，16，24，..... .64位作為有效數(shù)據(jù)使用，將不能保證DES加密數(shù)據(jù)的安全性，對(duì)運(yùn)用DES來達(dá)到保密作用的系統(tǒng)產(chǎn)生數(shù)據(jù)被破譯的危險(xiǎn)，這正是DES算法在應(yīng)用上的誤區(qū)，留下了被人攻擊、被人破譯的極大隱患。
[06/22-12:58:52]
DSA算法
Digital Signature Algorithm (DSA)是Schnorr和ElGamal簽名算法的變種，被美國(guó)NIST作為DSS(DigitalSignature Standard)。算法中應(yīng)用了下述參數(shù)：
p：L bits長(zhǎng)的素?cái)?shù)。L是64的倍數(shù)，范圍是512到1024；
q：p - 1的160bits的素因子；
g：g = h^((p-1)/q) mod p，h滿足h < p - 1, h^((p-1)/q) mod p > 1；
x：x < q，x為私鑰 ；
y：y = g^x mod p ，( p, q, g, y )為公鑰；
H( x )：One-Way Hash函數(shù)。DSS中選用SHA( Secure Hash Algorithm )。
p, q, g可由一組用戶共享，但在實(shí)際應(yīng)用中，使用公共模數(shù)可能會(huì)帶來一定的威脅。簽名及驗(yàn)證協(xié)議如下：
1. P產(chǎn)生隨機(jī)數(shù)k，k < q；
2. P計(jì)算 r = ( g^k mod p ) mod q
s = ( k^(-1) (H(m) + xr)) mod q
簽名結(jié)果是( m, r, s )。
3. 驗(yàn)證時(shí)計(jì)算 w = s^(-1)mod q
u1 = ( H( m ) * w ) mod q
u2 = ( r * w ) mod q
v = (( g^u1 * y^u2 ) mod p ) mod q
若v = r，則認(rèn)為簽名有效。
DSA是基于整數(shù)有限域離散對(duì)數(shù)難題的，其安全性與RSA相比差不多。DSA的一個(gè)重要特點(diǎn)是兩個(gè)素?cái)?shù)公開，這
樣，當(dāng)使用別人的p和q時(shí)，即使不知道私鑰，你也能確認(rèn)它們是否是隨機(jī)產(chǎn)生的，還是作了手腳。RSA算法卻作不到。
[06/22-12:59:06]
加密算法之ElGamal算法
ElGamal算法
ElGamal算法既能用于數(shù)據(jù)加密也能用于數(shù)字簽名，其安全性依賴于計(jì)算有限域上離散對(duì)數(shù)這一難題。
密鑰對(duì)產(chǎn)生辦法。首先選擇一個(gè)素?cái)?shù)p，兩個(gè)隨機(jī)數(shù), g 和x，g, x < p, 計(jì)算 y = g^x ( mod p )，則其公鑰為 y, g 和p。私鑰是x。g和p可由一組用戶共享。
ElGamal用于數(shù)字簽名。被簽信息為M，首先選擇一個(gè)隨機(jī)數(shù)k, k與 p - 1互質(zhì)，計(jì)算
a = g^k ( mod p )
再用擴(kuò)展 Euclidean 算法對(duì)下面方程求解b：
M = xa + kb ( mod p - 1 )
簽名就是( a, b )。隨機(jī)數(shù)k須丟棄。
驗(yàn)證時(shí)要驗(yàn)證下式：
y^a * a^b ( mod p ) = g^M ( mod p )
同時(shí)一定要檢驗(yàn)是否滿足1<= a < p。否則簽名容易偽造。
ElGamal用于加密。被加密信息為M，首先選擇一個(gè)隨機(jī)數(shù)k，k與 p - 1互質(zhì)，計(jì)算
a = g^k ( mod p )
b = y^k M ( mod p )
( a, b )為密文，是明文的兩倍長(zhǎng)。解密時(shí)計(jì)算
M = b / a^x ( mod p )
ElGamal簽名的安全性依賴于乘法群(IFp)* 上的離散對(duì)數(shù)計(jì)算。素?cái)?shù)p必須足夠大，且p-1至少包含一個(gè)大素?cái)?shù)
因子以抵抗Pohlig & Hellman算法的攻擊。M一般都應(yīng)采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依賴于p和g，若選取不當(dāng)則簽名容易偽造，應(yīng)保證g對(duì)于p-1的大素?cái)?shù)因子不可約。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻擊方法和對(duì)策。ElGamal的一個(gè)不足之處是它的密文成倍擴(kuò)張。
美國(guó)的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是經(jīng)ElGamal算法演
變而來。
[06/22-12:59:27]
BLOWFISH算法
作 者：夜月
聯(lián) 系：luoyi_ly1@sina.com
時(shí) 間：2001年10月6日
范 例：BlowFish's CrackMe1
注冊(cè)機(jī)：Bfkeygen
一、BlowFish算法說明（文中數(shù)據(jù)類型以Tc2.0為準(zhǔn)）
BlowFish算法用來加密64Bit長(zhǎng)度的字符串。
BlowFish算法使用兩個(gè)“盒”——ungigned long pbox[18]和unsigned long sbox[4,256]。
BlowFish算法中，有一個(gè)核心加密函數(shù):BF_En(后文詳細(xì)介紹）。該函數(shù)輸入64位信息，運(yùn)算后， 以64位密文的形式輸出。 用BlowFish算法加密信息，需要兩個(gè)過程：
1.密鑰預(yù)處理
2.信息加密
分別說明如下：
密鑰預(yù)處理：
BlowFish算法的源密鑰——pbox和sbox是固定的。我們要加密一個(gè)信息，需要自己選擇一個(gè)key， 用這個(gè)key對(duì)pbox和sbox進(jìn)行變換，得到下一步信息加密所要用的key_pbox和key_sbox。具體的變化算法如下：
1)用sbox填充key_sbox
2)用自己選擇的key8個(gè)一組地去異或pbox，用異或的結(jié)果填充key_pbox。key可以循環(huán)使用。
比如說：選的key是"abcdefghijklmn"。則異或過程為：
key_pbox[0]=pbox[0]^abcdefgh
key_pbox[1]=pbox[1]^ijklmnab
…………
…………
如此循環(huán)，直到key_box填充完畢。
3)用BF_En加密一個(gè)全0的64位信息，用輸出的結(jié)果替換key_pbox[0]和key_pbox[1]。i=0
4)用BF_En加密替換后的key_pbox[i],key_pbox[i+1],用輸出替代key_pbox[i+2]和key_pbox[i+3]
5)i+2，繼續(xù)第4步，直到key_pbox全部被替換
6)用key_pbox[16]和key_pbox[17]做首次輸入（相當(dāng)于上面的全0的輸入），用類似的方法，替換key_sbox 信息加密。信息加密就是用函數(shù)把待加密信息x分成32位的兩部分:xL,xR BF_En對(duì)輸入信息進(jìn)行變換，BF_En函數(shù)詳細(xì)過程如下：
對(duì)于i=1至16
xL=xL^Pi
xR=F(xL)^xR
交換xL和xR(最后一輪取消該運(yùn)算)
xR=xR^P17
xL=xL^P18
重新合并xL和xR
函數(shù)F見下圖:
8位 32位
|-----------S盒1-----------
| |加
| 8位 32位 |----
|-----------S盒2----------- |
| |
| |異或----
32位-| | |
| 8位 32位 | |
|-----------S盒3--------------- |加
| |-----------------32位
| |
| |
| 8位 32位 |
|-----------S盒4-----------------------
把xL分成4個(gè)8位分組:a,b,c和d
輸出為：F(xL)=((((S[1,a]+S[2,b])MOD 4294967296)^s[3,c])+S[4,d])MOD 4294967296
(2的32次方) (2的32次方)
重新合并后輸出的結(jié)果就是我們需要的密文。
用BlowFish算法解密，同樣也需要兩個(gè)過程。
1.密鑰預(yù)處理
2.信息解密
密鑰預(yù)處理的過程與加密時(shí)完全相同
信息解密的過程就是把信息加密過程的key_pbox逆序使用即可。
可以看出，選擇不同的key，用BlowFish算法加密同樣的信息，可以得出不同的結(jié)果。
要破解BlowFish算法，就是要得到BlowFish算法的key。所以，使用BlowFish算法進(jìn)行加密，最重要的也就是key的選擇以及key的保密。其中key的選擇可以使用bf_sdk中的_WeakKey函數(shù)進(jìn)行檢驗(yàn)。以下是該函數(shù)的說明：
源文：
---------------------------------------------------------------------------------------
_WeakKey
Function : Test if the generated Boxes are weak
Argument : none
Return : AX = Status (1=weak, 0=good)
Affects : AX, BX, CX, DX, SI, DI, direction Flag
Description: After "_InitCrypt" you should test the Boxes with this function.
If they provide a weakness which a cryptoanalyst could use to
break the cipher a "1" is returned. In this case you should
reload the original boxes and let the user choose a different
password.
---------------------------------------------------------------------------------------
譯文：
---------------------------------------------------------------------------------------
_WeakKey
功能：測(cè)試產(chǎn)生的box是否安全
參數(shù)：無
返回：AX=1 不安全；AX=0 安全
影響：AX, BX, CX, DX, SI, DI, 方向標(biāo)志
描述：使用"_InitCrypt"函數(shù)產(chǎn)生用于加密的Boxes后，你應(yīng)該用這個(gè)函數(shù)測(cè)試產(chǎn)生的Boxes是否安全。如果該key產(chǎn)生的Boxes不安全——可以被密碼分析者通過分析Boxes得到key，那么，你應(yīng)該采用另外一個(gè)key產(chǎn)生一個(gè)安全的Boxes用來加密。
---------------------------------------------------------------------------------------
二、BlowFish's CrackMe1分析
由于該CrackMe主要是測(cè)試你的密碼學(xué)知識(shí)，所以沒有在其他方面設(shè)關(guān)卡。為了減小文件體積，縮短大家下載的時(shí)間，用upx加了殼，直接用Trw2000的"PNewSec+Makepe"很方便地就能脫掉殼。
用常規(guī)的方法，很快找到下面關(guān)鍵比較處：
:004015D9 51 push ecx
:004015DA 52 push edx
:004015DB 6880894000 push 00408980
:004015E0 E8EBFAFFFF call 004010D0 //BF_De(sn)
:004015E5 8B442464 mov eax, dword ptr [esp+64]
:004015E9 8B0DF0994000 mov ecx, dword ptr [004099F0]
:004015EF 83C41C add esp, 0000001C
:004015F2 3BC1 cmp eax, ecx //比較
:004015F4 7529 jne 0040161F
:004015F6 8B4C244C mov ecx, dword ptr [esp+4C]
:004015FA A1EC994000 mov eax, dword ptr [004099EC]
:004015FF 3BC8 cmp ecx, eax //比較
:00401601 751C jne 0040161F
:00401603 6A30 push 00000030
由于BlowFish算法加密，解密輸出的信息都是64Bit的，所以要進(jìn)行兩次比較。
我們既然知道了他對(duì)我們的sn進(jìn)行的變換是BF_De，那么，很顯然，我們要找到程序初始化key_pbox和key_sbox的地方。跟進(jìn)4015E0的Call，找到key_pbox在408980處，下bpm，然后跟蹤，分析，找到程序初始化key_pbox和key_sbox的地方，如下：
:004016C0 50 push eax
* Possible StringData Ref from Data Obj ->"CrackingForFun"
|
:004016C1 6844804000 push 00408044
:004016C6 6880894000 push 00408980
:004016CB E860FAFFFF call 00401130 //初始化Boxes
由此我們知道了BF_De(sn)的key是"CrackingForFun"。
問題的一半已經(jīng)解決了。下面我們來看用來比較的另外的64Bit的數(shù)是從何而來。
bpm 4099EC w
跟蹤分析后，發(fā)現(xiàn)這個(gè)用來比較的數(shù)是由BF_En(ComputerID,key="ChinaCrackingGroup")生成。
至此，我們可以寫出注冊(cè)機(jī)的算法：
sn=BF_En((BF_En(ComputerID,key="ChinaCrackingGroup"),key="CrackingForFun")
只要你編程夠強(qiáng)，密碼學(xué)也還過得去，寫出這個(gè)東西的注冊(cè)機(jī)就不是困難的事情了。
附：
ComputerID的產(chǎn)生
如果你對(duì)這個(gè)CrackMe很有興趣，還想研究一下他的ComputerID是如何產(chǎn)生的，也可以繼續(xù)跟蹤，分析，在這里，我給處我分析的結(jié)果：
ComputerID=BF_En(0776f6c62h, 068736966h,key=PW_1)
其中，PW_1就是你的Windows版本號(hào)，可以在“系統(tǒng)屬性”里頭看到，也就是注冊(cè)表中的
H_L_M\Software\Microsoft\Windows\CurrentVersion 中的ProductId項(xiàng)。在我的機(jī)器上是：
"25001-OEM-0080247-46673"
注冊(cè)機(jī)源碼里頭有一些語句沒有派上用場(chǎng)，用“;”屏蔽了，如果你有興趣，可以把前面的;號(hào)去掉然后把.data段里頭的PW_1換成你機(jī)器的ComputerID,再按照程序中的說明自己修改一下源程序，用Masm32V6重新編譯，直接按Generate，也能得到正確的序列號(hào)。
三、注冊(cè)機(jī)源碼
;BlowFish's Crackme's KeyGen Writen By 夜月[CCG]
;Any Questions,Please E-Mail To luoyi.ly@yeah.net
;Thancks To Garfield,BlowFish,Toye
;軟件流程：
;1.GetVersion得到機(jī)器Windows版本號(hào)。PW_1
;2.固定字符串"ChinaCrackingGroup"。PW_2
;3.固定字符串"CrackingForFun"。PW_3
;4.你輸入的字符串。sn
;BF_En(0776f6c62h, 068736966h,key=PW_1)得到Computer ID
;BF_En(ComputerID,key=PW_2)得到MagicNum
;IF(BF_De(sn,key=PW_3)==MagicNum) Then Registed OK!
.386
.model flat,stdcall
option casemap:none
include windows.inc
include user32.inc
include kernel32.inc
include comctl32.inc
include comdlg32.inc
include masm32.inc
includelib masm32.lib
includelib user32.lib
includelib kernel32.lib
includelib comctl32.lib
includelib comdlg32.lib
DLG_MAIN equ 100
IDGEN equ 10
Edit1 equ 11
Edit2 equ 12
len_PW_1 equ offset data1_p - offset PW_1
_ProcDlgMain PROTO WORD,WORD,WORD,WORD
_Math PROTO WORD,WORD,WORD
BlowFish_En PROTO WORD,WORD
BlowFish_Fun PROTO WORD
BlowFish_Init PROTO WORD,WORD
.data?
hInstance dd ?
.data
;如果你直接用ComputerID產(chǎn)生序列號(hào)，你應(yīng)該把PW_1換成你自己機(jī)器的Windows版本號(hào)
;PW_1 db "25001-OEM-0080247-46673"
PW_2 db "ChinaCrackingGroup"
PW_3 db "CrackingForFun"
szID db 20 dup(0)
szText db 9 dup(0)
data1_p dd 0776f6c62h, 068736966h
key dd 1058 dup (0)
BFLOW dd 0
BFHIGH dd 0
MYBFLOW DD 0
MYBFHIGH DD 0
pbox dd 0243f6a88h, 085a308d3h, 013198a2eh, 003707344h, 0a4093822h, 0299f31d0h
dd 0082efa98h, 0ec4e6c89h, 0452821e6h, 038d01377h, 0be5466cfh, 034e90c6ch
dd 0c0ac29b7h, 0c97c50ddh, 03f84d5b5h, 0b5470917h, 09216d5d9h, 08979fb1bh
sbox1 dd 0d1310ba6h, 098dfb5ach, 02ffd72dbh, 0d01adfb7h, 0b8e1afedh, 06a267e96h
dd 0ba7c9045h, 0f12c7f99h, 024a19947h, 0b3916cf7h, 00801f2e2h, 0858efc16h
dd 0636920d8h, 071574e69h, 0a458fea3h, 0f4933d7eh, 00d95748fh, 0728eb658h
dd 0718bcd58h, 082154aeeh, 07b54a41dh, 0c25a59b5h, 09c30d539h, 02af26013h
dd 0c5d1b023h, 0286085f0h, 0ca417918h, 0b8db38efh, 08e79dcb0h, 0603a180eh
dd 06c9e0e8bh, 0b01e8a3eh, 0d71577c1h, 0bd314b27h, 078af2fdah, 055605c60h
dd 0e65525f3h, 0aa55ab94h, 057489862h, 063e81440h, 055ca396ah, 02aab10b6h
dd 0b4cc5c34h, 01141e8ceh, 0a15486afh, 07c72e993h, 0b3ee1411h, 0636fbc2ah
dd 02ba9c55dh, 0741831f6h, 0ce5c3e16h, 09b87931eh, 0afd6ba33h, 06c24cf5ch
dd 07a325381h, 028958677h, 03b8f4898h, 06b4bb9afh, 0c4bfe81bh, 066282193h
dd 061d809cch, 0fb21a991h, 0487cac60h, 05dec8032h, 0ef845d5dh, 0e98575b1h
dd 0dc262302h, 0eb651b88h, 023893e81h, 0d396acc5h, 00f6d6ff3h, 083f44239h
dd 02e0b4482h, 0a4842004h, 069c8f04ah, 09e1f9b5eh, 021c66842h, 0f6e96c9ah
dd 0670c9c61h, 0abd388f0h, 06a51a0d2h, 0d8542f68h, 0960fa728h, 0ab5133a3h
dd 06eef0b6ch, 0137a3be4h, 0ba3bf050h, 07efb2a98h, 0a1f1651dh, 039af0176h
dd 066ca593eh, 082430e88h, 08cee8619h, 0456f9fb4h, 07d84a5c3h, 03b8b5ebeh
dd 0e06f75d8h, 085c12073h, 0401a449fh, 056c16aa6h, 04ed3aa62h, 0363f7706h
dd 01bfedf72h, 0429b023dh, 037d0d724h, 0d00a1248h, 0db0fead3h, 049f1c09bh
dd 0075372c9h, 080991b7bh, 025d479d8h, 0f6e8def7h, 0e3fe501ah, 0b6794c3bh
dd 0976ce0bdh, 004c006bah, 0c1a94fb6h, 0409f60c4h, 05e5c9ec2h, 0196a2463h
dd 068fb6fafh, 03e6c53b5h, 01339b2ebh, 03b52ec6fh, 06dfc511fh, 09b30952ch
dd 0cc814544h, 0af5ebd09h, 0bee3d004h, 0de334afdh, 0660f2807h, 0192e4bb3h
dd 0c0cba857h, 045c8740fh, 0d20b5f39h, 0b9d3fbdbh, 05579c0bdh, 01a60320ah
dd 0d6a100c6h, 0402c7279h, 0679f25feh, 0fb1fa3cch, 08ea5e9f8h, 0db3222f8h
dd 03c7516dfh, 0fd616b15h, 02f501ec8h, 0ad0552abh, 0323db5fah, 0fd238760h
dd 053317b48h, 03e00df82h, 09e5c57bbh, 0ca6f8ca0h, 01a87562eh, 0df1769dbh
dd 0d542a8f6h, 0287effc3h, 0ac6732c6h, 08c4f5573h, 0695b27b0h, 0bbca58c8h
dd 0e1ffa35dh, 0b8f011a0h, 010fa3d98h, 0fd2183b8h, 04afcb56ch, 02dd1d35bh
dd 09a53e479h, 0b6f84565h, 0d28e49bch, 04bfb9790h, 0e1ddf2dah, 0a4cb7e33h
dd 062fb1341h, 0cee4c6e8h, 0ef20cadah, 036774c01h, 0d07e9efeh, 02bf11fb4h
dd 095dbda4dh, 0ae909198h, 0eaad8e71h, 06b93d5a0h, 0d08ed1d0h, 0afc725e0h
dd 08e3c5b2fh, 08e7594b7h, 08ff6e2fbh, 0f2122b64h, 08888b812h, 0900df01ch
dd 04fad5ea0h, 0688fc31ch, 0d1cff191h, 0b3a8c1adh, 02f2f2218h, 0be0e1777h
dd 0ea752dfeh, 08b021fa1h, 0e5a0cc0fh, 0b56f74e8h, 018acf3d6h, 0ce89e299h
dd 0b4a84fe0h, 0fd13e0b7h, 07cc43b81h, 0d2ada8d9h, 0165fa266h, 080957705h
dd 093cc7314h, 0211a1477h, 0e6ad2065h, 077b5fa86h, 0c75442f5h, 0fb9d35cfh
dd 0ebcdaf0ch, 07b3e89a0h, 0d6411bd3h, 0ae1e7e49h, 000250e2dh, 02071b35eh
dd 0226800bbh, 057b8e0afh, 02464369bh, 0f009b91eh, 05563911dh, 059dfa6aah
dd 078c14389h, 0d95a537fh, 0207d5ba2h, 002e5b9c5h, 083260376h, 06295cfa9h
dd 011c81968h, 04e734a41h, 0b3472dcah, 07b14a94ah, 01b510052h, 09a532915h
dd 0d60f573fh, 0bc9bc6e4h, 02b60a476h, 081e67400h, 008ba6fb5h, 0571be91fh
dd 0f296ec6bh, 02a0dd915h, 0b6636521h, 0e7b9f9b6h, 0ff34052eh, 0c5855664h
dd 053b02d5dh, 0a99f8fa1h, 008ba4799h, 06e85076ah
sbox2 dd 04b7a70e9h, 0b5b32944h
dd 0db75092eh, 0c4192623h, 0ad6ea6b0h, 049a7df7dh, 09cee60b8h, 08fedb266h
dd 0ecaa8c71h, 0699a17ffh, 05664526ch, 0c2b19ee1h, 0193602a5h, 075094c29h
dd 0a0591340h, 0e4183a3eh, 03f54989ah, 05b429d65h, 06b8fe4d6h, 099f73fd6h
dd 0a1d29c07h, 0efe830f5h, 04d2d38e6h, 0f0255dc1h, 04cdd2086h, 08470eb26h
dd 06382e9c6h, 0021ecc5eh, 009686b3fh, 03ebaefc9h, 03c971814h, 06b6a70a1h
dd 0687f3584h, 052a0e286h, 0b79c5305h, 0aa500737h, 03e07841ch, 07fdeae5ch
dd 08e7d44ech, 05716f2b8h, 0b03ada37h, 0f0500c0dh, 0f01c1f04h, 00200b3ffh
dd 0ae0cf51ah, 03cb574b2h, 025837a58h, 0dc0921bdh, 0d19113f9h, 07ca92ff6h
dd 094324773h, 022f54701h, 03ae5e581h, 037c2dadch, 0c8b57634h, 09af3dda7h
dd 0a9446146h, 00fd0030eh, 0ecc8c73eh, 0a4751e41h, 0e238cd99h, 03bea0e2fh
dd 03280bba1h, 0183eb331h, 04e548b38h, 04f6db908h, 06f420d03h, 0f60a04bfh
dd 02cb81290h, 024977c79h, 05679b072h, 0bcaf89afh, 0de9a771fh, 0d9930810h
dd 0b38bae12h, 0dccf3f2eh, 05512721fh, 02e6b7124h, 0501adde6h, 09f84cd87h
dd 07a584718h, 07408da17h, 0bc9f9abch, 0e94b7d8ch, 0ec7aec3ah, 0db851dfah
dd 063094366h, 0c464c3d2h, 0ef1c1847h, 03215d908h, 0dd433b37h, 024c2ba16h
dd 012a14d43h, 02a65c451h, 050940002h, 0133ae4ddh, 071dff89eh, 010314e55h
dd 081ac77d6h, 05f11199bh, 0043556f1h, 0d7a3c76bh, 03c11183bh, 05924a509h
dd 0f28fe6edh, 097f1fbfah, 09ebabf2ch, 01e153c6eh, 086e34570h, 0eae96fb1h
dd 0860e5e0ah, 05a3e2ab3h, 0771fe71ch, 04e3d06fah, 02965dcb9h, 099e71d0fh
dd 0803e89d6h, 05266c825h, 02e4cc978h, 09c10b36ah, 0c6150ebah, 094e2ea78h
dd 0a5fc3c53h, 01e0a2df4h, 0f2f74ea7h, 0361d2b3dh, 01939260fh, 019c27960h
dd 05223a708h, 0f71312b6h, 0ebadfe6eh, 0eac31f66h, 0e3bc4595h, 0a67bc883h
dd 0b17f37d1h, 0018cff28h, 0c332ddefh, 0be6c5aa5h, 065582185h, 068ab9802h
dd 0eecea50fh, 0db2f953bh, 02aef7dadh, 05b6e2f84h, 01521b628h, 029076170h
dd 0ecdd4775h, 0619f1510h, 013cca830h, 0eb61bd96h, 00334fe1eh, 0aa0363cfh
dd 0b5735c90h, 04c70a239h, 0d59e9e0bh, 0cbaade14h, 0eecc86bch, 060622ca7h
dd 09cab5cabh, 0b2f3846eh, 0648b1eafh, 019bdf0cah, 0a02369b9h, 0655abb50h
dd 040685a32h, 03c2ab4b3h, 0319ee9d5h, 0c021b8f7h, 09b540b19h, 0875fa099h
dd 095f7997eh, 0623d7da8h, 0f837889ah, 097e32d77h, 011ed935fh, 016681281h
dd 00e358829h, 0c7e61fd6h, 096dedfa1h, 07858ba99h, 057f584a5h, 01b227263h
dd 09b83c3ffh, 01ac24696h, 0cdb30aebh, 0532e3054h, 08fd948e4h, 06dbc3128h
dd 058ebf2efh, 034c6ffeah, 0fe28ed61h, 0ee7c3c73h, 05d4a14d9h, 0e864b7e3h
dd 042105d14h, 0203e13e0h, 045eee2b6h, 0a3aaabeah, 0db6c4f15h, 0facb4fd0h
dd 0c742f442h, 0ef6abbb5h, 0654f3b1dh, 041cd2105h, 0d81e799eh, 086854dc7h
dd 0e44b476ah, 03d816250h, 0cf62a1f2h, 05b8d2646h, 0fc8883a0h, 0c1c7b6a3h
dd 07f1524c3h, 069cb7492h, 047848a0bh, 05692b285h, 0095bbf00h, 0ad19489dh
dd 01462b174h, 023820e00h, 058428d2ah, 00c55f5eah, 01dadf43eh, 0233f7061h
dd 03372f092h, 08d937e41h, 0d65fecf1h, 06c223bdbh, 07cde3759h, 0cbee7460h
dd 04085f2a7h, 0ce77326eh, 0a6078084h, 019f8509eh, 0e8efd855h, 061d99735h
dd 0a969a7aah, 0c50c06c2h, 05a04abfch, 0800bcadch, 09e447a2eh, 0c3453484h
dd 0fdd56705h, 00e1e9ec9h, 0db73dbd3h, 0105588cdh, 0675fda79h, 0e3674340h
dd 0c5c43465h, 0713e38d8h, 03d28f89eh, 0f16dff20h, 0153e21e7h, 08fb03d4ah
dd 0e6e39f2bh, 0db83adf7h
sbox3 dd 0e93d5a68h, 0948140f7h, 0f64c261ch, 094692934h
dd 0411520f7h, 07602d4f7h, 0bcf46b2eh, 0d4a20068h, 0d4082471h, 03320f46ah
dd 043b7d4b7h, 0500061afh, 01e39f62eh, 097244546h, 014214f74h, 0bf8b8840h
dd 04d95fc1dh, 096b591afh, 070f4ddd3h, 066a02f45h, 0bfbc09ech, 003bd9785h
dd 07fac6dd0h, 031cb8504h, 096eb27b3h, 055fd3941h, 0da2547e6h, 0abca0a9ah
dd 028507825h, 0530429f4h, 00a2c86dah, 0e9b66dfbh, 068dc1462h, 0d7486900h
dd 0680ec0a4h, 027a18deeh, 04f3ffea2h, 0e887ad8ch, 0b58ce006h, 07af4d6b6h
dd 0aace1e7ch, 0d3375fech, 0ce78a399h, 0406b2a42h, 020fe9e35h, 0d9f385b9h
dd 0ee39d7abh, 03b124e8bh, 01dc9faf7h, 04b6d1856h, 026a36631h, 0eae397b2h
dd 03a6efa74h, 0dd5b4332h, 06841e7f7h, 0ca7820fbh, 0fb0af54eh, 0d8feb397h
dd 0454056ach, 0ba489527h, 055533a3ah, 020838d87h, 0fe6ba9b7h, 0d096954bh
dd 055a867bch, 0a1159a58h, 0cca92963h, 099e1db33h, 0a62a4a56h, 03f3125f9h
dd 05ef47e1ch, 09029317ch, 0fdf8e802h, 004272f70h, 080bb155ch, 005282ce3h
dd 095c11548h, 0e4c66d22h, 048c1133fh, 0c70f86dch, 007f9c9eeh, 041041f0fh
dd 0404779a4h, 05d886e17h, 0325f51ebh, 0d59bc0d1h, 0f2bcc18fh, 041113564h
dd 0257b7834h, 0602a9c60h, 0dff8e8a3h, 01f636c1bh, 00e12b4c2h, 002e1329eh
dd 0af664fd1h, 0cad18115h, 06b2395e0h, 0333e92e1h, 03b240b62h, 0eebeb922h
dd 085b2a20eh, 0e6ba0d99h, 0de720c8ch, 02da2f728h, 0d0127845h, 095b794fdh
dd 0647d0862h, 0e7ccf5f0h, 05449a36fh, 0877d48fah, 0c39dfd27h, 0f33e8d1eh
dd 00a476341h, 0992eff74h, 03a6f6eabh, 0f4f8fd37h, 0a812dc60h, 0a1ebddf8h
dd 0991be14ch, 0db6e6b0dh, 0c67b5510h, 06d672c37h, 02765d43bh, 0dcd0e804h
dd 0f1290dc7h, 0cc00ffa3h, 0b5390f92h, 0690fed0bh, 0667b9ffbh, 0cedb7d9ch
dd 0a091cf0bh, 0d9155ea3h, 0bb132f88h, 0515bad24h, 07b9479bfh, 0763bd6ebh
dd 037392eb3h, 0cc115979h, 08026e297h, 0f42e312dh, 06842ada7h, 0c66a2b3bh
dd 012754ccch, 0782ef11ch, 06a124237h, 0b79251e7h, 006a1bbe6h, 04bfb6350h
dd 01a6b1018h, 011caedfah, 03d25bdd8h, 0e2e1c3c9h, 044421659h, 00a121386h
dd 0d90cec6eh, 0d5abea2ah, 064af674eh, 0da86a85fh, 0bebfe988h, 064e4c3feh
dd 09dbc8057h, 0f0f7c086h, 060787bf8h, 06003604dh, 0d1fd8346h, 0f6381fb0h
dd 07745ae04h, 0d736fccch, 083426b33h, 0f01eab71h, 0b0804187h, 03c005e5fh
dd 077a057beh, 0bde8ae24h, 055464299h, 0bf582e61h, 04e58f48fh, 0f2ddfda2h
dd 0f474ef38h, 08789bdc2h, 05366f9c3h, 0c8b38e74h, 0b475f255h, 046fcd9b9h
dd 07aeb2661h, 08b1ddf84h, 0846a0e79h, 0915f95e2h, 0466e598eh, 020b45770h
dd 08cd55591h, 0c902de4ch, 0b90bace1h, 0bb8205d0h, 011a86248h, 07574a99eh
dd 0b77f19b6h, 0e0a9dc09h, 0662d09a1h, 0c4324633h, 0e85a1f02h, 009f0be8ch
dd 04a99a025h, 01d6efe10h, 01ab93d1dh, 00ba5a4dfh, 0a186f20fh, 02868f169h
dd 0dcb7da83h, 0573906feh, 0a1e2ce9bh, 04fcd7f52h, 050115e01h, 0a70683fah
dd 0a002b5c4h, 00de6d027h, 09af88c27h, 0773f8641h, 0c3604c06h, 061a806b5h
dd 0f0177a28h, 0c0f586e0h, 0006058aah, 030dc7d62h, 011e69ed7h, 02338ea63h
dd 053c2dd94h, 0c2c21634h, 0bbcbee56h, 090bcb6deh, 0ebfc7da1h, 0ce591d76h
dd 06f05e409h, 04b7c0188h, 039720a3dh, 07c927c24h, 086e3725fh, 0724d9db9h
dd 01ac15bb4h, 0d39eb8fch, 0ed545578h, 008fca5b5h, 0d83d7cd3h, 04dad0fc4h
dd 01e50ef5eh, 0b161e6f8h, 0a28514d9h, 06c51133ch, 06fd5c7e7h, 056e14ec4h
dd 0362abfceh, 0ddc6c837h, 0d79a3234h, 092638212h, 0670efa8eh, 0406000e0h
sbox4 dd 03a39ce37h, 0d3faf5cfh, 0abc27737h, 05ac52d1bh, 05cb0679eh, 04fa33742h
dd 0d3822740h, 099bc9bbeh, 0d5118e9dh, 0bf0f7315h, 0d62d1c7eh, 0c700c47bh
dd 0b78c1b6bh, 021a19045h, 0b26eb1beh, 06a366eb4h, 05748ab2fh, 0bc946e79h
dd 0c6a376d2h, 06549c2c8h, 0530ff8eeh, 0468dde7dh, 0d5730a1dh, 04cd04dc6h
dd 02939bbdbh, 0a9ba4650h, 0ac9526e8h, 0be5ee304h, 0a1fad5f0h, 06a2d519ah
dd 063ef8ce2h, 09a86ee22h, 0c089c2b8h, 043242ef6h, 0a51e03aah, 09cf2d0a4h
dd 083c061bah, 09be96a4dh, 08fe51550h, 0ba645bd6h, 02826a2f9h, 0a73a3ae1h
dd 04ba99586h, 0ef5562e9h, 0c72fefd3h, 0f752f7dah, 03f046f69h, 077fa0a59h
dd 080e4a915h, 087b08601h, 09b09e6adh, 03b3ee593h, 0e990fd5ah, 09e34d797h
dd 02cf0b7d9h, 0022b8b51h, 096d5ac3ah, 0017da67dh, 0d1cf3ed6h, 07c7d2d28h
dd 01f9f25cfh, 0adf2b89bh, 05ad6b472h, 05a88f54ch, 0e029ac71h, 0e019a5e6h
dd 047b0acfdh, 0ed93fa9bh, 0e8d3c48dh, 0283b57cch, 0f8d56629h, 079132e28h
dd 0785f0191h, 0ed756055h, 0f7960e44h, 0e3d35e8ch, 015056dd4h, 088f46dbah
dd 003a16125h, 00564f0bdh, 0c3eb9e15h, 03c9057a2h, 097271aech, 0a93a072ah
dd 01b3f6d9bh, 01e6321f5h, 0f59c66fbh, 026dcf319h, 07533d928h, 0b155fdf5h
dd 003563482h, 08aba3cbbh, 028517711h, 0c20ad9f8h, 0abcc5167h, 0ccad925fh
dd 04de81751h, 03830dc8eh, 0379d5862h, 09320f991h, 0ea7a90c2h, 0fb3e7bceh
dd 05121ce64h, 0774fbe32h, 0a8b6e37eh, 0c3293d46h, 048de5369h, 06413e680h
dd 0a2ae0810h, 0dd6db224h, 069852dfdh, 009072166h, 0b39a460ah, 06445c0ddh
dd 0586cdecfh, 01c20c8aeh, 05bbef7ddh, 01b588d40h, 0ccd2017fh, 06bb4e3bbh
dd 0dda26a7eh, 03a59ff45h, 03e350a44h, 0bcb4cdd5h, 072eacea8h, 0fa6484bbh
dd 08d6612aeh, 0bf3c6f47h, 0d29be463h, 0542f5d9eh, 0aec2771bh, 0f64e6370h
dd 0740e0d8dh, 0e75b1357h, 0f8721671h, 0af537d5dh, 04040cb08h, 04eb4e2cch
dd 034d2466ah, 00115af84h, 0e1b00428h, 095983a1dh, 006b89fb4h, 0ce6ea048h
dd 06f3f3b82h, 03520ab82h, 0011a1d4bh, 0277227f8h, 0611560b1h, 0e7933fdch
dd 0bb3a792bh, 0344525bdh, 0a08839e1h, 051ce794bh, 02f32c9b7h, 0a01fbac9h
dd 0e01cc87eh, 0bcc7d1f6h, 0cf0111c3h, 0a1e8aac7h, 01a908749h, 0d44fbd9ah
dd 0d0dadecbh, 0d50ada38h, 00339c32ah, 0c6913667h, 08df9317ch, 0e0b12b4fh
dd 0f79e59b7h, 043f5bb3ah, 0f2d519ffh, 027d9459ch, 0bf97222ch, 015e6fc2ah
dd 00f91fc71h, 09b941525h, 0fae59361h, 0ceb69cebh, 0c2a86459h, 012baa8d1h
dd 0b6c1075eh, 0e3056a0ch, 010d25065h, 0cb03a442h, 0e0ec6e0eh, 01698db3bh
dd 04c98a0beh, 03278e964h, 09f1f9532h, 0e0d392dfh, 0d3a0342bh, 08971f21eh
dd 01b0a7441h, 04ba3348ch, 0c5be7120h, 0c37632d8h, 0df359f8dh, 09b992f2eh
dd 0e60b6f47h, 00fe3f11dh, 0e54cda54h, 01edad891h, 0ce6279cfh, 0cd3e7e6fh
dd 01618b166h, 0fd2c1d05h, 0848fd2c5h, 0f6fb2299h, 0f523f357h, 0a6327623h
dd 093a83531h, 056cccd02h, 0acf08162h, 05a75ebb5h, 06e163697h, 088d273cch
dd 0de966292h, 081b949d0h, 04c50901bh, 071c65614h, 0e6c6c7bdh, 0327a140ah
dd 045e1d006h, 0c3f27b9ah, 0c9aa53fdh, 062a80f00h, 0bb25bfe2h, 035bdd2f6h
dd 071126905h, 0b2040222h, 0b6cbcf7ch, 0cd769c2bh, 053113ec0h, 01640e3d3h
dd 038abbd60h, 02547adf0h, 0ba38209ch, 0f746ce76h, 077afa1c5h, 020756060h
dd 085cbfe4eh, 08ae88dd8h, 07aaaf9b0h, 04cf9aa7eh, 01948c25ch, 002fb8a8ch
dd 001c36ae4h, 0d6ebe1f9h, 090d4f869h, 0a65cdea0h, 03f09252dh, 0c208e69fh
dd 0b74e6132h, 0ce77e25bh, 0578fdfe3h, 03ac372e6h
.code
;s盒變換函數(shù)
BlowFish_Fun proc uses ebx edi esi edx ecx,BfNumWORD
MOV ECX,BfNum
MOV AL,CL
AND EAX,0FFh
SHR ECX,08
MOV EDX,EAX
MOV AL,CL
MOV EDI,offset key
AND EAX,0FFh
SHR ECX,08
MOV ESI,EAX
MOV EAX,ECX
SHR EAX,08
AND EAX,0FFh
AND ECX,0FFh
AND ESI,0FFFFh
AND EDX,0FFFFh
MOV EAX,[EDI+EAX*4+48h]
MOV EBX,[EDI+ECX*4+0448h]
MOV ECX,[EDI+ESI*4+0848h]
ADD EAX,EBX
XOR EAX,ECX
MOV ECX,[EDI+EDX*4+0C48h]
ADD EAX,ECX
RET
BlowFish_Fun endp
;BlowFish加密算法函數(shù)
BlowFish_En proc uses ebx edi esi edx ecx,highbfWORD,lowbfWORD
LOCAL num WORD
MOV EAX,highbf
MOV ECX,lowbf
MOV EAX,[EAX]
MOV ESI,[ECX]
MOV EDI,offset key
MOV num,10h
MOV EBX,EDI
loc_40108E:
XOR EAX,[EBX]
MOV EDX,EAX
invoke BlowFish_Fun,EAX
MOV ECX,num
XOR EAX,ESI
ADD EBX,4
DEC ECX
MOV ESI,EDX
MOV num,ECX
JNZ loc_40108E
MOV ECX,[EDI+40h]
MOV EDX,[EDI+44h]
XOR ECX,EAX
XOR EDX,ESI
MOV [BFHIGH],EDX
MOV [BFLOW],ECX
RET
BlowFish_En endp
;BlowFish初始化函數(shù)
BlowFish_Init proc uses ebx edi esi edx ecx,PWDWORD,len_PWDWORD
LOCAL pbox_num18WORD
LOCAL pbox_num4 WORD
LOCAL snum WORD
;初始化s盒
MOV ESI,offset key
MOV EAX,offset sbox1
LEA ECX,[ESI+48h]
loc_401141:
MOV EDX,0100h
loc_401146:
MOV EDI,[EAX]
ADD EAX,4
MOV [ECX],EDI
ADD ECX,4
DEC EDX
JNZ loc_401146
CMP EAX,offset sbox1+1000h
JL loc_401141
;初始化p盒
;第一步：原p盒與PWD逐項(xiàng)異或
MOV EDX,PWD
MOV EDI,offset pbox
XOR EAX,EAX
SUB EDI,ESI
MOV pbox_num18,12h
loc_401173:
XOR ECX,ECX
MOV pbox_num4,04
loc_40117D:
XOR EBX,EBX
MOV BL,[EAX+EDX]
SHL ECX,08
OR ECX,EBX
INC EAX
CMP EAX,len_PWD
JL loc_40118E
XOR EAX,EAX
loc_40118E:
MOV EBX,pbox_num4
DEC EBX
MOV pbox_num4,EBX
JNZ loc_40117D
MOV EBX,[EDI+ESI]
ADD ESI,4
XOR EBX,ECX
MOV ECX,pbox_num18
MOV [ESI-04],EBX
DEC ECX
MOV pbox_num18,ECX
JNZ loc_401173
;用連續(xù)的blowfish算法填充p盒
MOV EBX,offset key
XOR EAX,EAX
MOV BFLOW,EAX
MOV BFHIGH,EAX
MOV ESI,EBX
MOV EDI,09
loc_4011C4:
LEA EAX,BFLOW
LEA ECX,BFHIGH
invoke BlowFish_En,ECX,EAX
MOV EAX,BFHIGH
MOV ECX,BFLOW
MOV [ESI],EAX
MOV [ESI+04],ECX
ADD ESI,8
DEC EDI
JNZ loc_4011C4
;用連續(xù)的blowfish算法填充s盒
LEA ESI,[EBX+4Ch]
MOV snum,04 ;4個(gè)s盒。
loc_4011F2:
MOV EDI,80H ;每個(gè)盒填充80h=128次（每次填充兩個(gè)數(shù)）。
loc_4011F7:
LEA ECX,BFLOW
LEA EDX,BFHIGH
invoke BlowFish_En,EDX,ECX
MOV ECX,BFHIGH
MOV EDX,BFLOW
MOV [ESI-04],ECX
MOV [ESI],EDX
ADD ESI,8
DEC EDI
JNZ loc_4011F7
DEC snum
JNZ loc_4011F2
RET
BlowFish_Init endp
;消息處理函數(shù)
_ProcDlgMain proc uses ebx edi esi edx ecx,hWndWORD,wMsgWORD,wParamWORD,lParamWORD
mov eax,wMsg
.if eax==WM_CLOSE
invoke EndDialog,hWnd,NULL
.elseif eax==WM_COMMAND
mov eax,wParam
and eax,0ffffh
.if eax==IDGEN
;如果你直接用ComputerID產(chǎn)生序列號(hào)，從這里到mov MYBFLOW,ebx一段應(yīng)該屏蔽
invoke GetDlgItemText,hWnd,Edit1,offset szID,17
xor ebx,ebx
xor eax,eax
mov esi,offset szID
mov ecx,8
@@33:
or ebx,eax
xor eax,eax
lodsb
cmp eax,39h
jle @@3
sub eax,7
@@3:
sub eax,30h
shl ebx,4
loop @@33
or ebx,eax
mov MYBFHIGH,ebx
mov esi,offset szID+8
mov ecx,8
xor eax,eax
xor ebx,ebx
@@44:
or ebx,eax
lodsb
cmp eax,39h
jle @@4
sub eax,7
@@4:
sub eax,30h
shl ebx,4
loop @@44
or ebx,eax
mov MYBFLOW,ebx
;…………………………………………………………………………………………………………
;如果你直接用ComputerID產(chǎn)生序列號(hào)，這里后面的所有語句你都應(yīng)將其激活
; invoke BlowFish_Init,offset PW_1,23
; invoke BlowFish_En,offset data1_p,offset data1_p+4
; MOV EAX,BFHIGH
; MOV MYBFHIGH,EAX
; MOV EAX,BFLOW
; MOV MYBFLOW,EAX
invoke BlowFish_Init,offset PW_2,18
invoke BlowFish_En,offset MYBFHIGH,offset MYBFLOW
MOV EAX,BFHIGH
MOV MYBFHIGH,EAX
MOV EAX,BFLOW
MOV MYBFLOW,EAX
invoke BlowFish_Init,offset PW_3,14
invoke BlowFish_En,offset MYBFHIGH,offset MYBFLOW
mov ebx,BFHIGH
mov eax,ebx
mov edi,offset szText
mov ecx,8
@@12:
mov eax,ebx
shl ebx,4
shr eax,28
cmp eax,9
jle @@11
add eax,7
@@11: add eax,30h
and eax,0ffh
stosb
loop @@12
mov ebx,BFLOW
mov eax,ebx
mov edi,offset szText+8
mov ecx,8
@@22:
mov eax,ebx
shl ebx,4
shr eax,28
cmp eax,9
jle @@21
add eax,7
@@21: add eax,30h
and eax,0ffh
stosb
loop @@22
xor eax,eax
mov [edi],eax
invoke SetDlgItemText,hWnd,Edit2,offset szText
mov eax,FALSE
ret
.elseif eax==IDCLOSE
invoke EndDialog,hWnd,NULL
.endif
.else
mov eax,FALSE
ret
.endif
mov eax,TRUE
ret
_ProcDlgMain endp
;主程序
start:
invoke InitCommonControls
invoke GetModuleHandle,NULL
mov hInstance,eax
invoke DialogBoxParam,hInstance,DLG_MAIN,NULL,offset _ProcDlgMain,0
invoke ExitProcess,NULL
end start
end
;資源文件：rsrc.rc
;#include <Resource.h>
;#define IDGEN 10
;#define DLG_MAIN 100
;#define EDIT1 11
;#define EDIT2 12
;
;DLG_MAIN DIALOGEX 100,150,250,60
;STYLE DS_MODALFRAME|WS_POPUP|WS_VISIBLE|WS_CAPTION|WS_SYSMENU|WS_THICKFRAME
;CAPTION "BlowFish's CrackMe KenGen By 夜月[CCG] "
;FONT 9,"宋體"
;
;BEGIN
;CONTROL " ID:",-1,"Static",SS_LEFT,10,13,40,17
;CONTROL "SN:" ,-2,"Static",SS_CENTER,10,40,20,17
;CONTROL "" ,11,"Edit",ES_LEFT,30,13,150,10
;CONTROL "" ,12,"Edit",ES_LEFT,30,40,150,10
;CONTROL "GENERATE",IDGEN,"BUTTON",BS_PUSHBUTTON,200,11,40,15
;CONTROL "EXIT",IDCLOSE,"BUTTON",BS_PUSHBUTTON,200,36,41,14
;END
[06/22-12:59:35]
ASProtect的加密算法初步分析
原來ASProtect的幾個(gè)函數(shù)的作用對(duì)保護(hù)強(qiáng)度提高不小。一改以前我見過的殼重技巧輕算法的毛病，的確在有些方面值得學(xué)習(xí)。
其利用的原理如下：
1)程序在編程時(shí)可以根據(jù)需要選擇使用ASProtect提供的幾個(gè)函數(shù)。
比如：
SetRegistrationKey(...),
GetRegistrationInformation(...),
GetHardwareID(...)
這幾個(gè)函數(shù)由于使用了導(dǎo)出方式的聲明所以會(huì)在ExportTable中出現(xiàn)，ASProtect在加殼時(shí)可以通過分析ExportTable識(shí)別出程序使用了哪些其提供的函數(shù)，從而對(duì)這些函數(shù)的入口進(jìn)行掛鉤，從而使其加殼后的外殼代碼可以象回調(diào)函數(shù)一樣調(diào)用這些函數(shù)與程序進(jìn)行通信。
比如見以下代碼：
0041333E loc_41333E: ; CODE XREF: sub_413253+B0j
0041333E mov eax, ds:4155CCh
00413343 cmp dword ptr [eax+0Ch], 0
00413347 jz short loc_413360
00413349 mov eax, ds:41555Ch
0041334E mov eax, [eax]
00413350 call @System@@LStrToPChar$qqrv ; System __linkproc__ LStrToPChar(void)
00413355 push eax
00413356 mov eax, ds:4155CCh
0041335B mov eax, [eax+0Ch]
0041335E call eax
00413360
00413360 loc_413360: ; CODE XREF: sub_413253+F4j
00413360 mov eax, ds:4155CCh
00413365 cmp dword ptr [eax+30h], 0 ; eax 是一內(nèi)部結(jié)構(gòu)指針
00413369 jz short loc_413389
0041336B push 41105Ch
00413370 mov eax, ds:4155CCh
00413375 mov eax, [eax+30h]
00413378 call eax ; 這里將調(diào)用 GetDecryptProc(...)
0041337A push 41105Ch
0041337F mov eax, ds:4155CCh
2)程序在編程時(shí)還可以加入ASProtect提供的兩個(gè)宏定義，這兩個(gè)宏定義實(shí)際上將起到特殊的標(biāo)志作用，有點(diǎn)類似"塊開始"和"塊結(jié)束"的作用。在ASProtect將在加殼時(shí)將對(duì)"這些塊"中的代碼進(jìn)行加密。對(duì)這些代碼塊的加、解密使用了的密碼學(xué)算法。目前還不十分清楚其使用的算法，初步分析這里可能用到了TWOFISH。因?yàn)榘l(fā)現(xiàn)了一些特征：
初始化部分有以下常數(shù)設(shè)置：
0040C4AE mov dword ptr [ebx+48h], 67452301h
0040C4B5 mov dword ptr [ebx+4Ch], 0EFCDAB89h
0040C4BC mov dword ptr [ebx+50h], 98BADCFEh
0040C4C3 mov dword ptr [ebx+54h], 10325476h
0040C4CA mov dword ptr [ebx+58h], 0C3D2E1F0h
0040C4D1 mov dword ptr [ebx+5Ch], 76543210h
0040C4D8 mov dword ptr [ebx+60h], 0FEDCBA98h
0040C4DF mov dword ptr [ebx+64h], 89ABCDEFh
0040C4E6 mov dword ptr [ebx+68h], 1234567h
0040C4ED mov dword ptr [ebx+6Ch], 3C2D1E0Fh
而運(yùn)算部分有大量類似MD5算法的運(yùn)算。由于代碼太長(zhǎng)，不列舉了。
3)在ASProtect中我們看到其提供了Registration_Keys加密方式。ASProtect可以對(duì)你提供的"Registration_Information"進(jìn)行加密，形成"Registeration_Key"，(按照幫助中介紹的你還可以使用自己的"加解密算法"，但是RegKey必須至少173個(gè)字符，才有安全性)。這個(gè)"RegKey"將以注冊(cè)表文件(.reg)文件方式保存。在加殼后的外殼代碼運(yùn)行時(shí)將解密"RegKey"從而得到"RegInfo"，當(dāng)然這分為兩種方式：一種方式，程序編程時(shí)使用了其提供的回調(diào)函數(shù)SetRegistrationKey(...)，那么外殼代碼運(yùn)行時(shí)將調(diào)用該函數(shù)從而得到"RegKey"來解密出"RegInfo"，如果程序沒有使用這個(gè)函數(shù)，外殼代碼將從注冊(cè)表中相應(yīng)鍵名處提取鍵值作為"RegKey"來解密出"RegInfo"。初步分析其可能使用了RSA算法。
其解密部分的代碼：
0040B4D4 loc_40B4D4: ; CODE XREF: license+156j
0040B4D4 ; license+15Fj
0040B4D4 lea edi, [ebp+lpInterBlock]
0040B4DA inc edi
0040B4DB mov esi, edi
0040B4DD push esi
0040B4DE lea eax, [ebp+lpInterStruct+8]
0040B4E4 push eax
0040B4E5 lea eax, [ebp+lpInterStruct+88h]
0040B4EB push eax
0040B4EC push esi
0040B4ED call decrypt_engine ; Criper Text to Plain Text...
從 decrypt_engine 函數(shù)的入口參數(shù)看有四個(gè)：
1)加密數(shù)據(jù)地址指針....(函數(shù)按每一塊進(jìn)行解密).....即 m
2)可能是RSA.N
3)可能是RSA.E
4)用于輸出解密數(shù)據(jù)地址指針....
目前還有幾個(gè)問題還沒有來得及分析：
1)還沒有見到TEA算法，不過在CASPR中介紹中至少提到這個(gè)算法，不知道這個(gè)算法在哪里，用于作什么？
2)在我了解了ASProtect會(huì)利用宏定義定義出"代碼塊"以后，我想象ASProtect中其會(huì)把"代碼塊"挖出來"，與"RegInfo"一起加密形式成"RegKey"。不過實(shí)際發(fā)現(xiàn)這些"代碼塊"并沒有被"挖"出來，而是使用一種算法(可能是TWOFISH)解密，不知道這個(gè)KEY到底保存在哪里？不知道是否保存在"RegKey"中。我想大概如此。^_^
我想我們可以把ASProtect看成一個(gè)"軟鎖"。"鎖"中的數(shù)據(jù)包括用于解密的代碼塊的KEY和用于解密"RegInfo"的KEY，即我們所見到的字符串形式的"RegKey"。在外殼代碼運(yùn)行時(shí)ASProtect將提取"鎖"中的數(shù)據(jù)用于解密。
如果某程序分為"注冊(cè)版本"和"試用版本"，其使用ASProtect外殼+內(nèi)部函數(shù)組合方式加密。其注冊(cè)版本將提供.reg注冊(cè)表文件形式的"RegKey"作為開鎖的"鑰匙"，那么我們能否在沒有"鑰匙"的情況下破門而入呢？
由于RegKey中包含了用于解密程序中提取出來的"代碼塊"的KEY，那么在沒有RegKey的情況下自然我們也就缺少了這個(gè)KEY，因此程序中的被提取出來的"代碼塊"就無法正確解密。如果在此情況下脫殼，那么那些加密了的代碼塊中的數(shù)據(jù)依然是無用的數(shù)據(jù)，因此脫殼的軟件就成了破碎的脫殼版本了。因此在沒有鑰匙的情況下看來破門而入的想法不太樂觀。
[06/22-13:00:07]
Hash 算法及其應(yīng)用
---------------
什么是 Hash
Hash 的重要特性
Hash 函數(shù)的實(shí)現(xiàn)
主要的 Hash 算法
Hash 算法的安全問題
Hash 算法的應(yīng)用
結(jié) 論
---------------
Hash，一般翻譯做“散列”，也有直接音譯為"哈希"的，就是把任意長(zhǎng)度的輸入（又叫做預(yù)映射， pre-image），通過散列算法，變換成固定長(zhǎng)度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能會(huì)散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。
數(shù)學(xué)表述為：h = H(M) ，其中H( )--單向散列函數(shù)，M--任意長(zhǎng)度明文，h--固定長(zhǎng)度散列值。
在信息安全領(lǐng)域中應(yīng)用的Hash算法，還需要滿足其他關(guān)鍵特性：
第一當(dāng)然是單向性(one-way)，從預(yù)映射，能夠簡(jiǎn)單迅速的得到散列值，而在計(jì)算上不可能構(gòu)造一個(gè)預(yù)映射，使其散列結(jié)果等于某個(gè)特定的散列值，即構(gòu)造相應(yīng)的M=H-1(h)不可行。這樣，散列值就能在統(tǒng)計(jì)上唯一的表征輸入值，因此，密碼學(xué)上的 Hash 又被稱為"消息摘要(message digest)"，就是要求能方便的將"消息"進(jìn)行"摘要"，但在"摘要"中無法得到比"摘要"本身更多的關(guān)于"消息"的信息。
第二是抗沖突性(collision-resistant)，即在統(tǒng)計(jì)上無法產(chǎn)生2個(gè)散列值相同的預(yù)映射。給定M，計(jì)算上無法找到M'，滿足H(M)=H(M') ，此謂弱抗沖突性；計(jì)算上也難以尋找一對(duì)任意的M和M'，使?jié)M足H(M)=H(M') ，此謂強(qiáng)抗沖突性。要求"強(qiáng)抗沖突性"主要是為了防范所謂"生日攻擊(birthday attack)"，在一個(gè)10人的團(tuán)體中，你能找到和你生日相同的人的概率是2.4%，而在同一團(tuán)體中，有2人生日相同的概率是11.7%。類似的，當(dāng)預(yù)映射的空間很大的情況下，算法必須有足夠的強(qiáng)度來保證不能輕易找到"相同生日"的人。
第三是映射分布均勻性和差分分布均勻性，散列結(jié)果中，為 0 的 bit 和為 1 的 bit ，其總數(shù)應(yīng)該大致相等；輸入中一個(gè) bit 的變化，散列結(jié)果中將有一半以上的 bit 改變，這又叫做"雪崩效應(yīng)(avalanche effect)"；要實(shí)現(xiàn)使散列結(jié)果中出現(xiàn) 1bit 的變化，則輸入中至少有一半以上的 bit 必須發(fā)生變化。其實(shí)質(zhì)是必須使輸入中每一個(gè) bit 的信息，盡量均勻的反映到輸出的每一個(gè) bit 上去；輸出中的每一個(gè) bit，都是輸入中盡可能多 bit 的信息一起作用的結(jié)果。
Damgard 和 Merkle 定義了所謂“壓縮函數(shù)(compression function)”，就是將一個(gè)固定長(zhǎng)度輸入，變換成較短的固定長(zhǎng)度的輸出，這對(duì)密碼學(xué)實(shí)踐上 Hash 函數(shù)的設(shè)計(jì)產(chǎn)生了很大的影響。Hash函數(shù)就是被設(shè)計(jì)為基于通過特定壓縮函數(shù)的不斷重復(fù)“壓縮”輸入的分組和前一次壓縮處理的結(jié)果的過程，直到整個(gè)消息都被壓縮完畢，最后的輸出作為整個(gè)消息的散列值。盡管還缺乏嚴(yán)格的證明，但絕大多數(shù)業(yè)界的研究者都同意，如果壓縮函數(shù)是安全的，那么以上述形式散列任意長(zhǎng)度的消息也將是安全的。這就是所謂 Damgard/Merkle 結(jié)構(gòu)：
在下圖中，任意長(zhǎng)度的消息被分拆成符合壓縮函數(shù)輸入要求的分組，最后一個(gè)分組可能需要在末尾添上特定的填充字節(jié)，這些分組將被順序處理，除了第一個(gè)消息分組將與散列初始化值一起作為壓縮函數(shù)的輸入外，當(dāng)前分組將和前一個(gè)分組的壓縮函數(shù)輸出一起被作為這一次壓縮的輸入，而其輸出又將被作為下一個(gè)分組壓縮函數(shù)輸入的一部分，直到最后一個(gè)壓縮函數(shù)的輸出，將被作為整個(gè)消息散列的結(jié)果。
MD5 和 SHA1 可以說是目前應(yīng)用最廣泛的Hash算法，而它們都是以 MD4 為基礎(chǔ)設(shè)計(jì)的。
1) MD4
MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年設(shè)計(jì)的，MD 是 Message Digest 的縮寫。它適用在32位字長(zhǎng)的處理器上用高速軟件實(shí)現(xiàn)--它是基于 32 位操作數(shù)的位操作來實(shí)現(xiàn)的。它的安全性不像RSA那樣基于數(shù)學(xué)假設(shè)，盡管 Den Boer、Bosselaers 和 Dobbertin 很快就用分析和差分成功的攻擊了它3輪變換中的 2 輪，證明了它并不像期望的那樣安全，但它的整個(gè)算法并沒有真正被破解過，Rivest 也很快進(jìn)行了改進(jìn)。
下面是一些MD4散列結(jié)果的例子：
MD4 ("") = 31d6cfe0d16ae931b73c59d7e0c089c0
MD4 ("a") = bde52cb31de33e46245e05fbdbd6fb24
MD4 ("abc") = a448017aaf21d8525fc10ae87aa6729d
MD4 ("message digest") = d9130a8164549fe818874806e1c7014b
MD4 ("abcdefghijklmnopqrstuvwxyz") = d79e1c308aa5bbcdeea8ed63df412da9
MD4 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 043f8582f241db351ce627e153e7f0e4
MD4 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = e33b4ddc9c38f2199c3e7b164fcc0536
2) MD5
MD5(RFC 1321)是 Rivest 于1991年對(duì)MD4的改進(jìn)版本。它對(duì)輸入仍以512位分組，其輸出是4個(gè)32位字的級(jí)聯(lián)，與 MD4 相同。它較MD4所做的改進(jìn)是：
1) 加入了第四輪
2) 每一步都有唯一的加法常數(shù)；
3) 第二輪中的G函數(shù)從((X ∧ Y) ∨ (X ∧ Z) ∨ (Y ∧ Z)) 變?yōu)?((X ∧ Z) ∨ (Y ∧ ～Z))以減小其對(duì)稱性；
4) 每一步都加入了前一步的結(jié)果，以加快"雪崩效應(yīng)"；
5) 改變了第2輪和第3輪中訪問輸入子分組的順序，減小了形式的相似程度；
6) 近似優(yōu)化了每輪的循環(huán)左移位移量，以期加快"雪崩效應(yīng)"，各輪的循環(huán)左移都不同。
盡管MD5比MD4來得復(fù)雜，并且速度較之要慢一點(diǎn)，但更安全，在抗分析和抗差分方面表現(xiàn)更好。
消息首先被拆成若干個(gè)512位的分組，其中最后512位一個(gè)分組是“消息尾+填充字節(jié)(100…0)+64 位消息長(zhǎng)度”，以確保對(duì)于不同長(zhǎng)度的消息，該分組不相同。64位消息長(zhǎng)度的限制導(dǎo)致了MD5安全的輸入長(zhǎng)度必須小于264bit，因?yàn)榇笥?4位的長(zhǎng)度信息將被忽略。而4個(gè)32位寄存器字初始化為A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210，它們將始終參與運(yùn)算并形成最終的散列結(jié)果。
接著各個(gè)512位消息分組以16個(gè)32位字的形式進(jìn)入算法的主循環(huán)，512位消息分組的個(gè)數(shù)據(jù)決定了循環(huán)的次數(shù)。主循環(huán)有4輪，每輪分別用到了非線性函數(shù)
F(X, Y, Z) = (X ∧ Y) ∨ (～X ∧ Z)
G(X, Y, Z) = (X ∧ Z) ∨ (Y ∧ ～Z)
H(X, Y, Z) =X ⊕ Y ⊕ Z
I(X, Y, Z) = X ⊕ (Y ∨ ～Z)
這4輪變換是對(duì)進(jìn)入主循環(huán)的512位消息分組的16個(gè)32位字分別進(jìn)行如下操作：將A、B、C、D的副本a、b、c、d中的3個(gè)經(jīng)F、G、H、I運(yùn)算后的結(jié)果與第4個(gè)相加，再加上32位字和一個(gè)32位字的加法常數(shù)，并將所得之值循環(huán)左移若干位，最后將所得結(jié)果加上a、b、c、d之一，并回送至ABCD，由此完成一次循環(huán)。
所用的加法常數(shù)由這樣一張表T[i]來定義，其中i為1…64，T[i]是i的正弦絕對(duì)值之4294967296次方的整數(shù)部分，這樣做是為了通過正弦函數(shù)和冪函數(shù)來進(jìn)一步消除變換中的線性性。
當(dāng)所有512位分組都運(yùn)算完畢后，ABCD的級(jí)聯(lián)將被輸出為MD5散列的結(jié)果。下面是一些MD5散列結(jié)果的例子：
MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = d174ab98d277d9f5a5611c2c9f419d9f
MD5 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 57edf4a22be3c955ac49da2e2107b67a
參考相應(yīng)RFC文檔可以得到MD4、MD5算法的詳細(xì)描述和算法的C源代碼。
3) SHA1 及其他
SHA1是由NIST NSA設(shè)計(jì)為同DSA一起使用的，訪問http://www.itl.nist.gov/fipspubs可以得到它的詳細(xì)規(guī)范--[/url]"FIPS PUB 180-1 SECURE HASH STANDARD"。它對(duì)長(zhǎng)度小于264的輸入，產(chǎn)生長(zhǎng)度為160bit的散列值，因此抗窮舉(brute-force)性更好。SHA-1 設(shè)計(jì)時(shí)基于和MD4相同原理,并且模仿了該算法。因?yàn)樗鼘a(chǎn)生160bit的散列值，因此它有5個(gè)參與運(yùn)算的32位寄存器字，消息分組和填充方式與MD5相同，主循環(huán)也同樣是4輪，但每輪進(jìn)行20次操作，非線性運(yùn)算、移位和加法運(yùn)算也與MD5類似，但非線性函數(shù)、加法常數(shù)和循環(huán)左移操作的設(shè)計(jì)有一些區(qū)別，可以參考上面提到的規(guī)范來了解這些細(xì)節(jié)。下面是一些SHA1散列結(jié)果的例子：
SHA1 ("abc") = a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d
SHA1 ("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq") = 84983e44 1c3bd26e baae4aa1 f95129e5 e54670f1
其他一些知名的Hash算法還有MD2、N-Hash、RIPE-MD、HAVAL等等。上面提到的這些都屬于"純"Hash算法。還有另2類Hash算法，一類就是基于對(duì)稱分組算法的單向散列算法，典型的例子是基于DES的所謂Davies-Meyer算法，另外還有經(jīng)IDEA改進(jìn)的Davies-Meyer算法，它們兩者目前都被認(rèn)為是安全的算法。另一類是基于模運(yùn)算/離散對(duì)數(shù)的，也就是基于公開密鑰算法的，但因?yàn)槠溥\(yùn)算開銷太大，而缺乏很好的應(yīng)用前景。
沒有通過分析和差分攻擊考驗(yàn)的算法，大多都已經(jīng)夭折在實(shí)驗(yàn)室里了，因此，如果目前流行的Hash算法能完全符合密碼學(xué)意義上的單向性和抗沖突性，就保證了只有窮舉，才是破壞Hash運(yùn)算安全特性的唯一方法。為了對(duì)抗弱抗沖突性，我們可能要窮舉個(gè)數(shù)和散列值空間長(zhǎng)度一樣大的輸入，即嘗試2^128或2^160個(gè)不同的輸入，目前一臺(tái)高檔個(gè)人電腦可能需要10^25年才能完成這一艱巨的工作，即使是最高端的并行系統(tǒng)，這也不是在幾千年里的干得完的事。而因?yàn)?生日攻擊"有效的降低了需要窮舉的空間，將其降低為大約1.2*2^64或1.2*2^80，所以，強(qiáng)抗沖突性是決定Hash算法安全性的關(guān)鍵。
在NIST新的 Advanced Encryption Standard (AES)中，使用了長(zhǎng)度為128、192、256bit 的密鑰，因此相應(yīng)的設(shè)計(jì)了 SHA256、SHA384、SHA512，它們將提供更好的安全性。
Hash算法在信息安全方面的應(yīng)用主要體現(xiàn)在以下的3個(gè)方面：
1) 文件校驗(yàn)
我們比較熟悉的校驗(yàn)算法有奇偶校驗(yàn)和CRC校驗(yàn)，這2種校驗(yàn)并沒有抗數(shù)據(jù)篡改的能力，它們一定程度上能檢測(cè)并糾正數(shù)據(jù)傳輸中的信道誤碼，但卻不能防止對(duì)數(shù)據(jù)的惡意破壞。
MD5 Hash算法的"數(shù)字指紋"特性，使它成為目前應(yīng)用最廣泛的一種文件完整性校驗(yàn)和(Checksum)算法，不少Unix系統(tǒng)有提供計(jì)算md5 checksum的命令。它常被用在下面的2種情況下：
第一是文件傳送后的校驗(yàn)，將得到的目標(biāo)文件計(jì)算 md5 checksum，與源文件的md5 checksum 比對(duì)，由兩者 md5 checksum 的一致性，可以從統(tǒng)計(jì)上保證2個(gè)文件的每一個(gè)碼元也是完全相同的。這可以檢驗(yàn)文件傳輸過程中是否出現(xiàn)錯(cuò)誤，更重要的是可以保證文件在傳輸過程中未被惡意篡改。一個(gè)很典型的應(yīng)用是ftp服務(wù)，用戶可以用來保證多次斷點(diǎn)續(xù)傳，特別是從鏡像站點(diǎn)下載的文件的正確性。
更出色的解決方法是所謂的代碼簽名，文件的提供者在提供文件的同時(shí)，提供對(duì)文件Hash值用自己的代碼簽名密鑰進(jìn)行數(shù)字簽名的值，及自己的代碼簽名證書。文件的接受者不僅能驗(yàn)證文件的完整性，還可以依據(jù)自己對(duì)證書簽發(fā)者和證書擁有者的信任程度，決定是否接受該文件。瀏覽器在下載運(yùn)行插件和java小程序時(shí)，使用的就是這樣的模式。
第二是用作保存二進(jìn)制文件系統(tǒng)的數(shù)字指紋，以便檢測(cè)文件系統(tǒng)是否未經(jīng)允許的被修改。不少系統(tǒng)管理/系統(tǒng)安全軟件都提供這一文件系統(tǒng)完整性評(píng)估的功能，在系統(tǒng)初始安裝完畢后，建立對(duì)文件系統(tǒng)的基礎(chǔ)校驗(yàn)和數(shù)據(jù)庫，因?yàn)樯⒘行ｒ?yàn)和的長(zhǎng)度很小，它們可以方便的被存放在容量很小的存儲(chǔ)介質(zhì)上。此后，可以定期或根據(jù)需要，再次計(jì)算文件系統(tǒng)的校驗(yàn)和，一旦發(fā)現(xiàn)與原來保存的值有不匹配，說明該文件已經(jīng)被非法修改，或者是被病毒感染，或者被木馬程序替代。TripWire就提供了一個(gè)此類應(yīng)用的典型例子。
更完美的方法是使用"MAC"。"MAC" 是一個(gè)與Hash密切相關(guān)的名詞，即信息鑒權(quán)碼(Message Authority Code)。它是與密鑰相關(guān)的Hash值，必須擁有該密鑰才能檢驗(yàn)該Hash值。文件系統(tǒng)的數(shù)字指紋也許會(huì)被保存在不可信任的介質(zhì)上，只對(duì)擁有該密鑰者提供可鑒別性。并且在文件的數(shù)字指紋有可能需要被修改的情況下，只有密鑰的擁有者可以計(jì)算出新的散列值，而企圖破壞文件完整性者卻不能得逞。
2) 數(shù)字簽名
Hash 算法也是現(xiàn)代密碼體系中的一個(gè)重要組成部分。由于非對(duì)稱算法的運(yùn)算速度較慢，所以在數(shù)字簽名協(xié)議中，單向散列函數(shù)扮演了一個(gè)重要的角色。
在這種簽名協(xié)議中，雙方必須事先協(xié)商好雙方都支持的Hash函數(shù)和簽名算法。
簽名方先對(duì)該數(shù)據(jù)文件進(jìn)行計(jì)算其散列值，然后再對(duì)很短的散列值結(jié)果--如Md5是16個(gè)字節(jié)，SHA1是20字節(jié)，用非對(duì)稱算法進(jìn)行數(shù)字簽名操作。對(duì)方在驗(yàn)證簽名時(shí)，也是先對(duì)該數(shù)據(jù)文件進(jìn)行計(jì)算其散列值，然后再用非對(duì)稱算法驗(yàn)證數(shù)字簽名。
對(duì) Hash 值，又稱"數(shù)字摘要"進(jìn)行數(shù)字簽名，在統(tǒng)計(jì)上可以認(rèn)為與對(duì)文件本身進(jìn)行數(shù)字簽名是等效的。而且這樣的協(xié)議還有其他的優(yōu)點(diǎn)：
首先，數(shù)據(jù)文件本身可以同它的散列值分開保存，簽名驗(yàn)證也可以脫離數(shù)據(jù)文件本身的存在而進(jìn)行。
再者，有些情況下簽名密鑰可能與解密密鑰是同一個(gè)，也就是說，如果對(duì)一個(gè)數(shù)據(jù)文件簽名，與對(duì)其進(jìn)行非對(duì)稱的解密操作是相同的操作，這是相當(dāng)危險(xiǎn)的，惡意的破壞者可能將一個(gè)試圖騙你將其解密的文件，充當(dāng)一個(gè)要求你簽名的文件發(fā)送給你。因此，在對(duì)任何數(shù)據(jù)文件進(jìn)行數(shù)字簽名時(shí)，只有對(duì)其Hash值進(jìn)行簽名才是安全的。
3) 鑒權(quán)協(xié)議
如下的鑒權(quán)協(xié)議又被稱作"挑戰(zhàn)--認(rèn)證模式：在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡(jiǎn)單而安全的方法。
需要鑒權(quán)的一方，向?qū)⒈昏b權(quán)的一方發(fā)送隨機(jī)串（“挑戰(zhàn)”），被鑒權(quán)方將該隨機(jī)串和自己的鑒權(quán)口令字一起進(jìn)行 Hash 運(yùn)算后，返還鑒權(quán)方，鑒權(quán)方將收到的Hash值與在己端用該隨機(jī)串和對(duì)方的鑒權(quán)口令字進(jìn)行 Hash 運(yùn)算的結(jié)果相比較（“認(rèn)證”），如相同，則可在統(tǒng)計(jì)上認(rèn)為對(duì)方擁有該口令字，即通過鑒權(quán)。
POP3協(xié)議中就有這一應(yīng)用的典型例子：
S: +OK POP3 server ready <1896.697170952@dbc.mtview.ca.us>
C: APOP mrose c4c9334bac560ecc979e58001b3e22fb
S: +OK maildrop has 1 message (369 octets)
在上面的一段POP3協(xié)議會(huì)話中，雙方都共享的對(duì)稱密鑰（鑒權(quán)口令字）是tanstaaf，服務(wù)器發(fā)出的挑戰(zhàn)是<1896.697170952@dbc.mtview.ca.us>，客戶端對(duì)挑戰(zhàn)的應(yīng)答是MD5("<1896.697170952@dbc.mtview.ca.us>tanstaaf") = c4c9334bac560ecc979e58001b3e22fb，這個(gè)正確的應(yīng)答使其通過了認(rèn)證。
散列算法長(zhǎng)期以來一直在計(jì)算機(jī)科學(xué)中大量應(yīng)用，隨著現(xiàn)代密碼學(xué)的發(fā)展，單向散列函數(shù)已經(jīng)成為信息安全領(lǐng)域中一個(gè)重要的結(jié)構(gòu)模塊，我們有理由深入研究其設(shè)計(jì)理論和應(yīng)用方法。
