散列函數(shù)與數(shù)字簽名

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

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

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

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