《網(wǎng)絡安全與保密》課件第3章

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

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

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

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

h?=?H(M)

其中，h的長度為m。

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

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

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

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

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

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

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

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

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

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

3.1MD5算法

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

1．附加填充位

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

2．附加長度

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

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

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

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

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

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

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

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

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

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

5．輸出

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

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

3.1.2舉例

在本章的參考文獻[1]中，給出了實現(xiàn)MD5的C源代碼。我們以求字符串“abc”的MD5散列值為例來說明上面描述的過程?！癮bc”的二進制表示為011000010110001001100011。

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

(2)初始化：

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

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

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

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

1．填充消息

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

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

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

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

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

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

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

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

4．輸出

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

3.2.2SHA-1與MD5的比較

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

3.2.3舉例

我們以求字符串“abc”的SHA-1散列值為例來說明上面描述的過程?！癮bc”的二進制表示為011000010110001001100011。

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

(2)初始化：

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

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

3.3消息認證碼(MAC)

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

MAC可為擁有共享密鑰的雙方在通信中驗證消息的完整性；也可被單個用戶用來驗證他的文件是否被改動。如圖3-6所示。圖3-6MAC應用于消息認證

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

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

B：計算消息摘要時輸入塊的字節(jié)長度(如對于SHA-1，B=64)。

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

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

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

K：共享密鑰。

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

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

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

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

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

異或。

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

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

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

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

參考文獻

[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)缺點。[2]假定a1a2a3a4是一個32比特字中