3.4 單向函數加密
密碼學中有一種特殊類型的加密技術，但稱其為加密實在有點勉為其難，第一因為其不支持解密，第二通常沒有密鑰。
Alice帶來一個筒形背包，里面裝的圓柱形的木塊的直徑與背包一致，恰好裝得滿滿當當。Alice邊把木塊取出來邊對Bob說：“這些木塊圓柱直徑相等，高度不等，問怎么求背包高度？”
“算這個初等數學題我還是游刃有余的。”Bob不假思索地刷刷寫下一個算式：
“這里hi是各種木塊的高度，ni是背包中這種木塊的塊數，h就是你背包的高度。”
“好。換一個問題。”Alice當然不會考Bob如此簡單的問題，后面肯定會有個大坑在等著，“假如我告訴你各種木塊的高度，還告訴你背包的高度，問各需要多少塊不同木塊正好裝滿背包？”
Bob認真想了想，無奈地回答：“這是多元一次方程，除非有更多的條件構成方程組，否則只能湊數求解。”
Alice所提的正是有名的背包問題（knapsack problem）。設高度值hi為已知系數，各種高度對應的塊數的集合{ni}為數據，則從數據計算總高度h是非常容易的，而從總高度反推數據則非常困難。
相似的還有離散對數問題：令質數p滿足p-1含有另一大質因子q及一整數g（1＜g＜p-1）。給定整數x，求y=gx mod p，只需要有限次的乘法運算；但如果給定y、g和p，要求解x，則除了暴力嘗試別無他法，在計算上不可行。
3.4.1 單向函數技術原理
單向函數（one-way function）運用了背包問題的原理，如圖3.24所示，將原消息作為函數的輸入（相當于{ni}），函數的輸出（相當于h）為消息摘要（message digest）。單向函數是將原消息進行處理后生成固定長度（一般比原消息短很多）的數據，無法還原，這是其名為單向的原因所在。單向函數又稱為哈希函數（hash function），消息摘要就稱為原消息的哈希（hash）。
圖3.24 單向函數原理圖
哈希值能夠在統計上唯一地表征輸入值，即把消息進行數學意義上的內容摘要，但從摘要中無法得到比摘要本身更多的關于原有消息的信息，具有安全性。哈希算法需要滿足以下關鍵特性：
（1）單向性。從輸入值能夠簡單、迅速地得到哈希值，而反過來在計算上不可行。
（2）抗沖突性（collision resistant）。給定M，計算上難以找到M′，滿足H（M）=H（M′），此謂弱抗沖突性；如果計算上也難以尋找一對任意的M和M′，滿足H（M）=H（M′），此謂強抗沖突性。抗沖突性在某種程度上可以認為就是哈希的唯一性。
（3）分布均勻性。存在映射分布均勻性和差分分布均勻性。哈希值中，0和1的數量應該大致相等；輸入中每1b的變化，哈希值中應有一半以上的位改變，這被稱為雪崩效應（avalanche effect）；反之，要實現使哈希值中出現1b的變化，則輸入中至少有一半以上的位必須發生變化。分布均勻性本質上是必須使輸入中每一位的信息，盡量均勻地反映到輸出的每一位上去，同時輸出中的每一位，都是輸入中盡可能多的位一起作用的結果。
單純從理論上看，原消息的編碼空間巨大，例如照片、電影，動輒幾兆、幾百兆字節，而哈希僅有數十個字節長度，編碼空間相對很小，哈希沖突的概率應當很高才對。然而，考查實際的數據對象，以英文文章為例，每個字節的256個不同編碼中可讀ASCII字符只占不到一半，文章大部分字符都是小寫字母，有效編碼空間大幅縮小，再考慮到文章不是字母的胡亂組合，而是字母構成數量有限的單詞、單詞組成有意義的語句，這就進一步壓縮了編碼空間。因此，修改一篇文章，至少要通順，表達的意思上達到篡改的目的，還要使之輸出相同的哈希，無疑是天方夜譚。
單向函數因為具備這些獨特的性質，可在信息安全領域發揮巨大作用。哈希攜帶了原消息的內容特征，不同的消息有不同的哈希，因此也稱其為數字指紋（digital fingerprint），就好比人類的指紋可以用來“畫押”，與親筆簽名有同等效力，可以用來代表一個人。犯罪現場的指紋鑒定也是同理。
例如，有一份帶上哈希的電子合同，如圖3.25所示，倘若合同被篡改，哪怕只是改了一個小數點，用同樣的單向函數得到的哈希將發生巨大的變化，而且幾乎不可能偽造一份具有相同哈希的合同，所以數字指紋可以用來驗證合同真偽。然而，如果合同篡改者同時用虛假合同生成了新的哈希，替換了原有的數字指紋，則反而會帶來“虛假的真實”的弊端。因此，數字指紋在實際運用時還需要結合其他密碼學技術，例如配合公鑰加密，才能切實保障其安全性。
圖3.25 數字指紋應用示例
再例如，網絡用戶在客戶端輸入用戶名、密碼（口令）登錄幾乎是每天要做的事。如果直接把用戶輸入的密碼傳送到服務端進行驗證，就存在兩方面的安全隱患：一是傳輸過程中可能被竊聽，明文密碼就暴露了；二是服務端數據庫存儲的明文密碼也有暴露風險（例如被“脫庫”或被“內鬼”竊取賬號）。為防范登錄密碼安全風險，網絡系統通常采用對密碼作哈希的方法，客戶端向服務器傳輸的是密碼的哈希值，而服務端存儲的也是哈希值，不影響登錄驗證，也不會暴露用戶密碼，這是單向函數加密技術的成功應用范例。
但是網絡登錄密碼單純采用哈希加密手段仍然存在安全風險，例如攻擊者截取到哈希值后，至少有兩種手法可實現攻擊：一種是“重放攻擊”，即直接向服務端傳送密碼哈希值要求登錄，服務端會照樣放行；另一種是“字典攻擊”，即利用事先做好的密碼串－哈希值對應表（因為大部分人會用便于記憶的單詞和詞組來做密碼），查表“恢復”密碼明文。抵抗這一風險的做法是采用“哈希加鹽”的一次性登錄（Single-time Sign-On，SSO）方案，如圖3.26所示，每次登錄使用隨機數作為“鹽”（salt），與密碼哈希拼接后再做哈希，從而實現每次登錄都傳輸不同的密文（隨機數可事先傳輸或隨密文傳輸，不影響安全性）。
圖3.26 一次性口令技術原理
單向函數的另一項重要用途是信息標識。如果需要識別大數據量的信息對象，例如不同的電影，“全量比較”費力不討好，則可生成信息對象的數字指紋，例如32B的定長哈希，作為類似身份證號碼的ID，檢索時只需出示ID，存儲、傳輸、比對、查找都很便捷。例如網上P2P下載應用就是采用DHT（分布式哈希表）方法，從各個用戶終端上尋找大文件的不同片段，實現并發式下載。
比特幣系統設計中大量運用了成熟的單向函數加密技術，將單向函數各種技術特點和功能發揮得淋漓盡致：
? 數據纏結——利用哈希對原消息的變化極其敏感的特性，構造數據之間的纏結關系，防范信息篡改和偽造，包括：形成區塊之間的鏈和生成交易默克爾樹。
? 信息標識——利用哈希短小（壓縮性）、等長、抗沖突等特性，以之為區塊和交易的標識，非常便于存儲和檢索。
? 地址編碼——利用哈希單向轉換的特性，生成比特幣用戶地址，既提高了安全性、規范性、隱蔽性，又實現了可驗證。
? 交易簽名——利用哈希作為原消息數字指紋的特性，對資金歸屬和使用規則進行簽名鎖定，并可驗證、解鎖，實現智能化交易。
常用的單向函數算法有CRC、MD、RIPEMD、SHA等。
3.4.2 CRC算法
循環冗余碼（Cyclic Redundancy Check，CRC）通常不被當作單向函數來看待，常用在網絡通信中的數據鏈路層，例如作為傳輸檢錯的幀校驗序列（Frame Check Sequence，FCS）編碼。但CRC碼確實就是一種單向函數，而且適合流式數據，可以邊傳輸邊計算哈希，具備獨特的能力。
CRC碼是一種線性分組碼，一般為16b或32b數值，編碼和解碼方法簡單，能夠達到0.0047%以下漏檢率，可檢測出所有奇數個隨機錯誤以及長度小于或等于生成多項式階數的突發錯誤。
設：生成多項式P（x）為n階，傳輸的比特流為M，則生成nb的CRC碼R（x）。生成多項式是系數為1或0的一元多次多項式，其最高指數就是階。例如，P（x）=x7+x5+x+1，階為7，對應8b二進制數為10100011。
CRC碼計算公式為：R（x）=（M×2n）modP（x）。即原消息比特流M擴展到n位后作為被除數，并以生成多項式P（x）轉換而來的二進制數據為除數，做按位除法，取余數R（x）擴展到n位即為CRC碼。
CRC碼緊接在M比特流的后面進行傳輸，信息接收方采用同樣的生成多項式進行按位除法運算以驗證：R′（x）=（M×2n+R（x））mod P（x），若R′（x）=0，說明M無差錯，否則說明傳輸有誤（存在誤碼或被篡改）。
如圖3.27所示為計算余數的按位除法的豎式運算法示例，其中每一步采用的不是減法，而是按位異或運算。
圖3.27 CRC按位除法示例
CRC碼生成多項式的選擇非常重要，是保障檢錯能力的基礎。國際標準中較常用的生成多項式有：
? CRC-16=x16+x15+x2+1；
? CRC-CCITT=x16+x12+x5+1；
? CRC-32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1。
3.4.3 MD算法
消息摘要（Message Digest，MD）是一種經典的單向函數加密算法，由R.Rivest于1989—1992年間開發并升級，分為MD2、MD4和MD5，其中MD5算法使用最為廣泛。
MD5以512b（64B）分組為單位來處理輸入信息，輸出128b（16B）哈希值。
首先對信息進行填充，在信息的尾部填充一個1和連續的0，直到滿足位長度對512求余的結果等于448（即n×512+448），其后附加64b原信息長度值（以byte為單位）。
MD5對4個32b的鏈接變量（chaining variable）分別設置初始值為：Va=0x01234567，Vb=0x89abcdef，Vc=0xfedcba98，Vd=0x76543210。執行算法流程如下：
（1）令a=Va，b=Vb，c=Vc，d=Vd。
（2）將輸入的512b分組劃分成16個32b子分組mj，j=0，1，2，…，15。
（3）進行4輪運算，每輪由16步組成，每步為K（A，B，C，D，mj，s，ti）函數運算（如圖3.28所示），K函數表示為：A=B+（（A+k（B，C，D）+mj+ti）＞＞s），K∈{F，G，P，Q}，k∈{f，g，p，q}，＞＞s表示循環右移s位，s是常數（圖3.28中對應數值）。在第i步中（i=1，2，…，64），以i為弧度值，可計算常數為：ti=int（232×|sin（i）|）。分別用于4輪運算的4個非線性函數如下（每輪一個，均為按位邏輯運算：&與，|或，~非，⊕異或）：
f（x，y，z）=（x&y）|（（~x）&z）
g（x，y，z）=（x&z）|（y&（~z））
p（x，y，z）=x⊕y⊕z
q（x，y，z）=y⊕（x|（~z））
（4）計算：Va=Va+a，Vb=Vb+b，Vc=Vc+c，Vd=Vd+d。
（5）若存在更多512b分組，回到（1）繼續運算，否則算法結束。
圖3.28 MD5 4輪函數運算表
圖3.28 (續)
對所有原消息分組運算完畢后，最后輸出Va、Vb、Vc、Vd的級聯{Va|Vb|Vc|Vd}，即為128b（16B）的MD5值。
例如，第2輪的第1步（總第17步）為G（a，b，c，d，m1，s，t17），表示：
a=b+（（a+g（b，c，d）+m1+t17）＞＞s）
即為：
a=b+（（a+（（b&d）|（c&（~d）））+m1+t17）＞＞s）
也即：
a=b+（（a+（（b&d）|（c&（~d）））+m1+0xf61e2562）＞＞5）
采用MD5加密字符串（例如加密口令）的樣例如下（第一個例子為空字符串，即長度為0的字符串）：
md5(＂＂)=D41D8CD98F00B204E9800998ECF8427E
md5(＂a＂)=0CC175B9C0F1B6A831C399E269772661
md5(＂abc＂)=900150983CD24FB0D6963F7D28E17F72
md5(＂message digest＂)=F96B697D7CB7938D525A2F31AAF161D0
md5(＂abc…z＂)=C3FCD3D76192E4007DFB496CCA67E13B
可見MD5單向函數生成的哈希具備非常隨機的外觀，原字符串哪怕僅發生微小的變化，哈希值的很多位都會隨之而變，杜絕了推測攻擊的可能性。
3.4.4 RIPEMD算法
RIPEMD（RACE Integrity Primitives Evaluation Message Digest）是一種單向函數算法，由Hans Dobbertin、Antoon Bosselaers和Bart Preneel等3人在MD4的基礎上于1996年提出，與MD5一樣都是著眼于改善MD4存在的安全缺陷。RIPEMD算法共有4個標準RIPEMD-128、RIPEMD-160、RIPEMD-256和RIPEMD-320，其對應輸出長度分別為16B、20B、32B和40B。讓人難以置信的是256和320這兩種標準只是在128和160的基礎上修改了初始參數和S-box來達到輸出為256b和320b的目的，所以，256的強度和128相當，而320的強度和160位相當。其中RIPEMD-160在比特幣系統的地址生成算法中得到運用，在此之前RIPEMD基本上處于默默無聞的狀態。
RIPEMD-160算法以32b字為計算單元，輸入16個32b字X（i）組成的分組，輸出5個32b字（即20B）的級聯。輸入消息的填充方式與MD5相同。
每個分組的運算進行5輪，每輪分別對16個32b字進行操作，共80步。每一步分為左、右兩部分操作，執行邏輯均為：A=（A+f（B，C，D）+X+K）?s+E；C=C?10（?s為循環左移s位，+為模232加法）。
定義算法所用的160個32b常量如下所示，其中：K（j）用于左側操作，K′（j）用于右側操作，j為0~79步操作步驟（每行為1輪）：
定義r（j）、r′（j）為輸入分組的32b字X（i）的選擇下標。在不同的輪次及左右側操作中，16個字的計算次序各有不同。
在一種改進的RIPEMD算法中，設ρ（i）={7，4，13，1，10，6，15，3，12，0，9，5，2，14，11，8}（i=0，1，2，…，15），又設π（i）=9i+5（mod 16），則5輪運算中采用的r（j）、r′（j）為（均為mod 16運算）：
但在標準的RIPEMD算法中，5輪運算中采用的r（j）、r′（j）固定定義為：
r(j)=j r′(j)=5，14，7，0，9，2，11，4，13，6，15，8，1，10，3，12 0≤j≤15
r(j)=7，4，13，1，10，6，15，3，12，0，9，5，2，14，11，8 r′(j)=6，11，3，7，0，13，5，10，14，15，8，12，4，9，1，2 16≤j≤31
r(j)=3，10，14，4，9，15，8，1，2，7，0，6，13，11，5，12 r′(j)=15，5，1，3，7，14，6，9，11，8，12，2，10，0，4，13 32≤j≤47
r(j)=1，9，11，10，0，8，12，4，13，3，7，15，14，5，6，2 r′(j)=8，6，4，1，3，11，15，0，5，12，2，13，9，7，10，14 48≤j≤63
r(j)=4，0，5，9，7，12，2，10，14，1，3，8，11，6，15，13 r′(j)=12，15，10，4，1，5，8，7，6，2，13，14，0，3，9，11 64≤j≤79
各個步驟使用的循環左移位數s（j）和s′（j）（在一種改進的RIPEMD算法中移位次數的定義有所不同，且兩側相同）按標準定義為：
s(j)=11，14，15，12，5，8，7，9，11，13，14，15，6，7，9，8′ s(j)=8，9，9，11，13，15，15，5，7，7，8，11，14，14，12，6 0≤j≤15
s(j)=7，6，8，13，11，9，7，15，7，12，15，9，11，7，13，12′ s(j)=9，13，15，7，12，8，9，11，7，7，12，7，6，15，13，11 16≤j≤31
s(j)=11，13，6，7，14，9，13，15，14，8，13，6，5，12，7，5′ s(j)=9，7，15，11，8，6，6，14，12，13，5，14，13，13，7，5 32≤j≤47
s(j)=11，12，14，15，14，15，9，8，9，14，5，6，8，6，5，12′ s(j)=15，5，8，11，14，14，6，14，6，9，12，9，12，5，15，8 48≤j≤63
s(j)=9，15，5，11，6，8，13，12，5，12，13，14，11，8，5，6′ s(j)=8，5，12，9，12，5，14，6，8，13，6，5，15，13，11，11 64≤j≤79
每輪每個步驟的運算所用的5個非線性按位操作函數（⊕異或、∧與、∨或、~非）分別為：
f（j，x，y，z）=x⊕y⊕z （0≤j≤15）
f（j，x，y，z）=（x∧y）∨（~x∧z）（16≤j≤31）
f（j，x，y，z）=（x∨~y）⊕z （32≤j≤47）
f（j，x，y，z）=（x∧z）∨（y∧~z） （48≤j≤63）
f（j，x，y，z）=x⊕（y∨~z） （64≤j≤79）
RIPEMD-160算法開始時，首先初始化級聯變量：h0=0x67452301，h1=0xEFCDAB89，h2=0x98BADCFE，h3=0x10325476，h4=0xC3D2E1F0。算法流程如下：
（1）初始化臨時變量。
A=A′=h0， B=B′=h1， C=C′=h2， D=D′=h3， E=E′=h4
（2）對16個32b字X（i）進行5輪共80步左、右兩側的運算。
（3）若存在更多分組，回（1）繼續運行；否則算法結束。
最后級聯h0、h1、h2、h3、h4，即為20B的RIPEMD-160哈希。采用RIPEMD-160單向函數對字符串進行哈希的樣例如下：
RIPEMD160(＂＂)=9C1185A5C5E9FC54612808977EE8F548B2258D31
RIPEMD160(＂a＂)=0BDC9D2D256B3EE9DAAE347BE6F4DC835A467FFE
RIPEMD160(＂abc＂)=8EB208F7E05D987A9B044A8E98C6B087F15A0BFC
RIPEMD160(＂message digest＂)=5D0689EF49D2FAE572B881B123A85FFA21595F36
RIPEMD160(＂abc…z＂)=F71C27109C692C1B56BBDCEB5B9D2865B3708DBC
3.4.5 SHA算法
安全哈希算法（Secure Hash Algorithm，SHA）是單向函數加密算法之一，包括SHA-1和SHA-2，SHA-2具體分為SHA-224、SHA-256、SHA-384和SHA-512，1995年發布為美國聯邦標準。SHA-1在SSL、SSH、S/MIME和IPSec等許多安全協議中廣為使用，被視為MD5的繼任者，但人們也對其安全性存在質疑，相比之下SHA-2更為安全，其算法與SHA-1基本一致，SHA-256在比特幣系統中得到大量運用。
SHA-1以512b（32B）分組為處理單位，輸出160b值；SHA-2中SHA-xyz表示輸出xyzb值，前兩者分組大小與SHA-1相同為512b（32B），后兩者為1024b（64B）。
SHA-1算法如下（所有變量為32b字長，計算均為mod 232）。
對原消息的預處理與MD5算法相同：在原消息的尾部填充一個1和連續的0，直到滿足位長度對512求余的結果等于448（即n×512+448），其后附加64b原消息長度值（以byte為單位）。
設置級聯變量初始值為h0∶=0x67452301，h1∶=0xEFCDAB89，h2∶=0x98BADCFE，h3∶=0x10325476，h4∶=0xC3D2E1F0。將原消息分為512b長度的分組（Chunk），依次處理每個分組，直到處理完全部分組。
（1）將分組分為16個32b字w[i]（i=0，1，2，…，15）。
（2）將w[i]（i=0，1，2，…，15）擴展成80個32b字（＜＜循環左移，⊕異或）：
（3）臨時變量賦值：{a，b，c，d，e}={h0，h1，h2，h3，h4}。
（4）主處理程序（循環80輪次；&與，|或，~非）：
（5）級聯變量賦值：{h0，h1，h2，h3，h4}={h0+a，h1+b，h2+c，h3+d，h4+e}。
（6）若已為最后分組，則進行第（7）步；否則返回第（1）步處理下一分組。
（7）Hash值為h0、h1、h2、h3、h4順序級聯而成（160b）。
SHA-2算法加強了各個字的位元混合程度，以提升安全強度。以SHA-256為例，算法如下（所有變量為32B字長，計算均為mod 232）。
初始化變量：h0∶=0x6A09E667，h1∶=0xBB67AE85，h2∶=0x3C6EF372，h3∶=0xA54FF53A，h4∶=0x510E527F，h5∶=0x9B05688C，h6∶=0x1F83D9AB，h7∶=0x5BE0CD19。
對64個常量賦值k[0，1，2，…，63]∶=
續表
（1）將分組分為16個32b字w[i]（i=0，1，2，…，15）。
（2）將w[i]（i=0，1，2，…，15）擴展成64個32b字（＞＞循環右移，＞＞＞邏輯右移，⊕異或，+加）：
（3）臨時變量賦值：{a，b，c，d，e，f，g，h}={h0，h1，h2，h3，h4，h5，h6，h7}。
（4）主處理程序（循環64輪次；&與，|或，~非）：
（5）中間變量賦值：
{h0，h1，h2，h3，h4，h5，h6，h7}
={h0+a，h1+b，h2+c，h3+d，h4+e，h5+f，h6+g，h7+h}。
（6）若已為最后分組，則進行第（7）步；否則返回第（1）步處理下一分組。
（7）Hash值為h0、h1、h2、h3、h4、h5、h6、h7順序鏈接而成（256b）。
SHA-224與SHA-256的算法基本相同，除了h0~h7的初始值不同且SHA-224輸出時截掉h7的值（因此為224b）。SHA-512和SHA-256的結構相同，但是，SHA-512處理64B字，執行80次循環，兩者循環移位量不同。SHA-384和SHA-512的不同點為：h0~h7的初始值不同，SHA-384輸出時截掉了h6和h7的值。