密碼學(xué)專題 - 單向散列函數(shù)

散列函數(shù)是一類將任意長(zhǎng)度的輸入位 (或字節(jié)) 串轉(zhuǎn)換為固定長(zhǎng)度的輸出的函數(shù)。散列函數(shù)的一個(gè)典型應(yīng)用是數(shù)字簽名。給定一個(gè)消息 $m$ ，當(dāng)然可以對(duì)這個(gè)消息本身進(jìn)行簽名。然而，大多數(shù)數(shù)字簽名方案所采用的公鑰運(yùn)算的運(yùn)算很大，直接對(duì)消息本身簽名非常不經(jīng)濟(jì)。因此不會(huì)直接對(duì) $m$ 進(jìn)行簽名，而是應(yīng)用散列函數(shù) $h$ ，對(duì) $h(m)$ 進(jìn)行簽名。相對(duì)于成千上萬(wàn)位長(zhǎng)度的消息而言，散列函數(shù)的輸出一般在 128 位到 1024 位之間。對(duì) $h(m)$ 的簽名比對(duì)消息 $m$ 的簽名要快得多。為保證采取這種方法構(gòu)造的簽名是安全的，必須要求散列函數(shù) $h$ 滿足以一條件：很難構(gòu)造兩個(gè)消息 $m_1$ 和 $m_2$ ，使得 $h(m_1)=h(m_2)$ 。下面將詳細(xì)討論散列函數(shù)的安全性質(zhì)。

散列函數(shù)有時(shí)又稱為消息摘要函數(shù)，其散列結(jié)果也稱作摘要或者指紋。

散列函數(shù)在密碼學(xué)中有很多應(yīng)用，它在密碼系統(tǒng)中的各個(gè)不同部分之間建立緊密的聯(lián)系。當(dāng)輸入是變長(zhǎng)的值時(shí)，可以使用散列函數(shù)映射為固定長(zhǎng)度的值。散列函數(shù)可以作為密碼學(xué)中的偽隨機(jī)數(shù)生成器，從一個(gè)共享密鑰生成幾個(gè)密鑰。它所具有的單向性也可以起到隔離系統(tǒng)不同部分的作用，以保證即使攻擊者得到了其中某個(gè)值，也不能獲得其他值。

7.1 散列函數(shù)的安全性

如上文所述散列函數(shù)將任意長(zhǎng)度的消息 $m$ 映射為固定長(zhǎng)度的輸出 $h(m)$ ， $h(m)$ 的長(zhǎng)度一般在 128 位到 1024 位之間?？赡軙?huì)對(duì)輸入的長(zhǎng)度有所限制，但對(duì)所有實(shí)用的目的而言輸入都可以是任意長(zhǎng)度的。散列函數(shù)要滿足幾個(gè)要求，其中最基本的要求是它必須是單向函數(shù)：即對(duì)給定的消息 $m$ ，計(jì)算 $h(m)$ 很容易；而對(duì)于給定的 $x$ ，不可能求出滿足 $x=h(m)$ 的 $m$ 。換句話說(shuō)，單向函數(shù)是計(jì)算容易但求逆困難的函數(shù)，單向函數(shù)也因此得名。

在散列函數(shù)的所有性質(zhì)中，最常提到的是它的抗碰撞性。一對(duì)碰撞是指兩個(gè)不同的輸入 $m_1$ 和 $m_2$ 使得 $h(m_1)=h(m_2)$ 。任意一個(gè)散列函數(shù)都會(huì)有無(wú)窮多個(gè)這樣的碰撞 (因?yàn)橛袩o(wú)限個(gè)可能輸入值，有限個(gè)可能輸出值)。因此，散列函數(shù)不可能是無(wú)碰撞的?？古鲎残允且箅m然碰撞存在，但很難被找到。

7.2 實(shí)際的散列函數(shù)

好的散列函數(shù)并不多。目前主要從 SHA 系統(tǒng)中選擇：SHA-1、SHA-224、SHA-256 和 SHA-512。當(dāng)然，還有 SHA-3。

幾乎所有實(shí)際使用的散列函數(shù)都是迭代的散列函數(shù)，這里我們也只討論這一類的散列函數(shù)。迭代的散列函數(shù)首先將輸入分成固定長(zhǎng)度的分組序列 $m_1,...,m_k$ ，最后一個(gè)分組要進(jìn)行填充以使其達(dá)到固定的長(zhǎng)度，分組的長(zhǎng)度一般為 512 位，最后一個(gè)分組通常包含一個(gè)表示輸入長(zhǎng)度的位串。然后使用一個(gè)壓縮函數(shù)和固定大小的中間狀態(tài)對(duì)這些消息分組按順序進(jìn)行處理，這個(gè)過(guò)程由固定的值 $H_0$ 開(kāi)始，隨后計(jì)算 $H_i=h'(H_{i-1},m_i)$ ，最后一個(gè)值 $H_k$ 便為散列函數(shù)的輸出。

散列函數(shù)的這種迭代設(shè)計(jì)有應(yīng)用上的優(yōu)勢(shì)。首先，與直接處理可變長(zhǎng)度的位輸入相比，這樣的迭代運(yùn)算易于規(guī)定和實(shí)現(xiàn)；其次，這種結(jié)構(gòu)使得我們可以在得到消息的第一部分時(shí)就開(kāi)始計(jì)算，在實(shí)際應(yīng)用中對(duì)一個(gè)數(shù)據(jù)計(jì)算散列值時(shí)，可以實(shí)時(shí)地進(jìn)行散列，而無(wú)須存儲(chǔ)這些數(shù)據(jù)。

7.2.1 一種簡(jiǎn)單但不安全的散列函數(shù)

在討論實(shí)際使用的散列函數(shù)之前，以一個(gè)不安全的迭代散列函數(shù)的例子來(lái)開(kāi)始，這個(gè)例子會(huì)幫助該讀者理解針對(duì)散列函數(shù)的通用攻擊的定義。該散列函數(shù)基于 256 位密鑰的 AES 算法來(lái)構(gòu)造，將 256 位密鑰 $K$ 設(shè)定為全 0。如果對(duì)消息 $m$ 進(jìn)行散列運(yùn)算，首先將消息進(jìn)行填充然后每 128 位一組分成 $k$ 個(gè)分組，分別為 $m_1,...,m_k$ 。具體的填充細(xì)節(jié)這里不詳述，也不重要。令 $H_0$ 的 128 位都為 0。然后根據(jù) $H_i=AES(H_{i-1} \bigoplus m_i)$ 進(jìn)行計(jì)算， $H_k$ 為散列函數(shù)的輸出結(jié)果。

接下來(lái)給出一種非通用攻擊。取一條消息 $m$ 經(jīng)過(guò)填充后可以分為兩個(gè)分組 $m_1$ 和 $m_2$ ，將這兩個(gè)明文分別用散列函數(shù)進(jìn)行迭代得到 $H_1$ 和 $H_2$ ， $H_2$ 也是該散列函數(shù)的輸出值。現(xiàn)在構(gòu)造消息 $m_1'=m_2 \bigoplus H_1$ 和 $m_2'=H_2 \bigoplus m_2 \bigoplus H_1$ ， $m_1'$ 和 $m_2'$ 合并構(gòu)成一段消息，進(jìn)行填充得到 $m'$ 。根據(jù)散列函數(shù)構(gòu)造的性質(zhì)可知 $m'$ 經(jīng)過(guò)散列后的結(jié)果仍然是 $H_2$ 。以較高的概率， $m$ 和 $m'$ 為不同的位串。也就是兩個(gè)不同的消息 $m$ 和 $m'$ 的散列值相同，即產(chǎn)生了碰撞。

證明：
$H_1 = AES(H_0 \bigoplus m_1) = AES(m_1)$

$H_2 = AES(H_1 \bigoplus m_2)$

$H_1' = AES(H_0 \bigoplus m_1') = AES(m_1') = AES(m_2 \bigoplus H_1)$

$H_2' = AES(H_1' \bigoplus m_2')$

$= AES(AES(m_2 \bigoplus H_1) \bigoplus (H_2 \bigoplus m_2 \bigoplus H_1))$

$= AES(AES(H_2))$

$= H_2$

也就是說(shuō)，這個(gè)證明需要 $K = 0, H_0 = 0$ 。那這個(gè)前提條件也太特殊了？

7.2.2 MD5

MD5 是由 Ron Rivest 設(shè)計(jì)的一個(gè) 128 位的散列函數(shù)。MD5 在 MD4 的基礎(chǔ)上強(qiáng)化了抗攻擊能力，MD4 的運(yùn)算非?？?，但是非常脆弱。現(xiàn)在也同樣發(fā)現(xiàn)了 MD5 的弱點(diǎn)，但是，MD5 仍然應(yīng)用于很多實(shí)際系統(tǒng)中。

計(jì)算 MD5 的第一步是將消息分為 512 位的序列分組，對(duì)最后一個(gè)分組要進(jìn)行填充，消息的長(zhǎng)度信息也在其中。MD5 有 128 位的狀態(tài)變量，它們被分為 4 個(gè) 32 位的字。壓縮函數(shù) $h'$ 共有 4 輪，在每一輪中，消息分組和狀態(tài)變量進(jìn)行混合，這種混合運(yùn)算由 32 位的字上的加法、異或、與、或、輪轉(zhuǎn)運(yùn)算組合而成。每一輪中將整個(gè)消息分組都混合在狀態(tài)變量中，因此每個(gè)消息字都使用了 4 次。在 4 輪的壓縮 $h'$ 完成之后，將結(jié)果與輸入狀態(tài)相加得到 $h'$ 的輸出。

這種在 32 位字上運(yùn)算的結(jié)構(gòu)在 32 位 CPU 的機(jī)器上特別有效，這種結(jié)構(gòu)首先由 MD4 采用，現(xiàn)已成為很多密碼學(xué)原主的一個(gè)基本特性。

對(duì)于大多數(shù)應(yīng)用來(lái)說(shuō)，MD5 的 128 位散列長(zhǎng)度是不夠的。由生日悖論可知，對(duì) 128 位散列函數(shù)大約進(jìn)行 $2^{64}$ 次計(jì)算就可以找到一個(gè)碰撞。這也就是說(shuō)通過(guò) $2^{64}$ 個(gè) MD5 的計(jì)算就可以發(fā)現(xiàn)碰撞，這對(duì)現(xiàn)在的密碼系統(tǒng)來(lái)說(shuō)是不夠的。

MD5 算法的問(wèn)題還更糟。MD5 的內(nèi)部結(jié)構(gòu)設(shè)計(jì)也會(huì)使很多更有效的攻擊成為可能。迭代散列函數(shù)設(shè)計(jì)背后的基本思想之一是如果 $h'$ 是抗碰撞的，那么由 $h'$ 所構(gòu)成的散列函數(shù) $h$ 也是抗碰撞的。也就是說(shuō)， $h$ 中的任何碰撞都是由迭代函數(shù) $h'$ 的碰撞所導(dǎo)致的。這些年來(lái) MD5 算法的迭代壓縮函數(shù) $h'$ 已經(jīng)被證明可以產(chǎn)生碰撞，雖然 $h'$ 的碰撞不能完全意味著是 MD5 算法的碰撞。但最近的密碼分析進(jìn)展表明 (由 Wang 和 Yu 的工作突破) 已經(jīng)可以通過(guò)少于 $2^{64}$ 步的計(jì)算找到針對(duì) MD5 算法的碰撞。雖然這種攻擊并不能攻破 MD5 算法的所有用法，但是可以說(shuō) MD5 是脆弱的，因此不宜再使用了。

7.2.3 SHA-1

安全散列算法由 NSA 設(shè)計(jì)并由 NIST 進(jìn)行標(biāo)準(zhǔn)化。最早的版本被稱為 SHA (現(xiàn)稱為 SHA-0)，這個(gè)算法有一個(gè)缺陷，NSA 發(fā)現(xiàn)并修復(fù)了這個(gè)缺陷，NIST 公布了改進(jìn)后的版本，稱為 SHA-1。

SHA-1 是 160 位的散列函數(shù)，與 MD5 一樣也是基于 MD4 的，因此與 MD5 有很多共同的特性，但它的設(shè)計(jì)更加保守，要慢于 MD5。盡管如此，SHA-1 算法仍然是不安全的。

SHA-1 算法的每一個(gè) 160 位的狀態(tài)是由 5 個(gè) 32 位的字組成。與 MD5 算法類似，SHA-1 算法總共也有 4 輪，每一輪都由定義在 32 位字長(zhǎng)上的基本運(yùn)算混合而成。所不同的是，MD5 對(duì)每個(gè)消息分組進(jìn)行 4 次處理，而 SHA-1 用線性遞歸的方法將 16 個(gè)字長(zhǎng)的消息分組擴(kuò)展為它所需要的 80 個(gè)字長(zhǎng)。這是對(duì) MD4 技術(shù)的一種推廣。在 MD5 中，消息的每一位在混合函數(shù)中都被使用 4 次，而 SHA-1 的線性遞歸保證了消息的每一位都至少影響混合函數(shù) 12 次。有趣的是，從 SHA-0 到 SHA-1 的唯一改變是對(duì)線性遞歸增加了 1 位的輪轉(zhuǎn)。

SHA-1 的主要問(wèn)題不是內(nèi)部缺陷，而是輸出為 160 位的長(zhǎng)度。進(jìn)行 $2^{80}$ 步運(yùn)算就可以使用 160 位的散列函數(shù)產(chǎn)生碰撞，這個(gè)安全等級(jí)低于我們對(duì)于分組密碼密鑰長(zhǎng)度為 128 ~ 256 位的要求，當(dāng)然也不符合對(duì)于分組密碼 128 位的設(shè)計(jì)安全等級(jí)。雖然進(jìn)行 SHA-1 運(yùn)算要比 MD5 花費(fèi)更多的時(shí)間，但是已經(jīng)可以證明采用少于 $2^{80}$ 步的運(yùn)算就可以使用 SHA-1 產(chǎn)生碰撞。

3.3 SHA-2

在 2001 年，NIST 公共的標(biāo)準(zhǔn)草案包含了 3 個(gè)新的散列函數(shù)，后于 2004 年又修訂了該規(guī)范，增加了一個(gè)新的散列函數(shù)。這些散列函數(shù)都屬于 SHA-2 系統(tǒng)，分別有 224 位、256 位、384 位、512 位的輸出，設(shè)計(jì)用于與密鑰長(zhǎng)度為 128 位、192 位、256 位的 AES 算法以及 112 位的 3DES 算法一起使用。這些算法的結(jié)構(gòu)與 SHA-1 非常類似。

SHA-256 比 SHA-1 慢得多。

有一些針對(duì) SHA-2 系列迭代散列函數(shù)其他缺陷的修復(fù)方案：截?cái)噍敵?。如果散列函?shù)是 $n$ 位輸出，那么只取其前面的 $n->s$ ( $s$ 為某個(gè)正整數(shù)) 作為散列值。事實(shí)上，SHA-224 和 SHA-384 算法都是如此設(shè)計(jì)的，SHA-224 是將 SHA-256 丟棄了 32 位輸出，而 SHA-384 是將 SHA-512 丟棄了 128 位位輸出。為了滿足 128 位的安全要求，需要采用 SHA-512 算法，然后丟棄 256 位輸出，返回剩余的 256 位作為截?cái)嗌⒘泻瘮?shù)的輸出結(jié)果。由于生日攻擊，這個(gè) 256 位的散列函數(shù)可以滿足 128 位的安全性設(shè)計(jì)目標(biāo)。

3.4 SHA-3

項(xiàng)目源代碼

項(xiàng)目源代碼會(huì)逐步上傳到 Github，地址為 https://github.com/windstamp。

Contributor

Windstamp, https://github.com/windstamp

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

7. 密碼學(xué)專題 - 單向散列函數(shù)

7. 密碼學(xué)專題 - 單向散列函數(shù)

密碼學(xué)專題 - 單向散列函數(shù)

7.1 散列函數(shù)的安全性