雜湊函數(shù)算法的探索與其在區(qū)塊鏈之應(yīng)用摘要本篇文章以密碼學(xué)為出發(fā)點(diǎn)，探討其中的加密方法與攻擊模式，接著介紹雜湊函數(shù)之原理與應(yīng)用。加密方法可分為對(duì)稱式加密和非對(duì)稱式加密，攻擊模式可分為唯密文攻擊，選擇明文攻擊與已知明文攻擊。我們將由雜湊函數(shù)訊息摘要算法(Message-DigestAlgorithm,MD)與安全雜湊算法(SecureHashAlgorithm,SHA)系列的歷史發(fā)展，帶出MD5訊息摘要算法(MD5Message-DigestAlgorithm)與SHA-256(SecureHashAlgorithm256)并探討MD5與其前身MD4算法之差異，比較MD5相較于MD4的優(yōu)勢(shì)，然后介紹如何修改MD5使其更加復(fù)雜。最后介紹雜湊函數(shù)于近來非常受矚目的虛擬貨幣之應(yīng)用，主要包含比特幣以及非同質(zhì)化代幣(NFT,Non-FungibleToken)。關(guān)鍵詞:密碼學(xué)，雜湊函數(shù)，MD5，SHA-256，虛擬貨幣，NFT。一、前言隨著網(wǎng)絡(luò)之迅速發(fā)展，信息安全可說是與我們?nèi)粘Ｉ蠲懿豢煞值闹匾h題。算法，進(jìn)階加密標(biāo)準(zhǔn)(AdvancedEncryptionStandard,AES人共同提出的RSA算法，以三人名字字首命名[3]。RSA算法是基于數(shù)學(xué)難題是對(duì)極大整數(shù)做質(zhì)因數(shù)分解，此難題目前仍無法有效的破解[3]非對(duì)稱式加密各有優(yōu)缺點(diǎn)，對(duì)稱式加密雖然速度快但也容的金鑰用收訊者的非對(duì)稱式的公鑰加密，再跟密文一起傳可用自己非對(duì)稱式的私鑰將加密后的對(duì)稱式金鑰解密，再使用對(duì)稱式金鑰將密文已知明文攻擊是指攻擊者掌握了某段明文x和對(duì)應(yīng)密文y。選擇密文攻擊是指任意搜集一定數(shù)量的密文，讓這些密文透過被攻擊的加密算法解密，透過未知的密鑰獲得解密后的明文。上述之加密方式可以反向推導(dǎo)，以下我們將介紹另一種不可逆的加密方式即雜湊函數(shù)(HashFunction)，雜湊函數(shù)是將訊息壓縮，經(jīng)過運(yùn)算后輸出雜湊值，由不同的訊息會(huì)得到不同的雜湊值。雜湊函數(shù)可驗(yàn)證信息是否被修改，保護(hù)資料，語音辨識(shí)或是建立雜湊位學(xué)位證書，如成大的數(shù)位學(xué)位證書技術(shù)即采用SHA-256雜湊函數(shù)，并搭配雜湊鏈(HashChain)技術(shù)[5]，教育部的數(shù)位證書驗(yàn)證網(wǎng)站[6可]以進(jìn)行各校數(shù)位證書的驗(yàn)證，而近來快速發(fā)展的虛擬貨幣與非同質(zhì)化貨幣(NFT,Non-FungibleToken)圖1(a):對(duì)稱式加密，(b):非對(duì)稱式加密(A為發(fā)訊人，B為收訊人)圖2:數(shù)位信封(A為發(fā)訊人，B為收訊人)二、雜湊函數(shù)之簡介與發(fā)展在本節(jié)中主要介紹雜湊函數(shù)及其演進(jìn)，雜湊函數(shù)意思是將任意長度的明文輸首先雜湊值無法反推出原來的訊息，其次雜湊值必須隨明文改變而摘要算法(Message-DigestAlgorithm,MD)系列、RACE原始完整性校驗(yàn)訊息摘要(RACEIntegrityPrimitivesEvaluationMessageDigest,RIPEMD)等等，本節(jié)我們將主要探討MD與SHA算法之演進(jìn)。SHA-1原本是被廣泛使用的密碼雜湊將探討MD5算法之原理，并比較其前一代MD4與MD5之差異與改良之處。然后再介紹目前較廣被采用的SHA-2中的SHA-256算法。圖3(a):雜湊函數(shù)，(b):雜湊碰撞MD系列由羅納德·李維特(RonaldRivest所)制作，MD2于1989年設(shè)計(jì)。MD4于1990年公開[10]1991年DenBoer和Bosselaers發(fā)表了一篇文章計(jì)算MD4時(shí)可能發(fā)生雜湊碰撞，并證實(shí)MD5算法無法防止碰撞攻擊[13]， MD6于2008年首次發(fā)布[15]，2011年9月MD6發(fā)布了一篇論文[16]，提供了改進(jìn)的證明。以下我們將介紹MD5算法，并與MD5前身—MD4比較其改良之處，然后介紹可產(chǎn)生MD5碰撞的方法—差分分析，并介紹如何改良MD5能使其更加復(fù)雜。由于大多數(shù)的瀏覽器與最后會(huì)介紹的比特幣皆使用SHA-256，所以MD5介紹完畢后將介紹SHA-256算法。 InstituteofStandardsandTechnolog是于2015年正式發(fā)布的SHA-3[9]。圖4:SHA與MD5發(fā)展三、MD5算法與SHA-256算法本節(jié)會(huì)介紹MD5算法及SHA-256算法，介紹MD5算法后會(huì)比較其前身—MD4，與可產(chǎn)生MD5碰撞的差分分析，并嘗試修改MD5使其更最后介紹SHA-2中的SHA-256算法。3.1MD5算法接下來會(huì)詳細(xì)講解MD5算法的執(zhí)行方式，分為了四個(gè)部分，第一部分是MD5明文處理方法，第二部分解釋MD5前置作業(yè)，第三部分解釋MD5的四個(gè)函數(shù)，最后一步是MD5操作方法。3.1.1MD5明文處理方法度的明文就能得到128bits的雜湊值，以輸入“1234”為例會(huì)輸出算法每次執(zhí)行需要將明文擴(kuò)充到統(tǒng)一的長度[17]，先把明文擴(kuò)充到被512除得進(jìn)制表示明文長度剛(好是512的倍數(shù))，如果初始長度以滿足條件也要進(jìn)行擴(kuò)充，所以最少補(bǔ)1位，最多補(bǔ)448位(如圖5所示)。明文擴(kuò)充結(jié)束后MD5算法會(huì)把512bits當(dāng)成一組，每組又分成16份，每而M16~M63它的產(chǎn)生方法如以下所示。{i圖5:MD5補(bǔ)碼以下將會(huì)介紹如何補(bǔ)碼以達(dá)上述之目的[7]，以“1234”為例進(jìn)行補(bǔ)位操作，“1234的”美國標(biāo)準(zhǔn)信息交換碼(AmericanStandardCodeforInformationInterchange,首先補(bǔ)一個(gè)1變成001100010011001000110011001101001，再來補(bǔ)415個(gè)0，以16進(jìn)制來表示000000000000000000000000000000000000000000000000接下來因?yàn)椤?234”長度為32bits，所以后面加上表示長度的64bit000000000000000000000000000000000000000000000000000000000000000000000003.1.2MD5前置作業(yè)MD5開始執(zhí)行前要先初始化，MD5使用4個(gè)暫存器初始化方式是將A,B,C,D復(fù)制一次到a,b,cMD5有64個(gè)固定常數(shù)，產(chǎn)生方式為232×|sin(i)|，i從0~63編號(hào)為3.1.3MD5的4輪計(jì)算3.H(a,b,c)=a?b?c4.I(a,b,c)=b?(a∨(?c))。圖6:F，G，H，I真值表。1.FF(a,b,c,d,Mi,w,ti)表示a=b+((a+ EQ\*jc3\*hps24\o\al(\s\up17(1),1)EQ\*jc3\*hps17\o\al(\s\up16(s3),s3)EQ\*jc3\*hps24\o\al(\s\up17(2),3)EQ\*jc3\*hps24\o\al(\s\up10(01),32)EQ\*jc3\*hps24\o\al(\s\up17(≤),6)EQ\*jc3\*hps24\o\al(\s\up10(53),47) 3.1.4MD5操作方法本節(jié)分成三個(gè)步驟，第一步是初始化，如3.1.2節(jié)所述，將A,B,C,D復(fù)制一1.初始化(如3.1.2節(jié))2.執(zhí)行圖(7)把c放到d，b放到c，F(xiàn)F(a,b,c,共64次，結(jié)束后將A~D分別與a~d相加3.重復(fù)第二步，直到每一組(一組512bits跑)完，最后將A~D串聯(lián)輸出圖7:MD5的操作[18]透過上述的操作方法可以發(fā)現(xiàn)，MD5算法每次運(yùn)算的值會(huì)循環(huán)右移后計(jì)算下一輪，并且每次只有A會(huì)改變。3.2MD4與MD5之比較認(rèn)識(shí)MD5的算法后接下來要與其前身MD4比較，可以透過MD5與MD4的差別來改善MD5使其更加復(fù)雜，MD5的相關(guān)改進(jìn)將會(huì)在3.3.1介紹。了減弱MD4第二輪的對(duì)稱性，MD5第二輪改成(?c)(表1)，且每一步都有加表1:第二輪由(b∧c改)成(b∧(?c))表2:MD4二三輪加上固定常數(shù)MD5改為加上ti，MD5的M及iW的取法也與MD4不同上，希望能找到1024bits的(M0,M1)，只要滿足290條充要條件就能找到(MEQ\*jc3\*hps17\o\al(\s\up4(′),0),EQ\*jc3\*hps17\o\al(\s\up4(′),1)EQ\*jc3\*hps17\o\al(\s\up4(′),0)EQ\*jc3\*hps17\o\al(\s\up4(′),1)另一則為循環(huán)輸出GoodbyeWorld:-([22]，但兩個(gè)檔案MD5雜湊值卻是相同的“18fcc4334f44fed60718e7dacd82dddf”。圖8:差分分析算式3.3.1MD5相關(guān)的改進(jìn)本節(jié)將介紹如何修改MD5將使其更加復(fù)雜，MD5可以更改sin的順序或是更改Mi選擇方式，例如“MD5加密算法的安全性分析與改進(jìn)”[23所]述，因?yàn)?個(gè)連續(xù)的數(shù)之間存在某種關(guān)聯(lián)，象是(sin(1)+sin(3))?sin(3)≈0.138663≈ 更改M選i擇方式，可以將M改i成取Mi×Mj×Mk取后32位相乘后為避免0的數(shù)量太多，所以最終公式EQ\*jc3\*hps17\o\al(\s\up4(2),x) EQ\*jc3\*hps17\o\al(\s\up4(2),x)EQ\*jc3\*hps17\o\al(\s\up4(2),x) EQ\*jc3\*hps17\o\al(\s\up4(2),x)表3:i，j，k取法此處%意思是mod或是改變M都i會(huì)增加復(fù)雜度。而透過本節(jié)可以知道使M更i復(fù)雜的修改方式，學(xué)習(xí)歷程檔案中的檔案校驗(yàn)方式就是使用MD5，但王小云教授等人發(fā)現(xiàn)其擬貨幣中的比特幣有使用SHA-256。3.4SHA-256算法介紹完MD5后，接下來會(huì)我們?cè)偬接憫?yīng)用于比特幣中的SHA-256算法[8]的執(zhí)行方式，其分為四個(gè)部分，第一部分是SHA-256明文處理方法，第二部分解釋SHA-256前置作業(yè)，第三部分解釋SHA-256的六個(gè)函數(shù)，最后一步是SHA- 256操作方法。3.4.1SHA-256明文處理方法SHA-256算法是給任意長度的明文就能得到256bits的雜湊值，以輸入“1234”為例，會(huì)輸出“03AC674216F3E15C761EE1A5E255F067953623C8B388B4459E13F978D7C846F4”，為了使輸出統(tǒng)一為256bits，SHA-256算法每次執(zhí)行需要將明文擴(kuò)充到統(tǒng)一的長度，SHA-256明文擴(kuò)充方式與MD5相同，明文擴(kuò)充結(jié)束后也是512bits為一組，1組分成16份，每份32bits，所以每組會(huì)分成法是在后面介紹。3.4.2SHA-256前置作業(yè)SHA-256開始執(zhí)行前要先初始化，與MD5的四個(gè)不同，此處使用八個(gè)質(zhì)數(shù) (2,3,5,7,11,13,17,19開)根號(hào)取小數(shù)部份的前32位[8]輸出的位數(shù)，分別是H0=0x6A09E667,H1=0xBB67AE85,H2=0x3C6EF372,H3=0xA54FF53A,H4=0x510E527F,H5=0x9B05688C,H6=0x1F83D9AB,H7=0x5BE0CD192有64個(gè)固定常數(shù)，產(chǎn)生方式為(2,3,5,7,11,13,17,19,23,29,31…共64個(gè)的)立方根小數(shù)部份取前32位[8]，K0~K63(K0=0x428a2f98,K1=0x71374491,K2=3.4.3SHA-256的六個(gè)函數(shù)1.fif(b,c,d)=b∧c??b∧d3.4.4SHA-256操作方法1.初始化(如3.4.2節(jié))2.執(zhí)行圖(9)i從0~63T1=?+∑1(e)+fif(e,f,g)+Ki+MiT2=∑0(a)+fmaj(a,b,c)3.重復(fù)第二步直到每一組都跑完，最后將H0~H串7聯(lián)輸出，H0+H1+H2+圖9:SHA-256執(zhí)行[24]也會(huì)比較久，依據(jù)Rachmawatietal.[25所]述，用相同的設(shè)備，同樣輸入11539Bytes，MD5要3.3644毫秒，而SHA-256要8.198342857143毫秒。了解SHA基礎(chǔ)原理后，以下我們將介紹雜湊函數(shù)在區(qū)塊鏈上的應(yīng)用。四、雜湊函數(shù)于區(qū)塊鏈之應(yīng)用也能應(yīng)用在輸入賬號(hào)密碼，虛擬貨幣和非同質(zhì)化代幣(NFT,Non-FungibleToken)證交易以及工作量證明，最后再針對(duì)近來受到矚目的NFT加以簡介。鏈作為基礎(chǔ)的虛擬貨幣，虛擬貨幣會(huì)使用雜湊函數(shù)，但MD5存在安全性問題，介紹比特幣如何驗(yàn)證貨幣持有者是否對(duì)此貨幣雙重支付，再來介紹比特幣中的工作量證明(ProofOfWork,POW)，透過工作量證明可以了解比特幣中挖礦的意思。比特幣錢包地址用于接收與支付比特幣，錢包地址是將公鑰使用SHA-256雜湊后再用RIPEMD-160雜湊，最后利用Base58編碼，公鑰是將私鑰使用橢圓曲線數(shù)位簽章算法(EllipticCurveDigitalSignatureAlgorithm,ECDSA)加密而得，為了要讓比特幣不被重復(fù)使用，需要全網(wǎng)廣播，讓所有人知道這筆交易的產(chǎn)生，并且應(yīng)用雜湊函數(shù)讓對(duì)方知道貨幣來源是否正常，主要概念就是ID1把前一次交易單跟對(duì)方ID2的公開金鑰雜湊后使用ID1的私鑰加密，并且傳送給ID2， ID2可以將ID1傳來的資料用ID1的公鑰解開，得到雜湊值，這時(shí)因?yàn)榻灰子腥W(wǎng)廣播，所以ID2也有前一次的交易單，ID2可以使用自己的公鑰和前一次交易單雜湊后，跟ID1傳送過來并解開的雜湊值比對(duì)，不同的話代表資料有誤，不會(huì)圖10:比特幣交易(Transactions)[26]。4.1.2工作量證明(ProofOfWork)免惡意竄改，比特幣里的區(qū)塊鏈?zhǔn)侨ブ行幕姆稚⑹綌?shù)據(jù)庫，每一個(gè)區(qū)塊包含了前一個(gè)區(qū)塊的雜湊，時(shí)間戳，交易資料，所謂的挖礦就是為了找到下一塊區(qū)塊，1.把最后一塊區(qū)塊資料雜湊2.把收到卻還沒列入?yún)^(qū)塊的交易放入新區(qū)塊3.計(jì)算一個(gè)隨機(jī)數(shù)，并把1到3的資料雜湊4.檢查前n個(gè)位置是不是05.符合要求就全網(wǎng)廣播，不符合就繼續(xù)1到4的步驟圖11:工作量證明(proof-of-work)[26]。是在2014年的一部影片[28]，在2017年NFT開始引起關(guān)注。目前已知第一個(gè)NF