密碼學(xué)家王小云：十年破解MD5和SHA-1兩大國(guó)際密碼

王小云在2019未來科學(xué)大獎(jiǎng)?lì)C獎(jiǎng)典禮上。本報(bào)記者李牧鳴攝

2019年11月17日，梳著干練短發(fā)、帶著金邊眼鏡的王小云，走進(jìn)“未來科學(xué)大獎(jiǎng)周”的報(bào)告廳，用一口淳樸的山東口音，開始講述她與密碼的往事。

首個(gè)由中國(guó)民間發(fā)起的“未來科學(xué)大獎(jiǎng)”，迎來了首位女性得主——今年53歲的清華大學(xué)高等研究院楊振寧講座教授王小云。她獲得了“數(shù)學(xué)與計(jì)算機(jī)科學(xué)獎(jiǎng)”，因?yàn)樗?ldquo;在密碼學(xué)中的開創(chuàng)性貢獻(xiàn)，她的創(chuàng)新性密碼分析方式揭示了被廣泛使用的密碼哈希函數(shù)的弱點(diǎn)，促進(jìn)了新一代密碼哈希函數(shù)標(biāo)準(zhǔn)”。

破解兩大國(guó)際密碼算法

偶然間看到的一條注釋，讓吳彥冰決定跟著王小云讀博士。

5年前，四川大學(xué)信息安全專業(yè)本科生吳彥冰，在閱讀公認(rèn)世界第一黑客的凱文·米特尼克所著《欺騙的藝術(shù)》時(shí)，發(fā)現(xiàn)一段文字中有個(gè)中國(guó)人的名字，這是一條關(guān)于“MD5已被王小云教授破解”的注釋。

了解這條注釋背后的故事后，吳彥冰被密碼學(xué)深深吸引了。畢業(yè)前他向王小云發(fā)了郵件，決定探索密碼學(xué)這個(gè)迷人的世界。如今，他已師從王小云，漫游密碼世界。

時(shí)間回到2004年，對(duì)于國(guó)際密碼學(xué)界來說，這注定是不同尋常的一年。

這年的8月，在美國(guó)加州圣巴巴拉召開的國(guó)際密碼大會(huì)上，王小云宣讀了自己和研究團(tuán)隊(duì)對(duì)于MD4、MD5、HAVAL-128和RIPEMD四個(gè)國(guó)際著名密碼算法的破譯結(jié)果。

這被認(rèn)為是2004年密碼學(xué)界最具突破性的結(jié)果，堪稱學(xué)術(shù)界的一場(chǎng)強(qiáng)烈地震。當(dāng)年國(guó)際密碼大會(huì)總結(jié)報(bào)告上寫道：我們?cè)撛趺崔k?MD5被重創(chuàng)了，它即將從應(yīng)用中淘汰。SHA-1仍然活著……

多年來，由美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究院(NIST)頒布的基于哈希函數(shù)的MD5和SHA-1算法，是國(guó)際上公認(rèn)最先進(jìn)、應(yīng)用范圍最廣的兩大重要算法，后者更被視為計(jì)算安全系統(tǒng)的基石，有著“白宮密碼”之稱。

沒多久，SHA-1的末日降臨。2005年2月，在美國(guó)召開的國(guó)家信息安全研討會(huì)上，5名著名密碼學(xué)家公布了哈希函數(shù)發(fā)展史上的重要研究進(jìn)展——他們收到了來自中國(guó)的王小云等3位女研究者對(duì)SHA-1全算法的攻擊。

2005年，美國(guó)《新科學(xué)家》雜志在一篇文章中，用了頗具震撼力的標(biāo)題——《崩潰!密碼學(xué)的危機(jī)》，報(bào)道了王小云團(tuán)隊(duì)花10年時(shí)間取得的學(xué)術(shù)成果。

2006年，NIST頒布了美國(guó)聯(lián)邦機(jī)構(gòu)2010年之前必須停止使用SHA-1的新政策，并于次年向全球密碼學(xué)者征集新的國(guó)際標(biāo)準(zhǔn)密碼算法。

改變戰(zhàn)爭(zhēng)走向的古典密碼

王小云從事的密碼學(xué)，是一個(gè)既古老又新興的學(xué)科。在1949年以前，人類社會(huì)經(jīng)歷了漫長(zhǎng)的古典密碼時(shí)期。

從古到今，密碼被頻繁應(yīng)用在戰(zhàn)爭(zhēng)中，保護(hù)己方秘密并洞悉對(duì)方情報(bào)成了克敵制勝的重要條件。

中國(guó)古代兵書《六韜》中記錄了陰符和陰書兩種加密通信方式。國(guó)君和在外主將之間用陰符秘密聯(lián)絡(luò)，八種不同尺寸長(zhǎng)度的陰符，隱藏著不同的軍情秘密。如需傳遞軍機(jī)大事則用陰書：把書信拆成三部分，分派三人發(fā)出，每人拿一部分，只有三部分合在一起才能讀懂信的內(nèi)容。

大約在公元前700年，古希臘軍隊(duì)用一種圓木棍進(jìn)行保密通信。公元前405年，雅典和斯巴達(dá)之間的伯羅奔尼撒戰(zhàn)爭(zhēng)進(jìn)入尾聲，斯巴達(dá)軍隊(duì)截獲了雅典信使的一條重要加密情報(bào)并破譯，由此改變了作戰(zhàn)計(jì)劃，贏得戰(zhàn)爭(zhēng)的最后勝利。

這種加密方法中，加密方把紙條纏繞在特定的木棒上，寫上原信息，木棒撤掉之后，紙條上的字母變成了亂碼。解密方收到這個(gè)紙條后，用相同的木棒就可以恢復(fù)原信息。

聰明的古人，用簡(jiǎn)單的置換方式就設(shè)計(jì)出一個(gè)密碼。不過，古典密碼的加密方式不能讓人知道，一旦泄露密碼就被破解。

當(dāng)王小云走進(jìn)密碼學(xué)的世界時(shí)，這門學(xué)科已經(jīng)發(fā)展到了公開加密方法的現(xiàn)代密碼時(shí)期。

家國(guó)情懷塑造密碼天才

1966年，王小云出生于山東諸城一個(gè)教師家庭。童年時(shí)，做數(shù)學(xué)老師的父親講“雞兔同籠”的故事，就是她最早的數(shù)學(xué)啟蒙。1983年，17歲的王小云考入山東大學(xué)數(shù)學(xué)系，師從著名數(shù)學(xué)家潘承洞。讀完了本科、碩士與博士，她留在山東大學(xué)任教。后聽從導(dǎo)師建議，將研究方向從解析數(shù)論轉(zhuǎn)向密碼學(xué)。

39歲時(shí)，王小云被聘為清華大學(xué)高等研究院楊振寧講座教授，之后曾獲得中國(guó)密碼學(xué)會(huì)“密碼創(chuàng)新獎(jiǎng)特等獎(jiǎng)”以及“網(wǎng)絡(luò)安全優(yōu)秀人才獎(jiǎng)”，51歲當(dāng)選中國(guó)科學(xué)院院士。

多年后，王小云回憶起讀書經(jīng)歷時(shí)，提到老師潘承洞對(duì)學(xué)生的一個(gè)特別要求，不管是出國(guó)深造，還是做訪問學(xué)者，兩年或者三年，到了時(shí)間就得回來，堅(jiān)決立足于國(guó)內(nèi)發(fā)展。

或許是耳濡目染了老一代學(xué)者身上的這種家國(guó)情懷，破解了兩大國(guó)際密碼算法后，王小云放棄了參與設(shè)計(jì)美國(guó)向全球征集的新國(guó)際標(biāo)準(zhǔn)密碼算法，轉(zhuǎn)而設(shè)計(jì)國(guó)內(nèi)的密碼算法標(biāo)準(zhǔn)。

此后，王小云和國(guó)內(nèi)其他專家設(shè)計(jì)了我國(guó)首個(gè)哈希函數(shù)算法標(biāo)準(zhǔn)SM3。如今，SM3已為我國(guó)多個(gè)行業(yè)保駕護(hù)航，在金融、國(guó)家電網(wǎng)、交通等國(guó)家重要經(jīng)濟(jì)領(lǐng)域廣泛使用。

“密碼破解非常重要，沒有破解，就很難有密碼應(yīng)用的標(biāo)準(zhǔn)化、規(guī)范化，商用密碼體系也很難加強(qiáng)起來。”王小云眼中的密碼學(xué)是矛與盾的交鋒，攻與防的藝術(shù)。

“天書”哈希函數(shù)到底是什么

今天，計(jì)算機(jī)網(wǎng)絡(luò)、移動(dòng)網(wǎng)絡(luò)、物聯(lián)網(wǎng)、衛(wèi)星網(wǎng)絡(luò)還有大數(shù)據(jù)、云計(jì)算，這些人們已經(jīng)熟知的科技場(chǎng)景，都離不開密碼技術(shù)的支撐，需要密碼來解決安全問題。

王小云曾將密碼比作鑰匙：“沒有密碼的保障，就相當(dāng)于有人偷了家里的鑰匙，可以隨時(shí)自由進(jìn)出你家，而你卻渾然不知。”

密碼學(xué)重要到何種地步?不得不從一個(gè)密碼學(xué)中的基本工具說起，它就是王小云打了多年交道的哈希函數(shù)。

這個(gè)時(shí)代的所有網(wǎng)絡(luò)信息安全，需要滿足機(jī)密性、可認(rèn)證性、不可抵賴性、完整性與有效性這五大安全屬性，才可以有效防御黑客的攻擊。其中，有效性是指效率問題，而前四個(gè)屬性中，機(jī)密算法保障機(jī)密性，即不被竊取、看到;數(shù)字簽名算法滿足的是可認(rèn)證性和不可抵賴性;哈希函數(shù)算法保證信息的完整性。

不過，數(shù)字簽名算法必須和哈希函數(shù)一起才能保證可認(rèn)證性和不可抵賴性。因此，五大安全屬性里有三個(gè)，都離不開哈希函數(shù)。

密碼上的哈希函數(shù)，可以將任意長(zhǎng)度的消息壓縮成固定長(zhǎng)度的哈希值，而哈希值就像每個(gè)人都擁有唯一的“指紋”一樣，哈希函數(shù)的重要之處就是能夠賦予每個(gè)消息唯一的“數(shù)字指紋”，即使更改該消息的一個(gè)比特，對(duì)應(yīng)的哈希值也會(huì)變?yōu)榻厝徊煌?ldquo;指紋”。

清華大學(xué)高等研究院數(shù)學(xué)博士吳彥冰打了個(gè)比方，就像把一本書里的某一頁(yè)或一個(gè)字更改了，但看書的人很難判斷更改的地方，即便全書通讀一遍也未必能發(fā)現(xiàn)，“但通過哈希函數(shù)，輸入稍有不同，輸出結(jié)果就會(huì)完全不同”。

“嚴(yán)師”與“慈母”

在現(xiàn)代密碼學(xué)中，哈希函數(shù)占據(jù)著基礎(chǔ)而又重要的地位。上世紀(jì)90年代，王小云開始進(jìn)行哈希函數(shù)研究，1994年開始嘗試破解MD5和SHA-1。

一種密碼算法的破解往往需要花費(fèi)十年，甚至更久的時(shí)間，即便如此，成功率也只有1%左右。這注定是一個(gè)要“坐冷板凳”的研究領(lǐng)域，王小云就是用了整整十年的時(shí)間，破解了MD5和SHA-1兩大密碼算法。

清華大學(xué)密碼學(xué)博士生叢天碩覺得，導(dǎo)師王小云似乎對(duì)密碼有特別的直覺，做科研“就像是在跟著電影里的世界級(jí)大師一起工作”。

有一次，叢天碩和師兄嘗試去攻擊破解一個(gè)密碼算法，想了很久不清楚是否可行，后來去找導(dǎo)師咨詢，“王老師聽完，說你們直接去做就行，她一眼就明白怎么回事兒了”。在叢天碩看來，王小云總能看到很遠(yuǎn)的地方，讓學(xué)生去嘗試前沿的研究。

學(xué)生眼中，這位導(dǎo)師在學(xué)術(shù)上要求“特別嚴(yán)厲”。學(xué)生的論文，一定要做到最好才能發(fā)表，“如果做到第二或有稍微的改進(jìn)空間，她都是不能接受的，會(huì)讓學(xué)生繼續(xù)深入做研究”。

學(xué)術(shù)之外，王小云又很慈祥。叢天碩打算申請(qǐng)一個(gè)國(guó)外實(shí)踐時(shí)，王小云會(huì)對(duì)出行住宿仔仔細(xì)細(xì)問個(gè)清楚，擔(dān)心學(xué)生的安全。“剛讀博時(shí)，王老師會(huì)和學(xué)生溝通，根據(jù)我們的興趣，制定培養(yǎng)計(jì)劃，還給出很多研究方向，讓我們?nèi)L試。”叢天碩說。

解密的驚心動(dòng)魄更多在內(nèi)心

在一些電影大片中，常有特工或黑客破解密碼的驚險(xiǎn)鏡頭，短短幾秒鐘就成功進(jìn)入了對(duì)方的內(nèi)部系統(tǒng)。當(dāng)邁進(jìn)密碼學(xué)的大門后，吳彥冰發(fā)現(xiàn)很多人對(duì)密碼的認(rèn)識(shí)并不準(zhǔn)確，或許是看電影后形成的刻板印象，誤把破解銀行卡或郵箱密碼當(dāng)成密碼學(xué)家的工作，“其實(shí)那不是真正的密碼，只是一個(gè)簡(jiǎn)單的‘口令’”。

王小云在一檔節(jié)目中做了這樣的科普：當(dāng)你輸入一串字符，如果不經(jīng)過任何處理直接送到服務(wù)器來驗(yàn)證，它一定不是密碼，只是一個(gè)口令;如果輸進(jìn)去的字符，通過密碼運(yùn)算得出另外一個(gè)結(jié)果，那么這個(gè)結(jié)果可以驗(yàn)證你是否為合法用戶時(shí)，這個(gè)口令就變成了密碼。

“比如戰(zhàn)爭(zhēng)中傳輸了一段密文，當(dāng)這段密文被攔截后，如果讓密碼學(xué)家上場(chǎng)，他們就會(huì)根據(jù)各自的數(shù)學(xué)方法和手段，推導(dǎo)出原文是什么，比簡(jiǎn)單破解銀行卡密碼要復(fù)雜很多。”吳彥冰說。

現(xiàn)實(shí)中密碼學(xué)家的工作，沒有電影中那樣驚心動(dòng)魄。吳彥冰甚至覺得，這是一個(gè)很枯燥的過程，不停地推導(dǎo)公式、做編程，然后用大型計(jì)算機(jī)驗(yàn)證，等待結(jié)果，“想盡各種方法，一個(gè)個(gè)去嘗試，失敗了再重來”。

在吳彥冰看來，破解密碼有時(shí)就像走進(jìn)了一個(gè)巨大的迷宮，一套密碼是經(jīng)過密碼大師在設(shè)計(jì)中一遍遍確認(rèn)，沒有問題后才公布出來，很多時(shí)候用傳統(tǒng)的方法和思維破解不了，可能在迷宮中碰壁多次也找不到出口。

像很多科學(xué)突破一樣，破解密碼也需要勤奮和靈感，熬夜攻關(guān)亦是常態(tài)。吳彥冰跟著王小云做科研時(shí)，有過幾次這樣的經(jīng)歷，“白天忙了一天，晚上腦袋里突然蹦出來一個(gè)靈感，會(huì)亢奮得睡不著，就要順著把理論推導(dǎo)完，不斷嘗試到底行不行”。

吳彥冰曾聽老師王小云講起破解MD5的經(jīng)歷，“那時(shí)候王老師還沒學(xué)過編程，就用手寫推導(dǎo)的方式，寫了400多頁(yè)紙，幾百個(gè)方程，推導(dǎo)了兩三個(gè)月才得到結(jié)果。”

王小云沉浸在密碼的美妙世界中，享受著外人無法體會(huì)的樂趣。生活中她喜歡在家里和實(shí)驗(yàn)室養(yǎng)花，有時(shí)候思考一個(gè)數(shù)學(xué)問題，卻找不到答案時(shí)，就會(huì)起來打掃打掃衛(wèi)生，或者是給花澆澆水，干點(diǎn)別的事情，但實(shí)際上腦子里一直沒有放下科學(xué)問題。

科研過程中，王小云也把這種樂趣傳遞給學(xué)生們。他們既扮演著“設(shè)謎者”的角色，設(shè)計(jì)一套巧妙的密碼算法，彌補(bǔ)前人的不足，希冀讓攻擊者無法突破;同時(shí)還扮演著“猜謎人”的角色，把別人設(shè)計(jì)精妙的體系一舉攻破。“參與者會(huì)有很大的喜悅感和成就感。”吳彥冰說。

就如王小云在未來科學(xué)大獎(jiǎng)的獲獎(jiǎng)致辭中所說，雖然目前密碼學(xué)只被少數(shù)人所熟悉，但未來會(huì)有更多的年輕力量為密碼學(xué)的發(fā)展助力，愿意盡自己的全力去幫助年輕的科學(xué)家們開拓密碼學(xué)這門神秘而又充滿力量的學(xué)科。

標(biāo)簽： MD5 國(guó)際密碼