1、網絡信息安全網絡信息安全中國科學技術大學中國科學技術大學肖肖 明明 軍軍2復習復習 對稱加密算法對稱加密算法 1DES算法算法 2IDEA算法算法3第二章第二章 信息加密技術（信息加密技術（3） 本節學習目標：本節學習目標： 掌握常用加密算法及其相關知識掌握常用加密算法及其相關知識對稱加密算法：對稱加密算法：DES、IDEA非對稱加密算法：非對稱加密算法：RSA4非對稱密碼算法原理非對稱密碼算法原理 對稱密鑰密碼系統的缺陷對稱密鑰密碼系統的缺陷 密鑰必須經過安全的信道分配密鑰必須經過安全的信道分配 無法用于數字簽名無法用于數字簽名 密鑰管理復雜密鑰管理復雜 O(n2) 76年年Diffie和和

2、Hellman發表了發表了“密碼學的新方向密碼學的新方向”，奠定了公，奠定了公鑰密碼學的基礎鑰密碼學的基礎 公鑰技術是二十世紀最偉大的思想之一公鑰技術是二十世紀最偉大的思想之一 ，是，是密碼學歷史上唯一密碼學歷史上唯一的一次真正的革命的一次真正的革命 改變了密鑰分發的方式改變了密鑰分發的方式 可以廣泛用于數字簽名和身份認證服務可以廣泛用于數字簽名和身份認證服務 基于數學函數而不是代替和換位基于數學函數而不是代替和換位5每個通信實體有一對密鑰每個通信實體有一對密鑰（公鑰，私鑰）（公鑰，私鑰）。公鑰公開，。公鑰公開，用于加密和驗證簽名，私鑰保密，用作解密和簽名用于加密和驗證簽名，私鑰保密，用作解密

3、和簽名A向向B 發送消息，用發送消息，用B的公鑰加密的公鑰加密B收到密文后，用自己的私鑰解密收到密文后，用自己的私鑰解密PlainText加密算法解密算法ABcipherPlainTextB的私鑰C的公鑰B的公鑰任何人向B發送信息都可以使用同一個密鑰（B的公鑰）加密沒有其他人可以得到B的私鑰，所以只有B可以解密公鑰密碼系統的加密原理公鑰密碼系統的加密原理6 A向向B 發送消息，用發送消息，用A的私鑰加密（簽名）的私鑰加密（簽名） B收到密文后，用收到密文后，用A的公鑰解密（驗證）的公鑰解密（驗證）PlainText加密算法解密算法cipherPlainTextABA的私鑰A的公鑰公鑰密碼系統的

4、簽名原理公鑰密碼系統的簽名原理7公鑰密碼算法的表示公鑰密碼算法的表示 對稱密鑰密碼對稱密鑰密碼 密鑰：會話密鑰（密鑰：會話密鑰（Ks） 加密函數：加密函數：C= EKsP 對密文對密文C，解密函數：，解密函數：DKsC， 公開密鑰公開密鑰 （KUa，KRa） 加密加密/簽名：簽名：C= EKUbP，EKRaP 解密解密/驗證：驗證：P= DKRbC，DKUaC8X加密（簽名）加密解密解密（驗證）XYZY = EKRa （X）, Z= EKUbY = EKUb EKRa （X）Y = DKRb （Z）, X= DKUaY = DKUa DKRb （Z）AB產生密鑰對產生密鑰對KRaKUaKRbK

5、Ub數字簽名和加密同時使用數字簽名和加密同時使用Y9基本思想和要求基本思想和要求 涉及到各方：發送方、接收方、攻擊者涉及到各方：發送方、接收方、攻擊者 涉及到數據：公鑰、私鑰、明文、密文涉及到數據：公鑰、私鑰、明文、密文 公鑰算法的條件：公鑰算法的條件： 產生一對密鑰是計算可行的產生一對密鑰是計算可行的 已知公鑰和明文，產生密文是計算可行的已知公鑰和明文，產生密文是計算可行的 接收方利用私鑰來解密密文是計算可行的接收方利用私鑰來解密密文是計算可行的 對于攻擊者，利用公鑰來推斷私鑰是計算不可行的對于攻擊者，利用公鑰來推斷私鑰是計算不可行的 已知公鑰和密文，恢復明文是計算不可行的已知公鑰和密文，恢

6、復明文是計算不可行的 (可選可選)加密和解密的順序可交換加密和解密的順序可交換10如何設計一個公鑰算法如何設計一個公鑰算法 公鑰和私鑰必須相關，而且從公鑰到私鑰不可公鑰和私鑰必須相關，而且從公鑰到私鑰不可推斷推斷 必須要找到一個難題，從一個方向走是容易的，必須要找到一個難題，從一個方向走是容易的，從另一個方向走是困難的從另一個方向走是困難的 如何把這個難題跟加解密結合起來如何把這個難題跟加解密結合起來 計算可行和不可行的界計算可行和不可行的界11公鑰密碼學的研究情況公鑰密碼學的研究情況 與計算復雜性理論密切相關與計算復雜性理論密切相關 計算復雜性理論可以提供指導計算復雜性理論可以提供指導 但是

7、需求不盡相同但是需求不盡相同 計算復雜性通常針對一個孤立的問題進行研究計算復雜性通常針對一個孤立的問題進行研究 而公鑰密碼學往往需要考慮一些相關的問題而公鑰密碼學往往需要考慮一些相關的問題比如，密碼分析還需要考慮已知明文、選擇明文等相關的情形比如，密碼分析還需要考慮已知明文、選擇明文等相關的情形 討論的情形不同討論的情形不同 計算復雜性考慮最壞的情形計算復雜性考慮最壞的情形 而對于公鑰密碼學則是不夠的而對于公鑰密碼學則是不夠的 一個困難問題必然會導致一個保密性很好的密碼系統嗎？一個困難問題必然會導致一個保密性很好的密碼系統嗎？ 不一定，還需要有好的構造不一定，還需要有好的構造12RSA算法簡介

8、算法簡介 77年發明，年發明，78年公布年公布 Ron Rivest, Adi Shamir , Leonard Adleman （這是（這是三位發明人）三位發明人） RSA的安全性基于的安全性基于大數分解大數分解的難度的難度 RSA在美國申請了專利（在美國申請了專利（2000年年9月已經到期），在其月已經到期），在其他國家沒有他國家沒有 RSA已經成了事實上的已經成了事實上的工業標準工業標準，在美國除外，在美國除外13數論基礎數論基礎 a與與b的最大公因數：的最大公因數：gcd（a, b），簡記為（），簡記為（a, b） gcd（20, 24）=4 , gcd（15, 16）=1 如果如果g

9、cd（a, b）=1 ，稱，稱a與與b 互素互素 模運算模運算 moda= q n +r 0rn ; q=a/n ; x 表示小于或等于表示小于或等于x的最大整數的最大整數a=a/nn + （a mod n） , r = a mod n 如果如果 （a mod n ）= （b mod n） ，則稱則稱a 與與b 模n同余，記為記為 a = b mod n 例如，例如， 23 =8 mod 5 , 8 =1 mod 714數論基礎（續）數論基礎（續）模運算對加法和乘法是可交換的、可結合的、可分配的模運算對加法和乘法是可交換的、可結合的、可分配的（a+b） mod n = （a mod n ） +

10、 （b mod n） ） mod n（a-b） mod n = （a mod n） （b mod n） ） mod n（ab） mod n = （a mod n ） （b mod n） ） mod n （a （b+c） ） mod n = （ a b） mod n + （a c） mod n） mod n冪冪,模運算模運算 ma mod n m2 mod n = （mm） mod n = （m mod n ） 2 mod n m4 mod n = （m2 mod n ） 2 mod nm8 mod n = （m2 mod n ）2 mod n ）2 mod n m25 mod n = （m m

11、8 m16） mod n 15數論基礎（續）數論基礎（續） 歐拉函數歐拉函數(n)n是正整數，是正整數， (n)是比是比n小且與小且與n 互素的正整數的個數互素的正整數的個數(2) = |1| =1(3) = |1, 2| =2 (4) = |1, 3| =2 (5) = |1, 2, 3, 4 | =4 (6) = |1, 5| =2 (7) = |1, 2, 3, 4, 5, 6| =6(10) = |1, 3, 7, 9| =4 (11) = |1, 2,3,4,5,6, 7,8, 9,10| =10 如果如果p是素數，則是素數，則(p)=(p-1), 比如比如(2), (5)， (11

12、) 如果如果p,q 是素數，則是素數，則(pq)=(p)(q) (p-1)(q-1),比如比如, (10)16數論基礎（續）數論基礎（續）定理定理1 若若ac=bd mod n 且且c=d mod n 及及 (c，n)=1，則，則 a=b mod n證明證明 由由(a-b)c+b(c-d)=ac-bd=0 mod n 可得可得 n | (a-b)c。因為及。因為及 (c，n)=1，故，故n | (a-b)。因此。因此a=b mod n定理定理2 若若(a，n)=1，則存在唯一整數，則存在唯一整數b，0bn，且，且(b，n)=1，使得，使得ab=1 mod n證明證明 由定理由定理1知，若知，若

13、(a，n)=1，且，且i j mod n，則，則ai aj mod n。因此，。因此，集合集合ai mod ni=0，1，n-1為集合為集合0，1，n-1的一個排列。因的一個排列。因此此b為為ab=1 mod n的唯一解。此外，因的唯一解。此外，因ab-1=kn，k為正數，若為正數，若(b，n)=g則則g | (ab-1)。因。因g | ab，所以，所以g|1。因此，。因此，g=1。故。故b也與也與n互互素。素。17數論基礎（續）數論基礎（續）定理定理3 令令r1，r2，r(n)為模為模n的一的一既約剩余系既約剩余系，且，且(a，n)=1，則，則ar1，ar2，ar(n)也為模也為模n的一既約

14、剩余系的一既約剩余系證明證明 設設(arj，n)=g，則，則g|a或或g|rj。因此我們得以下兩種情況。因此我們得以下兩種情況。1) g|a且且g|n，或，或 2) g|rj且且g|n。首先首先 1）不可能，因為）不可能，因為(a，n)=1；其次；其次 2）也不可能，因為）也不可能，因為rj為模為模n既既約剩余系的一元素。因此約剩余系的一元素。因此(arj，n)=1。此外，。此外， ari arj，否則，否則ri=rj。因。因此此ar1，ar2，ar(n)也為模也為模n的一既約剩余系。的一既約剩余系。 定理定理4 歐拉定理：若歐拉定理：若(a，n)=1，則，則a(n)=1 mod n證明證明

15、令令r1，r2，r(n)為模為模n的一既約剩余系，由定理的一既約剩余系，由定理3知，若知，若(a，n)=1，則，則ar1，ar2，ar(n)也為模也為模n的一既約剩余系。因此的一既約剩余系。因此 1=i=(n) ( ari) mod n = 1=i=(n) (ri) mod n，由消去法，可得，由消去法，可得a(n)=1 mod n18數論基礎（續）數論基礎（續）推論：推論：給定兩個素數給定兩個素數p, q , 兩個整數兩個整數 n, m ，使得，使得n=pq, 0mn ； 則對于則對于任意整數任意整數k ，下列關系成立：，下列關系成立：m k(n)+1 m mod n證明：分兩種情況：證明：

16、分兩種情況：1）m與與n互素，則由歐拉定理得互素，則由歐拉定理得 m(n) 1 mod n m k(n) 1 mod nm k(n)+1 m mod n2） gcd(m,n) 1，由于，由于n=pq，則，則gcd(m,n) 1意味著意味著m要么是要么是p的倍數，的倍數，要么是要么是q的倍數，不妨設的倍數，不妨設m=tp，其中，其中t為一正整數。此時，為一正整數。此時，gcd(m,q)=1，否則否則m也是也是q的倍數，從而是的倍數，從而是pq的倍數，與的倍數，與mn=pq矛盾。矛盾。由由gcd(m,q)=1及歐拉定理得及歐拉定理得m(q) 1 mod q， mk(q) (p)1 mod q， m

17、k(n) 1 mod q因此存在一整數因此存在一整數r，使得，使得mk(n) =1+rq，兩邊同乘以，兩邊同乘以m=tp，得，得 mk(n)+1 =m+rtpq=m+rtn，即，即m k(n)+1 m mod n19密鑰產生密鑰產生1. 取兩個大素數取兩個大素數 p, q , p q, 保密保密; 2. 計算計算n=pq，公開公開n; 3. 計算歐拉函數計算歐拉函數(n) =(p-1)(q-1)；4. 選擇整數選擇整數e,使得使得 gcd (e, (n)=1; 1e(n)5.計算計算d = e-1 mod (n)公開公開(e, n)=(5, 119)將將d 保密，丟棄保密，丟棄p, qp=7,

18、q=17n=119（n）=96選擇e=55d=k961令 k=4, 得到d=77RSA算法操作過程算法操作過程20 公開密鑰公開密鑰: KU=e, n 秘密密鑰秘密密鑰: KR=d, n 加密過程加密過程 把待加密的內容分成把待加密的內容分成k比特的分組，比特的分組，k log2n，并寫成數字，設為，并寫成數字，設為M，則：，則： C= Me mod n 解密過程解密過程 M = Cd mod nRSA 算法加密算法加密/解密過程解密過程5, 11977, 119c=m5 mod 119 m=c77 mod 11921RSA 算法正確性算法正確性 M=Cd mod n = (Me mod n)

19、d mod n = Med mod n = M k(n)+1 mod n = M mod n = M22計算乘冪計算乘冪 計算計算d=am, m=bkbk-1b0(二進制二進制表示表示)d1For ik downto 0 Do d(d d) mod n If bi = 1 Then d(d a) mod nReturn d 原理：原理：m = (bk2+bk-1)2+bk-2)2+bk-3)2+)2+b023RSA密鑰產生密鑰產生 產生兩個素數產生兩個素數 由于由于n = pq是公開的，所以，為了防止攻擊者是公開的，所以，為了防止攻擊者利用利用n獲得獲得p和和q，必須選擇足夠大的素數，必須選擇

20、足夠大的素數p和和q 大素數產生算法大素數產生算法 選擇選擇e或者或者d，然后求出另一個，然后求出另一個24大素數產生大素數產生 素數生成過程素數生成過程: 隨機選擇一個奇數隨機選擇一個奇數n(如通過偽隨機數發生器如通過偽隨機數發生器) 隨機選擇隨機選擇a, 使使an 進行素性測試進行素性測試(例如用例如用Miller-Rabin算法算法),若若n沒有通沒有通過測試過測試,拋棄拋棄n,轉到轉到 如果通過了足夠次數的測試如果通過了足夠次數的測試,認為認為n是素數是素數,否則轉到否則轉到. 素數理論素數理論: 在在N附近，每附近，每ln(N)個整數中有一個素數個整數中有一個素數25素性測試素性測試

21、素性測試是檢驗一個給定的整數是否為素數的測試。素性測試是檢驗一個給定的整數是否為素數的測試。確定型算法：確定型算法： 試除法：嘗試從試除法：嘗試從2到根號到根號N的整數是否整除的整數是否整除N。 AKS 質數測試：質數測試：PRIMES in P 這篇論文提到的方法，是第一個多項式這篇論文提到的方法，是第一個多項式時間的質數測試算法。時間的質數測試算法。 隨機算法隨機算法 費馬測試：利用費馬小定理來測試。費馬測試：利用費馬小定理來測試。 費馬小定理費馬小定理：如果：如果p是一個素數，且是一個素數，且0ap，則，則a p-11(mod p) 利用費馬小定理，對于給定整數利用費馬小定理，對于給定整

22、數n，可以設計一個素數判定算法，通過計算，可以設計一個素數判定算法，通過計算d=2n-1mod n (a=2)來判定整數來判定整數n的素性。當的素性。當d 1時，時，n肯定不是素數；當肯定不是素數；當d=1時，時，n則很可能是素數，但也可能是合數則很可能是素數，但也可能是合數(滿足費馬小定理的合數被稱作滿足費馬小定理的合數被稱作Carmichael數，前數，前3個是個是561，1105，1729，這種數非常少，這種數非常少，1-100000 000內只有內只有255個個)，為了提高測試的準確性，可用隨機的多次選取，為了提高測試的準確性，可用隨機的多次選取a26素性測試素性測試 Miller-R

23、abin（米勒（米勒-拉賓拉賓 ） 質數測試質數測試 定理定理 如果如果p為大于為大于2的素數，則方程的素數，則方程x21(mod p)的解只有的解只有x1或或x-1。 證明證明 由由x21(mod p)，有，有x2-10(mod p)，(x+1)(x-1) 0(mod p)，因此，因此p|(x+1)或或p|(x-1)或或p|(x+1)且且p|(x-1)。若若p|(x+1)且且p|(x-1)，則存在兩個整數，則存在兩個整數k和和j，使得，使得x+1=kp，x-1=jp兩式相減得兩式相減得2=(k-j)p，為不可能結果。所以有，為不可能結果。所以有p|(x+1)或或p|(x-1)。設。設p|(x

24、+1)，則，則x+1=kp，因此，因此x-1(mod p)，同理若，同理若p|(x-1)，則，則x1(mod p)。27素性測試素性測試 逆否命題：如果方程逆否命題：如果方程x21(mod p)有一解有一解x0 1，-1，那，那么么p不是素數不是素數 例如，考慮方程例如，考慮方程x21(mod 8)，我們有：，我們有：121(mod 8)， 321(mod 8)，521(mod 8)， 721(mod 8)又又5-3(mod 8)， 7-1(mod 8)，所以方程的解為，所以方程的解為1，-1，3，-3，可見，可見8不是素數。不是素數。28素性測試素性測試Miller-Rabin算法算法WIT

25、NESS(a,n) 設設bkbk-1b0是是(n-1)的二進制的二進制表示表示 d1 for ik downto 0 do xd d(d d) mod n if (d=1 & x 1 & x n-1) return TRUE if (bi=1) then d(d a) mod n if (d 1) return TRUE else return FALSE如返回如返回TRUE，說明，說明n不是素數。不是素數。29素性測試素性測試 For循環結束后，有循環結束后，有d an-1(mod n)，由，由費馬定理知，若費馬定理知，若n為為素數，則素數，則d為為1。因此若。因此若d 1，則，則n不為素數

26、，所以返回不為素數，所以返回false。 因為因為n-1-1(mod n)，所以，所以(x 1)and(x n-1)意指意指x21(mod n)有不在有不在-1,1中的根，因此中的根，因此n不為素數，返回不為素數，返回false。 該算法具有以下性質：對該算法具有以下性質：對s個不同的個不同的a，重復調用這一算法，只，重復調用這一算法，只要有一次算法返回要有一次算法返回false，就可以肯定，就可以肯定n不是素數。如果算法每不是素數。如果算法每次返回都為次返回都為true，則，則n是素數的概率至少為是素數的概率至少為1-2-s。因此，對于。因此，對于足夠大的足夠大的s，就可以非?？隙ǖ叵嘈牛?/p>

27、可以非?？隙ǖ叵嘈舗為素數為素數30RSA加密過程舉例加密過程舉例31舉例舉例 取兩個質數取兩個質數p=11，q=13，p和和q的乘積為的乘積為n=pq=143，算出另一個數算出另一個數z=(p-1)(q-1)=120；再選取一個與；再選取一個與z=120互質的數，例如互質的數，例如e=7，則公開密鑰，則公開密鑰=（n，e）=（143，7）。）。 對于這個對于這個e值，可以算出其逆：值，可以算出其逆：d=103。因為。因為ed=7103=721，滿足，滿足ed mod z =1；即；即721 mod 120=1成立。則秘密密鑰成立。則秘密密鑰=（n，d）=（143，103）。）。 32 設張小

28、姐需要發送機密信息（明文）設張小姐需要發送機密信息（明文）m=85給李先生，她給李先生，她已經從公開媒體得到了李先生的公開密鑰（已經從公開媒體得到了李先生的公開密鑰（n，e）=（143，7），于是她算出加密值：），于是她算出加密值： c= me mod n=857 mod 143=123并發送給李先生。并發送給李先生。 李先生在收到密文李先生在收到密文c=123后，利用只有他自己知道的秘密后，利用只有他自己知道的秘密密鑰計算：密鑰計算：m= cd mod n =123103 mod 143=85，所以，所以，李先生可以得到張小姐發給他的真正的信息李先生可以得到張小姐發給他的真正的信息m=85，

29、實現，實現了解密。了解密。33RSA 算法的安全性算法的安全性 攻擊方法攻擊方法 蠻力攻擊：對所有密鑰都進行嘗試蠻力攻擊：對所有密鑰都進行嘗試 數學攻擊：等效于對兩個素數乘積（數學攻擊：等效于對兩個素數乘積（n）的因子分解）的因子分解 大數的因子分解是數論中的一個難題大數的因子分解是數論中的一個難題十進制數字位數近似比特數得到的數據MIPS年100332199171103651992751203981993830129428199450001304311996500因子分解的進展34RSA 算法的安全性算法的安全性 就目前的計算機水平用就目前的計算機水平用1024位的密鑰是安全的，位的密鑰是安

30、全的，2048位是絕對安全的。位是絕對安全的。RSA實驗室認為，實驗室認為，512位位的的n已不夠安全，應停止使用，現在的個人需要用已不夠安全，應停止使用，現在的個人需要用668位的位的n，公司要用，公司要用1024位的位的n，極其重要的場，極其重要的場合應該用合應該用2048位的位的n。 35RSA 算法的性能算法的性能 速度速度 軟件實現比軟件實現比DES慢慢100倍倍 硬件實現比硬件實現比DES慢慢1000倍倍8位公開密鑰的位公開密鑰的RSA的的加密速度加密速度512位位768位位1024位位加密（秒）加密（秒）0.030.050.08解密（秒）解密（秒）0.160.480.93簽名（秒

31、）簽名（秒）0.160.520.97驗證（秒）驗證（秒）0.020.070.0836對公鑰密碼算法的誤解對公鑰密碼算法的誤解 公開密鑰算法比對稱密鑰密碼算法更安全公開密鑰算法比對稱密鑰密碼算法更安全 任何一種算法都依賴于任何一種算法都依賴于密鑰長度密鑰長度、破譯密碼的工作量，從抗、破譯密碼的工作量，從抗分析角度，沒有一方更優越分析角度，沒有一方更優越 公開密鑰算法使對稱密鑰成為過時了的技術公開密鑰算法使對稱密鑰成為過時了的技術 公開密鑰很慢，主要用在密鑰管理和數字簽名，對稱密鑰密公開密鑰很慢，主要用在密鑰管理和數字簽名，對稱密鑰密碼算法將長期存在碼算法將長期存在 使用公開密鑰加密，密鑰分配變得

32、非常簡單使用公開密鑰加密，密鑰分配變得非常簡單 事實上的密鑰分配既不簡單，也不有效事實上的密鑰分配既不簡單，也不有效 公認的有效方法是通過密鑰分配中心公認的有效方法是通過密鑰分配中心KDC來管理和分配公開來管理和分配公開密鑰。密鑰。37簽名方案一般地都是對一個較短的消息簽名，對一個很長的消息，簽名方案一般地都是對一個較短的消息簽名，對一個很長的消息，如果直接處理，則首先要把它分割成較短的段，再進行簽名。顯如果直接處理，則首先要把它分割成較短的段，再進行簽名。顯然，用這種方法簽名一個幾兆的文件是不合適的。然，用這種方法簽名一個幾兆的文件是不合適的。解決這一問題的方法：對被簽名消息用一個快速散列函

33、數產生一解決這一問題的方法：對被簽名消息用一個快速散列函數產生一個確定長度的消息摘要，比如：個確定長度的消息摘要，比如：160比特，最后對這個摘要簽名。比特，最后對這個摘要簽名。所謂散列函數是：從一個消息空間到另一個消息空間的一個映射，所謂散列函數是：從一個消息空間到另一個消息空間的一個映射，這是一個多一對應，可能出現不同消息對應于相同散列值的情形，這是一個多一對應，可能出現不同消息對應于相同散列值的情形，這一現象稱為碰撞這一現象稱為碰撞散散 列列 (hash)函函 數數38散散 列列 (hash)函函 數數無碰撞散列函數無碰撞散列函數: 對應用散列函數的數字簽名的一個可能攻擊方法是尋找一個碰

34、撞：對給對應用散列函數的數字簽名的一個可能攻擊方法是尋找一個碰撞：對給定的簽名消息定的簽名消息(x,y)，y=sigk(h(x)，如果找到一個消息，如果找到一個消息x x，h(x)=h(x)， 則則(x,y)成為一個偽造簽名。為了阻止這種攻擊，無碰撞成為一個偽造簽名。為了阻止這種攻擊，無碰撞散列函數是必須的。散列函數是必須的。弱無碰撞散列函數弱無碰撞散列函數: 對于給定消息對于給定消息x，在計算上幾乎找不到另一個消息在計算上幾乎找不到另一個消息x x，使得，使得h(x)= h(x) ；強無碰撞散列函數：強無碰撞散列函數： 在計算上幾乎不可能找到兩個消息在計算上幾乎不可能找到兩個消息x x，使得

35、，使得 h(x)=h(x)；單向散列函數單向散列函數： 對于給定的一個消息摘要（散列值）對于給定的一個消息摘要（散列值）z，找到一個消息找到一個消息x，滿足滿足h(x)=z是計算上不可能的；是計算上不可能的；39散散 列列 (hash)函函 數數 強無碰撞性包含弱無碰撞、單向性。強無碰撞性包含弱無碰撞、單向性。 MD4，MD5散列函數散列函數：1990年，年，Rivest提出了提出了散列函數散列函數MD4（Message Digest） ，MD4輸入輸入任意長度消息，輸出任意長度消息，輸出128比特消息摘要，它是一個比特消息摘要，它是一個強無碰撞強無碰撞散列函數。散列函數。1992年年Rive

36、st提出改進算法提出改進算法MD5，它比，它比MD4復雜，但思想類似。復雜，但思想類似。40MD5算法算法 輸入：任意長度的消息輸入：任意長度的消息 輸出：輸出：128位消息摘要位消息摘要 處理：以處理：以512位輸入數據塊為單位位輸入數據塊為單位41MD5步驟步驟第一步：消息填充第一步：消息填充 補長到補長到512的倍數的倍數 最后最后64位為消息長度（填充前的長度）的低位為消息長度（填充前的長度）的低64位（如果消息長大于位（如果消息長大于264，則以，則以264為模數取模）為模數取模） 一定要補長一定要補長(64+1512)，內容為，內容為1000（如若消息長（如若消息長448，則填充，

37、則填充512+64）第二步第二步 把結果分割為把結果分割為512位的塊：位的塊：Y0，Y1，YL-1（每一個有（每一個有16個個32比特長字）比特長字）第三步第三步 初始化初始化MD buffer，128位常量位常量(4個個32bit字字)，進入循環迭代，共，進入循環迭代，共L次次 每次：一個輸入每次：一個輸入128位，另一個輸入位，另一個輸入512位，結果輸出位，結果輸出128位，用于下一輪輸位，用于下一輪輸入入第四步第四步 最后一步的輸出即為散列結果最后一步的輸出即為散列結果128位位42MD5: 示意圖示意圖43MD5的每一步運算的每一步運算 將將512位的明文分成位的明文分成16份，每

38、份為份，每份為32位的子明文分組，位的子明文分組，用用Xk，k=0，1，15表示。表示。 每一步的數據處理都是針對每一步的數據處理都是針對4個個32位記錄單元中數據進行位記錄單元中數據進行的。它們的初始值為：的。它們的初始值為：A=01234567，B=89ABCDEF，C=FEDCBA98，D=76543210。 每一步有每一步有4輪，每一輪又有輪，每一輪又有16小步，共小步，共64個步驟運算后，個步驟運算后，記錄單元記錄單元A、B、C、D中的中的128位即為中間散列值。位即為中間散列值。 每一步的第一輪開始時，將每一步的第一輪開始時，將A、B、C、D復制到另外的記復制到另外的記錄單元錄單元

39、AA、BB、CC、DD中。這中。這4個值將在第個值將在第4輪的最后輪的最后與相關的與相關的A、B、C、D相加。相加。44MD5的每一步運算示意圖的每一步運算示意圖45每一輪中每一輪中16步的每一步運算步的每一步運算 在每一輪的每一小步中，將在每一輪的每一小步中，將A、B、C、D中中3個記個記錄單元中的數據以非線性的操作方式處理，結果再錄單元中的數據以非線性的操作方式處理，結果再與與512位明文分組中的一個位明文分組中的一個32位子明文分組位子明文分組Xk及一個固定數及一個固定數Ti相加。再將結果左循環移位相加。再將結果左循環移位s位，位，再與剩下的單元中的數據相加。最后的再與剩下的單元中的數據

40、相加。最后的32位結果位結果重新存入重新存入A、B、C、D中的一個記錄單元中。中的一個記錄單元中。46每一輪中每一輪中16步的每一步運算結構步的每一步運算結構ABCDABCD+CLSs+gMj=Xkti=Ti47每一輪中每一輪中16步的每一步運算結構步的每一步運算結構Function g g(x,y,z)1 F(x,y,z) (xy)(xz)2 G(x,y,z) (xz)(yz)3 H(x,y,z) xyz4 I (x,y,z) y(xz)設Mj表示消息的第j個分組(0j 15)，s表示循環左移s位，則FF(a,b,c,d,Mj,s,ti)表示a=b+(a+(F(b,c,d)+Mj+ti)s)

41、GG(a,b,c,d,Mj,s,ti)表示a=b+(a+(G(b,c,d)+Mj+ti)s)HH(a,b,c,d,Mj,s,ti)表示a=b+(a+(H(b,c,d)+Mj+ti)s)II(a,b,c,d,Mj,s,ti)表示a=b+(a+(I(b,c,d)+Mj+ti)s)48（A，B，C，D，Xk，S，Ti）49（A，B，C，D，Xk，S，Ti）50關于關于MD5常數常數ti的選擇：的選擇： 在第在第i步中，步中，ti是是232 abs(sin(i)的整數部分，的整數部分，i的單位是弧度。的單位是弧度。生日攻擊生日攻擊 對于單向散列函數有兩種窮舉攻擊方法：對于單向散列函數有兩種窮舉攻擊方法： 給定消息的散列函數給定消息的散列函數H(M)，破譯者逐個生產其他文件，破譯者逐個生產其他文件M，以使，以使H(M)=H(M) 攻擊者尋找兩