記憶重現中bac的密碼等於多少

A. 在公開密鑰密碼體制中，HASH演算法的作用是

Hash，一般翻譯做"散列"，也有直接音譯為"哈希"的，就是把任意長度的輸入（又叫做預映射， pre-image），通過散列演算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。

數學表述為：h = H(M) ，其中H( )--單向散列函數，M--任意長度明文，h--固定長度散列值。

在信息安全領域中應用的Hash演算法，還需要滿足其他關鍵特性：

第一當然是單向性(one-way)，從預映射，能夠簡單迅速的得到散列值，而在計算上不可能構造一個預映射，使其散列結果等於某個特定的散列值，即構造相應的M=H-1(h)不可行。這樣，散列值就能在統計上唯一的表徵輸入值，因此，密碼學上的 Hash 又被稱為"消息摘要(message digest)"，就是要求能方便的將"消息"進行"摘要"，但在"摘要"中無法得到比"摘要"本身更多的關於"消息"的信息。

第二是抗沖突性(collision-resistant)，即在統計上無法產生2個散列值相同的預映射。給定M，計算上無法找到M'，滿足H(M)=H(M') ，此謂弱抗沖突性；計算上也難以尋找一對任意的M和M'，使滿足H(M)=H(M') ，此謂強抗沖突性。要求"強抗沖突性"主要是為了防範所謂"生日攻擊(birthday attack)"，在一個10人的團體中，你能找到和你生日相同的人的概率是2.4%，而在同一團體中，有2人生日相同的概率是11.7%。類似的，當預映射的空間很大的情況下，演算法必須有足夠的強度來保證不能輕易找到"相同生日"的人。

第三是映射分布均勻性和差分分布均勻性，散列結果中，為 0 的 bit 和為 1 的 bit ，其總數應該大致相等；輸入中一個 bit 的變化，散列結果中將有一半以上的 bit 改變，這又叫做"雪崩效應(avalanche effect)"；要實現使散列結果中出現 1bit 的變化，則輸入中至少有一半以上的 bit 必須發生變化。其實質是必須使輸入中每一個 bit 的信息，盡量均勻的反映到輸出的每一個 bit 上去；輸出中的每一個 bit，都是輸入中盡可能多 bit 的信息一起作用的結果。

Damgard 和 Merkle 定義了所謂"壓縮函數(compression function)"，就是將一個固定長度輸入，變換成較短的固定長度的輸出，這對密碼學實踐上 Hash 函數的設計產生了很大的影響。Hash函數就是被設計為基於通過特定壓縮函數的不斷重復"壓縮"輸入的分組和前一次壓縮處理的結果的過程，直到整個消息都被壓縮完畢，最後的輸出作為整個消息的散列值。盡管還缺乏嚴格的證明，但絕大多數業界的研究者都同意，如果壓縮函數是安全的，那麼以上述形式散列任意長度的消息也將是安全的。這就是所謂 Damgard/Merkle 結構：

在下圖中，任意長度的消息被分拆成符合壓縮函數輸入要求的分組，最後一個分組可能需要在末尾添上特定的填充位元組，這些分組將被順序處理，除了第一個消息分組將與散列初始化值一起作為壓縮函數的輸入外，當前分組將和前一個分組的壓縮函數輸出一起被作為這一次壓縮的輸入，而其輸出又將被作為下一個分組壓縮函數輸入的一部分，直到最後一個壓縮函數的輸出，將被作為整個消息散列的結果。

MD5 和 SHA1 可以說是目前應用最廣泛的Hash演算法，而它們都是以 MD4 為基礎設計的。

1) MD4
MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年設計的，MD 是 Message Digest 的縮寫。它適用在32位字長的處理器上用高速軟體實現--它是基於 32 位操作數的位操作來實現的。它的安全性不像RSA那樣基於數學假設，盡管 Den Boer、Bosselaers 和 Dobbertin 很快就用分析和差分成功的攻擊了它3輪變換中的 2 輪，證明了它並不像期望的那樣安全，但它的整個演算法並沒有真正被破解過，Rivest 也很快進行了改進。

下面是一些MD4散列結果的例子：

MD4 ("") =
MD4 ("a") =
MD4 ("abc") =
MD4 ("message digest") =
MD4 ("abcdefghijklmnopqrstuvwxyz") =
MD4 ("") =
MD4 ("1234567890") =

2) MD5
MD5(RFC 1321)是 Rivest 於1991年對MD4的改進版本。它對輸入仍以512位分組，其輸出是4個32位字的級聯，與 MD4 相同。它較MD4所做的改進是：

1) 加入了第四輪
2) 每一步都有唯一的加法常數；
3) 第二輪中的G函數從((X ∧ Y) ∨ (X ∧ Z) ∨ (Y ∧ Z)) 變為 ((X ∧ Z) ∨ (Y ∧ ～Z))以減小其對稱性；
4) 每一步都加入了前一步的結果，以加快"雪崩效應"；
5) 改變了第2輪和第3輪中訪問輸入子分組的順序，減小了形式的相似程度；
6) 近似優化了每輪的循環左移位移量，以期加快"雪崩效應"，各輪的循環左移都不同。
盡管MD5比MD4來得復雜，並且速度較之要慢一點，但更安全，在抗分析和抗差分方面表現更好。

消息首先被拆成若干個512位的分組，其中最後512位一個分組是"消息尾+填充位元組(100...0)+64 位消息長度"，以確保對於不同長度的消息，該分組不相同。64位消息長度的限制導致了MD5安全的輸入長度必須小於264bit，因為大於64位的長度信息將被忽略。而4個32位寄存器字初始化為A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210，它們將始終參與運算並形成最終的散列結果。

接著各個512位消息分組以16個32位字的形式進入演算法的主循環，512位消息分組的個數據決定了循環的次數。主循環有4輪，每輪分別用到了非線性函數

F(X, Y, Z) = (X ∧ Y) ∨ (～X ∧ Z)
G(X, Y, Z) = (X ∧ Z) ∨ (Y ∧ ～Z)
H(X, Y, Z) =X ⊕ Y ⊕ Z
I(X, Y, Z) = X ⊕ (Y ∨ ～Z)
這4輪變換是對進入主循環的512位消息分組的16個32位字分別進行如下操作：將A、B、C、D的副本a、b、c、d中的3個經F、G、H、I運算後的結果與第4個相加，再加上32位字和一個32位字的加法常數，並將所得之值循環左移若干位，最後將所得結果加上a、b、c、d之一，並回送至ABCD，由此完成一次循環。

所用的加法常數由這樣一張表T[i]來定義，其中i為1...64，T[i]是i的正弦絕對值之4294967296次方的整數部分，這樣做是為了通過正弦函數和冪函數來進一步消除變換中的線性性。

當所有512位分組都運算完畢後，ABCD的級聯將被輸出為MD5散列的結果。下面是一些MD5散列結果的例子：

MD5 ("") =
MD5 ("a") =
MD5 ("abc") =
MD5 ("message digest") =
MD5 ("abcdefghijklmnopqrstuvwxyz") =
MD5 ("") =
MD5 ("1234567890") =
參考相應RFC文檔可以得到MD4、MD5演算法的詳細描述和演算法的C源代碼。

3) SHA1 及其他
SHA1是由NIST NSA設計為同DSA一起使用的，訪問http://www.itl.nist.gov/fipspubs可以得到它的詳細規范--[/url]"FIPS PUB 180-1 SECURE HASH STANDARD"。它對長度小於264的輸入，產生長度為160bit的散列值，因此抗窮舉(brute-force)性更好。SHA-1 設計時基於和MD4相同原理,並且模仿了該演算法。因為它將產生160bit的散列值，因此它有5個參與運算的32位寄存器字，消息分組和填充方式與MD5相同，主循環也同樣是4輪，但每輪進行20次操作，非線性運算、移位和加法運算也與MD5類似，但非線性函數、加法常數和循環左移操作的設計有一些區別，可以參考上面提到的規范來了解這些細節。下面是一些SHA1散列結果的例子：

SHA1 ("abc") = a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d
SHA1 ("") = 84983e44 1c3bd26e baae4aa1 f95129e5 e54670f1
其他一些知名的Hash演算法還有MD2、N-Hash、RIPE-MD、HAVAL等等。上面提到的這些都屬於"純"Hash演算法。還有另2類Hash演算法，一類就是基於對稱分組演算法的單向散列演算法，典型的例子是基於DES的所謂Davies-Meyer演算法，另外還有經IDEA改進的Davies-Meyer演算法，它們兩者目前都被認為是安全的演算法。另一類是基於模運算/離散對數的，也就是基於公開密鑰演算法的，但因為其運算開銷太大，而缺乏很好的應用前景。

沒有通過分析和差分攻擊考驗的演算法，大多都已經夭折在實驗室里了，因此，如果目前流行的Hash演算法能完全符合密碼學意義上的單向性和抗沖突性，就保證了只有窮舉，才是破壞Hash運算安全特性的唯一方法。為了對抗弱抗沖突性，我們可能要窮舉個數和散列值空間長度一樣大的輸入，即嘗試2^128或2^160個不同的輸入，目前一台高檔個人電腦可能需要10^25年才能完成這一艱巨的工作，即使是最高端的並行系統，這也不是在幾千年裡的幹得完的事。而因為"生日攻擊"有效的降低了需要窮舉的空間，將其降低為大約1.2*2^64或1.2*2^80，所以，強抗沖突性是決定Hash演算法安全性的關鍵。

在NIST新的 Advanced Encryption Standard (AES)中，使用了長度為128、192、256bit 的密鑰，因此相應的設計了 SHA256、SHA384、SHA512，它們將提供更好的安全性。

Hash演算法在信息安全方面的應用主要體現在以下的3個方面：

1) 文件校驗
我們比較熟悉的校驗演算法有奇偶校驗和CRC校驗，這2種校驗並沒有抗數據篡改的能力，它們一定程度上能檢測並糾正數據傳輸中的信道誤碼，但卻不能防止對數據的惡意破壞。

MD5 Hash演算法的"數字指紋"特性，使它成為目前應用最廣泛的一種文件完整性校驗和(Checksum)演算法，不少Unix系統有提供計算md5 checksum的命令。它常被用在下面的2種情況下：

第一是文件傳送後的校驗，將得到的目標文件計算 md5 checksum，與源文件的md5 checksum 比對，由兩者 md5 checksum 的一致性，可以從統計上保證2個文件的每一個碼元也是完全相同的。這可以檢驗文件傳輸過程中是否出現錯誤，更重要的是可以保證文件在傳輸過程中未被惡意篡改。一個很典型的應用是ftp服務，用戶可以用來保證多次斷點續傳，特別是從鏡像站點下載的文件的正確性。

更出色的解決方法是所謂的代碼簽名，文件的提供者在提供文件的同時，提供對文件Hash值用自己的代碼簽名密鑰進行數字簽名的值，及自己的代碼簽名證書。文件的接受者不僅能驗證文件的完整性，還可以依據自己對證書簽發者和證書擁有者的信任程度，決定是否接受該文件。瀏覽器在下載運行插件和java小程序時，使用的就是這樣的模式。

第二是用作保存二進制文件系統的數字指紋，以便檢測文件系統是否未經允許的被修改。不少系統管理/系統安全軟體都提供這一文件系統完整性評估的功能，在系統初始安裝完畢後，建立對文件系統的基礎校驗和資料庫，因為散列校驗和的長度很小，它們可以方便的被存放在容量很小的存儲介質上。此後，可以定期或根據需要，再次計算文件系統的校驗和，一旦發現與原來保存的值有不匹配，說明該文件已經被非法修改，或者是被病毒感染，或者被木馬程序替代。TripWire就提供了一個此類應用的典型例子。

更完美的方法是使用"MAC"。"MAC" 是一個與Hash密切相關的名詞，即信息鑒權碼(Message Authority Code)。它是與密鑰相關的Hash值，必須擁有該密鑰才能檢驗該Hash值。文件系統的數字指紋也許會被保存在不可信任的介質上，只對擁有該密鑰者提供可鑒別性。並且在文件的數字指紋有可能需要被修改的情況下，只有密鑰的擁有者可以計算出新的散列值，而企圖破壞文件完整性者卻不能得逞。

2) 數字簽名
Hash 演算法也是現代密碼體系中的一個重要組成部分。由於非對稱演算法的運算速度較慢，所以在數字簽名協議中，單向散列函數扮演了一個重要的角色。

在這種簽名協議中，雙方必須事先協商好雙方都支持的Hash函數和簽名演算法。

簽名方先對該數據文件進行計算其散列值，然後再對很短的散列值結果--如Md5是16個位元組，SHA1是20位元組，用非對稱演算法進行數字簽名操作。對方在驗證簽名時，也是先對該數據文件進行計算其散列值，然後再用非對稱演算法驗證數字簽名。

對 Hash 值，又稱"數字摘要"進行數字簽名，在統計上可以認為與對文件本身進行數字簽名是等效的。而且這樣的協議還有其他的優點：

首先，數據文件本身可以同它的散列值分開保存，簽名驗證也可以脫離數據文件本身的存在而進行。

再者，有些情況下簽名密鑰可能與解密密鑰是同一個，也就是說，如果對一個數據文件簽名，與對其進行非對稱的解密操作是相同的操作，這是相當危險的，惡意的破壞者可能將一個試圖騙你將其解密的文件，充當一個要求你簽名的文件發送給你。因此，在對任何數據文件進行數字簽名時，只有對其Hash值進行簽名才是安全的。

3) 鑒權協議
如下的鑒權協議又被稱作"挑戰--認證模式：在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡單而安全的方法。

需要鑒權的一方，向將被鑒權的一方發送隨機串（"挑戰"），被鑒權方將該隨機串和自己的鑒權口令字一起進行 Hash 運算後，返還鑒權方，鑒權方將收到的Hash值與在己端用該隨機串和對方的鑒權口令字進行 Hash 運算的結果相比較（"認證"），如相同，則可在統計上認為對方擁有該口令字，即通過鑒權。

POP3協議中就有這一應用的典型例子：

S: +OK POP3 server ready <[email protected]>
C: APOP mrose
S: +OK maildrop has 1 message (369 octets)
在上面的一段POP3協議會話中，雙方都共享的對稱密鑰（鑒權口令字）是tanstaaf，伺服器發出的挑戰是<[email protected]>，客戶端對挑戰的應答是MD5("<[email protected]>tanstaaf") = ，這個正確的應答使其通過了認證。

散列演算法長期以來一直在計算機科學中大量應用，隨著現代密碼學的發展，單向散列函數已經成為信息安全領域中一個重要的結構模塊，我們有理由深入研究其設計理論和應用方法。