密碼學(xué)教程 課件 4-Hash函數(shù)

第四章雜湊函數(shù)

4.1

概述

4.2SHA-1和SHA-2

4.3SHA-34.4我國商密標(biāo)準(zhǔn)SM3

4.

5

MAC和認(rèn)證加密

4.1概述認(rèn)證（authentication）：

采取一些措施保證實(shí)體（entity）是他們所宣稱那些

人，或消息不被非法者修改。

兩類基本認(rèn)證：

身份認(rèn)證（identificationorentityauthentication）

雙方在線、實(shí)時(shí)，例如電話；消息認(rèn)證（messageauthentication；或

數(shù)據(jù)源認(rèn)證dataoriginauthentication)

單向、可延時(shí)，例如E-mail。數(shù)據(jù)完整性（DataIntegrity）：

保證消息的不被修改（但不含數(shù)據(jù)源合法性）。實(shí)現(xiàn)數(shù)據(jù)完整性：

應(yīng)用抗碰撞的雜湊函數(shù)，檢查摘要值。實(shí)現(xiàn)消息認(rèn)證：

消息認(rèn)證=完整性+數(shù)據(jù)源認(rèn)證

采用：有密鑰的雜湊函數(shù)（消息認(rèn)證碼-MAC）；

數(shù)字簽名等。另外：在數(shù)字簽名中：

用雜湊函數(shù)將消息進(jìn)行壓縮后，對摘要值簽名；在隨機(jī)數(shù)產(chǎn)生器中：

用雜湊函數(shù)的摘要值作為隨機(jī)數(shù)；因此，雜湊函數(shù)是密碼學(xué)中最常用的部件之一。實(shí)現(xiàn)區(qū)塊鏈的基本工具！雜湊函數(shù)（算法）：

將任意長輸入的消息壓縮為短的摘要值。有密鑰的雜湊函數(shù)（MAC：MessageAuthenticationCode）有兩個(gè)輸入：密鑰和消息。給定消息，只有知道密鑰的人可計(jì)算MAC。

無密鑰的雜湊函數(shù)（MDC：ModificationDetectionCode）只有一個(gè)輸入即消息。

給定消息，任何人都可計(jì)算hash值；一般，將無密鑰的雜湊函數(shù)就叫做雜湊函數(shù)；而將有密鑰的雜湊函數(shù)叫做消息認(rèn)證碼MAC。雜湊函數(shù)的安全性：

抗原象性(pre-imageresistance):

由y=h(x)計(jì)算x是計(jì)算困難的；yxxx’yyx’x

生日問題：最少多少人中有人生日相同，概率大于50%？

不相同的迭代結(jié)構(gòu)＋壓縮函數(shù)雜湊函數(shù)的構(gòu)造：最常見的Merkle-Damgard(MD)迭代結(jié)構(gòu)利用分組密碼工作模式-構(gòu)造雜湊函數(shù)：利用分組密碼的密碼分組鏈接模式CBC和密碼反饋模

式CFB。Ekx1y1kx2y2kkH（x1..xn)yn初始矢量EkEkCBCCFBx1y1kx2kkH（x1..xn)xn初始矢量EkEky2Ek直接構(gòu)造f函數(shù)：采用類似分組密碼的基本部件和基本運(yùn)算，構(gòu)造偽隨機(jī)函數(shù)（避免分組密碼中不必要的密鑰擴(kuò)展過程）。利用模運(yùn)算構(gòu)造f函數(shù)：采用第五章介紹的公鑰密碼的方法，從單向函數(shù)設(shè)計(jì)壓縮函數(shù)。MASH-1國際標(biāo)準(zhǔn)，采用模平方運(yùn)算；利用格計(jì)算問題設(shè)計(jì)的SWIFFT算法；利用糾錯(cuò)碼設(shè)計(jì)的FSB算法；雖然具有較好的理論基礎(chǔ)，但實(shí)現(xiàn)效率仍有差距。SHA-1和SHA-2是美國（NIST）雜湊函數(shù)標(biāo)準(zhǔn)算法。（SHA：StandardHashAlgorithm）

4.2

SHA-1和SHA-2這是一系列雜湊函數(shù)MD4、MD5的發(fā)展，共同特點(diǎn)是：采用簡單的運(yùn)算多次迭代構(gòu)造壓縮函數(shù)。

被攻破的MD4、MD5的輪函數(shù)

輪常數(shù)消息子塊每個(gè)512比特消息塊分為16個(gè)32bit的消息字，經(jīng)擴(kuò)展，形成80個(gè)（步）的消息字；最后將輸入鏈接值反饋到輸出，保證壓縮函數(shù)單向性。

2002年美國NIST根據(jù)實(shí)際情況，增加了Hash算法

輸出長度，形成SHA-256、SHA-384、SHA-512，

這些算法統(tǒng)稱為SHA-2。2004年又提出SHA-224。SHA-2：SHA-256的輸出為256bit，鏈接值分為8個(gè)字，壓縮函數(shù)整體迭代64步，沒有明顯的輪界限。

SHA－256步運(yùn)算SHA-224：

與SHA-256初始值不同；

輸出從256bit左端截取224bit。SHA-512：

每個(gè)字64bit，鏈接值為512bit；

消息分塊為1024bit；迭代89步；SHA-384：

與SHA-512初始值不同；

輸出從512bit左端截取384bit。名稱輸出長度消息塊長度字長度輪數(shù)*每輪步數(shù)SHA-1160512324*20SHA-224/256224/256512321*64SHA-384/512384/5121024641*80我們國家商密標(biāo)準(zhǔn)雜湊函數(shù)是SM3關(guān)于MD-5、SHA-1的攻擊

關(guān)于MD結(jié)構(gòu)的攻擊2004年，A.Joux提出了多碰撞攻擊，已知碰撞時(shí)

找到多碰撞很容易；2005年，J.Keley等提出長消息的第二原像攻擊，

降低了復(fù)雜度，但需要較長的消息；2006年，J.Kelsey等提出了Herding攻擊，已知碰

撞時(shí)產(chǎn)生有意義的第二原像。第一階段：（2007年）在全世界征集了51個(gè)算法；第二階段：（2010年）剩余14個(gè)算法；第三階段：（2011年）剩余5個(gè)算法；(BLAKE、Groestl、JH、Keccak、Skein)2012年10月初

最終獲勝者是Keccak。美國NIST關(guān)于SHA-3的征集活動(dòng)：

4.3

SHA-3Keccak：整體結(jié)構(gòu)為Sponge結(jié)構(gòu)，好處是輸出任意長；結(jié)構(gòu)具有一定的可證明安全性。1600bit置換1600bit狀態(tài)，外部狀態(tài)r長度，內(nèi)部狀態(tài)為c長度；初始值為全0，排列為5*5*64的三維比特?cái)?shù)組。SHA3-224：r=1024,c=576SHA3-256:r=1024,c=576SHA3-384:r=512,c=1088SHA3-512:r=512,c=1088后有修改！rc

加輪常數(shù)每一行進(jìn)行這一變換；唯一的非線性部件（5*5的S盒）。Keccak軟件實(shí)現(xiàn)速度較好；

硬件實(shí)現(xiàn)速度最好。

新穎的結(jié)構(gòu)設(shè)計(jì)；

與SHA-2完全不同。SHA3-256輸出摘要長度（固定）為256的SHA3算法；SHA3-512輸出摘要長度（固定）為512的SHA3算法；SHAKE256輸出摘要長度可變（r=1024）的SHA3算法；SHAKE512輸出摘要長度可變（r=512）的SHA3算法。

4.

4我國商密標(biāo)準(zhǔn)SM3SM3是2010年10月我國商用密碼管理局頒布的商用密碼Hash標(biāo)準(zhǔn)算法。迭代結(jié)構(gòu)仍采用MD結(jié)構(gòu)，中間狀態(tài)長度為256比特，規(guī)模與SHA-2的SHA-256相當(dāng)，但要防止了發(fā)現(xiàn)的問題，增強(qiáng)了安全性。它在克服MD-x系列存在的問題基礎(chǔ)上，仍采用簡單運(yùn)算的組合，保持了計(jì)算簡便和速度優(yōu)勢。

其中兩個(gè)布爾函數(shù)為：其中兩個(gè)置換函數(shù)為：

4.5

MAC和認(rèn)證加密利用Hash構(gòu)造MAC。兩個(gè)輸入：消息+密鑰

沒有密鑰不能計(jì)算摘要；實(shí)現(xiàn)消息認(rèn)證。

消息認(rèn)證碼（MAC）是帶密鑰的Hash函數(shù)。

認(rèn)證加密：

保密性+密文認(rèn)證，密文+標(biāo)簽tag加密-then-MACMAC-then-加密（一般不安全）CAESAR競賽：

2013年1月由著名密碼學(xué)家Bernstein在NIST支持下

組織開展的密碼算法競賽，目的是選擇安全高效的

認(rèn)證加密算法，推動(dòng)其設(shè)計(jì)與分析技術(shù)的發(fā)展。2014年3月開始提交算法，48個(gè)算法；2015年7月選出29個(gè)算法進(jìn)入第二輪；2018年8月選出15個(gè)算法進(jìn)入第三輪；2019年2月宣布6個(gè)算法入選最終算法集。Ascon算法

利用Sponge結(jié)構(gòu)構(gòu)造的輕量級算法。

四個(gè)階段：初始階段、關(guān)聯(lián)數(shù)據(jù)、形成密文和

最后產(chǎn)生標(biāo)簽階段。Cryptographiccompetitions(http://competitions.cr.yp.to)NESSIE（2000-2003）:

(NewEuropeanSchemesforSignatures,IntegrityandEncryption)歐洲研究項(xiàng)目，篩選各種算法NIST

AES

（1997-2000）：

美國篩選分組算法活動(dòng)，確定AESeStream（2004-2008）：

歐洲ECRYPT篩選流密碼活動(dòng)NISTSHA-3（2007-2012）：

美國篩選雜湊函數(shù)活動(dòng)，確定SHA-3CAESAR（2012-2017）：

輕量級認(rèn)證加密算法PHC:Password