一、MD5碼原理

1、MD5碼簡(jiǎn)介

MD5訊息摘要演算法（英語(yǔ)：MD5 Message-Digest Algorithm），一種被廣泛使用的密碼雜湊函數(shù)，可以產(chǎn)生出一個(gè)128位元（16位元組）的散列值（hash value），用于確保信息傳輸完整一致。

2、MD5功能

• 輸入任意長(zhǎng)度的信息，經(jīng)過(guò)處理，輸出為128位的信息（數(shù)字指紋）
• 不同的輸入得到的不同的結(jié)果（唯一性）
• 由MD5碼不能看到原文,即不可逆
• MD5相當(dāng)于超損壓縮

3、MD5原理

image

簡(jiǎn)述：MD5以512位分組來(lái)處理輸入的信息，且每一分組又被劃分為16個(gè)32位子分組，經(jīng)過(guò)了一系列的處理后，算法的輸出由四個(gè)32位分組組成，將這四個(gè)32位分組級(jí)聯(lián)后將生成一個(gè)128位散列值。

第一步、填充

如果輸入信息的長(zhǎng)度(bit)對(duì)512求余的結(jié)果不等于448，就需要填充使得對(duì)512求余的結(jié)果等于448。填充的方法是填充一個(gè)1和n個(gè)0。填充完后，信息的長(zhǎng)度就為N*512+448(bit)；

第二步、記錄信息長(zhǎng)度

用64位來(lái)存儲(chǔ)填充前信息長(zhǎng)度。這64位加在第一步結(jié)果的后面，這樣信息長(zhǎng)度就變?yōu)镹 * 512+448+64=(N+1)*512位。

第三步、裝入標(biāo)準(zhǔn)的幻數(shù)（四個(gè)整數(shù)）

標(biāo)準(zhǔn)的幻數(shù)（物理順序）是

• A=(01234567)16
• B=(89ABCDEF)16
• C=(FEDCBA98)16
• D=(76543210)16

如果在程序中定義應(yīng)該是:

• A=0X67452301L
• B=0XEFCDAB89L
• C=0X98BADCFEL
• D=0X10325476L

第四步、四輪循環(huán)運(yùn)算

循環(huán)的次數(shù)是分組的個(gè)數(shù)（N+1）
1）將每一512字節(jié)細(xì)分成16個(gè)小組，每個(gè)小組64位（8個(gè)字節(jié)）

2）先認(rèn)識(shí)四個(gè)線性函數(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)=Y ^ (X | (~Z))

3）設(shè)Mj表示消息的第j個(gè)子分組（從0到15）

FF(a,b,c,d,Mj,s,ti)表示a=b+((a+F(b,c,d)+Mj+ti)<<<s)
GG(a,b,c,d,Mj,s,ti)表示a=b+((a+G(b,c,d)+Mj+ti)<<<s)
HH(a,b,c,d,Mj,s,ti)表示a=b+((a+H(b,c,d)+Mj+ti)<<<s)
II(a,b,c,d,Mj,s,ti)表示a=b+((a+I(b,c,d)+Mj+ti)<<<s)

4）四輪運(yùn)算

 第一輪
a=FF(a,b,c,d,M0,7,0xd76aa478)
b=FF(d,a,b,c,M1,12,0xe8c7b756)
c=FF(c,d,a,b,M2,17,0x242070db)
d=FF(b,c,d,a,M3,22,0xc1bdceee)
a=FF(a,b,c,d,M4,7,0xf57c0faf)
b=FF(d,a,b,c,M5,12,0x4787c62a)
c=FF(c,d,a,b,M6,17,0xa8304613)
d=FF(b,c,d,a,M7,22,0xfd469501)
a=FF(a,b,c,d,M8,7,0x698098d8)
b=FF(d,a,b,c,M9,12,0x8b44f7af)
c=FF(c,d,a,b,M10,17,0xffff5bb1)
d=FF(b,c,d,a,M11,22,0x895cd7be)
a=FF(a,b,c,d,M12,7,0x6b901122)
b=FF(d,a,b,c,M13,12,0xfd987193)
c=FF(c,d,a,b,M14,17,0xa679438e)
d=FF(b,c,d,a,M15,22,0x49b40821)

第二輪
a=GG(a,b,c,d,M1,5,0xf61e2562)
b=GG(d,a,b,c,M6,9,0xc040b340)
c=GG(c,d,a,b,M11,14,0x265e5a51)
d=GG(b,c,d,a,M0,20,0xe9b6c7aa)
a=GG(a,b,c,d,M5,5,0xd62f105d)
b=GG(d,a,b,c,M10,9,0x02441453)
c=GG(c,d,a,b,M15,14,0xd8a1e681)
d=GG(b,c,d,a,M4,20,0xe7d3fbc8)
a=GG(a,b,c,d,M9,5,0x21e1cde6)
b=GG(d,a,b,c,M14,9,0xc33707d6)
c=GG(c,d,a,b,M3,14,0xf4d50d87)
d=GG(b,c,d,a,M8,20,0x455a14ed)
a=GG(a,b,c,d,M13,5,0xa9e3e905)
b=GG(d,a,b,c,M2,9,0xfcefa3f8)
c=GG(c,d,a,b,M7,14,0x676f02d9)
d=GG(b,c,d,a,M12,20,0x8d2a4c8a)

第三輪
a=HH(a,b,c,d,M5,4,0xfffa3942)
b=HH(d,a,b,c,M8,11,0x8771f681)
c=HH(c,d,a,b,M11,16,0x6d9d6122)
d=HH(b,c,d,a,M14,23,0xfde5380c)
a=HH(a,b,c,d,M1,4,0xa4beea44)
b=HH(d,a,b,c,M4,11,0x4bdecfa9)
c=HH(c,d,a,b,M7,16,0xf6bb4b60)
d=HH(b,c,d,a,M10,23,0xbebfbc70)
a=HH(a,b,c,d,M13,4,0x289b7ec6)
b=HH(d,a,b,c,M0,11,0xeaa127fa)
c=HH(c,d,a,b,M3,16,0xd4ef3085)
d=HH(b,c,d,a,M6,23,0x04881d05)
a=HH(a,b,c,d,M9,4,0xd9d4d039)
b=HH(d,a,b,c,M12,11,0xe6db99e5)
c=HH(c,d,a,b,M15,16,0x1fa27cf8)
d=HH(b,c,d,a,M2,23,0xc4ac5665)

第四輪
a=II(a,b,c,d,M0,6,0xf4292244)
b=II(d,a,b,c,M7,10,0x432aff97)
c=II(c,d,a,b,M14,15,0xab9423a7)
d=II(b,c,d,a,M5,21,0xfc93a039)
a=II(a,b,c,d,M12,6,0x655b59c3)
b=II(d,a,b,c,M3,10,0x8f0ccc92)
c=II(c,d,a,b,M10,15,0xffeff47d)
d=II(b,c,d,a,M1,21,0x85845dd1)
a=II(a,b,c,d,M8,6,0x6fa87e4f)
b=II(d,a,b,c,M15,10,0xfe2ce6e0)
c=II(c,d,a,b,M6,15,0xa3014314)
d=II(b,c,d,a,M13,21,0x4e0811a1)
a=II(a,b,c,d,M4,6,0xf7537e82)
b=II(d,a,b,c,M11,10,0xbd3af235)
c=II(c,d,a,b,M2,15,0x2ad7d2bb)
d=II(b,c,d,a,M9,21,0xeb86d391)

5）每輪循環(huán)后，將A，B，C，D分別加上a，b，c，d，然后進(jìn)入下一循環(huán)。

二、bloom過(guò)濾器

1、簡(jiǎn)介

bloom算法類似一個(gè)hash set，用來(lái)判斷某個(gè)元素（key）是否在某個(gè)集合中。
和一般的hash set不同的是，這個(gè)算法無(wú)需存儲(chǔ)key的值，對(duì)于每個(gè)key，只需要k個(gè)比特位，每個(gè)存儲(chǔ)一個(gè)標(biāo)志，用來(lái)判斷key是否在集合中。

2、算法簡(jiǎn)介

算法：

1. 首先需要k個(gè)hash函數(shù)，每個(gè)函數(shù)可以把key散列成為1個(gè)整數(shù)
2. 初始化時(shí)，需要一個(gè)長(zhǎng)度為n比特的數(shù)組，每個(gè)比特位初始化為0
3. 某個(gè)key加入集合時(shí)，用k個(gè)hash函數(shù)計(jì)算出k個(gè)散列值，并把數(shù)組中對(duì)應(yīng)的比特位置為1
4. 判斷某個(gè)key是否在集合時(shí)，用k個(gè)hash函數(shù)計(jì)算出k個(gè)散列值，并查詢數(shù)組中對(duì)應(yīng)的比特位，如果所有的比特位都是1，認(rèn)為在集合中。

優(yōu)點(diǎn)：不需要存儲(chǔ)key，節(jié)省空間

缺點(diǎn)：

1. 算法判斷key在集合中時(shí)，有一定的概率key其實(shí)不在集合中
2. 無(wú)法刪除

image

三、性能評(píng)價(jià)

32位MD5碼：128bit --> 16byte

16位MD5碼：64bit --> 8byte

內(nèi)存：4GB = 4 * 1024 * 1024 * 1024 = 4294967296 byte

若用一位bit存放MD5碼中的一位:

即4G內(nèi)存大約能存放

• 268435456組32位MD5碼
• 536870912組16位MD5碼

四、實(shí)驗(yàn)結(jié)果性能對(duì)比

1、三種算法概述

2、BloomFilter算法的哈希函數(shù)個(gè)數(shù)

| 哈希函數(shù)個(gè)數(shù) | 錯(cuò)誤數(shù) | 錯(cuò)誤單詞率| 單詞量總數(shù) | 去除單詞總數(shù) | 所花費(fèi)時(shí)間 |
| --- | --- | -- | -- | --| -- | -- |
| 1 | 316 | 0.1587% | 199120 | 178716 | 0.8661s |
| 2 | 28 | 0.0141% | 199120 | 178428 | 1.4371s |
| 3 | 9 | 0.0045% |199120 | 178409 | 2.0398s |
| 4 | 7 | 0.0035% |199120 | 178407 | 2.6319s |
| 5 | 6 |0.0030% |199120 | 178406 | 3.0578s |
| 6 | 6 | 0.0030% |199120 | 178406 | 3.6117s |
| 7 | 6 | 0.0030% |199120 | 178406 | 4.0211s |

3、MD5_SHA1_Tree樹(shù)的深度

4、空間復(fù)雜度對(duì)比