《雜湊函數(shù)和數(shù)字簽名.ppt》由會員分享，可在線閱讀，更多相關(guān)《雜湊函數(shù)和數(shù)字簽名.ppt（41頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第6講 雜湊算法和數(shù)字簽名,信息安全概論課程幻燈片,主 要 內(nèi) 容,一、雜湊函數(shù)的概念和基本安全要求 二、MD5雜湊算法 三、數(shù)字簽名,雜湊函數(shù)又稱為Hash函數(shù)、報文摘要函數(shù)、散列函數(shù)等。其目的是將任意長度的報文m都壓縮成指定長度的數(shù)據(jù)H(m) H(m)又稱為m的指紋，代表了消息m的身份。如下圖所示:,一、 雜湊函數(shù)的概念和基本安全需求,長度是固定的，與報文的長度無關(guān),雜湊函數(shù)的用途: (1) 完整性檢驗----利用二元對(m, H(m))的不可更改性實現(xiàn)。 此時，m 的變化將導(dǎo)致 H(m)的變化. (2) 提供文件的指紋.用于數(shù)字簽名。 只要H(m)不可替換,就保證m不可能

2、再更改 (3) 將雜湊值作為密鑰，從而壓縮掉密鑰的冗余度; (4) 偽隨機數(shù)生成.,一、雜湊函數(shù)的概念和基本安全需求(續(xù)),雜湊函數(shù)技術(shù)----優(yōu)缺點,由于報文摘要不包含報文持有者的秘密信息，故雜湊函數(shù)的： 優(yōu)點: 任何人都可對報文的“指紋”進(jìn)行檢驗； 缺點: 掌握報文的人都可生成報文的“指紋” 上述缺點導(dǎo)致當(dāng)將報文及其指紋放在一起時，只能檢驗出對報文無意的修改，不能檢驗出有意的篡改或偽造。,(1) 單向性（第一原像不可求）. 給出一個雜湊值 z，從計算量上講，求出一個m，或者以不可忽略的概率求出一個m ，使得 H(m) = z 成立是不可行的。,雜湊函數(shù)的安全性要求,,在實際上

3、求不出,理論方法：窮舉攻擊,(2) 強無碰撞性. 從計算量上講，求出，或者以不可忽略的概率求出，具有相同雜湊值H(m1) = H(m2)的兩份報文m1和m2是不可行的。,雜湊函數(shù)的安全性要求(續(xù)1),理論方法：(1)窮舉攻擊----固定一個，窮舉另一個 (2)碰撞攻擊 ---- 兩個一起“窮舉”,(3) 求第二原像不可行(弱無碰撞性） 任意給定一個報文m1，找出或者以不可忽略的概率找出另一個報文m2，使得 H(m2) = H(m1) 在計算上不可行。,意義： 將一份報文的指紋偽造成另一份報文的指紋在計算上是不可行的。,預(yù)先固定的,理論方法：(1) 窮舉攻擊（窮舉m2),雜湊

4、函數(shù)的安全性要求(續(xù)2),對雜湊函數(shù)的基本攻擊方法----碰撞攻擊,目的: 構(gòu)造報文m1和報文m2使得H(m1)=H(m2) 生日悖論:20個人的生日互不相同的概率是多少,錯!,正確答案是:,,20個人中至少有兩人生日相同的概率是0.632,是20/365嗎?,?,對雜湊函數(shù)的碰撞攻擊算法,Step1 隨機選取N個報文m1,m2,, mN; Step2 以這N個報文作為雜湊函數(shù)的輸入,計算出相應(yīng)的雜湊值,得到集合 S=(mk, H(mk)): k = 1,2,, N Step3 根據(jù)H(mk)的大小，對集合S利用快速排序算法重新排序。 在排序過程中，如果找到了使H(mk)= H(m

5、t) 的兩個不同元mk和mt，就將(mk,mt)作為結(jié)果輸出，算法終止；如果找不到，就報告碰撞攻擊失敗，算法終止。,碰撞攻擊算法的性能指標(biāo),算法所需的存儲量: 需要存儲表S，以便進(jìn)行快速排序，故存儲復(fù)雜性是表S的規(guī)模O(N),S=(mk, H(mk)): k = 1,2,, N,算法所需的計算量： (1) 該算法生成集合S的計算量是計算N次雜湊函數(shù)； (2) 對集合S快速排序并找出全部碰撞的計算量為 |N|log2|N| 次比較。 故總的計算量為 N + |N|log2|N| = O(N),碰撞攻擊算法的性能指標(biāo),特別地，當(dāng) 時，碰撞攻擊的成功率近似為,成功率分析： 定理1

6、 設(shè)雜湊值為n比特且N遠(yuǎn)小于2n,則碰撞攻擊的成功率近似為,特例：如果n = 64,則 N1.4232 = 5.6G，此時碰撞攻擊算法可實現(xiàn)。,是存儲復(fù)雜性和計算復(fù)雜性,表S=(mk, H(mk)): k = 1,2,, N的規(guī)模,攻擊能力,能夠?qū)古鲎补舻?雜湊函數(shù)的安全界限,如果對抗窮舉攻擊的能力的密鑰長度的安全界限為 n 比特，則對抗碰撞攻擊的雜湊算法的雜湊值的比特數(shù)的安全界限應(yīng)為 2n 。,1. MD強化技術(shù)(Merkle-Damaard強化) 將消息M = (M1,M2,,Mn)的最后一個分組Mn設(shè)置為“真正消息”的長度，這個過程稱為MD強化。,二、基于分組密碼設(shè)計的雜湊函數(shù),2

7、. 迭代型雜湊函數(shù),一個迭代雜湊函數(shù)H(H0,M)是由一個容易計算的函數(shù)h(x,y)確定的一個雜湊函數(shù)H,其中 h: 0,1m :0,1t 0,1m 雜湊函數(shù)對給定的初始值H0, 遞歸地計算Hi=h(Hi-1,Mi),從而將報文M = (M1,M2,,Mn)雜湊到雜湊值Hn。 特別地,選取h=E(x,k)是一個安全的分組密碼,則當(dāng)將消息經(jīng)MD強化后,就得到一個安全的雜湊函數(shù)。,新的報文塊Mi的輸入位置是密鑰的位置!,被雜湊的消息必須經(jīng)過MD強化!,圈函數(shù)為 Hi = h(Hi-1, Mi) Hi-1,3. DM雜湊函數(shù)模型(Davies--Meyer方案),,函數(shù)h,Hi-1,,Hi,,

8、,Mi,,,初值H0： 是固定的常數(shù),被雜湊的消息必須經(jīng)過MD強化!,特例：取 h(Hi-1, Mi) = DESMi(Hi-1) 此時：消息是56比特為一塊，雜湊值是64比特,,,,,,三、MD5算法,MD4 是Ron Rivest 于1990年設(shè)計的，MD5是MD4的改進(jìn)形式。二者的設(shè)計思想思想相似。 MD5的特點： 對任意長度的輸入，都產(chǎn)生128位的輸出；其安全性不依賴于任何假設(shè)，適合高速實現(xiàn)。,三、MD5算法,MD5的安全分析現(xiàn)狀： 2004年夏，山東大學(xué)的王小云宣布找到使MD5的雜湊值相同的兩個報文，這兩個報文的差是一個特殊的值，但沒有公開構(gòu)造方法。 之后，王小云教授公

9、布了她的方法。人們后來發(fā)現(xiàn)，找出MD5的一個碰撞在PC機是非常容易的事情。 由于能產(chǎn)生碰撞的報文未必有實際的意義，而且按王小云的方法構(gòu)造的兩個報文都不能人為地控制，因而該攻擊并不對MD5造成實際的威脅。,方法：設(shè)原始報文x的長度是L比特. (1) 求出d0，使得L+1+d+64是512的倍數(shù)； (2) 在原始報文x后面先添加一個1，,MD5 算法第一步: 消息填充,目的:使MD強化后報文長度是512的整數(shù)倍,x,||1,|| 0d,||L,擴充后的報文 =,然后添加d個0，,最后將消息的長度L用64比特表示，加在最后。,(L+1+d+64)mod512 = 0,d = (L65)mod512

10、,由,,MD5 填充的例子,設(shè)x是具有 20768比特的長信息，則 d =( L65)mod512 =(20768 65)mod512 =20833mod512 =(40512+353)mod512 =353mod512 = 512353 = 159 故應(yīng)在x后面添加一個 1和159個0，最后再添加原始消息長度20768的64位表示。,MD5使用的編碼變換,逐位模2加運算： x y,逐位取補運算：,模232位加運算：x + y,循環(huán)左移s位: x <<< s,四個密碼變換:,面向32字設(shè)計----全部采用32位字的運算,

11、逐位與運算：x y 逐位或運算：x y,X,Y,Z都是32位字,MD5 初始化變量,(1) MD5的迭代函數(shù)一次處理512比特報文塊 (2) 512比特報文塊分為16個32比特字。 (3) N個32比特字共分為T = N/16個512比特塊 (4) 首先初始化MD5的4個變量(A, B, C, D), 每個變量 32 位。4 個變量分別取初始值如下（16進(jìn)制表示）：,記M = M0M1MN-1是M的32位字表示。,MD5 的主算法,圈函數(shù)模型: Hi = h(Hi-1,Mi) Hi-1.其中Hi-1=(A,B,C,D), h由round1,round2,round3和round4組成.,DM模

12、型,具體過程:對i=0至N/16-1,依次執(zhí)行以下步驟： // N/16是512比特塊的個數(shù) Step1 執(zhí)行X0M16i, X1M16i+1,, X15M16i+15 // 16是512比特塊中32位字的個數(shù),一次處理16個32比特塊 Step2 暫存(A,B,C D),即執(zhí)行: AAA, BBB,CCC,DDD Step3 執(zhí)行: (A,B,C D) Round1(A,B,C D,X0,, X15) Step4 執(zhí)行: (A,B,C D) Round2(A,B,C D,X0,, X15) Step5 執(zhí)行: (A,B,C D) Round3(A,B,C D,X0,, X15) S

13、tep7 執(zhí)行: (A,B,C D) Round4(A,B,C D,X0,, X15) Step6 執(zhí)行: (A,B,C D) (A,B,C D) +(AA,BB,CC, DD),函數(shù)Round 1的結(jié)構(gòu): 用 a b c d i s t 表示運算 a (b+a + f(b,c,d) + Mi+ti) <<< s). (僅替換a),則Round1依次執(zhí)行下述16層運算: (執(zhí)行完左邊8列,再 執(zhí)行右邊8列),A B C D 0 7 t1 A B C D 8 7 t9 D A B C 1 12 t2 D A B C 9 12 t10 C D A B 2 17 t3 C D A B

14、 10 17 t11 B C D A 3 22 t4 B C D A 11 22 t12 A B C D 4 7 t5 A B C D 12 7 t13 D A B C 5 12 t6 D A B C 13 12 t14 C D A B 6 17 t7 C D A B 14 17 t15 B C D A 7 22 t8 B C D A 15 22 t16,ti是232abs((sin i))的整數(shù)部分.,函數(shù)Round 2的結(jié)構(gòu): 用 a b c d i s t表示運算 a (b+a + g(b,c,d) + Mi+ti) <<< s) (僅替換a),A B C D 1

15、5 t17 A B C D 9 5 t25 D A B C 6 9 t18 D A B C 14 9 t26 C D A B 11 14 t19 C D A B 3 14 t27 B C D A 0 20 t20 B C D A 8 20 t28 A B C D 5 5 t21 A B C D 13 5 t29 D A B C 10 9 t22 D A B C 2 9 t30 C D A B 15 14 t23 C D A B 7 14 t31 B C D A 4 20 t24 B C D A 12 20 t32,ti是232abs((sin i))的整數(shù)部分.,則R

16、ound2先執(zhí)行左8列,再執(zhí)行右8列: (僅替換a),函數(shù)Round 3的結(jié)構(gòu): 用 a b c d i s t 表示運算 a (b+a + h(b,c,d) + Mi+ti) <<< s) (僅替換a),A B C D 5 4 t33 A B C D 13 4 t41 D A B C 8 11 t34 D A B C 0 11 t42 C D A B 11 16 t35 C D A B 3 16 t43 B C D A 14 23 t36 B C D A 6 23 t44 A B C D 1 4 t37 A B C D 9 4 t45 D A B C 4 1

17、1 t38 D A B C 12 11 t46 C D A B 7 16 t39 C D A B 15 16 t47 B C D A 10 23 t40 B C D A 2 23 t48,ti是232abs((sin i))的整數(shù)部分.,則Round3先執(zhí)行左8列,再執(zhí)行右8列:,函數(shù)Round 4的結(jié)構(gòu): 用 a b c d i s t 表示運算 a (b+a + I(b,c,d) + Mi+ti) <<< s) (僅替換a),A B C D 0 6 t49 A B C D 2 6 t57 D A B C 7 10 t50 D A B C 15 10 t58 C

18、D A B 14 15 t51 C D A B 6 15 t59 B C D A 5 21 t52 B C D A 13 21 t60 A B C D 12 6 t53 A B C D 4 6 t61 D A B C 3 10 t54 D A B C 11 10 t62 C D A B 10 15 t55 C D A B 2 15 t63 B C D A 1 21 t56 B C D A 9 21 t64,ti是232abs((sin i))的整數(shù)部分.,則Round3先執(zhí)行左8列,再執(zhí)行右8列:,山東大學(xué)的王小云教授構(gòu)造出的MD5的具有修改起點、指定模2和的

19、一類碰撞為: 起點: (與實際的MD5的初始值不同) A取: 0 x01234567 B取: 0 x89abcd4f C取: 0 xfedcba98 D取: 0 x76543210 明文1: (M, N )為1024比特，M, N均為512比特,其中:,明文2: 也是1024比特, 均為512比特,這里每個數(shù)都是32比特數(shù)。其中非零值位于從左邊數(shù)、從序號0起算第4,11,14位置。,雜湊函數(shù)SHA背景介紹,SHA (Secure Hash Algorithm) 是美國國家標(biāo)準(zhǔn)技術(shù)研究所（NIST）與美國國家安全局共同設(shè)計的。 1992年1月31日SHA在聯(lián)邦記錄

20、中公布。 1992年5月11日起采納為國家標(biāo)準(zhǔn)(SHS)。 1994年7月11日作了一個小的修改，1995年4月17日公布了修改后的版本，稱為SHA-1。 此后又陸續(xù)公布了SHA的各種版本.,數(shù)字簽名技術(shù),手工簽名的目的和作用,(1) 表示簽名者對消息的認(rèn)可； (2) 其他人可以識別和驗證出是誰的簽名； (3)其他人無法偽造和更改簽名，即 (A) 無法憑空偽造出一個簽名； (B) 對一個文件的簽名不能復(fù)制或篡改成對另一個文件的簽名； (4) 可仲裁性：出現(xiàn)爭議時第三方可仲裁. 仲裁的內(nèi)容: (A) 是否是簽名者在抵賴、否認(rèn)其簽名； (B) 簽名是

21、否是偽造的。,手工簽名的目的和作用（續(xù)）,簽名的實現(xiàn)方式： 就是在原文件上追加一定的筆跡信息，并使二者形成一個整體。 對電子文檔的簽名也應(yīng)達(dá)到同樣的目的。,如何才能達(dá)到簽名的目的?,(1) 簽名者對消息進(jìn)行某種變換完成簽名; (2) 識別和驗證: 利用簽名者的公開信息(簽名識別密鑰)和文件的公開性; (3) 它人不能偽造簽名: 簽名應(yīng)與簽名者獨有的秘密信息(簽名密鑰)密切相關(guān); (4) 可仲裁性: 靠法律解決.簽名者的簽名識別密鑰應(yīng)由可信的第三方的確認(rèn)、公布和認(rèn)可解決. 法律介入: ----兩個中心: (1) 發(fā)證中心(發(fā)布簽名識別密鑰); (2) 認(rèn)證中心(仲裁

22、中心)。,數(shù)字簽名方案的分類 (1) 利用特殊的公鑰加密算法實現(xiàn)。 并非所有的公鑰加密算法都能實現(xiàn)數(shù)字簽名，只有滿足,(2) 利用專用的數(shù)字簽名算法實現(xiàn)。 例如： EIGamal數(shù)字簽名方案,的公鑰加密算法的才能實現(xiàn)數(shù)字簽名。 其中D是脫密算法，E是加密算法。,數(shù)字簽名的一般過程,,報文摘要,,,對摘要的簽名,,公布,簽名者的身份,如果兩份文件的雜湊值相同，則這兩份文件的數(shù)字簽名一定相同。,,設(shè)計方法：用戶Alice將其私鑰 kd 作為她的簽名密鑰，將對應(yīng)的公鑰 ke 作為簽名識別密鑰；,基于公鑰加密算法的數(shù)字簽名方案,用戶Alice對文件m的簽名過程： (1) Alice選擇一個

23、安全的雜湊函數(shù)Hash(x)；,(3) 簽名者Alice將文件m及其簽名sign(m)一起公布。,(2) Alice利用簽名密鑰kd對Hash(m)執(zhí)行脫密變換D，得到Alice對文件m的簽名,基于公鑰加密算法的數(shù)字簽名方案,第三方的仲裁: 與簽名識別過程相同.,用戶B對簽名的識別過程： 利用用戶A的簽名識別密鑰ke對簽名sign(m)執(zhí)行加密變換D,,若它與m相等，則判斷Sign(m)是用戶A對文件m的簽名；否則判斷Sign(m)不是用戶A對文件m的簽名.,Hash(m),判斷依據(jù):,公開密鑰,,基于RSA公鑰加密算法的數(shù)字簽名方案,數(shù)字簽名實例: 設(shè)RSA算法為:,用戶Alice的RSA

24、密鑰為： 公開密鑰：(e, n) =(7, 33) 秘密密鑰：(d, n) =(3, 33),Sign(m)e mod n,221mod33,(210)22mod33, (1024)22mod33,(1024mod33)22mod33, (31331)mod3322mod33,2mod33 2,已知消息m的雜湊值是3，判斷8是否是Alice對消息m的簽名,由于Alice的公開密鑰是 (e, n) =(7, 33)，且,Sign(m) = 8,,87mod33,3 Hash(m),,8不是Alice對消息m的簽名,1985年由T.EIGamal提出,是專用的數(shù)字簽名方案，其安全性基于有限域上的離

25、散對數(shù)問題的難解性。,EIGamal數(shù)字簽名方案,上述過程與EIGamal加密算法相同過程,用戶A的設(shè)計過程： (1) 選取大素數(shù)p和Z/(p)中的本原元g,將p和g公開; (2) 隨機選取整數(shù)x:1xp-2,計算y=gxmodp，并將y作為公開的簽名識別密鑰，將x作為保密的簽名密鑰。,簽名過程: 設(shè)mZ/(p)0是待簽文件.用戶A秘密地隨機選取整數(shù)k:1kp-2,計算sign(m)=(r,),其中 r=gk modp, =(m-xr)k-1 mod(p-1) 將(m,sign(m))公布,并清除k.,x為私鑰, y=gxmodp為公鑰.,驗證過程: 對于(m,sign(m)),如果yrrmodp = gmmodp,則接受簽名,否則不承認(rèn)簽名。,驗證依據(jù): 注意： 涉及的都是g的指數(shù) yrrmodp = (gx)r(gk)modp= gxr-kmodp = g(xr-k)mod(p-1)modp = gxr-(m-xr)mod(p-1)modp = gmmodp,,,如果不知道x,也不知道k,就造不出,因而簽名無法偽造.若能解決離散對數(shù)問題,就能偽造簽名.,EIGamal數(shù)字簽名方案（續(xù)）,