《數(shù)據(jù)加密與PKI應(yīng)用（微課版）》 課件 Chapter05-散列算法、Chapter06-公鑰加密算法

數(shù)據(jù)加密與PKI應(yīng)用第5章散列算法散列算法（也被稱為散列函數(shù)、雜湊函數(shù)、哈希函數(shù)、Hash()）能夠?qū)Σ煌L度的輸入消息，產(chǎn)生固定長度的輸出。這個(gè)固定長度的輸出散列值被稱為原輸入消息的消息摘要（MessageDigest），也被稱為原消息的數(shù)字指紋。對(duì)于一個(gè)安全的散列算法，這個(gè)消息摘要通常可以直接作為消息的認(rèn)證標(biāo)簽。目錄015.1散列函數(shù)的結(jié)構(gòu)025.2MD5散列算法035.3SHA-1散列算法5.5散列算法的應(yīng)用05045.4散列算法分析

MD，即加強(qiáng)式迭代模式（Merkle-Damgard），1979年RalphMerkle基于數(shù)據(jù)壓縮函數(shù)f()建立的散列函數(shù)的通用模式。MD結(jié)構(gòu)消息M的散列值計(jì)算:Hash(M)=CVLCVq=f(CVq-1,mq-1),1≤q≤LCV0=IV目錄015.1散列函數(shù)的結(jié)構(gòu)025.2MD5散列算法035.3SHA-1散列算法5.5散列算法的應(yīng)用05045.4散列算法分析消息分組填充填充之后的消息比特長度Lm與448同模512，即填充后的消息比特長度比512的整數(shù)倍少64比特。即使原始消息長度已經(jīng)達(dá)到要求（原始消息比特長度與448同模512），也要進(jìn)行填充。填充的比特位數(shù)大于等于1比特，小于等于512比特。填充模式是第一位為1，后面跟足夠多的0。

MD5算法的輸入為任意長度的消息，對(duì)消息以512比特長度為單位進(jìn)行分組，對(duì)所有分組進(jìn)行迭代式處理，最終輸出128比特的散列值。消息分組填充【例5-1】不同長度原始消息的填充結(jié)果。

(1)原始消息恰好是448比特，則填充512比特，使消息長度為960比特，也就是512比特加上448比特。

(2)原始消息500比特，則填充460比特，使消息長度為960比特，即512比特加上448比特。

(3)原始消息512比特，則填充448比特，使消息長度為960比特，即512比特加上448比特。

最后，將原始消息的長度用64比特?cái)?shù)據(jù)表示，并添加到最后一個(gè)分組（448比特的分組）的末尾，使該分組的長度達(dá)到512比特。如果原始消息704比特，其二進(jìn)制值為1011000000，將這個(gè)數(shù)字寫為64比特（前面添加54個(gè)0），并把它添加到最后一個(gè)分組的末尾，使得該分組的大小也是512比特。如果原始消息的長度大于264比特，則以264為模數(shù)取模。初始化MD緩沖區(qū)

MD5的中間結(jié)果和最終結(jié)果保存在128比特的緩沖區(qū)中，緩沖區(qū)使用4個(gè)32比特的寄存器（A、B、C、D）表示，這些寄存器的初始值為：A=67452301H01B=efcdab89H02C=98badcfeH03D=10325476H04MD5的壓縮函數(shù)MD5散列算法壓縮函數(shù)處理512比特?cái)?shù)據(jù)分組，每個(gè)數(shù)據(jù)分組被分為16個(gè)子分組，每個(gè)子分組4字節(jié)。MD5壓縮函數(shù)由4輪運(yùn)算組成，每輪16步，每步處理1個(gè)子分組。每輪的輸入為當(dāng)前要處理的消息分組mq-1和緩沖區(qū)的當(dāng)前值A(chǔ)、B、C、D，輸出仍放在緩沖區(qū)中以產(chǎn)生新的A、B、C、D。MD5(M)=CVLCVq=SUM32(CVq-1,I(mq-1,H(mq-1,G(mq-1,F(mq-1,CVq-1))))),1≤q≤LCV0=IV基本邏輯函數(shù)常量數(shù)據(jù)子分組的使用

當(dāng)前要處理的512比特分組被分為16個(gè)子分組，保存于X[i]中，不同輪中使用順序不同。MD5算法的迭代運(yùn)算temp←B+CLSs(A+f(B,C,D)+X[ρ(i)]+T[k])A←DD←CC←BB←temp

符號(hào)“←”表示賦值運(yùn)算；

“+”為模232加法。例題分析∵B+CLSs(A+f(B,C,D)+X[ρ(i)]+T[k])

=

B+CLS9(A+G(B,C,D)+X[6]+T[18])

=A2EF9F08H∴temp=A2EF9F08H(1)A←D

∴A=99669966H(2)D←C

∴D=CCFFCCFFH(3)C←B

∴C=AA55AA55H(4)B←temp

∴B=A2EF9F08H【例5-4】請(qǐng)計(jì)算壓縮函數(shù)第2輪第2步的計(jì)算結(jié)果。假設(shè)輸入鏈接變量A=CC33CC33H，B=AA55AA55H，C=CCFFCCFFH，D=99669966H。使用的子分組為00AA00AAH。(1)temp←B+CLSs(A+f(B,C,D)+X[ρ(i)]+T[k])第2輪第2步使用的常量是T[18]=C040B340H。已經(jīng)計(jì)算得到第2輪16個(gè)子分組的使用順序，第2步使用子分組X[6]=00AA00AAH。已經(jīng)計(jì)算得到第2輪使用的邏輯函數(shù)G(B,C,D)=CCDDCCDDH。目錄015.1散列函數(shù)的結(jié)構(gòu)025.2MD5散列算法035.3SHA-1散列算法5.5散列算法的應(yīng)用05045.4散列算法分析SHA-1算法描述

SHA-1算法對(duì)消息以512比特長度的分組為單位進(jìn)行處理，輸出160比特的散列值。SHA-1算法的分組填充方式與MD5算法相同，但是散列值和鏈接變量的長度是160比特。

SHA-1的中間結(jié)果和最終結(jié)果保存于160比特的緩沖區(qū)中。緩沖區(qū)使用5個(gè)32比特的寄存器（A、B、C、D、E）表示A=67452301H01B=efcdab89H02C=98badcfeH03D=10325476H04E=c3d2e1f0H05SHA-1的整體結(jié)構(gòu)SHA-1(M)=CVLCVq=SUM32(CVq-1,f4(mq-1,f3(mq-1,f2(mq-1,f1(mq-1,CVq-1))))),1≤q≤LCV1=IV

這4輪運(yùn)算的結(jié)構(gòu)相同，但是各輪使用的邏輯函數(shù)不同，分別是f1()、f2()、f3()、f4()。SHA-1的壓縮函數(shù)

每輪使用一個(gè)加法常量Kt，其中0≤t≤79，表示迭代步數(shù)。80個(gè)常量中實(shí)際上只有4個(gè)不同的取值。temp←E+ft(B,C,D)+CLS5(A)+Wt+Kt

E←D

D←C

C←CLS30(B)

B←A

A←tempSHA-1的壓縮函數(shù)

SHA-1算法每一步迭代都要使用一個(gè)32比特的字Wt，所以一共需要80個(gè)字。Wt是由消息分組mq擴(kuò)充得到的。

如果mq=M0||M1||...||M15Wt=Mt,0≤t≤15Wt=CLS1(Mt-3

⊕Mt-8

⊕Mt-14

⊕Mt-16),16≤t≤79temp←E+ft(B,C,D)+CLS5(A)+Wt+Kt

E←D

D←C

C←CLS30(B)

B←A

A←temp【例5-5】如果M0=11221122H，M2=11AA11AA，M8=EE00EE00H，M13=FF66FF66H，M15=66996699H，請(qǐng)計(jì)算W15和W16的值。(1)W15==66996699H。(2)W16=CLS1(M13

⊕M8

⊕M2

⊕M0)=23DC23DCH目錄015.1散列函數(shù)的結(jié)構(gòu)025.2MD5散列算法035.3SHA-1散列算法5.5散列算法的應(yīng)用05045.4散列算法分析生日攻擊

分生日攻擊是對(duì)散列函數(shù)進(jìn)行分析和計(jì)算碰撞消息的一般方法。它只依賴于消息摘要的長度。這種攻擊方法給出了散列函數(shù)具備安全性的一個(gè)必要條件。

生日問題是指在k個(gè)人中至少有兩個(gè)人的生日相同的概率大于0.5時(shí)，k至少多大？(1)因?yàn)閔()有n個(gè)可能的輸出，所以任意取兩個(gè)不同的輸入x、y，使得h(x)≠h(y)的概率為

；(2)任意取三個(gè)不同的輸入，使得輸出不產(chǎn)生碰撞的概率為

；(3)任意取k個(gè)不同的輸入，使得輸出不產(chǎn)生碰撞的概率為

；(4)依據(jù)Taylor級(jí)數(shù)，在n>>1的情況下進(jìn)行約算，可以得到結(jié)論。所以，如果取n=365，則k≈23，即只需要23人，就能以大于0.5的概率找到兩個(gè)生日相同的人。

生日攻擊意味著安全消息摘要的長度有一個(gè)下限。通常，建議消息摘要的長度至少為128比特。安全散列算法SHA-1的輸出長度選擇160比特正是出于這種考慮。差分分析

差分分析的基本思想是通過分析特定明文差對(duì)密文差的影響來獲得可能性最大的密鑰。

2004年，我國山東大學(xué)的王小云教授做的破譯MD5、HAVAL-128、MD4、和RIPEMD算法的報(bào)告震驚了整個(gè)密碼學(xué)屆。2005年又宣布了破譯SHA-1的消息，再一次震撼了世界密碼學(xué)屆。王小云教授的攻擊方法采用模差分思想，根據(jù)每次循環(huán)中模減差分或異或差分，得到差分特征，通過兩種差分的結(jié)合，提出了新的一系列散列函數(shù)攻擊的有效方法。目錄015.1散列函數(shù)的結(jié)構(gòu)025.2MD5散列算法035.3SHA-1散列算法5.5散列算法的應(yīng)用05045.4散列算法分析散列算法的應(yīng)用數(shù)字指紋：散列算法可以用來生成文件的“數(shù)字指紋”，通過比對(duì)數(shù)字指紋來辨別文件是否被修改過。安全口令存儲(chǔ)：在實(shí)際應(yīng)用中，系統(tǒng)會(huì)用散列函數(shù)計(jì)算用戶提供的登錄口令，并將口令散列值存儲(chǔ)到應(yīng)用服務(wù)器中（不會(huì)直接存儲(chǔ)用戶的口令明文）。當(dāng)用戶登錄系統(tǒng)時(shí)，系統(tǒng)再次計(jì)算用戶提供的口令的散列值，并與服務(wù)器中存儲(chǔ)的散列值進(jìn)行比對(duì)，如果相同則允許用戶登錄，否則拒絕用戶登錄。感謝您的瀏覽第5章散列算法2023.08數(shù)據(jù)加密與PKI應(yīng)用第6章公鑰加密算法公鑰加密算法的思想是由W.Difie和Hellman在1976年提出的。使用公鑰加密算法，加密和解密時(shí)使不同密鑰，即Ke≠Kd。用于加密的密鑰稱為公鑰，可以公開；用于解密的密鑰稱為私鑰，必須被所有者秘密保存。公鑰加密算法均基于數(shù)學(xué)難解問題，目前常用的數(shù)學(xué)難解問題有“大數(shù)分解”難題和“離散對(duì)數(shù)”難題。目錄016.1公鑰秘密數(shù)學(xué)基礎(chǔ)026.2RSA公鑰密碼體制036.3ElGamal公鑰密碼體制6.5身份識(shí)別05046.4數(shù)字簽名與驗(yàn)證

例如，{1,5}構(gòu)成模6的簡化剩余系；{1,2,3,4,5,6}構(gòu)成模7的簡化剩余系。簡化剩余定理設(shè)m是一個(gè)正整數(shù)，對(duì)任意正整數(shù)a，稱：

為模m的a的剩余類。若有m個(gè)整數(shù)r0,r1,...,rm，其中任意兩個(gè)數(shù)都不在同一個(gè)剩余類中，則r0,r1,...,rm叫作模m的一個(gè)完全剩余系。在模m的一個(gè)剩余類中，如果有一個(gè)數(shù)與m互素，那么這個(gè)剩余類中所有的數(shù)均與m互素。如果模m的一個(gè)剩余類中存在與m互素的數(shù)，則稱它是模m的一個(gè)簡化剩余類。在模m的所有簡化剩余類中，從每個(gè)類任取一個(gè)數(shù)組成的集合，叫作模m的一個(gè)簡化剩余系，也叫既約剩余系、縮系。

【例6-1】計(jì)算120的歐拉函數(shù)值。120=23·3·5，因此：歐拉函數(shù)

設(shè)m是一個(gè)正整數(shù)，稱m個(gè)整數(shù)0,1,…,m-1中與m互素的整數(shù)個(gè)數(shù)為歐拉函數(shù)，記作

(m)。歐拉函數(shù)具有下列性質(zhì)：

(1)若p為素?cái)?shù)，則

(p)=p-1。

(2)若p和q為不同的素?cái)?shù)，則

(p·q)=(p-1)·(q-1)=

(p)·

(q)。

定理6.1設(shè)正整數(shù)n的標(biāo)準(zhǔn)分解式為：

則：歐拉定理

歐拉定理給出了模m的簡化剩余系中所有元素都具備的一個(gè)特性。

定理6.2（歐拉定理）設(shè)正整數(shù)m>1，如果整數(shù)a滿足gcd(a,m)=1，

則：中國剩余定理

定理6.3（中國剩余定理）設(shè)正整數(shù)m1,m2,...,mk兩兩互素，令：

則對(duì)任意整數(shù)a1,a2,...,ak，同余方程組：

有唯一解，即：其中：

【例6-2】按照中國剩余定理，計(jì)算“物不知數(shù)”問題。

(1)根據(jù)“物不知數(shù)”問題的定義，可知：a1=2,a2=3,a3=2，并且m1=3,m2=5,m3=7。

(2)計(jì)算：m=m1·m2·m3=105。

(3)計(jì)算：M1=35,M2=21,M3=15。

(4)計(jì)算：M1-1=2,M2-1=1,M3-1=1。

(5)根據(jù)中國剩余定理，得到：中國剩余定理原根與指數(shù)

設(shè)m,a為正整數(shù)，m>1,gcd(a,m)=1，稱使得：成立的最小正整數(shù)x為a模m的階，記作：

【例6-3】當(dāng)m=7，a分別為1,2,3,4,5,6時(shí)，計(jì)算a模m的階。

a模m的階如表6-1所示。

因?yàn)?/p>

(7)=6，所以

中最大的值是6。

如果

=

(m)，則稱a為模m的原根。

定理6.4（指數(shù)定理）設(shè)r是正整數(shù)m的一個(gè)原根，則

，

當(dāng)且僅當(dāng)

。

目錄016.1公鑰秘密數(shù)學(xué)基礎(chǔ)026.2RSA公鑰密碼體制036.3ElGamal公鑰密碼體制6.5身份識(shí)別05046.4數(shù)字簽名與驗(yàn)證2.加密

首先對(duì)明文進(jìn)行比特串分組，使得每個(gè)分組對(duì)應(yīng)的十進(jìn)制數(shù)小于n，然后依次對(duì)每個(gè)分組m進(jìn)行加密，所有分組的密文構(gòu)成的序列即是原始消息的加密結(jié)果，即m滿足0<m<n，則加密算法為：RSA算法描述1.密鑰生成(1)選取兩個(gè)保密的大素?cái)?shù)p和q。(2)計(jì)算

n=p·q，

(n)=(p-1)·(q-1)。其中

(n)是n的歐拉函數(shù)值。(3)隨機(jī)選取整數(shù)e，1<e<

(n)，滿足gcd(e,

(n))=1。(4)計(jì)算d，滿足(5)公鑰為(e,n)，私鑰為(d,n)。3.解密

對(duì)于密文c，解密算法為：對(duì)RSA算法的攻擊選擇密文攻擊計(jì)時(shí)攻擊數(shù)學(xué)攻擊窮舉攻擊對(duì)RSA算法的攻擊目錄016.1公鑰秘密數(shù)學(xué)基礎(chǔ)026.2RSA公鑰密碼體制036.3ElGamal公鑰密碼體制6.5身份識(shí)別05046.4數(shù)字簽名與驗(yàn)證2.加密首先對(duì)明文進(jìn)行比特串分組，使得每個(gè)分組對(duì)應(yīng)的十進(jìn)制數(shù)小于p，然后依次對(duì)每個(gè)分組m進(jìn)行加密。對(duì)于明文分組，首先隨機(jī)選取一個(gè)整數(shù)k，1≤k≤p-2，然后計(jì)算：則密文c=(c1,c2)。ElGamal算法描述1.密鑰生成(1)選取大素?cái)?shù)p，且要求p-1有大素?cái)?shù)因子。是一個(gè)生成元。

是一個(gè)生成元。(2)隨機(jī)選取整數(shù)x，1≤x≤p-2，計(jì)算。(3)公鑰為y，私鑰為x。3.解密

為了解密一個(gè)密文c=(c1,c2)，計(jì)算：ElGamal的安全性

在ElGamal公鑰密碼體制中，。由公開參數(shù)g和y求解私鑰x需要求解離散對(duì)數(shù)問題。目前還沒有找到一個(gè)有效算法來求解有限域上的離散對(duì)數(shù)問題。因此，ElGamal公鑰密碼體制的安全性基于有限域上離散對(duì)數(shù)問題困難性。為了抵抗已知的攻擊，p應(yīng)該選取至少1024位以上的大素?cái)?shù)，并且p-1至少應(yīng)該有一個(gè)長度不小于160比特的大的素因子。目錄016.1公鑰秘密數(shù)學(xué)基礎(chǔ)026.2RSA公鑰密碼體制036.3ElGamal公鑰密碼體制6.5身份識(shí)別05046.4數(shù)字簽名與驗(yàn)證RSA簽名算法1)RSA簽名算法

RSA算法公鑰為（e,n），私鑰為（d,n）。對(duì)于消息m（

），簽名為：2)RSA驗(yàn)證算法

對(duì)于消息簽名對(duì)兒（m,s），如果有：RSA數(shù)字簽名安全分析

1)消息破譯

2)騙取仲裁簽名

3)騙取用戶簽名數(shù)字簽名標(biāo)準(zhǔn)DSS1.參數(shù)與密鑰生成

(1)選取大素?cái)?shù)p，滿足，其中512≤L≤1024且L是64的倍數(shù)。(2)選取大素?cái)?shù)q，q是p-1的一個(gè)素因子且，即q是160位的素?cái)?shù)且是p-1的素因子。(3)選取一個(gè)生成元，其中h是一個(gè)整數(shù)，滿足1<h<p-1并且

。(4)隨機(jī)選取整數(shù)x，0<x<q，計(jì)算。(5)p、q和g是公開參數(shù)，y為公鑰，x為私鑰。數(shù)字簽名標(biāo)準(zhǔn)DSS2.簽名

對(duì)于消息m，首先隨機(jī)選取一個(gè)整數(shù)k，0<k<q，然后計(jì)算：r=f2(k,p,q,g)，

s=f1(h(m),k,x,r,q)，數(shù)字簽名標(biāo)準(zhǔn)DSS3.驗(yàn)證

對(duì)于消息簽名對(duì)兒（m,(r,s)），首先計(jì)算：w=f3(s,q)，

v=f4(y,q,g,h(m),w,r)，

然后驗(yàn)證：v=r簽密1.參數(shù)與密鑰生成(1)選取大素?cái)?shù)p和q，q為（p-1）的素因子。(2)g為乘法群中的一個(gè)q階元素。(3)H()是一個(gè)Hash函數(shù)。(4)E()和D()是對(duì)稱密碼體制中的一種加密和解密算法。(5)xs是簽密方的私鑰，1<xs<q；ys是簽密方的公鑰，。xv是驗(yàn)證方的私鑰，1<xv<q；yv是驗(yàn)證方的公鑰。

保密性和認(rèn)證性是當(dāng)代密碼系統(tǒng)最主要的兩個(gè)安全目標(biāo)，如果需要同時(shí)實(shí)現(xiàn)保密性和認(rèn)證性，那么可以采用“先簽名，再加密”的方式。這種方式相當(dāng)于兩種運(yùn)算“串連”在一起，其運(yùn)算代價(jià)是兩種運(yùn)算之和。

1997年，Y.Zheng首次提出了“簽密”的概念，在一個(gè)邏輯步驟內(nèi)，同時(shí)完成認(rèn)證和加密運(yùn)算，從而提高整體效率，該簽密方案稱為SCS。簽密3.解密與驗(yàn)證驗(yàn)證方收到簽密密文（c,r,s）后，執(zhí)行如下操作。(1)計(jì)算，并將k分為適當(dāng)長度的k1和k2。(2)計(jì)算m=Dk1(c)。(3)如果r=H(k2,m)，那么可以驗(yàn)證消息來自簽密方。2.簽密對(duì)于消息m，簽密方執(zhí)行如下操作。(1)選擇隨機(jī)數(shù)x，1<x<q。(2)計(jì)算，并將k分為適當(dāng)長度的k1和k2。(3)計(jì)算r=H(k2,m)。(4)計(jì)算。(5)計(jì)算c=Ek1(m)。對(duì)消息m的簽密密文為（c,r,s）。目錄016.1公鑰秘密數(shù)學(xué)基礎(chǔ)026.2RSA公鑰密碼體制036.3ElGamal公鑰密碼體制6.5身份識(shí)別05046.4數(shù)字簽名與驗(yàn)證身份識(shí)別強(qiáng)身份識(shí)別：

(1)P能向V證明他的確是P。

(2)P向V證明身份后，V不能獲得冒用P的身份的信息。

(3)除了P以外的第三者能夠以P的身份執(zhí)行協(xié)議，能夠讓V相信他是P的概率可以忽略不計(jì)。弱身份識(shí)別：

(1)生物特征：利用生物所具有的獨(dú)一無二的特征，例如指紋、虹膜、DNA等來進(jìn)行身份識(shí)別。

(2)口令：用戶提供賬戶信息的同時(shí)，提供只有他本人才用戶的口令，來向驗(yàn)證方證明自己的身份。

(3)智能卡：智能卡中存放著用戶的身份數(shù)據(jù)，智能卡由合法用戶隨身攜帶，通過專用的讀卡器讀出卡中的數(shù)據(jù)，從而識(shí)別用戶的身份。(4)USBKey：USBKey存儲(chǔ)著用戶的密鑰或數(shù)字證書，可以實(shí)現(xiàn)對(duì)用戶身份的識(shí)別。Guillou-Quisquater身份識(shí)別協(xié)議2.TA向P頒發(fā)身份證書

(1)TA為P建立身份信息IDP。

(2)P選擇一個(gè)整數(shù)u，0≤u≤n-1，且gcd(u,n)=1。計(jì)算，u作為P的私鑰，v作為P的公鑰，并將v發(fā)送給TA。

(3)TA計(jì)算簽名s=SignTA(IDP,v)，將證書CertP=(IDP,v,s)發(fā)送給P。1.參數(shù)選擇

(1)TA選擇兩個(gè)大素?cái)?shù)p和q，計(jì)算n=p·q，p和q保密，n公開。

(2)TA選擇一個(gè)大素?cái)?shù)b，b滿足gcd(b,

(n))=1，且b的長度為40bit。TA計(jì)算

作為私鑰。b作為TA公鑰公開。(3)TA確定自己的簽名算法SignTA和哈希函數(shù)h，h公開。Guillou-Quisquater身份識(shí)別協(xié)議3.P向V證明其身份

(1)P隨機(jī)選取整數(shù)k，0≤k≤n-1，計(jì)算，并將證書CertP和R發(fā)送給V。(2)V驗(yàn)證s是否是TA對(duì)(IDP,v)的簽名，如果是，V隨機(jī)選取整數(shù)r，0≤r≤b-1，并將r發(fā)送給P。(3)P計(jì)算，并將y發(fā)送給V。(4)V驗(yàn)證是否有：成立，如果成立，V就接受P的身份證明；否則，V拒絕P的身份證明。Guillou-Quisquater身份識(shí)別協(xié)議4.