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