王小云：讓網絡社會更安全可信

　　2005年，一位中國女科學家的名字震動了全球密碼學界。

　　她帶領博士生于紅波提出對兩大用于數字簽名經典Hash（哈希或者雜湊）算法體系（MD5和SHA-1）的破解策略，導致標準制定者美國標準技術研究所（NIST）不得不提前棄用SHA-1，啟動新算法的設計。

　　她就是密碼研究者王小云。

　　王小云的密碼破解研究始于在山東大學期間獲得國家自然科學基金的資助，她為此默默鉆研了整整10年。如今，已是清華大學楊振寧講座教授的王小云對密碼算法的設計工作進展如何，下一個5年她又準備迎接怎樣的挑戰？

　　從“破壞者”到“立法者”

　　密碼設計和破解的挑戰總是交替進行，二戰時那種靠轉輪機械加密和手工查字典式解密的傳統密碼學早已成為歷史，取而代之的是必須靠計算機才能處理的復雜算法。今天大量涉及商業機密、國家安全和個人隱私的原始數據只有經過加密和認證算法的轉換后，才能在網上傳輸和存儲。

　　2010年12月10日，經過長達5年的征集、設計和評估，美國安全局和美國標準技術研究所宣布進入最后一輪的5種候選算法，提交者分別來自意大利、美國、瑞士、新加坡和丹麥，王小云團隊沒有參加。

　　7天后，中國國家密碼管理局在網站發布公告，正式公開中國版的新一代數字簽名算法——SM3密碼雜湊算法。包括術語定義、函數及算法描述、運算示例在內共11頁。這是中國首度公開商用密碼算法，王小云是專家組組長。

　　“其實新算法我們早已經設計好了，并提交給國家密碼管理局，但沒有投出去發表。相信我們這個算法比國際上征集到的更有優勢和特色。”王小云說。

　　這正是王小云最擅長的領域——哈希函數的分析與設計。

　　“哈希函數是數字簽名里最基礎、最核心的技術。無論你用何種數字簽名，里面一定有一個哈希函數。它可以是MD5，可以是SHA-1，也可以是SM3或者SHA-3。”王小云說，“可以說我后來的成果都是從中積累而成。”

　　談到國家自然科學基金的支持，王小云充滿感激。正是這種從最基礎開始作研究的態度和“板凳甘坐十年冷”的毅力，使她對哈希函數潛心鉆研十年終結碩果。

　　王小云介紹說，一個算法的推出往往需要很長時間，而新的密碼體系在研發初期都要經歷一定階段的保密。從綜合各方面對于安全性的需求，到開展主體設計、優化、再設計，再到實施評估和測試，直到經過反復修訂后形成最終的規范文本，這個周期通常需要好幾年。“這是一個設計——分析——再設計的循環過程。”王小云說。而在各種密碼算法的研發中，哈希函數的周期可能是最長的，至少需要5年時間。等到一定的保密期過后，為促進學術研究，最終一般都會公布。相比之下，標準由誰掌握更為重要。

　　“一些新分析方法的出現，對密碼學的研究也具有很重要的推動作用。”王小云說。如果說設計方面主要是為了滿足國家網絡安全的需要，分析方面，王小云則完全是站在國際學術界前沿來做的。而與此同時，王小云還帶領年輕團隊對她自己提出的SHA-1碰撞攻擊進行了改進，繼2005年給出破解效率為2的69次方運算的理論碰撞攻擊后，2006年她將這一效率提高到了2的61次方。

　　扎實的基礎是團隊信心所在

　　在密碼學里，加密和認證是兩個完全不同的概念。加密的目的是保護數據本身的安全，使非法用戶即使取得加密過的資料，也無法獲取正確的資料內容。而認證的目的主要是確認用戶的真實性，使系統可以依據不同的用戶身份給予不同的權限。哈希函數主要用于數據認證中的數字簽名，而數據加密和其他認證技術還有分組密碼和流密碼兩種策略。作為對稱密碼的三大方向，三者之間有區別也有融合。

　　目前世界上最流行的分組密碼算法標準AES發布于2000年，用這種算法加密的數據常與另一種分組密碼MAC碼（消息認證碼）同時傳輸。在運用AES對數據加密的同時，由于MAC碼中往往攜帶有與身份有關的信息，接收方還可通過它進行校驗，以驗證數據的真實性。這樣便可以同時完成加密和認證。有趣的是，這種采用分組方法MAC碼也可以通過哈希函數構建，這就為用哈希函數方法實施攻擊提供了可能。

　　2009年，王小云帶領博士生王薇、賈珂婷等人，在哈希函數分析的基礎上提出了一種MAC破解策略。首次提出了“區分帶差分路線的碰撞或幾乎碰撞一般方法”，并在該年度密碼學界的頂級會議——歐洲密碼學大會上，給出了一個復雜度為2的97次方的有效攻擊。該方法適用于對好幾類重要MAC碼的攻擊。這無論對MAC碼還是哈希函數本身的設計，無疑又提出了新的要求。

　　據介紹，這種方法的秘訣在于“成功避開了哈希函數第一圈差分路線存在大量條件而造成的無概率優勢的分析障礙”。對此，王小云作了一個形象的比喻：上面是安全的AES，下面是安全的AES，中間是MAC。她抓起筆迅速畫了一張示意圖，說：“這就好像四周都是銅墻鐵壁，似乎根本無法穿透。”如果按照傳統思維，到這里工作就無法進行下去了。但王小云換了思路，她采用一種“誘導”策略，對AES實施了欺騙，使程序“繞過AES，直接‘空降’到MAC里面，對MAC里的認證信息進行收集，實施破解”。該方法曾吸引了前來訪問的圖靈獎得主Shamir的濃厚興趣。

　　流密碼是對稱密碼里的另一重要領域，常用于移動通信中的數據加密。2004年開始，歐洲啟動了一項流密碼標準工程eStream，經過公開征集，第二輪有10多個參賽算法入選。王小云帶領博士生張海納對參賽算法進行了跟蹤分析，在一次會議上給出了針對其中兩個算法——ABC V3 和TSC-4——的弱密鑰攻擊，當即導致這兩項算法被直接淘汰。并且后者是當時國際上針對TSC-4的唯一有效攻擊。“這主要是我的博士生所做的工作。”王小云高興地說。

　　在國家自然科學基金的支持下，現代密碼學特別是對稱密碼里的三個重要方向——哈希函數、分組密碼、流密碼全部在王小云團隊里建立了起來，而且實現了很好的融合。在王小云看來，其實這些不同的密碼分析方法并不必拘泥于教科書上的分類，在一定層次上都是可以交叉的。“關鍵是要能進入一定的深度后再來看，就很容易打通。”“另外很重要的一點，經過幾年的訓練，我們的博士生已經成長起來。”這可以說是王小云這5年來所做的主要工作，也是她今后工作的信心所在。

　　從“格”開始，迎接量子時代

　　2008年舉行的新興量子密碼學工作組國際會議公布了一些關于量子計算領域和量子密碼學的有趣結合。不僅為經典密碼學提供了一些量子計算可能的攻擊，同時也給出了一些能抵抗量子計算的特別密碼算法。其中一個被稱作“格”的新密碼體制再度引起了王小云的關注。

　　實際上，王小云和“格”的初次相遇是在20多年前。“這是我一直比較惦記的一個方向。”王小云回憶說。

　　那還是上世紀80年代末在山東大學念書時，她的老師潘承洞院士交給她一篇關于“低密度攻擊”的論文，論文針對經典的背包密碼體制給出了一個攻擊，但運用的方法卻是王小云從未聽說過的。

　　“當時我都沒看懂”，王小云說。本來是針對基于舊密碼體制提出來的問題，結果卻催生了一個新的密碼體制。一貫敏銳的直覺提醒她，這個方法將來或許會很有用。但由于當時她的主要精力在哈希函數上面，對“格”的好奇心只好先放下，這“心結”在她心里一擱就是20多年，直到她對哈希函數的研究取得階段性成果。

　　1977年，Rivest、Shamir和Adleman三位科學家聯合將一個數論難題運用于密碼學，締造了歷史上第一個公鑰密碼體制，三人因此分享了2002年的圖靈獎。該算法也被以三人的首字母命名。他們巧妙利用了將一個大整數逆向分解為兩個較小整數的乘積時，運算難度遠遠超過計算后者乘積這一原理。當大整數足夠大時，由于因子分解過程接近于無窮長，從而保證了密碼的不可破解。

　　當三位聰明的設計者提出這一密碼系統時，超級計算機每秒鐘已可運算百萬次，他們估計，照此速度可在4小時之內對一個50位整數進行因子分解，但要分解一個100位的數要花幾乎一個世紀。因此即使考慮到計算速度可以再提高百萬倍，基于200位數的密碼也足夠用了。然而，最新的統計數據卻表明，現在連512位的RSA算法都已經不安全了，要升級到1024位才夠用。正在發展的超級計算機運算能力和設計者們當時的考慮實在相去甚遠。

　　王小云說，格密碼體制在應用上最重要的優點，就是可以抵抗量子計算。“如果量子計算機研制成功，那么其他密碼體制都可能被破解，但格密碼體制卻破解不了。這一點已被國際密碼學界公認，所以‘格’也被稱為‘后量子時代’的密碼體制。”

　　現在，王小云已經和法國密碼學界的重鎮——法國巴黎高等師范學院開展了互訪，準備聯合探究這一新的密碼體制。圖靈獎得主Shamir也和她就該研究方向保持著密切交流。而Shamir正是以格的理論實施低密度攻擊的第一人。

　　在王小云指導下，她的學生在兩三年前已開始進入這一領域，沉下心來鉆研相關數學著作。“一開始確實比較難，但現在我們已經逐漸把它吃透了”，王小云相信自己的直覺。“只要堅持做下去，一定會有收獲的。”

　　這種深夯基礎的一貫做法起了效果。在一本介紹“格數學”的經典著作中，對于一個數學命題的證明，該書作者用了整整一章，“后來我們的小組用幾行就解決了”，談起這個，王小云的喜悅溢于言表。

　　和15年前相比，現在的王小云或許少了些年輕恣意，多了份擔子和責任。但無論如何，這注定她的下一個5年又將是一場充滿風險和樂趣的長跑。

　　王小云

　　清華大學高等研究院楊振寧講座教授、密碼理論與技術研究中心主任；山東大學數學與系統科學學院教授；中國密碼學會密碼數學理論專委會主任。