|
|
Hash 算法及其應(yīng)用
---------------
什么是 Hash
Hash 的重要特性
Hash 函數(shù)的實(shí)現(xiàn)
主要的 Hash 算法
Hash 算法的安全問題
Hash 算法的應(yīng)用
結(jié) 論
---------------
Hash，一般翻譯做“散列”，也有直接音譯為"哈希"的，就是把任意長度的輸入（又叫做
預(yù)映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這
種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能
會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。
數(shù)學(xué)表述為：h = H(M) ，其中H( )--單向散列函數(shù)，M--任意長度明文，h--固定長度散列
值。
在信息安全領(lǐng)域中應(yīng)用的Hash算法，還需要滿足其他關(guān)鍵特性：
第一當(dāng)然是單向性(one-way)，從預(yù)映射，能夠簡單迅速的得到散列值，而在計(jì)算上不可能
構(gòu)造一個預(yù)映射，使其散列結(jié)果等于某個特定的散列值，即構(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個散列值相同的預(yù)映射。
給定M，計(jì)算上無法找到M'，滿足H(M)=H(M') ，此謂弱抗沖突性；計(jì)算上也難以尋找一對
任意的M和M'，使?jié)M足H(M)=H(M') ，此謂強(qiáng)抗沖突性。要求"強(qiáng)抗沖突性"主要是為了防范
所謂"生日攻擊(birthday attack)"，在一個10人的團(tuán)體中，你能找到和你生日相同的人的
概率是2.4%，而在同一團(tuán)體中，有2人生日相同的概率是11.7%。類似的，當(dāng)預(yù)映射的空間
很大的情況下，算法必須有足夠的強(qiáng)度來保證不能輕易找到"相同生日"的人。
第三是映射分布均勻性和差分分布均勻性，散列結(jié)果中，為 0 的 bit 和為 1 的 bit ，
其總數(shù)應(yīng)該大致相等；輸入中一個 bit 的變化，散列結(jié)果中將有一半以上的 bit 改變，
這又叫做"雪崩效應(yīng)(avalanche effect)"；要實(shí)現(xiàn)使散列結(jié)果中出現(xiàn) 1bit 的變化，則輸
入中至少有一半以上的 bit 必須發(fā)生變化。其實(shí)質(zhì)是必須使輸入中每一個 bit 的信息，
盡量均勻的反映到輸出的每一個 bit 上去；輸出中的每一個 bit，都是輸入中盡可能多
bit 的信息一起作用的結(jié)果。
Damgard 和 Merkle 定義了所謂“壓縮函數(shù)(compression function)”，就是將一個固定
長度輸入，變換成較短的固定長度的輸出，這對密碼學(xué)實(shí)踐上 Hash 函數(shù)的設(shè)計(jì)產(chǎn)生了很
大的影響。Hash函數(shù)就是被設(shè)計(jì)為基于通過特定壓縮函數(shù)的不斷重復(fù)“壓縮”輸入的分組
和前一次壓縮處理的結(jié)果的過程，直到整個消息都被壓縮完畢，最后的輸出作為整個消息
的散列值。盡管還缺乏嚴(yán)格的證明，但絕大多數(shù)業(yè)界的研究者都同意，如果壓縮函數(shù)是安
全的，那么以上述形式散列任意長度的消息也將是安全的。這就是所謂 Damgard/Merkle
結(jié)構(gòu)：
在下圖中，任意長度的消息被分拆成符合壓縮函數(shù)輸入要求的分組，最后一個分組可能需
要在末尾添上特定的填充字節(jié)，這些分組將被順序處理，除了第一個消息分組將與散列初
始化值一起作為壓縮函數(shù)的輸入外，當(dāng)前分組將和前一個分組的壓縮函數(shù)輸出一起被作為
這一次壓縮的輸入，而其輸出又將被作為下一個分組壓縮函數(shù)輸入的一部分，直到最后一
個壓縮函數(shù)的輸出，將被作為整個消息散列的結(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位字長的處理器上用高速軟件實(shí)現(xiàn)--它是基于 32 位操作數(shù)的位操作
來實(shí)現(xiàn)的。它的安全性不像RSA那樣基于數(shù)學(xué)假設(shè)，盡管 Den Boer、Bosselaers 和 Dobb
ertin 很快就用分析和差分成功的攻擊了它3輪變換中的 2 輪，證明了它并不像期望的那
樣安全，但它的整個算法并沒有真正被破解過，Rivest 也很快進(jìn)行了改進(jìn)。
下面是一些MD4散列結(jié)果的例子：
MD4 ("") = 31d6cfe0d16ae931b73c59d7e0c089c0
MD4 ("a") = bde52cb31de33e46245e05fbdbd6fb24
MD4 ("abc") = a448017aaf21d8525fc10ae87aa6729d
MD4 ("message digest") = d9130a8164549fe818874806e1c7014b
MD4 ("abcdefghijklmnopqrstuvwxyz") = d79e1c308aa5bbcdeea8ed63df412da9
MD4 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 043f8
582f241db351ce627e153e7f0e4
MD4 ("123456789012345678901234567890123456789012345678901234567890123456789012
34567890") = e33b4ddc9c38f2199c3e7b164fcc0536
2) MD5
MD5(RFC 1321)是 Rivest 于1991年對MD4的改進(jìn)版本。它對輸入仍以512位分組，其輸出是
4個32位字的級聯(lián)，與 MD4 相同。它較MD4所做的改進(jìn)是：
1) 加入了第四輪
2) 每一步都有唯一的加法常數(shù)；
3) 第二輪中的G函數(shù)從((X ∧ Y) ∨ (X ∧ Z) ∨ (Y ∧ Z)) 變?yōu)?((X ∧ Z) ∨ (Y ∧
～Z))以減小其對稱性；
4) 每一步都加入了前一步的結(jié)果，以加快"雪崩效應(yīng)"；
5) 改變了第2輪和第3輪中訪問輸入子分組的順序，減小了形式的相似程度；
6) 近似優(yōu)化了每輪的循環(huán)左移位移量，以期加快"雪崩效應(yīng)"，各輪的循環(huán)左移都不同。
盡管MD5比MD4來得復(fù)雜，并且速度較之要慢一點(diǎn)，但更安全，在抗分析和抗差分方面表現(xiàn)
更好。
消息首先被拆成若干個512位的分組，其中最后512位一個分組是“消息尾+填充字節(jié)(100…
0)+64 位消息長度”，以確保對于不同長度的消息，該分組不相同。64位消息長度的限制
導(dǎo)致了MD5安全的輸入長度必須小于264bit，因?yàn)榇笥?4位的長度信息將被忽略。而4個32
位寄存器字初始化為A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210，它們
將始終參與運(yùn)算并形成最終的散列結(jié)果。
接著各個512位消息分組以16個32位字的形式進(jìn)入算法的主循環(huán)，512位消息分組的個數(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輪變換是對進(jìn)入主循環(huán)的512位消息分組的16個32位字分別進(jìn)行如下操作：將A、B、C、
D的副本a、b、c、d中的3個經(jīng)F、G、H、I運(yùn)算后的結(jié)果與第4個相加，再加上32位字和一個
32位字的加法常數(shù)，并將所得之值循環(huán)左移若干位，最后將所得結(jié)果加上a、b、c、d之一
，并回送至ABCD，由此完成一次循環(huán)。
所用的加法常數(shù)由這樣一張表T[i]來定義，其中i為1…64，T[i]是i的正弦絕對值之42949
67296次方的整數(shù)部分，這樣做是為了通過正弦函數(shù)和冪函數(shù)來進(jìn)一步消除變換中的線性性
。
當(dāng)所有512位分組都運(yùn)算完畢后，ABCD的級聯(lián)將被輸出為MD5散列的結(jié)果。下面是一些MD5散
列結(jié)果的例子：
MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = d174a
b98d277d9f5a5611c2c9f419d9f
MD5 ("123456789012345678901234567890123456789012345678901234567890123456789012
34567890") = 57edf4a22be3c955ac49da2e2107b67a
參考相應(yīng)RFC文檔可以得到MD4、MD5算法的詳細(xì)描述和算法的C源代碼。
|
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
