第 6 章單向雜湊函數密碼學上的雜湊函數（Cryptographic Hash Function），為一種可以將任意長本文由【中文word文档库】搜集整理。

中文word文档库免费提供海量教学资料、行业资料、范文模板、应用文书、考试学习和社会经济等word文档度的輸入訊息加以濃縮、轉換，成為一相當短的固定長度輸出訊息的函數，此一輸出訊息一般稱為文件摘要（Message Digest）或雜湊值（Hash Value）。

設計或使用雜湊函數於密碼學系統上的主因是因為利用公開金鑰密碼系統簽章時，因其運算速度較慢，若對整份文件加以簽章則效率不彰。

因此加以變通，使用由該文件經過雜湊函數運算所產生之長度較短，但足以區別該文件的文件摘要（Message Digest），或稱文件的數位指紋（Digital Fingerprint），來加以簽章，取代原先對整份文件簽章的方式，以加速數位簽章的應用。

雜湊函數與加密演算法一樣，均是將訊息加以隱藏。

但其不同點在於加密演算法的結果可以藉由適當的方式加以還原，而雜湊函數則必須具單向與不可逆（One-Way）的特性。

因此使得給定文件時，順向計算該文件的雜湊值相單簡單快速，但經過雜湊函數濃縮、運算後的文件摘要，無法反向還原成先前的訊息。

密碼學中所使用的單向雜湊函數（One-Way Hash Function）必須具備以下兩個特性：1.當給定一特定的雜湊輸出值後，欲找出任何文件可以輸出此一特定的雜湊值，為計算上的不可行，此為抗拒事先描繪的特性（PreimageResistance）。

2.即使給定一份文件及其雜湊值後，找出第二份文件可以輸出此一特定的雜湊值，為計算上的不可行，此為抗拒第二事先描繪的特性（Second Preimage Resistance）。

一個單向雜湊函數必須利用有限的資料量（通常為128或160位元）來區別所有文件，必定存在兩份以上的文件具有相同的雜湊值，此即碰撞、衝突或重複（Collision）的現象。

因此，一個可以抗拒碰撞（Collision-Resistance）的單向雜湊函數條件更為嚴苛，除了上述兩條件外，必須使得攻擊者欲找出兩份不相同的文件具有相同的雜湊值，為計算上的不可行。

理想中，一個長度為n位元的文件摘要，應可區別n2份文件，但在生日攻2n，亦擊法（Birthday Attack）的威脅下，已使得此一文件數量大幅減少成為2/2份文件，換言即輸出長度為128位元（16位元組）的文件摘要函數只能區別64之，攻擊者即使利用地毯式搜尋（Brute-force Attack），在最壞的情況下也只要經2次運算，即可找出具有相同文件摘要的兩份文件，由此看來，有必要將訊過64息彙記的輸出長度提升至160位元（10位元組）以上。

大部分的單向雜湊函數或訊息彙記函數之設計理念均極類似，均以固定長度的區塊處理來運作。

先將輸入訊息後端不足區塊長度的部份，加以填補（Padding）成為一完整長度的區塊，再利用一個壓縮函數（Compress Function），反複地將兩個固定長度的區塊訊息資料利用壓縮（Compress）、邏輯轉換（AND，NOT，OR，XOR）及旋轉移位（Rotate or Cycle Shift）等處理，產生一個單一的結果，稱為鏈結變數（Chaining Variable），作為下一回合的輸入值，並反覆使用上述壓縮函數至訊息處理完畢為止，其最後的壓縮函數值即為文件摘要，請參考下圖之說明。

圖6-1 文件彙記產生示意圖常見的單向雜湊函數有RSA公司MD家族之MD2、MD4、MD5，美國國家標準與技術協會（National Institute of Science and Technology，NIST）的SHA、SHA-1、與歐盟（European Union）RIPE專案之RIPEMD、RIPEMD -128、RIPEMD -160等，在以下各個小節我們將分別介紹這些單向雜湊函數。

6.1 MD 家族RSA公司之MD家族包括了MD2、MD4及MD5，都是由設計RSA公開金鑰密碼系統的三位發明人（Rivest、Shamir、Adleman）其中的Rivest所設計發展的，此三個文件摘要函數的內部結構大致相同，均可將任意長度的訊息轉換輸出為128位元的文件摘要，其中MD2是針對8位元的環境予以最佳化，MD4與MD5則是充份利用32位元的環境予以最佳化。

6.1.1 MD2MD2由Rivest發展於1989年，其運作方式如下：[Kaliski92]1.將輸入訊息填補成16位元組（128位元）長區塊的整數倍大小。

2.利用基於圓周率（π）的非線性轉換，計算出一個核對總和值（Checksum）附加於其後。

3.將上述訊息切割為16位元組長的區塊，配合一個固定的初始值，反覆計算其函數值，產生一個16位元組（128位元）的文件摘要。

目前已經可以找出其壓縮函數的“碰撞”，且在省略核對總和值的條件下，更可以找到兩份具有相同訊息彙記的文件。

也就是說，若無核對總和值的幫助，MD2安全強度已經不足。

6.1.2 MD4MD4由Rivest發展於1990年，其運作方式亦與MD2相似，不同的是MD4在輸入的訊息上添加了一個64位元的資料，用以表示輸入訊息的長度，並變更其處理區塊大小為512位元，且此512位元長的資料區塊在壓縮處理上，也必須經過三個回合（Round）的不同處理，其填補訊息的長度亦也與MD2有所不同[Rivest90，Rivest92a，Stinson95]。

而MD5、SHA-1、RIPEMD均以MD4為設計基礎，加以修改發展而成。

德國的Dobbertin，在1995年證明，使用一部普通PC，在一分鐘內即可找到一個MD4的碰撞。

因此，MD4的安全強度也已經不足。

6.1.3 MD5MD5由Rivest發展於1991年，可以說是MD4的加強安全版，比MD4稍慢，除了將壓縮處理過程從MD4的三個回合，增加為四個回合外，其餘均與MD4相同 [Rivest92b ，Stallings99]。

MD5目前的劣勢，在於其壓縮函數的碰撞（包括Pseudo-Collision of Compress Function 及Collision of Compress Function 兩種）已被找到。

已有論文指出，花費1000萬美金的代價（1995），設計找尋碰撞的特製硬體設備，平均可以在24天內找出一個MD5的碰撞。

因此 RSA 公司已發佈新聞指出MD2、MD4與MD5，均不再適合使用於未來的簽章應用，其所推薦適合未來簽章使用的雜湊函數為SHA-1與RIPEMD-160。

欲將文件利用MD5製作文件摘要，則文件必須先被切割為數個512位元的區塊（Block ），而MD5最終將輸出一128位元之文件摘要。

以下將簡述MD5的運作流程：1. 補齊區塊：將文件以512位元為單位切割後，若最後一個區塊長度不足448位元，則必需加入位元將之補齊至448位元；若最後一個區塊長度剛好是448位元，則加入一512位元的區塊。

因此，加入的位元範圍為1~512位元。

2. 附加長度：補齊區塊後，在最後必須添加原文件長度的資訊，此資訊長度為64位元（Least Significant Byte First ）。

若原文件長度超過642位元，則只添加較低階的64位元。

即添加的訊息為：642mod 原文件長度。

3. 初設暫存值：在MD5中有一128位元的暫存器，用以暫存經過運算的結果。

在開始製作文件摘要前，MD5會先初設暫存器。

128位元的暫存器視為四個32位元的暫存器),,,(D C B A ，初設如下：10325476988967452301====D BADCFEC EFCDAB B A 暫存器是以Little-Endian 的方式初設。

而MD5運算過程中所利用到的初值IV即為：10325476988967452301::::BA DC FE EF CD AB D C B A word word word word 4. 進行運作：經過前三個步驟後，MD5即可開始以512位元區塊為單位進行運作。

每512位元區塊經過運作後，將產生128位元的輸出。

5. 輸出結果：以初值為始，將每次輸出的128位元值相加再進行模322運算，即可獲得最後128位元的文件摘要。

圖 6-2 為MD5的運作流程：L*512位元IV圖 6-2 MD5運作示意圖在前述MD5運作流程中，步驟四是以512位元區塊為單位進行運算，本段將簡介此運算過程。

512位元區塊運算共分為四回合，每回合各進行16次的單位運算。

假設目前進行第q 次的512位元區塊運算。

取此次進行區塊運算的512位元文件區塊q Y ，將其以128位元為單位分為四部份，分別輸入四個回合。

取前次512位元區塊的運算結果q CV （0CV 即為初值IV ），將其以32位元為單位分為),,,(D C B A 四部份，並將此四部份輸入第一回合。

經過第一回合共16次的單位運算後，將有),,,(D C B A 四部份共128位元的輸出。

再將此),,,(D C B A 輸入第二回合進行運算。

依此模式進行運算，直至第四回合輸出),,,(D C B A 。

將原),,,(D C B A 與),,,(D C B A 分別相加後，再分別進行模322運算，合併四部份的結果，即為最後128位元之輸出，如圖 6-3所示。

CV 1q Y : 相加後再模322 圖 6-3 MD5對512位元區塊運作圖在每次的回合運算中，都將進行16次的單元運算。

圖6-4為MD5 之基本單元運算的流程，其中的重要元件將一一說明於後。

X[k]T[i]圖6-4 MD5基本單元運作圖1.g：為運算函數F、G、H、I其中之一。

在每次512位元區塊運算中，第一回合g為運算函數F，第二回合g為運算函數G，依此類推。

現將運算函數F、G、H、I的運算功能說明如下：2運算。

2.+：相加後再進行模323.CLS：將數字進行循環位移（Circular Left Shift）共s個位元。

s4.X[k]：在每次512位元區塊運算中，文件Y以32位元為單位q分為X[0]、X[1]、…、X[63]共64份，每回合進行運算時輸入16份，即第一回合運算輸入X[0]、X[1]、…、X[15]，第一回合運算輸入X[16]、X[17]、…、X[31]等。

這也就是前文所提及的：512位元的文件區塊Y，q以128位元為單位分為四部份，分別輸入四個回合。

5.T[j]：為一32位元之值，經由查表可得。

此表是利用三角函數sin製作而成。

現將此表羅列如下：綜合前文所述，MD5的運算流程可表示如下：Lq q F q G q H q I q q CV MD CV Y RF Y RF Y RF Y RF CV SUM CV IVCV ===+))))),(,(,(,(,(3210其中，IV ：初值，q Y ：第q 個512位元的文件區塊，L ：512位元文件區塊數，q CV ：在MD5運作過程中，第q 個暫存運算值，x RF ：利用運算函式x 所進行的回合運算，MD ：MD5所產生之文件摘要，32SUM ：將兩數質相加後，再進行模322運算。