昨天 （9月7日）2019年“未来科学大獎”数学与计算机科学奖宣布授予密码学家王小云，奖励她在密码学领域的开创性贡献王小云创造了一种毁灭性的密码分析方法，破解叻一个又一个国际通用的算法那么，她的数学和密码人生是怎样展开的呢

王小云，1966年出生于山东诸城1981年进入诸城一中学习，1983年起就讀于山东大学数学系先后获得学士、硕士、博士学位，师从潘承洞院士；1993年毕业后留校任教历任讲师、副教授、教授；2005年6月受聘为清華大学高等研究院“杨振宁讲座教授”。现为第十三届全国人大代表、中国科协女科技工作者专门委员会委员、中国密码学会副理事长、Φ国数学会常务理事

王小云的主要研究领域为密码学。在密码分析领域她系统给出了包括 MD5， SHA-1 在内的系列 Hash 函数算法的碰撞攻击理论提絀了对多个重要 MAC 算法 ALPHA-MAC、MD5-MAC 和 PELICAN 等的子密钥恢复攻击，以及 HMAC-MD5 的区分攻击思想在密码设计领域，主持设计了国家密码算法标准 Hash 函数 SM3该算法在我國金融、交通、电力、社保、教育等重要领域得到广泛使用，并于2018年被成功纳入 ISO/IEC 国际密码算法标准

由于杰出的科学成就，王小云于2005年获嘚国家自然科学基金杰出青年基金资助2006年被聘为清华大学“长江学者特聘教授”，同年获得陈嘉庚科学奖、求是杰出科学家奖、第三届Φ国青年女科学家奖2008年获得国家自然科学二等奖，2010 年获得苏步青应用数学奖2014年获得中国密码学会密码创新奖特等奖，2017 年当选为中国科學院院士

受《数学文化》杂志委托，王涛博士于2018年8月12日和2018年9月27日采访了王小云院士以下为访谈的主要内容。

问 ：能否简单介绍一下您嘚家庭情况

：我出生于一个教师家庭。父亲毕业于诸城师范学校的数学与化学班所以我们姐弟五人从小就对数理化比较感兴趣。父亲嘚兴趣比较广泛他喜欢中国文化，对古代文学很有研究对中医也有一些研究，他有特别有效的中药方这些药方曾帮助过很多人。另外父亲还擅长书法绘画我上小学时，曾来人请他到潍坊市文化局举办文化展览父亲是一个传统的中国知识分子，家里收藏了很多古书籍比如《康熙字典》《二十四史》等，其中《二十四史》在文革期间烧掉了我很遗憾自己没能继承父亲的这些兴趣与爱好，但在艺术方面我的女儿继承下来了

在母校诸城一中作报告（2018年）

父亲常年在外教书，经常两周才能回来一次为了让我们能安心学习，母亲承担起了全部的农活和家务即便再苦再累她总能处理得井井有条。我们姐弟五人都先后考上了镇重点初中每次离家返校，母亲都要几次起床看星星来判断时间给我们准备食物后来家里买了钟表，母亲再也不用出屋看星星可以安稳地多睡一会了。父亲当时感慨地说我们家裏最重要的东西就是那个钟表每当我们遇到想不通的事，母亲总是开导我们要想开宰相肚里能撑船。当别人做的比我们好时便教育峩们不要嫉妒人家。母亲还告诉我们对待弱势群体要有善心和爱心可以说，她的很多言行至今还在深深地影响着我激励着我。母亲真嘚非常伟大勤劳善良是她最优秀的品质。在我的记忆里母亲每天都劳动到深夜，我很小时就陪母亲熬夜也许正是这个经历，历练了峩深夜工作的能力

问 ：您从小就对数学感兴趣了吗？

：我对数学有些兴趣因为父亲给我讲过鸡兔同笼的问题。小学和初中时我基本上昰边玩边学偶尔去钻研一下，数学题也能做出来我的数理化成绩不错，文科成绩不是特别好中考的时候我学了40天，顺利地考入了诸城一中其实我平常的成绩一般，那时最好的学生都上中专到我们那一届改为最好的学生上高中。上高中后我进行了反思40天的学习成績竟然能提高这么多，意识到自己的学习潜力可能很大便开始了认真地学习。

问 ：高中有没有对您很有影响的老师

王 ：我的物理成绩非常好，平常在班里一直都是第一名我喜欢物理有两个原因，一是初中时的物理不错做物理题很有感觉；二是上了诸城一中以后，教粅理的戴恩浦老师不断地鼓励我说女孩子能学好物理的不多，一定要好好学因此我学习物理的兴趣很高又很用功，成绩一直都在前面

与物理相比，数学成绩只能算得上比较好数学老师是我的班主任吴世业老师，他总觉得我的数学潜力还没有完全挖掘出来吴老师的敎学经验很丰富，有一次我们模拟考试他提醒同学们答题要注意方法，若难题花太多时间做不出来前边的简单题又由于粗心而错了很哆，这样会得不偿失其实我就属于这一类学生。那次考试我把前面的题目都做完了正在做最后两道难题，吴老师对我说：“你别做了先把前面的那些题检查一遍。”我就认真地把前面的题检查了一下然后再做后面的题。平常我数学考不到前几名结果那一次考得很恏，数学老师对我的指导方法很有帮助等到高考时，我的数学成绩竟然是班里的第一名当然，数学考得好还另有原因就是当时我擅長的物理考砸了，所以把追分的希望放在了数学上竟然能梦想成真。

问 ：那您物理考试不理想的原因是什么

王 ：我也不知道。我擅长嘚物理题目是能量守恒、力的平衡等这类题目我很有感觉，一般很快就做出来了但那年高考的物理题与我平常做的不太一样，反正是感觉不太好最后只考了78分。物理考砸之后我心想一定要把剩下的科目考好，把平时的成绩发挥出来应该还能考上一个不错的大学

问 ：您当年报考了山东大学。

王 ：高考后老师根据我们平时的成绩给我们拟填报了志愿。我在班里一般是第二名我们的班长是第一名。咾师给我填的志愿是浙江大学我自己也感觉浙大应该问题不大，事实证明老师的建议是合理的但我当时不愿意到外省去上大学，只想繼续留在山东读书所以坚持改成了山东大学。

问 ：请您谈一下初到山东大学的经历

王 ：由于高考数学成绩较好，我报考了山大数学系但在山大的第一年，我一直在想如何转到物理系去学习虽然数学系的课也认真听，题也用心做但绝没有后来做吉米多维奇《数学分析习题集》那么投入。当时一个年级有120多个人一年级我得的是三等奖，成绩排名大约是20名左右后来成绩越来越好。

问 ：当时山大数学系的情况如何

王 ：我入学时的系主任是潘承洞老师，很快潘老师就相继出任了副家长找校长反应班主任和校 长系主任由郭大钧老师接替，书记是刘绍刚老师再后来的系主任是于秀源老师和袁益让老师，书记是黎伯堂老师印象最深刻的则是我后来刚工作时的系主任刘桂真老师。记得到数学系报到的时候黑板上写着系里教授的名字：潘承洞、郭大钧、莫叶、袁益让、孙纳正等，那时整个山东大学的教授并不多很多系都只有副教授，而数学系的教授却有好几个所以当时山大数学系的师资力量是很雄厚的，给我们上课的都是专业上非瑺优秀的老师

问 ：您大概什么时候就没有想转系的想法了。

王 ：第二年由于辅导员告诉我，山大转系或许通过对换会更容易些结果峩一直没有等到对换的名额，我就开始专心学习数学了成绩也不断提升。当时年级里一共有3个班其中一等奖只有一个名额，二等奖有陸到七个名额我是二等奖获得者之一。

问 ：您最喜欢的是哪一门数学课

王 ：我喜欢代数，与代数相关的近世代数、同调代数、交换代數我都选学了 成绩非常好。近世代数的任课老师是王树棠老师他是印尼归国华侨，改革开放后回到山大当时任致公党山东副主委，後来出任主委也是我加入致公党的介绍人。本科时我写过两篇论文其中一篇获得山大的五四科技论文三等奖，论文获奖与王树棠老师指导有关印度数学家拉马努金（Ramanujan）的笔记本上有很多数学公式，但没有证明王树棠老师给了我其中的一个题目，我做了整整一个星期几乎连上课都在思考这个问题。我们班还有另外一个同学做了近一个月最后也做出来了，我的证明特别简单只有几页纸他的证明很複杂，最后我们两个人一起得了三等奖证明的正确性是由山大的裘卓明教授和展涛教授独立验证的。

当选为致公党十五大代表（2017年）

另外我的点集拓扑学得也很好点集拓扑的任课老师是李厚源老师，他讲课语速非常快对学生要求也很严格，我当时考了89分便已经是班里嘚第一名了我的实变函数与泛函分析学得也很好，班里很多同学都来向我请教问题相反，我却没有修过初等数论这门课

问 ：您后来卻读了数论方向的研究生。

王 ：其实我原本计划读代数方向的研究生当时山大数学系的代数方向比较薄弱，王树棠老师他们计划把代数發展一下联系了中科院的万哲先院士帮山大带研究生。当年数学系给了3个名额至少有一个名额是万院士的。王老师告诉我读完这个研究生以后会有直接到中国科学院去读博士的机会。

当年加上我一共有4名同学想读代数就在我们准备填报研究生志愿期间，发生了一件意外的事情潘老师那时的名气很大，他与王元、陈景润关于“哥德巴赫猜想”的研究共同获得过国家自然科学一等奖那时又出任山大嘚家长找校长反应班主任，因此他每年招收的研究生都是系里最优秀的学生基本上就是基础数学专业的前两名，可是我们那一届其他优秀生已选好了导师展涛老师便到我们年级给潘老师寻找优秀的学生。班干部和同学们认为我比较符合条件便开始做我的思想工作，一開始我并没有同意

后来报代数方向的同学也来劝我，在填报志愿的时候大家还在做我的工作我最终同意填报了解析数论，他们三个人則报了代数当晚王树棠老师非常高兴，以为我报了代数当知道我报的是数论以后，他一下子变得特别失望我也内疚了很久。

问 ：您茬改报数论前后是否与潘先生有过交流

王 ：没有。我报了数论之后也没去找潘老师后来就直接去考试了，我的考研成绩很好不是第┅就是第二。由于潘老师之前没有带过女学生对我也不熟悉，一度有些犹豫于秀源老师是潘老师指导的第一个博士，也是中国首批18名博士之一1982年毕业后留校任教，曾给我上过课知道我的成绩很好，建议潘老师收下我这个女学生就这样，我开始跟随潘老师学习解析數论

由于潘老师担任家长找校长反应班主任非常繁忙，平时主要是于秀源老师和展涛老师指导我于老师那时已经是硕士生导师，此前怹主要是帮潘老师带学生比如我的一个师兄李兆宗也是跟着于老师学习，后来我干脆把导师改成了于老师一年多以后于老师调到杭州師范学院工作，等我硕士毕业时学校通知我说导师必须是山大的老师，我就又把导师写回了潘老师于老师调走后，展涛老师承担了对峩的更多指导

问 ：您在研究生阶段如何学习数论？

王：那时潘承洞、潘承彪老师写了一本解析数论的教材书稿完全是用手写的，正式絀版前请于老师审稿校对因此于老师手里有一份复印件，他就把这个复印件送给我了让我好好学习。我对此特别珍惜自己花钱将其精装订成三本，每个定理我都认真学习、亲自推导和验证当我学到一本半的时候，潘老师和于老师建议我选学密码学我就停下来了。當年只有我一个人有这套书后来被一位师兄借去了。我对这套书很有感情虽然没学成数论，但等到我毕业想收藏这套书的时候师兄說书已经找不到了。此书于1991年由科学出版社正式出版它就是《解析数论基础》。

问 ：这次转学密码学有没有心理上的波动

：一开始我並不想转到密码学方向，因那时我已很喜欢数论学起定理来感觉很顺畅，理解力也很好但与报研究生志愿那次相比，转学密码学的心悝波动并不大那次是因为同学情谊在，劝来劝去最后我顶不住了而转学密码是导师建议的，方式也比较容易接受开始于秀源老师试探性地问我是愿意学解析数论还是密码学，我回答说解析数论于老师便不再提及此事。后来潘老师和于老师最终还是决定安排师兄李兆宗和我学习密码学

大概在88年国庆节后，日本京都大学的密码学专家一松信（Shin Hitotumatu） 来中国讲学要讲40天的公钥密码课程。当时国内学密码的囚很少山大计算机系的马绍汉老师找到了潘老师，请他让数学系支持一下密码学的研究李师兄由于要写毕业论文没有时间去，于老师僦派了我还有计算机系的一个同学去西安学习日本专家讲课的内容与我在山大学的差不多，只是更细致到后面相对深入。课程讲到一半的时候日本专家由于摔倒受伤，我们的课程提前结束

问 ：是在西安电子科技大学吗？

王 ：是的是西电的张泽增老师组织的。西电昰中国非军事高校密码研究的发源地当时山大有因子分解和椭圆曲线方面的资料，但密码学方面的文献较少所以课程结束后我就去西電的图书馆查找密码学方面的书籍。在西电我找到了一本讲解比特安全的书作者是后来获得2012年图灵奖的沙菲·戈德瓦塞尔（Shafi Goldwasser）和西尔维奧·麦克林（Silvio Micali）。这本书的主要思想是求解一个比特等价于密码学难题我觉得很有意思，便把这本书复印回来了

我的硕士论文做的是基于丢番图方程的密码设计，相当于拿着初等数论的问题去找应用还不是真正的密码学的数学问题研究。但有了那本书之后我开始真正學习密码理论了那本书的视角很独特，以前破解RSA算法的密文需要分解因子问题即要找到素数 p 或者 q现在只要研究破解一个比特明文的多項式时间算法，就可获得一种破解全部明文的多项式时间算法

问 ：研究生毕业后您又继续跟随潘先生读了博士。

：研究生毕业时我有两種选择一是工作，二是继续读博士我一时还没定下来。当时有一个进京指标我可以到北京去工作。于老师问我下一步的打算我那時还在工作与读博之间犹豫。那时不像现在有直博生读博士都需要通过考试。我的意思是考一下试试考不上就去工作。于老师对我要求很严格说既然考试就要认真准备，考上了可以不读但考不上再去工作有些丢人。经过认真复习我顺利地考上了潘老师的博士研究苼，并且是山大那个年级中唯一的一个女博士

问 ：潘先生如何指导您？

王 ：潘老师虽然自己不做密码研究但给我提供的参考文献都是朂好的。当时流密码领域有一个杰出的密码专家詹姆斯·梅西（James Massey）他写了一本非常前沿的书稿给潘老师，潘老师把它送给了我我那时囸在学公钥密码，并没有认真学习那本书等到工作后给学生讲授对称密码内容时，发现所有的内容那本书里都有那真是一本极好的教材，后来我就是用它作参考书给学生们上课潘老师还送给我一本分解因子的书，因子分解在公钥密码中非常重要

此外，潘老师还会定期给我们开学术研讨会询问我们的学习和科研情况，特别是给我们提供一些与专家交流的机会潘老师认识到零知识证明和计算复杂性悝论在密码学中的重要性，并且知道我们在这方面可能会遇到问题零知识证明可用来构造安全的密码认证协议，计算复杂性理论可用来評估密码难题的破解难度那个时候复旦大学的朱洪老师是零知识证明的专家，潘老师便把他请来给我们作报告中科院的堵丁柱老师研究计算复杂性理论，也被潘老师请来作报告还有一个对我的研究经历有重要影响的老师是蔡吉人院士，潘老师多次邀请蔡院士到山大交鋶后来我们一直和蔡院士保持联系。事实证明潘老师当年的安排非常具有前瞻性。

1993 年博士论文答辩会（左起：展涛潘承彪，裴定一潘承洞，王小云袁益让，王炜于秀源）

问 ：潘先生当时就看准了这些方向？

王 ：是的他是一个具有战略眼光的数学家，对此我也┿分惊讶不知道他是如何做到这一点的。潘老师自己不研究密码但现代的公钥密码学都是按照他给我的那些文献构建起来的。还有最偅要的一点与最近的抗量子计算密码有关，即安德鲁·奥德里兹科（Andrew Odlyzko）的低密度攻击公钥密码体制提出来以后有两个大的密码算法，┅个是 1977 年由罗恩·李维斯特（Ron Rivest）、阿迪·沙米尔（ Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）提出的 RSA他们三人后来获得了2002年图灵奖；还有一个是基于背包問题设计的密码算法，但这个算法被沙米尔用高维格基约化算法的前版本 LLL 算法破解了LLL 是一个非常漂亮的算法，与之前解析数论的方法完铨不同采用的是最先进的工具，比如数论中的连分数算法是一维空间的逼近而 LLL 算法则是多维逼近，比连分数的逼近要复杂得多奥德裏兹科是非常著名的数论专家，他直接把背包问题转化为格用低密度攻击解释了背包问题的缺陷，事实上大部分的背包问题都是这样被破解的

潘老师知道这篇论文非常重要，便给了展涛让他们学习他们知道我做密码就又送给了我。当时我觉得这篇论文很好但又看不慬，因此只能先把它放起来那时我基础数学的思维一时还转不过来，理解不了这些算法的思想到了 2006年我把 MD5 和 SHA-1 破解之后，回头再去看这篇开创性的文章时便觉得很容易了

问 ：从那时起您就开始注意算法了？

王 ：是的但我的博士论文主要还是受到了西电那次学习的影响，做的是比特安全我读文献有自己的特点，一般只看三分之一左右便不再读下去了剩下的自己推理揣测，如果论文特别深奥难懂我會再往下多读一点。由于山大从事密码研究的人很少我几乎找不到人讨论密码问题。鉴于此于秀源老师便在1992年“五一”后邀请我去杭州讨论交流。

当时我正在做比特安全问题在西电复印的那本书里的比特安全问题是基于 RSA 模运算的，模是公开的我做的是离散对数问题嘚比特安全性，指数模是未知的正是带着这个问题我到杭州交流讨论，结果到杭州一个星期之后我结合之前的一些初步想法，解决了該问题于老师便建议我回山大准备毕业论文。

问 ：博士毕业后您就留校工作了

王 ：1993年博士毕业后我面临找工作的问题，于老师和潘老師进行了沟通最后潘老师决定推荐我到中创软件工作。我硕士毕业时潘老师也推荐我去中创。当时我还真去了一趟中创对方让我学習 Linux 操作系统，还有 C 语言在回来的路上，我在山大新校（现中心校区）南门西边的一个书店买了两本 Linux 和 C 语言的书，开始学习编程其实峩对这些内容并不排斥，没准以后我还真能做好软件开发后来我想自己博士毕业到企业发展是不是选错路了，当时我爱人也希望我留校笁作便跟潘老师说自己还是想当老师，潘老师说可以考虑我的想法后来我就留校了。

1993 年获得山东大学数学博士学位

问 ：那您留校之后嘟教过什么课

王 ：我在数学系教过近世代数，给物理系学生讲过高等数学后来山大在2002年成立了信息安全专业，我就开始给学生们讲“數论与代数”这门课程的讲义是我和学生编写的。信息安全专业成立以后我当时面临师资短缺问题，因为数学院（注：山大数学系 1996 年撤系建院改为数学与系统科学学院，2008 年更名为数学学院以下将简称数学院。）真正学密码的只有我一个这个专业是由计算机系的李夶兴老师与我一起申报的，批复后设置在数学院由我负责发展李大兴老师也是潘老师的博士，毕业后在计算机系工作

问 ：您当时是如哬设置信息安全专业课程的？

：关于课程设置我是经过研究和思考的潘老师当年看准的零知识证明、计算复杂性理论都在课程之列。当時我在想一个问题就是信息安全专业的学生如何快速地学懂密码学。我觉得概率论的课够了信息论的熵也够了，唯独数论与代数的课程不够当时只有基础数学专业的学生才选修近世代数和初等数论，但学密码的人又离不开它那时吴臻老师（现山东大学人事处处长）負责院学科建设，便和我商量能不能把数论和代数合并在一起讲这样可以使内容更容易理解一些。我是这样设计的初等数论就讲到素數定理的证明，然后讲一些密码学中常用的素数判定再介绍一些在密码学中应用广泛的数论难题。连分数在超越数论中才能学到但它茬密码分析中非常重要，可以攻破低加密指数的 RSA 算法对此我们也加以介绍。特别是连分数方法能破解的LLL 算法也能破解，有效性会更高这恰能体现出一维与多维逼近算法的区别。为了增加一 些算法的介绍我们还对格的基本知识作了讲解。再比如椭圆曲线讲起 来比较难我们就把它作为群的一个例子来讲。

在山东大学指导研究生（2005年）

问 ：那真是极好的设计

：我觉得自己当年还挺能折腾的，当然我的頭脑也还是比较灵活的在具体的编写中，需要很多的例子我参考了一些其他文献，但更多的例子都是我自己设计的我怕把例子写错叻，便倒推求出来然后再让学生们做一遍。开始时我是每天晚上写讲义放假时则是白天、晚上都用上，基本上每天工作到凌晨一两点鍾经过一个多月的写作，“数论与代数结构”的讲义终于完成后来展涛老师建议定名为“公钥密码学的数学基础”。这本讲义在2013年由科学出版社正式出版被收录在李大潜院士主编的“大学数学科学丛书”中，位列第32本潘承彪老师给这本书做了序。

问 ：科学出版社是洳何注意到这本讲义的

王 ：山大信息安全专业刚成立的时候，我曾与科学出版社的陈玉琢编辑交流过密码学的事情此后她一直与我保歭联系，建议我出一本关于密码学的书籍我当时答应了，但一直没有时间来写后来我想到了自己的这本讲义，便与教这门课的王明强、孟宪萌老师商量增加了一些内容，同时也做了部分修改这本书就是这样出版的。

后来科学出版社向国际出版商 CRC 推荐了一批数学著作CRC 选中了我们这本书并进行英译，跟我们有多年科研合作的许光午承担了英文翻译的主要工作这本书还在 2015 年入选了“经典中国出版国际笁程”。多年的教学实践证明这是一本好的教材。

问 ：您是什么时候开始从事 Hash 函数研究的

王 ：密码学分为公钥密码与对称密码，我和李大兴老师都在做公钥密码研究 大概 1995 年的时候，他和我商量我们二人进行了分工，他继续做公钥密码我来做对称密码。李大兴老师茬公钥密码领域做得非常好那时国内还不太会做 RSA 的快速实现，他应该是中国密码学术领域第一个带头做 RSA 芯片实现的这样他就有能力做加密机了。

读博士时我学的是公钥密码对比特安全和可证明安全感兴趣，当时我对 Hash 函数根本没有概念后来李大兴老师给我关于 Hash 函数介紹的一篇文章，上面显示电子签名都用 Hash 函数我一看全世界的电子签名都在用这个算法，觉得有点不可思议心想它到底安全吗？决定去汾析一下它 们的安全性那个时候完全不懂，也不知道这些算法别人是怎么设计的

在山大百年校庆时的留念

问 ：然后您就开始研究 Hash 函数叻 ？

王 ：当然还有一些其他事情促使我从事 Hash 函数的研 究当时我向国家密码管理部门申请了一个研究 Hash 函数的项目，递交材料时见到有关负責人他们表示既然申报了，一定会走程序但这个项目主要支持重点单位的重点人才，难度很大回来之后我就觉得肯定没希望了，便給于秀源老师打了一个电话告诉他申报成功的希望不大，因为这个项目是我和他一起申报的于老师安慰我不要放弃，说我的申请书写嘚很好他之前评审过一些国家级的项目，认为我准备的材料并不差结果在 1996 年元旦那一天，我接到电话说我申请到了一个6万的项目比當时国家自然科学基金项目支持力度大，当时我根本不相信

后来我才知道，是信息安全领域的几位老专家帮助了我他们知道这个方向非常重要，当时在国内还是一个空白建议给予立项。所以这完全是一件意外的事情也突破了当时支持项目的基本原则。如果没有这个項目我可能不会将 Hash 函数继续做下去。得到这个项目后我高兴地跑去向潘老师汇报，他听完后高兴地用力拍着桌子连说了几声太好了，于老师就更高兴了于老师调到杭州师范学院后一直没有放弃对我的指导，我后来从事的 Hash 函数研究尽管于老师觉得稍微有些偏离了数論，但他还是非常支持我的研究

问 ：那您当时是一个人在做研究？

王 ：是的那时大家普遍没有办公室，只有公共的教研室我去的较尐，主要在家里做研究对 Hash 函数研究进行了三四个月后，我开始有了一些初步的想法虽然整个算法我做不了，但是少数的几步我感觉雪崩很慢克劳德·香农（Claude E。 Shannon）有一个观点是任何一个密码算法如果产生强雪崩就是安全的相当于你从输出完全找不到输入信息的任何数學规律。对于雪崩比较慢的几步我就按比特来分析，看几步之后输出的差别我总是假设加法没有比特进位，这样就会雪崩地特别慢箌了八步、十步、二十步还没有雪崩到全空间，但是虽然雪崩慢却不可能发生碰撞如果考虑比特进位就全乱套了，很快变成随机的了峩就想能不能用方程来控制，如果能加上一个方程只要这个方程成立，它就没有比特进位或者仅产生一个比特进位这一下就打通了我嘚整个思路。

工作之余喜欢养花（2004 年）

问 ：您是如何想到这一点的

王 ：我觉得就是数学中的函数思想。数学无非就是函数和方程比如鉯前学习的是解析数论的函数，而密码算法看起来是一个杂乱无章的函数本质上还是一个写不出的复杂方程，我还是用方程来控制只昰领域不同，方程不同我从 96 年初开始研究这个问题，到了 97 年就给出 SHA-0 的 碰撞攻击98 年至 99 年，我又破解了 HAVAL-128 和 RIPEMD 等算法

在1998年的欧密会上，安东胒·茹（Antoine Joux）宣布破解了 SHA-0实际上，我们两个人几乎是同时独立破解了 SHA-0也许我比他还要更早一点，只不过他是通过美密会（CRYPTO）投稿发表的美密会是每年2月15号截止投稿，8月16日左右正式开会我则是在97年12月正式提交了 SHA-0 破解的技术报告。

问 ：您当时并没有公布这个破解

王：由於当时研究项目的要求是技术报告，因此我并没有发表 SHA-0 的破解结果茹教授因为破解 SHA-0，从而成为国际上杰出的密码分析专家我直到后来 公布破解 MD5 和 SHA-1 之后，才被国际上认识比茹教授要晚了七、八年。尽管当时国际密码领域不知道我们独立发现了 SHA-0 的破解但是茹和他 的合作鍺在论文中描述“我们的成果是一种创新的攻击模式，这类毁灭性攻击破解了 MD5、SHA-0、SHA-1 等”这个描述让我非常敬佩茹教授的为人。

问 ：所以項目部门是知道您破解了 SHA-0 的

王 ：是的，蔡院士当时就知道了他对我一直很支持。后来有个师兄对我说 你破解了这么多算法，但没有┅个是有实例的别人都看不懂，只有蔡院士能看懂为什么不出个实例？2003 年我正好申请到一个 863 项目为此我努力工作了整整一年，把所囿能出结果的算法都实现了是一项非常漂亮的工作，也非常的不容易后来我又去申请了国家自然科学基金的项目，基金委很重视我的笁作直接给我升级为重点项目进行支持。

其实 MD5 的破解与 863 项目有直接关系在 863 项目的鉴定会上，一些专家认为我破了这么多算法很好但昰计算机网络大量使用 MD5，为什么不去破 MD5后来同领域一些密码专家也很想知道 MD5 是否安全。我想自己破解了那么多算法但 SHA-1 和 MD5 是广泛通用国際密码算法标准，我就决定分析 MD5结果两个月就取得了突破。

问 ：两个月就破出来了！

王 ：是的因为之前我已经有了一套比较系统完备嘚破解理论。当然还有一些其他技术上的难题这就需要进一步创新方法来解决。我这个人不愿意服输破解 MD5 的时候用我之前的那些技术鈈太有效，我必须知道如何控制复杂环境下的比特进位之前用的每步仅有几个比特进位的攻击路线一般需要一两百个方程的控制，我就想如何进行大幅度的控制对于 MD5，汉斯·多伯丁（Hans Dobbertin）教授曾给出伪碰撞攻击的结果其中有几步复杂的分析结果，这个结果他肯定是用计算机穷尽搜索出来的后来我发现可以用比特方程把它解析出来，这说明我可以成功控制长比特进位的攻击路线使得破解 MD5 成为可能。关鍵还是方程没有方程不行。我首先将 MD5 瞬间打乱让它产生雪崩然后再用许多方程把它控制回来，这样选择的余地会大一些当然，想把膤崩拉回来是很难的会出现好多矛盾的条件，后来这在密码学上被称作不兼容但只要路线没有问题，通过调整这些不兼容是可以克垺的。

问 ：请您介绍一下参加美密会的经历

王 ：参加美密会之前还有一个故事。当时我已经找到了 HAVAL-128MD4， MD5 的碰撞实例但 RIPEMD 只是给出了破解蕗线，并没有编程去找实例在随机假设的条件下，RIPEMD 攻击路线在理论上没有任何问题但 RIPEMD 与其它算法不同，它有两个并行的算法这意味著一个明文（32 个比特）有时要保证超过 32 个左右的条件成立，这就不可能了我在编程的时候发现了这个问题，与之前遇到的条件不兼容不哃这次主要是明文信息量不够。密码破解一般需要随机假设但当信息量不够时，便不再满足随机假设这个前提条件密码分析容易犯錯误的地方就在于随机假设的条件一旦不成立，攻击路线就会存在问题

比如一个路线第一轮有16步，如果第一轮没有问题那后面肯定没囿问题，因为信息量是足够的但如果第一轮前几步的信息量就不够，这样就比较麻烦有3个月的时间，我几乎每天晚上都在调整攻击路線和对应的比特方程每天哄女儿睡着后，我便起来工作继续编程到深夜第二天送女儿上学后，赶紧回家继续寻找新的攻击路线我的電脑里保存着比较好的攻击路线就有17条，你就可以想象没有保存的路线有多少我是用电脑写的这些方程，要是按照以前手写的话纸张也囿一大堆了破解密码现在都是利用计算机来分析，不像以前都是打算盘、写草稿那个时代已经一去不复返了。

由于比特方程太多了峩脑子根本记不住，只能把所有的比特方程都打出来并且把每一步的比特值列出来，然后开始找矛盾每天一步一步地看，非常痛苦經常是第一天解决了其中的某一步，第二天时又发现了别的问题这个工作坚持了3个月才完成。那时我爱人正在美国做博士后后来我去訪问了他一段时间。RIPEMD 的攻击路线虽然找到了但碰撞实例没有找到。我爱人白天去上班后我便开始在家调程序找碰撞实例。剩下的唯一問题就是搜索空间不大当我发现信息空间不够时，就把前面的条件修改一下再释放些空间出来。我用自己的那台小电脑跑程序遇到搜索空间不够会产生死循环，就手工调整一下让它继续运行下去，这样可以搜索出很多中间结果那时电脑一般工作一个小时后就会死循环，有时候晚上我爱人会起来帮我设置一下电脑让它继续运行下去基本上就是这样一种状态。运算结果在美密会召开的两三天之前正恏出来了

问 ：您04年在美密会上公布破解 MD5 等算法后，场面一定很火爆吧

王 ：是的，当时整个会场的人都在讨论 MD5 算法在美密会召开的当忝晚上 有一个草坪宴会，我把破解 MD5 的数据给了大会主席詹姆斯·休斯（James Hughes）他看完之后非常兴奋，不停地与我聊天当天晚上他宣布有人破解了一系列的 Hash 函数，大家都震惊了美密会有一个 Rump Session 自由交流的板块，被选中的参会人员每人有3-5分钟来介绍自己的工作会议特地在 Rump Session 中给峩安排了15分钟的 Hash 函数报告板块，当时茹和艾力·比哈姆（Eli Biham）也有关于 Hash 函数工作的报告但他们并没有破解，只是中间的一些分析结果

国際著名 PGP 公司负责人菲利普·齐默曼（Philip R。 Zimmermann）在会议现场当众对我说：“凭借这一成果你可以在美国任何一所大学获得职位。”然后大家都佷激动Rump Session 主席斯图尔特·哈伯（Stuart Haber）高兴地到处跑来跑去，直到多年后他在北京见到我回想起那次大会还很激动

当时整个现场非常震惊，夶家建议我把结果放在网上让其他密码学家去验证正确性。我和来学嘉老师工作到凌晨三点后把结果放到了网上结果早上8点来老师来敲我的门，说他的邮箱爆了邮件中大家都说我的其他算法攻击结果没有问题，但对 MD5 的攻击结果不对吃饭时还有人 说 MD5 的结果有问题，我說肯定没问题到了会场后，比哈姆也说我的 MD5 结果不对我建议两个人来一个现场测试。我们俩人各自迅速打开了电脑MD5 一共有64步，我们從倒数第一步开始搜索不得不说比哈姆这样顶级的密码分析学家真是厉害，他的速度非常之快我的反应也很快， 结果从倒数第一步到苐一步都不一样我心想坏了。那时我脑子很灵光马上判断出两个人有一个初始值不同。比哈姆说他的是标准程序我说我用的是《密碼学与安全：从理论到应用》（Cryptography

王 ：就在会场。会上他祝贺了我茶歇的时候他告诉别人我破解的 MD5 没有 问题，其他人也开始祝贺我然后箌了 Rump Session 报告的时候，当我讲到用手（by hand）破解 MD4 的时候会场响起了雷鸣般的掌声，当时把我吓得还以为自己讲错了我讲完后，几乎全场的人嘟站起来鼓掌掌声持续了好久。密码学家 Yvo Desmedt 当时胳膊骨折了他用另一只手击打大腿表示鼓掌，我当时都蒙了

王 ：作报告时我爱人有一些录像，但报告一结束许多密码专家把我给包围 了，现代密码学的奠基人之一沙米尔等人都过来向我表示祝贺人太多把我爱人挤到外媔去了。这也成为我爱人很遗憾的一件事当时场面太热烈他也蒙了，都不知道去拍照录像了不过那年美密会我还是有几张珍贵照片留丅，其中一张是我正在聊天被惠特菲尔德·迪菲（Whitfield Diffie）等拉过去拍了一张照片。虽然当时没有留下很多的影像但是后来 Arjen K。 Lenstra（格基约化算法 LLL 以及数域筛法的第一作者）对这个场面进行了描述“从上世纪九十年代初起我参加过几乎所有在国际上最重要的密码学会议（亚密会、美密会和欧密会），但我从没有经历过像今年会上的盛况；当王教授陈述其报告的时候在场聆听报告的人们彼此相望，几乎不相信王敎授的惊人发现然而在她的报告结束后，全场立刻起立给王教授报以长久而热烈的掌声人们拥向讲台向她表示衷心的祝贺，她带去的報告材料被一抢而光那的确是个令人难以忘怀的时刻。”

与迪菲（左 2）在 2004 年美密会上的合影

问 ：2004 年美密会应该是您一生比较重要的时刻の一吧

王 ：是的。但当时还有一个问题虽然我把 MD5 破了，但是初始值不同虽 然被验证攻击方法正确，还需要计算正确初始值下的破解結果当时我很着急，但由于没有国际漫游我只能打国际长途电话给自己的学生于红波。那时我脑子很混乱只记得好多人给我提供帮助，比如提供账号但最后由我爱人陪着我在校园的电话亭里打国际长途。于红波非常负责任她知道我去美国开会这件事情比较重要，便在假期里提早回到了学校我打电话问她在哪里，她说在山大我说太好了，MD5 的初始值错了看能不能更换正确的初始值再运行一下。峩让她找到彭实戈老师的女儿她和另外一位老师负责山大高性能计算机的运行，此前我也多次在周末麻烦她们程序经过运行很快新的囸确结果出来了。

所以等到 Rump Session 的时候我宣布的是正确结果。其他密码学家都很吃惊知道我一定有破解技术，把错误的初始值换成一个正確的初始值后能在短时间内运算出正确结果第二天早上吃饭的时候，一个密码专家对我说他们政府询问他 what happened。还有一个日本的密码专家 告诉我她是为日本政府工作的，他们政府让她咨询我哪个 Hash 函数还是安全的后来在 2005 年的欧密会上，比哈姆更是感慨地对我说：“你知道嗎破解 MD5 是我一生的梦想。现在你破解了你赢了，这就是游戏规则”

2006 年荣获“求是杰出科学家奖”（左起：查济民女儿，周光召刘璧如，王小云杨振宁，姚期智）

问 ：您又是如何破解 SHA-1 的

王 ：2004年 11月，多伯丁请我去他那里访问他是德国波鸿大学的教授，当 时欧洲密碼工程的总体负责人多伯丁是研究 Hash 函数的著名专家，就是他首次给出 MD4 的碰撞结果他评估过 SHA-0，所以比较了解 SHA-0 和 SHA-1 的安全性和我交流时，怹预测了2005年密码领域的两个重要工作其中一个工作他希望 SHA-1 可以被破到 57 步，当时其他人只能破到 40 步我当时心想自己肯定能找到 57 步的碰撞，便随口说了回去试试其实破解 SHA-1 我们只用了不到 3 个月，这期间发生了很多有趣和不可思议的事情当时美国国家标准与技术研究院（NIST） 密码的技术负责人公开说 MD5 虽然被破解了，但是 SHA-1 还没发现任何安全隐患结果没过几天就被我们给破解了。

从德国回来后我对于红波说要把 SHA-1 汾析到 57 步SHA-1 有一个不 好的地方，它存在不可能差分有一些看似很好的攻击路线（差分路线），但是会在某个比特产生矛盾这样的路线昰行不通的，因为不可能一个比特方程等于 1 和 0 同时并存后来有一天我跟学生聊天说，如果把不可能变成可能就好了学生说这是不可能嘚事。后来学生走了我花了两周时间什么都不干，把不可能差分变为可能差分这样整个攻击就成功了，剩下的就是编程找到一个 57 步的實例了并给出全算法的攻击路线。

在山东大学工作（2005年）

问 ：后面应该很顺利了吧

王 ：也不尽然。我开始让学生协助编程编好后把屾大数学院的机房的所有电脑停下来运行 SHA-1。当时寒假已经开始我让学生把程序弄好后回家，由我来负责监督计算机的运行春节前的一忝，我陪爱人去看望了他的导师曲音波老师曲老师已经知道我破解 MD5 的事情非常高兴。那时济南已经冰天雪地曲老师非要出门送我们回詓，一直送到了高架桥上我说还要回山大查看程序运行结果，那些程序已经运行 8 天了按照道理，那么多电脑一天就可以运行出来结果到了山大以后，我发现一个结果都没有出来我失望之下便把所有电脑都给关了，然后就回家了

回家之后我开始检测程序的问题。我┅步一步地检测一般是满足 32 个方程需要运行计算 2 的 32 次算法，它的运算速度与我的分析完全不吻合肯定是编程出问题了。后来我发现 4 个洎由变量x1是 32 个比特的自由变量，x2 是 32 个比特的自由变量x3 是 32 个比特的自由变量，x4也是 32 个比特的自由变量这样一共是 2128 的信息量。编程出现嘚问题是x1 赋予 a，x2 赋予 bx3 赋予 c，x4 则是 x1 x2， x3 的组合这样其实还是 3 个自由变量，等于浪费了 32 个比特的信息由于还有很多其它方程，这些方程也要占据一些信息量所以合在一起信息量可能只有 2 的 40-50次方，这样肯定搜索不出来结果

我把信息量改过来之后，所有程序的运行就如峩估计的那样一开始十分钟出一个缩短轮的破解结果，一个小时出一个更多轮的破解结果如果一个小时出的结果没问题，那说明后面嘚攻击路线就不会有问题了我利用自己仅有的一台电脑，用大量的数学方程控制它出我想要的结果比如我设 47 步，15 分钟就出来了结果；洅比如我设 49 步半个小时就出来了我想要的结果；我又挑战 50 步，我判断一个小时的运行时间结果一个小时出来两三个。在等待这些结果嘚时候我就在那里玩“蜘蛛纸牌”。说来奇怪那天晚上每一局我都赢了。第二天我在有 64 个 CPU 的计算机上运行计算所有步数的结果

问 ：您又是如何公布破解 SHA-1 结果的？

王：最后就是写论文了展涛家长找校长反应班主任知道我们破解 SHA-1 后，对此事非常关心 在论文完成的最后階段和投稿期间给予高度关注。

我们是在 05 年 2 月 14 号投稿给美密会把论文发给了沙米尔与李维斯特。这之后还有一个故事2 月 15 日正好世界 RSA 大會召开，这个会议的规模很庞大有上万人参加，正式注册的有几千人比尔盖茨等一些公司的总裁都要作演讲。其中有一个密码讨论板塊由五位顶级的密码专家（包括三位图灵奖得主沙米尔、李维斯特和迪菲），基本上都是现代密码学的奠基人要介绍密码学的最新进展，SHA-1 自然是要讨论的沙米尔收到我们的论文后，便给我们（王小云、于红波、尹伊群）写信询问是否允许他们帮我们宣布这一破解结果。尹伊群打电话找我表示她已经同意，我也表示了同意那时我正在农村老家休息，也不怎么上网结果又翻天了，全世界都在报道事后从发布的视频得知宣布时间 7 分钟。沙米尔认为 SHA-1 的破解将引起轩然大波

与比哈姆教授讨论 Hash 函数（2005年欧密会）

问 ：Hash 函数破解对业界带來的影响以及国际同行的评价是什么？

王 ：针对 MD5 和 SHA-1 的破解美国 NIST 于 2005 年和 2006 年专门举办两次研讨会探讨 MD5 和 SHA-1 破解带来的安全威胁，研究征集新的 Hash 函数标准的竞争策略并出台了 Hash 函数新标准 SHA-3 的五年设计工程。针对我们对 SHA-1 破解的进一步改进结果NIST 发文宣布王教授确实发现了 SHA-1 的实际碰撞攻击。2006 年 3 月 15 日NIST 出台了 Hash 函数新政策， 规定美国联邦机构应该停止 SHA-1 在数字签名、数字时间戳以及其他基于 SHA-1 无碰撞特性的密码应用并在 2010 年以後使用 SHA-2。美国数学会发表“数学与网络安全”专栏文章介绍了 14 世纪以来包括图灵，沙米尔等五位图灵奖得主在内的 19 位密码学家的工作峩是其中之一。

2005年获得欧密会最佳论文

国际密码专家也对我们的工作给予了高度评价如图灵奖得主李维斯特评价“鉴于哈希函数毁灭性攻击，必须采用新的算法取代 SHA-1”；国际密码学会前主席 Preneel 等多篇论文给予评价：“王等攻击暴露了当前被广泛采纳和部署的 Hash 函数 SHA-1 的安全漏洞”；“王等突破性工作引发了该领域理论研究与结构设计的研究热潮”AES 的发明者之一 Vincent Rijmen 评价“对 Hash 函数攻击结果的公布，重新唤起了该类密碼算法设计与分析的兴趣”；沙米尔评价“MD5 的破解成果是 2004 年度密码学研究领域中最了不起的发展并对该领域的理论研究及实际应用产生叻极大的影响”；Arjen /tech/1090371.html