密碼學是理論計算機的一個很大的方向。之前準備先寫密碼學概論再提在hash函數(shù)破解上做出重大貢獻的王小云教授的工作，不過前兩天王小云獲得求是杰出科學家獎以及100萬獎金，在媒體上又掀起了一輪宣傳狂潮，但是有些報道極端弱智，錯誤百出，所以我趁機糾正一下，并介紹密碼學的一個組成部分——hash函數(shù)，以及王小云在這上面的工作。
王小云的主要工作是關于hash函數(shù)的破解工作。她在2005一個密碼學會議上宣布破解了SHA-1，震驚了全世界。所以要介紹和理解她的工作，先看一下hash函數(shù)具體是怎么回事。
簡單的說，hash函數(shù)就是把任意長的輸入字符串變化成固定長的輸出字符串的一種函數(shù)。通俗得說，hash函數(shù)用來生成信息的摘要。輸出字符串的長度稱為hash函數(shù)的位數(shù)。
目前應用最為廣泛的hash函數(shù)是SHA-1和MD5，大多是128位和更長。
hash函數(shù)在現(xiàn)實生活中應用十分廣泛。很多下載網(wǎng)站都提供下載文件的MD5碼校驗，可以用來判別文件是否完整。另外，比如在WordPress的數(shù)據(jù)庫，所有密碼都是保存的MD5碼，這樣即使數(shù)據(jù)庫的管理員也無法知道用戶的原始密碼，避免隱私泄露（很多人在不同地方都是用的同一個密碼）。
如果兩個輸入串的hash函數(shù)的值一樣，則稱這兩個串是一個碰撞(Collision)。既然是把任意長度的字符串變成固定長度的字符串，所以，必有一個輸出串對應無窮多個輸入串，碰撞是必然存在的。
一個“優(yōu)良”的hash函數(shù) f 應當滿足以下三個條件：
- 任意y，找x，使得f(x)=y，非常困難。
- 給定x1，找x2，使得f(x1)=f(x2)，非常困難。
- 找x1，x2，使得f(x1)=f(x2)，非常困難。
上面的“非常困難”的意思是除了枚舉外不可能有別的更快的方法。比如第3條，根據(jù)生日定理，要想找到這樣的x1，x2，理論上需要大約2^(n/2)的枚舉次數(shù)。
幾乎所有的hash函數(shù)的破解，都是指的破壞上面的第三條性質，即找到一個碰撞（前兩條都能被破壞的hash函數(shù)也太弱了點，早就被人拋棄了）。在密碼學上還有一個概念是理論破解，指的是提出一個算法，使得可以用低于理論值得枚舉次數(shù)找到碰撞。
王小云的主要工作是給出了MD5，SHA-0的碰撞，以及SHA-1的理論破解，她證明了160位SHA-1，只需要大約2^69次計算就能找出來，而理論值是2^80次。她的尋找MD5碰撞的方法是極端高效的。傳說王小云當時在會議上把碰撞寫出來，結果被下面的人驗證發(fā)現(xiàn)不對，原來她把MD5算法的一個步驟弄錯了。但是她立馬聯(lián)系她的當時留在中國的學生，修正算法，并找到一個新的碰撞。這一個是對的。
看到這里，那些認為中國國安局應該將這些結果封存作為秘密武器甚至幻想用這些成果來襲擊美國之徒可以停住你們的YY了。這種形式上的破解，在大多數(shù)情況下沒有實際性的作用。更別提MD5早就被美國人拋棄了。
但是，說這種破解一點實際意義都沒有，那就侮辱了廣大密碼學家的智商，密碼學家不會無緣無故的弄出碰撞這么一個概念來。下面簡單的介紹一下在特定情況下，怎么利用給定的碰撞來做壞事(翻譯自Attacking Hash Functions)：
Caesar給實習生Alice叫寫了一封推薦信(letter)。同一天，Alice叫Caesar在推薦信上數(shù)字簽名，并提供了一份推薦信的電子板。Caesar打開文件，發(fā)現(xiàn)和原件一模一樣。所以他在文件上簽了名。
幾個月后，Caesar發(fā)現(xiàn)他的秘密文件被非法察看。這到底是怎么回事呢？
a25f7f0b 29ee0b39 68c86073 8533a4b9
事實上，Alice要求Caesar簽名的文件letter已經(jīng)被Alice做了手腳，準確地說，Alice還準備了另外一個文件order，它們的MD5碼完全一致。而Caesar的數(shù)字簽名還依賴于MD5算法，所以Alice用order文件替換Letter文件之后，Caesar的數(shù)字簽名依然有效。那封order給Alice提供了察看秘密文件的權限。
具體的實現(xiàn)方法可見Hash Functions and the Blind Passenger Attack。我在這里簡單的解釋一下(只是大致思路，具體實現(xiàn)方式，需要對文件結構信息有所了解)：
letter文件的內容是：
if(x1==x1) show "letter" else show "order"
order文件的內容是：
if(x2==x1) show "letter" else show "order"
其中字符串"letter"和"order"代表兩封信實際顯示的內容。x1，x2是一個MD5的碰撞。
上面的方法，只供參考和學術用途，實際使用所引起的后果概不負責。
參考：
PS：我跟王小云老師的接觸很少，上過倆次她的討論班而已，亦感覺到王小云老師的嚴謹和耐心。在去年一個Turing獎獲得者的演講上，王小云提問的時候竟口而出“I ask who”的中式英語，在引起哄笑的同時，我也極端佩服她的勇氣。也許只有這樣才能做出非常好的工作吧。
PS2: wikipedia在國內可以通過free_door瀏覽。