散列函數與數字簽名第一頁，共四十八頁，2022年，8月28日2023/2/25第五章散列函數與數字簽名5.1概述5.2消息摘要5.3消息認證5.4數字簽名5.5小結2第二頁，共四十八頁，2022年，8月28日5.1概述——消息摘要消息摘要（消息的數字指紋）是數字簽名體系中實現信息完整性保障的技術。消息摘要的工作原理：將消息作為Hash函數的輸入數據，生成定長的輸出數據（即消息摘要），并將其作為消息的附加信息。Hash函數有兩個基本特性：輸入數據的任何細微變化將導致輸出數據的巨大改變難以進行逆運算利用這兩個特性，消息接收方根據消息摘要能驗證收到的消息在傳輸過程中是否發生了改變，從而驗證了消息的完整性和有效性。2023/2/253第三頁，共四十八頁，2022年，8月28日5.1概述——公開密鑰技術公開密鑰技術是數字簽名體系中進行身份認證和保障不可抵賴性的主要技術。在公鑰加密技術中，利用發送者A的私鑰加密的信息只有用發送者A的公鑰才能解密。在A的私鑰沒有泄露的情況下，如果一個經某私鑰加密的信息能被A的公鑰解密，那么就說明該私鑰屬于A，從而可以確定該信息是由A發出的。（A無法抵賴）同理，別人也無法冒充A發送信息，因為他沒有A的私鑰。2023/2/254第四頁，共四十八頁，2022年，8月28日2023/2/255.1概述——數字簽名信息完整性和不可抵賴性是信息安全的兩個基本要素。數字簽名技術通過結合消息摘要技術和公開密鑰技術，保證了不可靠網絡中傳輸的信息的完整性和抗否認性。數字簽名的大致步驟發送方利用Hash函數對待發消息M進行摘要處理，生成一個固定長度的消息摘要H(M)。用自己的私鑰對該消息摘要（即一個hash值）進行加密，形成發送方的一個數字簽名。（這個數字簽名作為消息的附件隨消息一起發送到接收方。）接收方利用數字簽名中的消息摘要對消息的完整性進行判斷，利用發送方的公鑰對發送方進行身份認證和保證抗否認性。5圖5.1數字簽名過程第五頁，共四十八頁，2022年，8月28日5.2消息摘要5.2.1Hash函數的概念和原理5.2.2MD5算法5.2.3SHA-1算法5.2.4MD5和SHA-1算法的比較5.2.5HMAC算法2023/2/256第六頁，共四十八頁，2022年，8月28日2023/2/255.2消息摘要——概述在通信過程中，信息的完整性是信息安全保證的重要指標。信息完整性是指信息在存儲和傳輸過程中不被非法篡改、破壞、增刪，能真實無誤地到達目的地的特性。消息摘要是保證信息完整性的基本技術之一，Hash函數則是消息摘要技術的核心內容。目前最典型的兩個Hash算法：MD5算法和SHA-1算法。7第七頁，共四十八頁，2022年，8月28日2023/2/255.2.1Hash函數的概念Hash函數的定義把可變長度的輸入數據轉換成固定長度的輸出數據的一種函數。這個定長的輸出數據稱為輸入數據的消息摘要，也稱為散列值、哈希值或數字指紋。Hash函數具有單向性指從輸入數據很容易計算其Hash值，但通過Hash值想找到其對應的輸入數據是很困難的。也就是說，要找到一個輸入數據使其Hash值等于一個特定值是很困難的。一個好的Hash函數也是無碰撞的即很難產生兩個輸入數據，使它們的Hash值相同。8第八頁，共四十八頁，2022年，8月28日5.2.1Hash函數的性質一個典型的Hash函數應具有下列特性：單向性：已知Hash函數的輸出c=hash(m)，要求它的輸入m是困難的。快速性：已知輸入m，計算hash(m)是容易的。抗碰撞性：已知hash(m1)=c1，構造m2使hash(m2)=c1是困難的。雪崩性：c=hash(m)，c的每一比特都與m的每一比特有關，具有高度敏感性。輸入數據沒有長度限制：對輸入任何長度的數據能夠生成該輸入消息固定長度的輸出。2023/2/259第九頁，共四十八頁，2022年，8月28日5.2.1Hash函數的例子一個最簡單的Hash函數的例子將輸入數據M分成n個等長的分組Mi(1≤i≤n)，然后對每個分組按位進行異或運算，得到的結果便為其消息摘要。2023/2/2510圖5.2簡單的Hash函數示例第十頁，共四十八頁，2022年，8月28日2023/2/255.2.1Hash函數的攻擊方法Hash函數的安全性取決于其抗各種攻擊的能力。攻擊者的目標通常是找到兩個不同消息映射為同一值。一般假定攻擊者知道Hash算法。攻擊Hash函數有兩種基本方法，都屬于選擇明文攻擊。窮舉攻擊法(ExhaustiveAttack)生日攻擊(BirthdayAttack)窮舉攻擊法給定H=h(M)，其中H為初值，攻擊者在所有可能的M中尋求有利于攻擊者的M’，使h(M’)=h(M)，由于限定了目標h(M)來尋找M’，這種攻擊又稱為目標攻擊法。11第十一頁，共四十八頁，2022年，8月28日2023/2/255.2.1Hash函數的生日攻擊法生日攻擊法可用于攻擊任何Hash算法，它只依賴于消息摘要的長度，即Hash值的長度。生日攻擊基于生日悖論。在一個教室中，找一個與某人生日相同的概率不小于0.5時，所需學生為183人。在一個教室中，至少有兩個學生的生日在同一天的概率不小于0.5的學生人數僅為23人。對于n比特Hash值的生日攻擊，當進行2n/2次的選擇明文攻擊下成功的概率將超過0.63。12第十二頁，共四十八頁，2022年，8月28日2023/2/255.2.1Hash函數的生日攻擊法生日攻擊對Hash函數提出了一個必要的安全條件，即消息摘要必須足夠的長。一個40比特長的消息摘要是很不安全的，因為僅僅用220(大約一百萬)次隨機Hash可至少以1/2的概率找到一個碰撞。為了抵抗生日攻擊，通常建議消息摘要的長度至少應選取為128比特，此時生日攻擊需要約264次Hash。統計結果表明：當hash值的長度為128比特時，則任意兩個報文M1和M2具有相同hash值的概率接近于零。安全Hash標準的輸出長度選為160比特。13第十三頁，共四十八頁，2022年，8月28日2023/2/25Hash函數的單向性和抗碰撞性使Hash函數適用于加密與認證機制。UNIX系統一直使用Hash函數進行口令認證，系統并不直接存儲用戶的登錄口令明文，而是存儲其Hash值。用戶登錄時，系統對其輸入的口令進行Hash值計算，如果結果與系統中存儲的Hash值匹配，則允許該用戶登錄系統。這種機制還實現了對用戶口令的保密，因為即使攻擊者進入系統竊取了用戶口令的Hash值，他也無法通過其計算出用戶口令。Hash函數的雪崩性則使其適用于數據完整性的保障機制中。145.2.1Hash函數的應用第十四頁，共四十八頁，2022年，8月28日5.2.1Hash函數的分類Hash函數按其是否有密鑰控制分為兩大類一類有密鑰控制稱為密碼Hash函數。密碼Hash函數的Hash值不但與輸入數據有關，還與密鑰有關，因此具有認證功能。一類沒有密鑰控制稱為一般Hash函數，一般Hash函數的Hash值只與輸入數據有關，因此不具備認證功能，只用于檢測輸入數據的完整性，一般與公鑰加密技術結合使用。典型的Hash算法有MD5和SHA等。2023/2/2515第十五頁，共四十八頁，2022年，8月28日2023/2/255.2.2MD5算法簡介

MD5(Message-DigestAlgorithm5)在90年代初由MIT的計算機科學實驗室和RSADataSecurityInc發明，經MD2、MD3和MD4發展而來。MD5將任意長度的輸入消息變換成一個128bit的大整數，并且它是一個不可逆的變換算法。MD5的典型應用是對一段信息（Message）產生信息摘要（Message-Digest），以防止被篡改。MD5還廣泛用于加密技術上。比如在UNIX系統中用戶的密碼就是經MD5（或其它類似的算法）加密后存儲在文件系統中。16第十六頁，共四十八頁，2022年，8月28日2023/2/255.2.2MD5算法的工作原理17圖5.3MD5算法處理過程第十七頁，共四十八頁，2022年，8月28日5.2.2MD5算法的具體過程（1）信息填充對輸入信息進行填充，使信息長度為512比特（分組長度）的整數倍。（2）初始化鏈接變量(ChainingVariable)4個32位整型參數A,B,C,D（3）循環處理以A,B,C,D作為輸入參數，對填充后信息的每個分組進行四輪循環處理，每輪循環對分組進行16次操作。2023/2/2518第十八頁，共四十八頁，2022年，8月28日2023/2/255.2.2MD5算法——信息填充信息填充在信息的后面填充一個1和若干個0，直到信息長度擴展至512n+448比特為止。然后在其后附加一個64比特的數據，此數據表示填充前信息的長度。此時信息的比特長度恰好是512的整數倍。填充后將消息被劃分成若干個512位的分組，每一分組又被劃分為16個32位子分組。這些分組即為算法后續循環處理的輸入信息。19第十九頁，共四十八頁，2022年，8月28日5.2.2MD5算法——初始化鏈接變量初始化鏈接變量MD5算法中有A、B、C、D四個變量，最初存放的4個32位整數被稱作鏈接變量，鏈接變量初始化為如下值：A=0x01234567B=0x89abcdefC=0xfedcba98D=0x76543210當設置好這四個鏈接變量后，就開始進入算法的循環處理。2023/2/2520第二十頁，共四十八頁，2022年，8月28日5.2.2MD5算法——循環處理循環處理消息的每一個分組均經過4輪循環處理，處理前將緩沖區A、B、C、D的內容作為輸入參數，處理后的結果再加入到A、B、C、D中去。2023/2/2521第二十一頁，共四十八頁，2022年，8月28日5.2.2MD5算法——循環處理每輪循環處理每輪循環對一個分組進行16次操作。每次操作對a,b,c和d中的其中三個作一次非線性函數運算，然后將所得結果加上第四個變量、分組的一個子分組和一個常數。再將所得結果循環左移，并加上a,b,c或d中之一。最后用該結果取代a,b,c或d中之一。2023/2/2522第二十二頁，共四十八頁，2022年，8月28日2023/2/255.2.3SHA-1算法安全哈希算法SHA(SecurehashAlgorithm)由美國國家標準技術局NIST(NationalInstituteofStandardsTechnology)在MD4的基礎上開發出來的。SHA于1993作為聯邦消息處理標準(FIPSPUB180)公布。在1995年出版了改進版本FIPSPUB181，叫做SHA-1。SHA-1算法允許的最大輸入報文的長度不超過264位，輸出160比特的報文摘要。SHA算法同樣以512位分組為單位進行處理。23第二十三頁，共四十八頁，2022年，8月28日5.2.3SHA-1算法的具體過程1.信息填充填充方法與MD5算法相同。2.初始化消息摘要(MD)緩存器使用由5個32位寄存器組成的160位緩存來存放中間結果和最終散列值。3.摘要處理處理核心是一個4個循環的壓縮函數模塊，其中每個循環由20個處理步驟組成。2023/2/2524第二十四頁，共四十八頁，2022年，8月28日2023/2/255.2.4MD5算法和SHA-1算法的比較MD5和SHA-1都屬于MD4的改進版本，它們之間的比較如下表所示。25MD4SHA-1MD5Hash值128bit160bit128bit分組處理長512bit512bit512bit基本字長32bit32bit32bit步數48(3*16)80(4*20)64(4*16)消息長≤264bit≤264bit≤264bit基本邏輯函數特征3個簡單非線性并且對稱3個簡單非線性并且對稱4個簡單非線性并且對稱常數個數3464速度約為MD4的3/4約為MD4的1/7第二十五頁，共四十八頁，2022年，8月28日5.2.5HMAC算法2023/2/2526HMAC在SSL協議采用。HMAC算法步驟：（1）密鑰變換：使密鑰k與消息塊l等長。（2）異或：ipad=0x3636…36…（3）消息級聯（4）計算消息摘要（5）異或：opad=0x5A5A…5A…（6）消息級聯（7）輸出最終結果第二十六頁，共四十八頁，2022年，8月28日5.3消息認證5.3.1消息認證概述5.3.2采用Hash函數的消息認證5.3.3采用MAC的消息認證2023/2/2527第二十七頁，共四十八頁，2022年，8月28日2023/2/255.3.1消息認證概述消息認證的定義使消息接收者能驗證收到的消息在傳輸過程中有沒有被篡改、偽造和假冒，消息的完整性和有效性是否被破壞的過程。消息認證的兩種模式采用Hash函數采用消息認證碼MAC(MessageAuthenticationCode)區別：是否需要密鑰的參與28第二十八頁，共四十八頁，2022年，8月28日2023/2/255.3.2采用Hash函數的消息認證消息認證方式一：明文29特點？第二十九頁，共四十八頁，2022年，8月28日5.3.2采用Hash函數的消息認證消息認證方式二：加密消息2023/2/2530特點？第三十頁，共四十八頁，2022年，8月28日5.3.2采用Hash函數的消息認證消息認證方式三：加密全部2023/2/2531特點？第三十一頁，共四十八頁，2022年，8月28日5.3.3采用MAC的消息認證消息認證碼MAC的概念消息認證碼MAC是由可變長度的消息M和收發雙方共享的密鑰K產生的定長函數值MAC=f(K,M)

。舉例：基于DES的消息認證碼DES算法可用于生成消息認證碼，可使用密文的后若干位作為消息認證碼。MAC函數類似于加密。它與加密的區別是MAC函數不可逆。由于認證函數的這個數學性質使得它比加密函數更不容易破解。2023/2/2532第三十二頁，共四十八頁，2022年，8月28日5.3.3采用MAC的消息認證消息認證方式一：明文2023/2/2533第三十三頁，共四十八頁，2022年，8月28日5.3.3采用MAC的消息認證消息認證方式二：加密消息2023/2/2534第三十四頁，共四十八頁，2022年，8月28日5.3.3采用MAC的消息認證消息認證方式三：加密全部2023/2/2535第三十五頁，共四十八頁，2022年，8月28日5.4數字簽名5.4.1基本概念5.4.2RSA簽名算法5.4.3DSA簽名算法5.4.4多重數字簽名5.4.5不可抵賴數字簽名5.4.6數字盲簽名2023/2/2536第三十六頁，共四十八頁，2022年，8月28日2023/2/255.4.1基本概念數字簽名的定義首先，數字簽名不是將手寫的簽名經過掃描儀掃描后輸入電腦。《電子簽名法》：數據電文中以電子形式所含（所附）、用于識別簽名人身份、并表明簽名人認可其中內容的數據。數字簽名是一串數據，該數據僅能由簽名人生成，并且該數據能夠表明簽名人的身份。數字簽名的作用確認信息發送者，提供身份認證和不可抵賴性。與傳統文件中的手寫簽名具有同等法律效力。37第三十七頁，共四十八頁，2022年，8月28日5.4.1基本概念數字簽名無法用消息認證碼代替假設Alice和Bob正通過網絡完成一筆交易，那么可能出現兩種欺騙：

（1）Bob偽造一個消息并使用與Alice共享的密鑰K產生該消息的認證碼，然后聲稱該消息來自于A。但實際上Alice并未發送任何消息。（2）既然Bob有可能偽造Alice發來的消息，那么Alice就可以對自己發過的消息予以否認。這兩種欺騙在實際應用中都有可能發生。雙方爭執不下而對簿公堂，但如果沒有更有效的機制避免這種爭端，法庭根本無法作出仲裁。2023/2/2538第三十八頁，共四十八頁，2022年，8月28日5.4.1基本概念數字簽名必須具有以下特點①發送方必然產生自己獨有的信息來簽名以防止偽造和否認。②這種簽名很容易產生。③對于接收方，應該很容易驗證簽名的真偽。④對于給定的x，找出y(y≠x)使得簽名Sig(y)=Sig(x)在計算上是不可行的。⑤找出任意兩個不同的輸入x、y，使得Sig(y)=Sig(x)在計算上是不可行的。2023/2/2539第三十九頁，共四十八頁，2022年，8月28日2023/2/255.4.1基本概念數字簽名體制的組成簽名生成算法：對消息m的簽名可記為Sig(m)=s。簽名密鑰是秘密的。簽名驗證算法：對簽名s的驗證可記為Ver(s)={真，偽}={0,1}。驗證密鑰應當公開。常用的數字簽名體制RSA簽名體制DSA簽名體制ElGamal簽名體制Rabin簽名體制40第四十頁，共四十八頁，2022年，8月28日2023/2/255.4.1基本概念數字簽名的分類直接數字簽名：發送者直接把消息和簽名發送給接收者，接收者直接利用發送者公鑰驗證簽名。基于仲裁的數字簽名：發送者把消息和簽名經由稱做仲裁者的