下载文档原格式
![第6章[第2部分]杂凑函数](https://img.taocdn.com/s1/m/56fc23eae009581b6bd9ebb9.png)
杂凑函数散列函数一、杂凑函数杂凑函数是一种将任意长度的输入数据（也称为关键字）转换为固定长度的输出数据的方法。
输出数据的长度通常被称为散列值的位数。
由于杂凑函数在处理大量数据时，可以将数据分布到固定长度的散列表中，因此它们在密码学、数据压缩、数据存储等领域得到了广泛应用。
1. 杂凑函数的原理杂凑函数的基本原理是将输入数据通过一系列复杂的数学运算，生成一个散列值。
这些数学运算通常包括哈希函数、压缩函数、置换函数等。
杂凑函数的输出结果应该是散列值，而不是具体的数据，因此其输出结果通常无法直接与输入数据建立一一对应的关系。
2. 杂凑函数的性能指标性能指标主要包括散列值的位数、碰撞率、负载因子等。
散列值的位数决定了输出的散列值可以表示的长度，对于某些应用来说，过短的位数可能会导致数据无法有效存储或检索。
碰撞率是指两个不同的输入数据生成相同散列值的情况，负载因子则是指散列表中存储的键值对数量与散列表容量的比值。
3. 常见杂凑函数算法常见的杂凑函数算法包括MD5、SHA-1、SHA-256等。
这些算法均采用了特定的数学运算方法，如乘法、位移、异或等操作，生成散列值。
此外，这些算法通常还提供了碰撞检测机制，以保证输出的散列值是唯一的。
二、散列函数散列函数是一种将任意长度的数据转换为固定长度的数据的函数，但与杂凑函数不同的是，散列函数通常要求在已知输出结果的情况下，能够通过输入数据重新得到输出结果，而不需要进行其他复杂的数学运算。
散列函数在密码学中具有重要的应用价值，例如哈希链的构建、数字签名等。
1. 散列函数的性能指标散列函数的性能指标主要包括碰撞率、单向性、计算复杂度等。
碰撞率是指两个不同的输入数据产生相同散列值的情况，单向性是指无法从散列值反推出原始输入数据，计算复杂度则是指生成散列值所需的时间和空间。
2. 常见散列函数算法常见的散列函数算法包括MD4、SHA-0、SHA-3等。
这些算法在计算过程中采用了多种不同的技术手段，如特殊的哈希函数结构、位运算等操作，以实现高效的散列计算。
杂凑函数散列函数-回复什么是杂凑函数和散列函数？它们有什么不同之处？在现实生活中，我们如何使用它们来保障数据的安全性和完整性？杂凑函数和散列函数是密码学中常用的两种概念。
杂凑函数，也被称为哈希函数，是一种将任意长度的输入映射成固定长度输出的函数。
而散列函数，是一种将输入按特定规则转换为固定长度输出的函数。
虽然它们在概念上类似，但在一些细节上有所不同。
一、杂凑函数杂凑函数的作用是将任意长度的输入转换为固定长度的输出，常见的输出长度有128位、256位等。
它的一大特点是，对于相同的输入，输出的结果也是相同的。
即使输入中只有最小的改动，输出结果也会发生很大的变化。
这使得杂凑函数在数据完整性验证、密码校验等方面具有重要的作用。
杂凑函数的设计要求具备以下特性：1. 独特性：每个不同的输入应产生唯一的输出，确保了数据的独一性。
2. 不可逆性：根据输出结果无法逆推出原始输入，保护了数据的安全性。
3. 雪崩效应：即原始输入的微小变动会引起输出结果的巨大变化。
在实际应用中，杂凑函数常被用于密码校验、数字签名、数据完整性验证等场景。
比如，我们常见的MD5、SHA-1、SHA-256等算法就是用于生成杂凑值的算法。
在密码校验中，系统会将用户输入的密码与预存储的密码进行杂凑计算，对比其结果是否一致，从而判断用户密码是否正确。
二、散列函数散列函数也是一种将输入映射成固定长度的输出，但与杂凑函数相比，散列函数更注重将输入分散在输出空间中，以减少冲突。
假设输入空间为无限大，而输出空间为有限大，散列函数的目标是尽可能均匀地将输入分布到输出空间，以避免碰撞。
散列函数的设计要求具备以下特性：1. 均匀性：将输入映射到输出空间中的每个值的概率相等。
2. 易计算性：计算散列函数的时间复杂度应该尽可能低，以提高效率。
3. 隐蔽性：根据输出结果无法推断出输入的信息，保护了数据的安全性。
在实际应用中，散列函数常被用于数据存储和查找。
比如，哈希表（Hash Table）是一种常见的数据结构，它使用散列函数将键映射为对应的数值，以实现高效的数据存储和查找。
杂凑函数（散列函数）1. 定义杂凑函数（Hash Function），也称为散列函数，是一种将任意大小的数据映射到固定大小的数据的函数。
它将输入数据通过一系列的计算操作，转换成一个固定长度的输出，通常称为散列值或哈希值。
杂凑函数是密码学、数据完整性校验、数据索引等领域中重要的基础工具。
2. 用途杂凑函数有广泛的应用，主要包括以下几个方面：2.1 数据完整性校验杂凑函数可以用于验证数据的完整性，即通过计算数据的散列值，然后与预先保存的正确散列值进行比对，来判断数据是否被篡改。
这在网络传输、文件存储等场景中非常重要，可以有效防止数据被篡改而不被察觉。
2.2 数据唯一标识杂凑函数可以将数据映射为唯一的散列值。
由于散列值的长度固定，可以大大减小数据的存储空间。
在数据索引、数据库中，可以使用散列值作为数据的唯一标识，提高数据的查询和存储效率。
2.3 密码学杂凑函数在密码学中有重要的应用。
比如，密码存储时通常不会直接保存明文密码，而是将密码的散列值保存在数据库中。
当用户登录时，输入的密码经过散列计算后与数据库中的散列值进行比对，以验证用户的身份。
2.4 数据分片杂凑函数可以将数据按照一定的规则进行分片，将大规模数据分散存储在不同的节点上。
这样可以提高数据的并行处理能力和分布式存储系统的可扩展性。
3. 工作方式杂凑函数的工作方式主要包括两个方面：输入处理和输出生成。
3.1 输入处理杂凑函数接受一个任意长度的输入数据，并经过一系列的计算操作将其转换为固定长度的中间结果。
常见的输入处理操作包括：•消息扩展：将输入数据进行填充，使其长度满足计算要求。
常见的填充方式有补零、补位数等。
•消息分块：将输入数据按照固定长度进行划分，得到多个块。
每个块独立处理，可以提高计算效率。
•迭代计算：对每个数据块进行迭代计算，将当前数据块的计算结果作为下一个数据块的输入，直到处理完所有数据块。
3.2 输出生成经过输入处理后，杂凑函数会生成一个固定长度的输出，即散列值或哈希值。
第 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運算。
