资讯大咖秀

未来科学大奖得主访谈:王小云的数学和密码人生

更新时间:2019-09-08 10:29:49    来源:返朴    手机版

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

来源 | 《数学文化》2019第10卷第2期

访问整理 | 王涛、王坤

王小云,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 年入选了“经典中国出版国际工程”。多年的教学实践证明,这是一本好的教材。

破解MD5

问 :您是什么时候开始从事 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-128,MD4, 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 函数工作的报告,但他们并没有破解,只是中间的一些分析结果。

2004年美密会宣布破解 MD5

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

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

问 :是在会场吗?

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

问 :Rump Session 时您有照片留下吗?

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

与迪菲(左 2)在 2004 年美密会上的合影

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

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

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

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

破解SHA-1

问 :您又是如何破解 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 天了。按照道理,那么多电脑一天就可以运行出来。结果到了山大以后,我发现一个结果都没有出来,我失望之下便把所有电脑都给关了,然后就回家了。

我把信息量改过来之后,所有程序的运行就如我估计的那样。一开始十分钟出一个缩短轮的破解结果,一个小时出一个更多轮的破解结果,如果一个小时出的结果没问题,那说明后面的攻击路线就不会有问题了。我利用自己仅有的一台电脑,用大量的数学方程控制它出我想要的结果。比如我设 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 K.Lenstra 评价 :“全世界的其他密码学家现在仍然在努力试图跟上王教授,理解她的结果和方法,这对于正确地估价其影响是至关重要的。”

2005年受聘成为杨振宁讲座教授(左起:杨振宁、王小云、顾秉林)

十年坚守,方得始终。面对这些褒奖,虽然它们是对我研究成果的认可,但我更认为这是对我团队的肯定,是对我国密码学界工作的肯定。

任职清华

问 :后来您到了清华大学高等研究院工作。

王 :离开山大原因是多方面的,其中两个原因是我要认真考虑的。一是 2004年 11 月,姚期智先生邀请我到清华大学高等研究院作报告,应是杨振宁先生和姚先生共同的决定,他们想让我到清华去工作。杨先生去山大访问,一下飞机便问展涛校长我能不能到清华工作。

二是正好那时我爱人完成了博士后研究,面临着找工作的问题,他希望到北京去工作。这时清华邀请我,我们一家面临着到底是留在山大还是去清华的问题。后来我去找展涛校长汇报了此事,展校长说他认为我到清华与大师们一起工作,对我将来的事业发展是有帮助的,但是作为校长,从山大的发展角度来说,他不同意我离开山大。

与杨振宁先生交流(2012年清华大学高等研究院成立 15 周年)

问 :所以还是需要您自己做最后的决定。

王 :后来我想要不就去试试吧。我很理解山大老师与同学们对我的深厚感情,毕竟山大培养了我,所以我把自己的所有成果留给了山大,比如我的国家自然科学奖的获奖单位就是山东大学,清华大学并没有拥有我的这些成果。直到现在我一直是山大与清华双聘教授,除了停止了本科生的教学,在山大的其他工作依然正常进行。现在在北京工作,我可以更多地站在国家的角度思考问题,虽然在济南和北京都能为国家做贡献,但北京毕竟是学术中心,许多会议都在北京召开,开完会后我可以立刻回到办公室工作,这是我坚持一线工作的最好选择。

当年 MD5 和 SHA-1 破解,我申报了国家自然科学一等奖,但最后评定为二等奖,我当时没有接受,觉得申报得有些仓促,国际影响力还不凸显,另外我个人觉得这个成果申报一等奖是有资格的, 所以最后没有接受。第二年我继续申报,还是得了二等奖,这次我接受了。我认为第一次我不接受代表了我的学术观点,第二次接受则是尊重大家 的评审, 这就是我看待这个问题的观点。或许一项成果在不太好判断的情况下,评定为二等奖是比较稳妥的。另外一等奖也确实比较难获得,只有像潘承洞、王元、陈景润等学术大师的研究成果,才配得上国家自然科学一等奖。

问 :能不能谈一下与姚期智先生的合作?

王 :姚先生是研究计算复杂性理论的,他的随机性理论在密码学中有很重要的应用,是开创性的工作,他对密码学做了重要的贡献。我和姚先生合作是很自然的一件事情,我们在一起合作了两年多的时间,我们的 973 项目的合作对中国密码学发展起到了很好的推动作用。

与研究生在清华大学办公室讨论问题(2018)

问 :那您与杨振宁先生的接触多吗?

王 :与杨先生的接触很多。他经常到高等研究院的办公室来工作,还不时组织或参加高等研究院的一些活动。杨先生经常给我讲一些物理学界好的工作和他本人的一些经历,另外谈论数学也比较多,特别是提到数学家闵嗣鹤先生。杨先生的父亲杨武之先生是数学家,与闵嗣鹤先生是世交,杨先生曾经谈及昆明居住期间,闵先生经常到杨先生家聊天,谈自己工作中面临的苦恼,有时用诗抒发感情。谈到上世纪 30 年代华罗庚来杨先生家和杨武之讨论数学,还谈到 1928 年至 1929 年期间在厦门柯召和杨武之下围棋的情景。另外也问一些潘承洞老师的事情。我觉得杨先生对密码很关心,经常问我一些密码学的问题。最近杨先生还希望我写一篇区块链的普及文章,他想了解一下区块链的问题。

问 :您在清华做研究还和在山大一样吗?

王 :在山大时我主要是在家中一个人做研究,在清华则主要是在办公室里指导学生做研究,我觉得两个形式不大一样。在山大时我推路线也编程,学生主要帮我部分编程和调整路线,到清华的前半阶段我还是和在山大差不多,后来我发现带出来的学生总体效果欠佳。我开始逐渐调整,把重心放在人才培养上,现在基本上以我指导为主,主要由学生来做。现在流密码的团队已经建立起来了,2012 年开始做这个方向,我指导了三批学生,最后一个学生做成了,当然前面的学生也做了很多工作,但这些工作与问题的解决差距仍很大,主要还是和大量的方程控制和长久坚持有关。现在我主要把握研究方向和思路,提供可能的方法和需要解决的关键技术,激发学生的潜能,使创新成为常态,就跟自己当年做 MD5 和 SHA-1 一样。经过多年的努力,现在终于做出了一些优秀成果。

从白春礼院长手中接过院士聘书

问 :您在去年(2017)当选为中国科学院院士。

王 :我之前申报过四次院士,都是在信息学部。其实一开始朱邦芬老师就建议我从数理学部申报,但更多的密码专家建议我从信息学部申报,我觉得院士申报多次很正常,谁先当选都没有问题。近年来,中国科学院的院士选举进行了改革,国家开始重视交叉领域,因为学科交叉能推动科技创新,国家的重大需求也需要交叉学科。我很幸运第一次在数理学部走交叉就成功了。数理学部的评选非常客观,对我的学术成果比较了解和认同。我非常感谢国家对交叉学科的重视和支持,这是一个积极的信号,将来还会有其他交叉学科的研究人员从中受益。

密码普及

问 :能不能谈一下您和一些数学家的交往经历?

王 :从我在山大读书开始,由于当时的原因与国内数学家接触比较多的是王元院士和潘承彪老师,还有彭实戈老师,他们对我的影响较大。在山大数学院工作时和彭老师是同事,我们常在一起开会交流,他对数学的热爱简直到了痴迷的程度,对密码学的数学问题一直很关心,并且兴趣非常高。我们经常讨论密码数学问题。

与裴定一(左 1)、李淑英(左 2)、于秀源(左 3)教授合影

潘承洞老师任校长时比较忙,实际上我的博士论文和几个师兄的一些论文都得到了潘承彪老师的认真审核,得到了他的细致指导,相当于又多了一个导师。潘老师兄弟对中国数论的发展贡献很大,在人才培养方面做得也很成功。我对潘老师最敬佩的是当年山大数论老师都有在国外交流与工作机会,于秀源、展涛、王玮他们曾出国交流,并且已在国际上崭露头角,潘老师写信让他们按时回国,所有成员都做到了,为国家留住了人才。潘老师当年在山大出台了很多博士、博士后引进计划。

我自己培养人才也是按照这个模式。我培养的学生有的已获得了国家科技进步一等奖,还有一名女学生王美琴的密码分析工作很出色,刚获得省部级的一等奖。我鼓励学生们出国留学,但并不支持他们在国外待那么长的时间,不一定以“青千”的身份引进才回来。当然,是否是“青千”在待遇上的差别很大,不过我相信国家和学校很快会做出调整,让更多真正有能力的学者待遇得到大幅度提高。目前国家人才计划入选者非常优秀,但没有头衔同样优秀的人仍然很多,如何通过支持他们加大国家科技创新能力与水平是一个需要思考的问题。

问 :您刚才谈了与几位数学家的交往,那信息安全专家呢?

王 :信息安全专家主要是蔡吉人院士,他对我的影响是比较深刻的,也是一生的。蔡院士在很多公开场合提到要学习王小云十年磨一剑的精神,我很感动。我特别感动的是蔡院士读了国外顶级密码专家给我的学术评价激动地说感谢你为国家争得了荣誉。还有沈昌祥院士,在学科建设方面给我很多指导,我们同在教育部信息安全指导委员会里任职,他是主任,我是副主任。再有就是肖国镇老师,还有裴定一老师,裴定一老师曾担任中国密码学会理事长。

问 :最后想问您一下数学与密码普及的问题,这方面您有什么好的建议?

王 :我现在主要从事密码学的研究,对数学的普及没有发言权,但我自己可以做一些与密码相关的数学普及。比如分解因子是密码学和数学的交叉领域,从埃氏搜索到连分数方法、数域筛法,计算机能够分解几十比特到 700 多个比特的整数,到今天量子计算机分解十几个比特的整数等。目前国内这方面的书籍并不多,需要下功夫来写。从因子分解的经典数学算法到量子计算算法,里面有很多内容是可以介绍的。

对于密码普及我们已开始做了一些工作,比如在网络空间安全教材体系的规划中,我们为密码普及做了很好的计划。由于密码与网络攻击有关,我认为密码普及适合采用书本和网站这两种形式。密码的普及网站可以介绍密码是什么、密码的重要性、密码如何保护信息和网络安全、密码中的数学问题、密码攻击事件、网络安全事件,用书本的方式向公众普及密码知识,2017 年 10 月,人民出版社出版的《商用密码知识与政策干部读本》就是一本很好的密码应用和科普书籍。杨振宁先生很重视科学普及,他曾送我一本《邮票上的物理学史》,是清华大学出版社出版的,只是忙于工作我只阅读了少部分。

问 :目前公众对密码的理解是不是还有很大偏差?

王 :是的,经常有人来找我破行李箱密码和计算机的口令(笑)。实际上口令 与密码是不一样的,如果有密码技术才可以叫密码,否则就是口令。还有一点就是大家对破译与破解的认识有很大的差异,这个一定要解释清楚,否则对中国的密码和信息安全学术领域是有一定影响的。英文中有两个单词 break 和 attack,我们统一译做破解与攻击。如果一个密码算法的破解难度是 2128 次计算,你用了 2100 次运算破了是破解,230 次运算破了也是破解。2000 年左右学术界把大于 264 次计算的破解叫做理论破解,小于 264次计算的破解叫做实际破解,即大型计算机可以把结果运算出来,当然这个标准是会随着计算机的速度而调整的,目前比特币运算时间可提升至 270 次左右。2006 年我们破解的 SHA-1 是263 次运算,美国的 NIST 官方网站定为实际攻击(practical attack),这在学术界还是比较严格的。十年后,Marc Steven 在谷歌的支持下找到的 SHA-1 碰撞实例也验证了 NIST 的断言,其计算复杂度约为 263 ,与 2006 年我们宣布的攻击复杂度相当。

由于之前的密码学只有加密算法,我们国家一般把明文译出来叫破译,这是延续了传统的概念,是正确的。然而现代密码在计算机网络中有 3 类算法:加密算法、签名算法和 Hash 函数算法。按照原来的定义,只有将加密算法恢复出明文才能叫做破译,其他算法的破解一般不叫做破译,而只能叫做破解。即使就加密算法而言,大量的加密算法由于具有过高的计算复杂度而只能做到理论破解,因此也不能叫做破译。在现代密码学的学术研究中,不管是求出明文或密钥,还是得到了签名私钥或者伪造了签名、给出了 Hash 函数的碰撞攻击,破解了区块链等我们统一都叫破解,破译只是针对其中的一种破解形式。

英文中其实并没有专门对应破译的单词,为此我专门查了牛津字典和百科全书,破译和破解是一个单词 break。这个问题给我造成了一定的困惑,过去十多年大家普遍关心的就是我到底有没有破译。我回应说没有破译,而是破解。大家一听你说没破译,就觉得我没破解算法。由此可见密码普及的重要性。

问 :这还是密码普及得不够。

王 :是的,普及不够,概念不清就容易混乱。这个问题也是我被问到次数最多的问题。国际上就是 break(attack),国内追究破译与破解,后来我明白了可能还是受文化的一些影响。破译叫破解没问题,但是破解可不可以叫破译呢?没人对此下定义。实际上很简单,统一叫破解没有任何问题。

我也很想有时间了专门写一篇关于密码方面的科普文章,也许投给《数学文化》是一个不错的选择。如果我们搞密码的人不重视这件事情,那谁还会去做这件事呢,这也是我们密码人义不容辞的责任。

问 :那文章一定会极受欢迎。非常感谢您接受《数学文化》的访谈,祝您生活愉快!

王小云院士审阅了全文,汤涛教授对本文的访问整理给予了大力支持与鼓励,特此致谢。

特 别 提 示

1. 进入『返朴』微信公众号底部菜单“精品专栏“,可查阅不同主题系列科普文章。

2. 『返朴』开通了按月检索文章功能。关注公众号,回复四位数组成的年份+月份,如“1903”,可获取2019年3月的文章索引,以此类推。

《返朴》,科学家领航的好科普。国际著名物理学家文小刚与生物学家颜宁共同出任总编辑,与数十位不同领域一流学者组成的编委会一起,与你共同求索。关注《返朴》(微信号:fanpu2019)参与更多讨论。二次转载或合作请联系fanpusci@163.com。


文章转载自网络,作者观点不代表本网站立场,如需处理请联系客服

返朴其它文章

一颗肉眼能看到的星星,怎就引出了一个诺贝尔物理学奖?

一颗肉眼能看到的星星,怎就引出了一个诺贝尔物理学奖?

麦耶与奎洛兹的工作首次证明了“径向速度法”是可以用来搜寻系外行星的。撰文 | 王善钦北京时间2019年10月8日晚间,2019年度的诺贝尔物理学奖公布。今年的物理诺奖被分为两部分:著名宇宙学家吉姆·皮伯斯(James Peebles,1935-)得到其中一半;著名“系外行星”专家米歇尔·麦耶(Michel Mayor,1942-)和迪迪埃·奎洛兹(Didier Queloz,1966-)分享另外一半。2019年诺贝尔物理学奖得主 | 诺奖官网这个消息出来后,很多天文圈子里的人觉得有些惊讶,因为宇宙学和系外行星是两个很不相同的领域。不过,我们可以这么想:宇宙学告诉我们从哪里来,系外行星科学告诉我们可以到哪里去:以后地球不适应生存了,就可以考虑搬到“太阳系外的行星”——“系外行星”——上去。麦耶与奎洛兹获奖的原因是:他们发现天上的一颗星星在摆动,然后根据摆动的速度大小确定出这颗星星周围有一颗类...

2019-10-10 10:31:05
复杂度:理解时空和黑洞的新钥匙?

复杂度:理解时空和黑洞的新钥匙?

“It from bit symbolizes the idea that every item of the physical world has at bottom — a very deep bottom, in most instances — an immaterial source and explanation… In short, that all things physical are information-theoretic in origin and that this is a participatory universe.”John A. Wheeler, 1990撰文 | 蔡荣根、阮善明、杨润秋一、背景:It From Qubit?物理学是研究物质和时空的基本结构、相互作用及其运动规律的科学。所以物理学诞生始,物理学家们就一直在努力寻找描述从大到宇宙、小至微观...

2019-09-29 11:10:16
细胞内也有相变:给渐冻症病人“解冻”有了新思路

细胞内也有相变:给渐冻症病人“解冻”有了新思路

物质的气、液、固态三相变化是生活中常见的现象。生命体,作为物质的一种,也不例外。2009年,科学家首次报道了细胞内生物大分子存在“液-液相分离”现象。实际上,相变在细胞中普遍存在,而相变失调可能是一些疾病的病理病因——这为科学家们审视相关疾病提供了新的视角。撰文 | 蒋昕人们有时候会用“单细胞生物”戏称一个人头脑简单甚至缺心眼儿,其实,细胞一点也不简单。一个细胞就像是一座由蛋白质、DNA、RNA等“砖块”建造的城邦,这些“砖块”搭建了不同的办公机构,保障城邦的正常运转。而散布在胞内的细胞器(organelle)就是这些重要的办公场所。其中,有一类细胞器被称为有膜细胞器,它们在磷脂膜建造的“办公室”里干活儿,例如产生能量的线粒体、贮藏和转录DNA并产生RNA的细胞核、翻译和加工蛋白质的内质网等。此外,要正常发挥细胞功能,许多没有“办公室”的无膜细胞器也必不可少,包括细胞核内存储核糖体RNA(...

2019-09-17 22:12:19
人类染色体数发现史:一位华裔科学家的孤独挑战

人类染色体数发现史:一位华裔科学家的孤独挑战

撰文 | 李兆栋千人之诺诺,不如一士之谔谔 。——司马迁《史记·商君列传》“1955年12月22日,凌晨2点,观察到人类细胞含有46条染色体。”当蒋有兴 (Joe Hin Tjio) 在他新拍摄的人类细胞染色体照片的左下角标注上实验观察结果的时候,就已经意识到这个数字将会对人类细胞遗传学领域产生怎样的历史性影响。此刻,瑞典隆德大学 (Lund University) 遗传学研究所的红砖大楼里只剩数点灯火,从蒋有兴所在的一楼实验室窗户朝外望去,瑞典南部城市隆德的郊区一片漆黑,使这座空荡的大楼显得越发寂静、冷清。然而,对蒋有兴来说,这可能是他科学职业生涯中最激动人心的时刻:如果我的观察是正确的,那么佩因特 (T. S. Painter) 就是错误的,整个人类细胞遗传学30多年来对人类染色体数的认识都是错误的!他马上又多拍了几张染色体的照片,还在其中一张上用法语做了类似的记录。在接下来的日子里,...

2019-09-16 08:59:54
未来科学大奖得主访谈:王小云的数学和密码人生

未来科学大奖得主访谈:王小云的数学和密码人生

昨天 (9月7日),2019年“未来科学大奖”数学与计算机科学奖宣布授予密码学家王小云,奖励她在密码学领域的开创性贡献。王小云创造了一种毁灭性的密码分析方法,破解了一个又一个国际通用的算法。那么,她的数学和密码人生是怎样展开的呢?来源 | 《数学文化》2019第10卷第2期访问整理 | 王涛、王坤王小云,1966年出生于山东诸城,1981年进入诸城一中学习,1983年起就读于山东大学数学系,先后获得学士、硕士、博士学位,师从潘承洞院士;1993年毕业后留校任教,历任讲师、副教授、教授;2005年6月受聘为清华大学高等研究院“杨振宁讲座教授”。现为第十三届全国人大代表、中国科协女科技工作者专门委员会委员、中国密码学会副理事长、中国数学会常务理事。王小云的主要研究领域为密码学。在密码分析领域,她系统给出了包括 MD5, SHA-1 在内的系列 Hash 函数算法的碰撞攻击理论,提出了对多个重要...

2019-09-13 16:50:47
未来科学大奖得主访谈:王小云的数学和密码人生

未来科学大奖得主访谈:王小云的数学和密码人生

昨天 (9月7日),2019年“未来科学大奖”数学与计算机科学奖宣布授予密码学家王小云,奖励她在密码学领域的开创性贡献。王小云创造了一种毁灭性的密码分析方法,破解了一个又一个国际通用的算法。那么,她的数学和密码人生是怎样展开的呢?来源 | 《数学文化》2019第10卷第2期访问整理 | 王涛、王坤王小云,1966年出生于山东诸城,1981年进入诸城一中学习,1983年起就读于山东大学数学系,先后获得学士、硕士、博士学位,师从潘承洞院士;1993年毕业后留校任教,历任讲师、副教授、教授;2005年6月受聘为清华大学高等研究院“杨振宁讲座教授”。现为第十三届全国人大代表、中国科协女科技工作者专门委员会委员、中国密码学会副理事长、中国数学会常务理事。王小云的主要研究领域为密码学。在密码分析领域,她系统给出了包括 MD5, SHA-1 在内的系列 Hash 函数算法的碰撞攻击理论,提出了对多个重要...

2019-09-08 10:29:49
对称性与拓扑序:新型量子计算机的物理基础——众妙之门

对称性与拓扑序:新型量子计算机的物理基础——众妙之门

2019年9月5日,2020年物理学新视野奖(New Horizons in Physics Prize)宣布授予凝聚态物理学家陈谐,以表彰她对于理解拓扑物质状态及其关系的深刻贡献。今天的文章就将介绍陈谐近期在拓扑序方面的工作。凝聚态物理学家正尝试列举和分类所有可能的相。如果实现了完整的分类,不仅可以更好地解释目前为止自然界中已知的相,还可能指引新材料和新技术的发展方向。撰文 | N. Wolchover翻译 | 乌鸦少年审校 | 文小刚、陈谐在过去三十年里,凝聚态物理学家发现了物质的相的崭新领域:相互作用粒子的集体运动所演生的新型量子物态。这些新的物质状态迥异于通常的固态、液态或气态,只有在冷却到接近绝对零度时才可能出现,在如此寒冷的条件下,相互作用粒子由于其量子特性,在时空中作十分有规则的集体运动,掩盖了单个粒子的个性,从而导出了全新的量子物态。这些集体运动就像是完美的集体舞,描写了最...

2019-09-07 08:51:27
专访新科物理学新视野奖得主,Caltech物理学家陈谐

专访新科物理学新视野奖得主,Caltech物理学家陈谐

北京时间2019年9月5日晚上,科学突破奖(Breakthrough Prize)委员会宣布,将2020年物理学新视野奖(New Horizons in Physics Prize)授予陈谐、Lukasz Fidkowski、Michael Levin 和 Max A. Metlitski,以表彰他们对于理解拓扑物质状态及其关系的深刻贡献。物理学新视野奖每年最多授予三项物理领域的研究,今年获奖的另外两项研究是,从天文数据中提取基本物理的新技术,以及对量子场论的研究。此前获得新视野奖的华人科学家有物理学家傅亮、祁晓亮(2016年物理学新视野奖)、尹希(2017年物理学新视野奖),以及数学家恽之玮、张伟(2018年数学新视野奖)、许晨阳(2019年数学新视野奖)。今年,凝聚态物理学家陈谐和数学家朱歆文也加入其中。陈谐的研究领域主要是量子多体系统中的相与相变过程,涉及强关联系统中的拓扑序、多体系...

2019-09-06 12:32:13
2020年科学突破系列奖项揭晓,三位华人科学家获奖

2020年科学突破系列奖项揭晓,三位华人科学家获奖

北京时间2019年9月5日晚上,2020年科学突破奖(Breakthrough Prize)宣布授予以下科学突破:拍摄第一张黑洞照片,确定肥胖的生物学基础,在痛觉感知的生物化学方面的发现,以及其他重大成就。编译 | 拾贝壳的孩子今年的获奖者因为一些重大而引人注目的科学发现而获奖,比如黑洞是什么样子的?为什么辣椒吃起来那么辣?神经退行性疾病的原因是什么?其中基础物理学突破奖授予事件视界望远镜(EHT)合作项目的347名成员,他们探测遥远的星系,并捕捉到了黑洞的第一张图像。生命科学突破奖的获奖者们为非阿片类镇痛药物消除慢性疼痛奠定了基础,为食物摄入和体重的关系建立了生物学基础,并发现了神经退行性疾病的共同机制,包括早发性痴呆。此外,6项新视野奖颁发给12位科学家,以表彰他们在物理学和数学方面的早期职业成就。以下是完整的获奖理由。基础物理学突破奖事件视界望远镜(EHT)合作项目来自哈佛-史密森天...

2019-09-06 12:27:56
为啥著名美籍华裔科学家多是中国移民,而非美国土长?

为啥著名美籍华裔科学家多是中国移民,而非美国土长?

说到当代最具创造性的华人科学家,人们常常会想到那些著名的美籍华裔科学家,如杨振宁、李政道、陈省身、丘成桐等,并将他们能取得如此成就归结为美国浓厚的经济、发达的教育和良好的学术氛围。但本文却用统计数据揭示了一个出乎意料的结果:著名的美籍华裔科学家几乎全部出自从中国去的知识移民及其后裔!那么,是什么原因导致了这样一种现象,又是哪些因素促成了人才史上这样一座高峰的形成?美国华裔人才史折射了撰文 | 沈登苗现当代最具创造性的华人科学家应是美籍华裔科学家。这当然是作为世界科学中心的美国,其浓厚的经济、发达的教育和良好的学术氛围所致。但是,如果我们仅把目光停留在美国而忽视了华人自身的因素,甚或根据一般的成材规律,人们就自然会产生这样的联想:既然华裔科学工作者能在美国如鱼得水,那么,土生土长的美籍华裔比外来华人移民不是更能成为著名的科学家吗?可统计的结果却却相反——六十三位著名的美籍华裔科学家,既不是以...

2019-09-01 09:51:19
返朴
返朴

最新文章

推荐作者

换一批