第3章單向散列函數(shù)3.1MD5算法3.2安全散列函數(shù)(SHA)3.3消息認(rèn)證碼(MAC)參考文獻(xiàn)思考題

在很多情況下，我們需要鑒別和認(rèn)證用戶。如用戶登錄計(jì)算機(jī)(或自動(dòng)柜員機(jī)等)時(shí)，計(jì)算機(jī)往往需要知道用戶是誰(shuí)，確認(rèn)是某個(gè)用戶而不是其他人在冒充，傳統(tǒng)的方法是用口令來(lái)解決這個(gè)問(wèn)題。用戶在登錄計(jì)算機(jī)前輸入其口令，由計(jì)算機(jī)確認(rèn)口令正確后用戶才可登錄計(jì)算機(jī)。用戶和計(jì)算機(jī)均知道口令。用戶每次登錄均需輸入口令。由于計(jì)算機(jī)需要知道口令，這就需要把口令保存在計(jì)算機(jī)中。這為入侵計(jì)算機(jī)偷取口令提供了可能。為此，我們不直接保存口令本身，而保存口令的散列值(口令的某種表示形式)。

當(dāng)用戶輸入口令后，計(jì)算機(jī)先計(jì)算口令的散列值并與保存在計(jì)算機(jī)中的散列值進(jìn)行比較，以此來(lái)鑒別用戶。由于用來(lái)計(jì)算散列值的單向函數(shù)具有單向性，即根據(jù)散列值不可能逆向恢復(fù)出口令，從而即使獲得了由口令產(chǎn)生的散列值表也無(wú)法知道用戶的口令。

上面提到的散列值是由單向散列函數(shù)產(chǎn)生的。所謂的單向散列函數(shù)(哈希函數(shù)、雜湊函數(shù)，hashfunction)是將任意長(zhǎng)度的消息M映射成一個(gè)固定長(zhǎng)度散列值h的函數(shù)

h?=?H(M)

其中，h的長(zhǎng)度為m。

散列函數(shù)要具有單向性，則必須滿足如下特性：

(1)給定M，很容易計(jì)算h。

(2)給定h，根據(jù)H(M)?=?h反推M很難。

(3)給定M，要找到另一消息M′?并滿足H(M)?=?H(M′)很難。

在某些應(yīng)用中，單向散列函數(shù)還需要滿足抗碰撞(collision)的條件：要找到兩個(gè)隨機(jī)的消息M和M′，使H(M)?=?H(M′)滿足很難。

在實(shí)際中，單向散列函數(shù)是建立在壓縮函數(shù)的想法之上，如圖3-1所示。圖3-1HASH函數(shù)工作模式

給定一任意長(zhǎng)度的消息輸入，單向函數(shù)輸出長(zhǎng)為m的散列值。壓縮函數(shù)的輸入是消息分組和前一分組的輸出(對(duì)第一個(gè)壓縮函數(shù)，其輸入為消息分組1和初始化向量IV)；輸出是到該點(diǎn)的所有分組的散列，即分組Mi的散列為

hi?=?f(Mi，hi-1)

該散列值和下一輪的消息分組一起作為壓縮函數(shù)下一輪的輸入。最后一分組的散列就是整個(gè)消息的散列。

單向散列函數(shù)還經(jīng)常用于消息認(rèn)證(防篡改)、數(shù)字簽名。本章將介紹幾種常用的單向散列函數(shù)。

3.1MD5算法

3.1.1算法MD表示消息摘要(MessageDigest)。MD5是MD4的改進(jìn)版，算法對(duì)輸入的任意長(zhǎng)度消息產(chǎn)生128位散列值(或消息摘要)。MD5算法可由圖3-2表示。由圖3-2可知，MD5算法包括以下5個(gè)步驟。圖3-2MD5算法

1．附加填充位

首先填充消息使其長(zhǎng)度為一個(gè)比512的倍數(shù)小64位的數(shù)。填充方法是：在消息后面填充一位1，然后填充所需數(shù)量的0。填充位的位數(shù)從1～512。

2．附加長(zhǎng)度

將原消息長(zhǎng)度的64位表示附加在填充后的消息后面。當(dāng)原消息長(zhǎng)度達(dá)大于264時(shí)，用(消息長(zhǎng)度mod264)填充。這時(shí)消息長(zhǎng)度恰好是512的整數(shù)倍。令M[01…N-1]為填充后消息的各個(gè)字(每字M[i]為32位)，N是16的倍數(shù)。

3．初始化MD緩沖區(qū)

初始化用于計(jì)算消息摘要的128位緩沖區(qū)。這個(gè)緩沖區(qū)由4個(gè)32位寄存器A、B、C、D表示。寄存器的初始化值為(按低位字節(jié)在前的順序存放)：

4．按512位的分組處理輸入消息

這一步為MD5的主循環(huán)，包括四輪，如圖3-3所示。每個(gè)循環(huán)都以當(dāng)前的正在處理的512比特分組Yq和128比特緩沖值A(chǔ)BCD為輸入，然后更新緩沖內(nèi)容。圖3-3單個(gè)512比特分組的MD5主循環(huán)處理

圖3-3中，四輪的操作類似，每一輪進(jìn)行16次操作。每一輪的操作過(guò)程如圖3-4所示。圖3-4MD5某一輪的執(zhí)行過(guò)程

四輪操作的不同之處在于每輪使用的非線性函數(shù)不同，在第一輪操作之前首先把A、B、C、D復(fù)制到另外的變量a、b、c、d中。這四個(gè)非線性函數(shù)分別為(其輸入輸出均為32位字)

其中，∧表示按位與；表示按位或；～表示按位反；⊕表示按位異或。

此外，由圖3-4可知，這一步中還用到了一個(gè)有64個(gè)元素的表T[1…64]，T[i]?=?232?×?abs(sin(i))，i的單位為弧度。

根據(jù)以上描述，將這一步驟的處理過(guò)程歸納如下：

5．輸出

由A、B、C、D四個(gè)寄存器的輸出按低位字節(jié)在前的順序(即以A的低字節(jié)開(kāi)始、D的高字節(jié)結(jié)束)得到128位的消息摘要。

以上就是對(duì)MD5算法的描述。MD5算法的運(yùn)算均為基本運(yùn)算，比較容易實(shí)現(xiàn)且速度很快。

3.1.2舉例

在本章的參考文獻(xiàn)[1]中，給出了實(shí)現(xiàn)MD5的C源代碼。我們以求字符串“abc”的MD5散列值為例來(lái)說(shuō)明上面描述的過(guò)程。“abc”的二進(jìn)制表示為011000010110001001100011。

(1)填充消息：消息長(zhǎng)l=24，先填充1位‘1’，然后填充423位‘0’，再用消息長(zhǎng)，24，即0x0000000000000018填充。則

(2)初始化：

(3)主循環(huán)：利用2.1.1中描述的過(guò)程對(duì)字塊1(本例只有一個(gè)字塊)進(jìn)行處理。變量a、b、c、d每一次計(jì)算后的中間值可根據(jù)參考文獻(xiàn)[1]提供的C源代碼得到，這里不詳細(xì)列出。

(4)輸出：消息摘要=900150983cd24fb0d6963f7d28e17f72

3.2安全散列函數(shù)(SHA)

3.2.1算法SHA是美國(guó)NIST和NSA共同設(shè)計(jì)的安全散列算法(SecureHashAlgorithm)，用于數(shù)字簽名標(biāo)準(zhǔn)DSS(DigitalSignatureStandard)。SHA的修改版SHA-1于1995年作為美國(guó)聯(lián)邦信息處理標(biāo)準(zhǔn)公告(FIPSPUB180-1)發(fā)布[2]。SHA-1產(chǎn)生消息摘要的過(guò)程類似MD5，如圖3-5所示。SHA-1的輸入為長(zhǎng)度小于264位的消息，輸出為160位的消息摘要。具體過(guò)程如下。圖3-5SHA-1算法

1．填充消息

首先將消息填充為512位的整數(shù)倍，填充方法和MD5完全相同：先填充一個(gè)1，然后填充一定數(shù)量的0使其長(zhǎng)度比512的倍數(shù)少64位；接下來(lái)用原消息長(zhǎng)度的64位表示填充。這樣，消息長(zhǎng)度就成為512的整數(shù)倍。以M0、M1、…、Mn表示填充后消息的各個(gè)字塊(每字塊為16個(gè)32位字)。

2．初始化緩沖區(qū)

在運(yùn)算過(guò)程中，SHA要用到兩個(gè)緩沖區(qū)，兩個(gè)緩沖區(qū)均有5個(gè)32位的寄存器。第一個(gè)緩沖區(qū)標(biāo)記為A、B、C、D、E；第二個(gè)緩沖區(qū)標(biāo)記為H0、H1、H2、H3、H4。此外，運(yùn)算過(guò)程中還用到一個(gè)標(biāo)記為W0、W1、…、W79的80個(gè)32位字序列和一個(gè)單字的緩沖區(qū)TEMP。在運(yùn)算之前，初始化{Hj}：

3．按512位的分組處理輸入消息

SHA運(yùn)算主循環(huán)包括4輪，每輪20次操作。SHA用到一個(gè)邏輯函數(shù)序列f0、f1、…、f79。每個(gè)邏輯函數(shù)的輸入為3個(gè)32位字，輸出為一個(gè)32位字。定義如下(B、C、D均為32位字)：

其中運(yùn)算符的定義與3.1節(jié)中MD5運(yùn)算中的相同。

SHA運(yùn)算中還用到了常數(shù)字序列K0、K1、…、K79，其值為：

SHA算法按如下步驟處理每個(gè)字塊Mi：

4．輸出

在處理完Mn后，160位的消息摘要為H0、H1、H2、H3、H4級(jí)聯(lián)的結(jié)果。

3.2.2SHA-1與MD5的比較

SHA-1與MD5的比較如表3-1所示。

3.2.3舉例

我們以求字符串“abc”的SHA-1散列值為例來(lái)說(shuō)明上面描述的過(guò)程?！癮bc”的二進(jìn)制表示為011000010110001001100011。

(1)填充消息：消息長(zhǎng)l?=?24，先填充1位‘1’，然后填充423位‘0’，再用消息長(zhǎng)24即0x0000000000000018填充。

(2)初始化：

(3)主循環(huán)：處理消息字塊1(本例中只有1個(gè)字塊)，分成16個(gè)字：

然后根據(jù)3.2.1節(jié)中描述的過(guò)程計(jì)算，其中循環(huán)“fort=0to79”中，各步A、B、C、D、E的值如下：

3.3消息認(rèn)證碼(MAC)

與密鑰相關(guān)的單向散列函數(shù)通常稱為MAC，即消息認(rèn)證碼MAC?=?CK(M)其中，M為可變長(zhǎng)的消息；K為通信雙方共享的密鑰，C為單向函數(shù)。

MAC可為擁有共享密鑰的雙方在通信中驗(yàn)證消息的完整性；也可被單個(gè)用戶用來(lái)驗(yàn)證他的文件是否被改動(dòng)。如圖3-6所示。圖3-6MAC應(yīng)用于消息認(rèn)證

HMAC全稱為keyed-hashmessageauthenticationcode，它用一個(gè)秘密密鑰來(lái)產(chǎn)生和驗(yàn)證MAC[3]。

為了論述的方便，首先給出HMAC中用到的參數(shù)和符號(hào)如下。

B：計(jì)算消息摘要時(shí)輸入塊的字節(jié)長(zhǎng)度(如對(duì)于SHA-1，B=64)。

H：散列函數(shù)如SHA-1、MD5等。

ipad：將數(shù)值0x36重復(fù)B次。

opad：將數(shù)值0x5c重復(fù)B次。

K：共享密鑰。

K0：在密鑰K的左邊附加0使其為B字節(jié)的密鑰。

L：消息摘要的字節(jié)長(zhǎng)度(如對(duì)于SHA-1，L=20)。

t：MAC的字節(jié)數(shù)。

TEXT：要計(jì)算HMAC的數(shù)據(jù)。數(shù)據(jù)長(zhǎng)度為n字節(jié)，n的最大值依賴于采用的hash函數(shù)。

X||Y：將字串連接起來(lái)，即把字串Y附加在字串X后面。

異或。

密鑰K的長(zhǎng)度應(yīng)大于或等于L/2。當(dāng)使用長(zhǎng)度大于B的密鑰時(shí)，先用H對(duì)密鑰求得散列值，然后用得到的L字節(jié)結(jié)果作為真正的密鑰。

利用HMAC函數(shù)計(jì)算數(shù)據(jù)text的MAC過(guò)程如圖3-7所示。圖3-7HMAC

由圖可知，HMAC執(zhí)行的是如下操作：

HMAC算法可以和任何密碼散列函數(shù)結(jié)合使用，而且對(duì)HMAC實(shí)現(xiàn)作很小的修改就可用一個(gè)散列函數(shù)H代替原來(lái)的散列函數(shù)H′。

參考文獻(xiàn)

[1]RRivest.TheMD5Message-DigestAlgorithm.RFC1321，April1992[2]NationalInstituteofStandardsandTechnology，F(xiàn)IPSPUB180-1.SecureHashStandard.U.S.DepartmentofCommerce，April1995

[3]NationalInstituteofStandardsandTechnology，F(xiàn)IPSPUB#HMAC.TheKeyed-HashMessageAuthenticationCode(HMAC).U.S.DepartmentofCommerce，DRAFT，2001

[4]MihirBellare，RanCanetti，HugoKrawczyk.MessageAuthenticationusingHashFunctions－TheHMACConstruction.RSALaboratoriesCryptoBytes，Vol.2，No.1，Spring1996

思考題

[1]概述MD4和MD5各自的優(yōu)缺點(diǎn)。[2]假定a1a2a3a4是一個(gè)32比特字中