3.2消息摘要和數(shù)字簽名ppt課件

1、消息摘要和數(shù)字簽名消息摘要和數(shù)字簽名主講人：裴士輝主講人：裴士輝e_mail: shihui_pei sina息摘要和消息摘要和hash 函數(shù)函數(shù)消息摘要消息摘要單向散列函數(shù)單向散列函數(shù)安全散列標(biāo)準(zhǔn)安全散列標(biāo)準(zhǔn)SHS其他的單向散列函數(shù)其他的單向散列函數(shù)消息摘要消息摘要對(duì)任意長(zhǎng)度的明文對(duì)任意長(zhǎng)度的明文m，經(jīng)由哈希函數(shù)，經(jīng)由哈希函數(shù)(雜湊函數(shù)雜湊函數(shù))h產(chǎn)生固定長(zhǎng)度的哈希值產(chǎn)生固定長(zhǎng)度的哈希值h(m)，用來對(duì)明文作鑒別，用來對(duì)明文作鑒別(authentication)或數(shù)字簽名或數(shù)字簽名(digital signature)。哈希函數(shù)值是對(duì)明文的一種哈希函數(shù)值是對(duì)明文的一

2、種“指紋指紋”(finger print)或是摘要或是摘要(digest)。對(duì)哈希函數(shù)值的數(shù)字簽名，就是對(duì)此明文的數(shù)字對(duì)哈希函數(shù)值的數(shù)字簽名，就是對(duì)此明文的數(shù)字簽名，可以用來提高數(shù)字簽名的效率。簽名，可以用來提高數(shù)字簽名的效率。單向散列函數(shù)單向散列函數(shù) x = h (m) 使用在數(shù)字簽名上的哈希函數(shù)必須滿足：對(duì)任意長(zhǎng)度的明文m，產(chǎn)生固定長(zhǎng)度的哈希值h(m)；對(duì)任意的明文m，哈希函數(shù)值h(m)可由硬件或軟件容易得到；對(duì)任意哈希函數(shù)值x，要找到一個(gè)明文m與之對(duì)應(yīng)， 即x = h(m)，在計(jì)算上不可行；對(duì)一個(gè)明文m1，要找到另一個(gè)不同的明文m2，使之具有相同的哈希值,即h(m1) = h(m2)，在

3、計(jì)算上不可行；要找到任意一對(duì)不同的明文(m1, m2)，具有相同的哈希值，即h(m1) = h(m2)，在計(jì)算上不可行。安全散列標(biāo)準(zhǔn)安全散列標(biāo)準(zhǔn)SHS2019由美國由美國NIST提出，提出，SHS(Secure Hash Standard)，算法為，算法為SHA。要求輸入小于要求輸入小于264位，位，輸出為輸出為160位位(5個(gè)寄存器，個(gè)寄存器，A, B, C, D, E)。將明文分成若干將明文分成若干512位的定長(zhǎng)塊，每一塊與當(dāng)前的信位的定長(zhǎng)塊，每一塊與當(dāng)前的信息摘要值結(jié)合，產(chǎn)生信息摘要的下一個(gè)中間結(jié)果，直息摘要值結(jié)合，產(chǎn)生信息摘要的下一個(gè)中間結(jié)果，直到處理完畢。到處理完畢。SHA的運(yùn)算過程

4、的運(yùn)算過程將消息填充為將消息填充為512位的整數(shù)倍位的整數(shù)倍5個(gè)個(gè)32位中間變量位中間變量a b c d e,起初值為常數(shù)起初值為常數(shù)對(duì)對(duì)5個(gè)個(gè)32位的寄存器位的寄存器A、B、C、D、E,進(jìn)行運(yùn)算進(jìn)行運(yùn)算 A B C D E的初值為的初值為0對(duì)每一個(gè)對(duì)每一個(gè)512位的消息進(jìn)行如下處理：位的消息進(jìn)行如下處理： 將中間變量將中間變量a b c d e 賦給賦給A B C D E； 進(jìn)行主循環(huán)進(jìn)行主循環(huán) 四輪，每輪四輪，每輪20次次 a=a+A, b=b+B,c=c+C,d=d+D, e=e+e最后輸出為最后輸出為a b c d e 的級(jí)聯(lián)的級(jí)聯(lián)a,b,c,d,e的初值的初值 a=0 x674523

5、01 b=0 xefcdab89 c=0 x98badcfe d=0 x10325476 e=0 xc3d2e1f0Ei-1Di-1Ci-1Bi-1Ai-1EiDiCiBiAi非線性函數(shù)非線性函數(shù)f305 FtWt Kt非線性函數(shù)非線性函數(shù)FFt(x,y,z)=(x&y)|（x&z） 0=t20Ft(x,y,z)=xyz 20=t40Ft(x,y,z)=(xy)|（xz）|(yz) 40=t60Ft(x,y,z)=xyz 60=t80Kt:常數(shù)常數(shù)Kt=0 x5a827999 0=t20Kt=0 x6ed9eda1 20=t40Kt=0 x8f1bbcdc 40=t60Kt=0

6、 xca62c1d6 60=t80Wt:消息的變形消息的變形消息：消息：512bit,16個(gè)個(gè)32bit字字 M0M15 Wt: 32bit字字 0=t=15 Wt=Mt 16=t=79 Wt=(Wt-3Wt-8Wt-14Wt-16)1其他的單向散列函數(shù)其他的單向散列函數(shù)RIPEMD-160 歐洲歐洲RIPE項(xiàng)目的結(jié)果項(xiàng)目的結(jié)果 RIPEMD為為128位位 更新后成為更新后成為RIPEMD-160 基礎(chǔ)是基礎(chǔ)是MD5MD5 Ron Rivest于于1990年提出年提出MD4 1992年年, MD5 (RFC 1321) developed by Ron Rivest at MIT MD5把數(shù)據(jù)

7、分成把數(shù)據(jù)分成512-bit塊塊 MD5的的hash值是值是128-bit 在最近數(shù)年之前在最近數(shù)年之前,MD5是最主要的是最主要的hash算法算法 現(xiàn)行美國標(biāo)準(zhǔn)現(xiàn)行美國標(biāo)準(zhǔn)SHA-1以以MD5的前身的前身MD4為基礎(chǔ)為基礎(chǔ)王小云對(duì)王小云對(duì)MD5的攻擊的攻擊方法：方法： 差分攻擊差分攻擊 模整數(shù)減法模整數(shù)減法 異或運(yùn)算異或運(yùn)算王小云對(duì)王小云對(duì)MD5的攻擊的攻擊目的：尋找如下條件的消息：目的：尋找如下條件的消息：(a, b, c, d) = MD5(a0, b0, c0, d0,M0),(a, b, c, d) = MD5(a0, b0, c0, d0,M0 ),MD5(a, b, c, d,M

8、1) = MD5(a, b, c, d,M1 )2019年的攻擊結(jié)果年的攻擊結(jié)果找到找到(M0,M0 )需要需要 239 次次MD5操作操作, IBM P690上上需要時(shí)間需要時(shí)間15分到分到1小時(shí)小時(shí)找到找到 (M1,M1)需要需要 232 次次MD5操作操作, IBM P690上上需要時(shí)間需要時(shí)間5分到分到15分分The Story of Alice and her Boss Caesars View At the day Alice is supposed to leave, Caesar writes a letter of recommendation for Alice - on

9、paper. The same day, she asks Caesar to digitally sign the letter. For his convenience she presents an electronic copy of the document. Caesar opens the document - it looks exactly like the original document. So he signs the document. Months later, Caesar discovers that there has been a breach of se

10、crecy with his French affair files. Will he ever find out who tricked him and how? The Story of Alice and her Boss Alices View Being an intern, Alice does not have any access to secret documents. Not enough for her . . tricky Alice decides to fool Caesar. Because Caesar is still relying on the widel

11、y used MD5 hash function, she implements the attack from Wang and Yu How to break MD5 and other hash functions. Eurocrypt 2019 to find MD5 collisions. When she receives her letter of recommendation (on paper), she prepares two postscript files with the same MD5 hash: One to display the letter of rec

12、ommendation, and a second one, an order from Caesar to grant Alice some kind of a security clearance. The Story of Alice and her Bossa25f7f0b 29ee0b39 68c86073 8533a4b9 a25f7f0b 29ee0b39 68c86073 8533a4b9 數(shù)字簽名數(shù)字簽名 數(shù)字簽名是手寫簽名的數(shù)字相似物。消息的數(shù)字簽數(shù)字簽名是手寫簽名的數(shù)字相似物。消息的數(shù)字簽名其實(shí)是一個(gè)數(shù)值，它依賴于只有簽名者知道的某名其實(shí)是一個(gè)數(shù)值，它依賴于只有簽名者知道

13、的某個(gè)秘密數(shù)和待簽的消息內(nèi)容。數(shù)字簽名應(yīng)具有如下個(gè)秘密數(shù)和待簽的消息內(nèi)容。數(shù)字簽名應(yīng)具有如下性質(zhì)性質(zhì)能夠驗(yàn)證簽字產(chǎn)生者的身份，以及產(chǎn)生簽字的日期能夠驗(yàn)證簽字產(chǎn)生者的身份，以及產(chǎn)生簽字的日期和時(shí)間。和時(shí)間。能用于證實(shí)被簽消息的內(nèi)容。能用于證實(shí)被簽消息的內(nèi)容。數(shù)字簽字可由第三方驗(yàn)證，從而能夠解決通信雙方數(shù)字簽字可由第三方驗(yàn)證，從而能夠解決通信雙方的爭(zhēng)議。的爭(zhēng)議。數(shù)字證書的用途包括認(rèn)證、數(shù)據(jù)完整性和不可抵賴數(shù)字證書的用途包括認(rèn)證、數(shù)據(jù)完整性和不可抵賴性。而它最重要的一個(gè)應(yīng)用是數(shù)字證書。性。而它最重要的一個(gè)應(yīng)用是數(shù)字證書。數(shù)字簽名法數(shù)字簽名法 美國的猶他州于美國的猶他州于20192019年頒布的年頒布

14、的 是全世是全世界范圍內(nèi)第一部全面規(guī)范電子簽名的法律。美國界范圍內(nèi)第一部全面規(guī)范電子簽名的法律。美國20002000年開始實(shí)行年開始實(shí)行 數(shù)字簽名法，數(shù)字簽名法具有法數(shù)字簽名法，數(shù)字簽名法具有法律效率。美國目前已經(jīng)建立了覆蓋全國的律效率。美國目前已經(jīng)建立了覆蓋全國的PKIPKI網(wǎng)絡(luò)，網(wǎng)絡(luò)，聯(lián)邦、州和大型企業(yè)之間的聯(lián)邦、州和大型企業(yè)之間的PKIPKI實(shí)現(xiàn)了橋接。實(shí)現(xiàn)了橋接。 歐洲各國已經(jīng)建立了自己的歐洲各國已經(jīng)建立了自己的PKIPKI。20192019年歐盟建立了年歐盟建立了橋接的橋接的CACA，20192019年歐盟開始實(shí)行年歐盟開始實(shí)行 數(shù)字簽名法。數(shù)字簽名法。 亞洲范圍內(nèi)的日本、韓國和新加

15、坡在亞洲范圍內(nèi)的日本、韓國和新加坡在PKIPKI建設(shè)方面起建設(shè)方面起步較早，這步較早，這3 3個(gè)國家目前已經(jīng)實(shí)現(xiàn)了交叉認(rèn)證。個(gè)國家目前已經(jīng)實(shí)現(xiàn)了交叉認(rèn)證。數(shù)字簽名法數(shù)字簽名法 我國的立法從我國的立法從20192019年開始的，形成了年開始的，形成了 中華人民共和中華人民共和國電子簽名法國電子簽名法( (草案草案) )。 20192019年年8 8月月2828日中華人民共和國第十屆全國人民代表日中華人民共和國第十屆全國人民代表大會(huì)常務(wù)委員會(huì)第十一次會(huì)議通過了大會(huì)常務(wù)委員會(huì)第十一次會(huì)議通過了 中華人民共和中華人民共和國電子簽名法國電子簽名法 20192019年年4 4月月1 1日起施行。日起施行。

16、Hash()簽名算法簽名算法Alice 私鑰私鑰發(fā)送方：發(fā)送方： Alice用用RSA算法進(jìn)行數(shù)字簽名算法進(jìn)行數(shù)字簽名Hash()驗(yàn)證算法驗(yàn)證算法Alice 公鑰公鑰?=用用RSA算法進(jìn)行身份驗(yàn)證算法進(jìn)行身份驗(yàn)證數(shù)字簽名標(biāo)準(zhǔn)數(shù)字簽名標(biāo)準(zhǔn) 公布于1994年5月19日的聯(lián)邦記錄上， 并于1994年12月1日采納為標(biāo)準(zhǔn)DSS DSS為EIGamal簽名方案的改進(jìn)。DSA的參數(shù)的參數(shù)參數(shù)參數(shù) p: 512位到位到1024位的素?cái)?shù)可有一組用戶共享）位的素?cái)?shù)可有一組用戶共享） q: 160位長(zhǎng)，位長(zhǎng)，p-1的素因子的素因子 (可有一組用戶共享可有一組用戶共享) g=h(p-1)/q mod p, 其中其中

17、h是一整數(shù)是一整數(shù),1h(p-1)公開密鑰公開密鑰 y=gx mod p （一個(gè)（一個(gè)p位的數(shù)）位的數(shù)）私人密鑰：私人密鑰： xq (一個(gè)一個(gè)160位的數(shù)位的數(shù))DSA的簽名和驗(yàn)證的簽名和驗(yàn)證簽名簽名 k:選取小于選取小于q的隨機(jī)數(shù)的隨機(jī)數(shù) r(簽名簽名)=(gk mod p)mod q s(簽名簽名)=(k-1(H(m)+xr)mod q驗(yàn)證驗(yàn)證 w=s-1 mod q u1=(H(m)w)mod q u2=(rw)mod q v=(gu1yu2)mod p)mod q 如果如果v=r, 則簽名被驗(yàn)證則簽名被驗(yàn)證小參數(shù)小參數(shù)DSA舉例舉例參數(shù)參數(shù) p: 124 540 019 q: 17 389 h=110 217 528 g=h(p-1)/q mod p=10 083 255私人密鑰：私人密鑰： x&.N.5.0040: 0A 63 35 2E 78 E6 42 AF 4C 62 AC DA 8B 63 FF 86 .c5.x.B.Lb.c.0050