[山东科技人物] 王小云：搬倒两座“密码大厦”(图)

实习生 张琪 本报记者 孙明河 魏东

    2004年8月，国际密码大会上，她向世人公布了MD5等四个著名密码算法的破译结果，在公布到第三个成果的时候，会场上已经是掌声四起，报告不得不一度中断。报告结束后，所有与会专家对她的突出工作报以长时间的掌声。

　　2005年2月15日，国际信息安全RSA研讨会上，国际著名密码学专家AdiShamir当场宣读了她的论文，如何使得两个不同的文件产生相同的SHA-1散列值，再次震惊了国际密码学领域。

　　短短半年的时间，数字签名加密算法的两座大厦先后倒塌———MD5和SHA-1这两种应用最为广泛的数字签名加密算法都被山东大学的王小云教授破解，世人又再次将目光投向了中国。

　　三个月破译SHA-1

王小云教授

　　“在MD5破译之后，有位美国律师协会顾问说：‘中国的这几位研究人员太疯狂了。’我不喜欢轻而易举就可以完成的工作，挑战性比较强的才对我的胃口。”

　　“早在1989年，我就开始了密码算法的研究工作，在确定MD5作为自己的研究方向时，也考虑到了它的安全性很高的问题。但是自己又一定的数学功底，而且自己也喜欢接受挑战。”

　　就在MD5被王小云踩在脚下之后，世界密码学界仍然认为SHA-1是安全的算法。勇于面对挑战的她，又再次将目标锁定了SHA-1。

　　“国际密码学家认为破解55步左右的简化SHA-1是2005年的一个挑战，而包含80步的整个SHA-1算法的破解被认为是不可能的，我本人当时也是认为全算法的破解是几乎不太可能的，但还是特别想去尝试一下。”

　　2005年2月7日，美国国家标准技术研究院(NIST)对外宣称，SHA-1还没有被攻破，并且也没有足够的理由怀疑它会很快被攻破。仅在一周之后，王小云教授再度令世界密码学界大跌眼镜———SHA-1也被她“碰撞”了。而更让大家跌破眼镜的是，整个破译过程仅仅用了两三个月而已。

　　选择做“无用功”课题

　　“我认为课题最好是有意义的，不仅要有理论价值，还要有应用价值，要具有实用性。而不是仅仅为了研究而研究，最后研究出来一大堆没用的东西放在那，那纯属浪费。”

　　当初选取MD5和SHA-1作为课题，仅仅有勇气还是不够的，还是王小云坚持原则的结果。

　　“当时选取这两种在别人看来是在做无用功的课题来研究，就是因为这两种密码算法都是现在最常用的密码算法。现在电子商务、电子政务的迅速发展，迫切需要有效的信息安全技术保证计算机网络安全，而密码技术是保证信息安全的最重要的核心技术之一。其中HASH函数是保证完整性、合法性、认可性的关键技术，所以研究出来也就能够满足大家的需要，而不是当作理论仅仅是看看就扔那么简单。”

　　“现在从事研究工作都有硬性指标，选取难的课题就很难出成绩。虽然自己也可以‘随大流’，选择容易的课题，出更多的成绩，但是自己心理上无法接受。就像设计服装一样，总是希望自己设计的衣服能够得到大家的喜爱和认同。自己在这一方面确实是个原则性很强的人，很坚持原则，不想因为一时的成绩超越了自己的底线。”

　　将不可能变为可能

　　“自己先从SHA-0开始进行研究，将不可能差分转化成可能差分，再进行进一步的研究。就像原本有条大河将两岸的居民分离，很难取得联系，那么我们架座桥，就可以让他们的联系变成可能。”

　　在条件不满足的情况下，创造条件，而不是固步自封。王小云凭着这样的信念，将一系列的不可能转化为可能。就像SHA-0的差分是不可能出现的，很难用有效的分析方法进行分析，这就使得刚刚开始的工作一下子陷入了僵局。在这种情况下，一种从未有人想到过的想法冲击了王小云的大脑———将不可能差分转化为可能差分！

　　当她把这个思想告诉其他人的时候，她的学生都认为是天方夜谭。但是，这种思想在王小云看来，是完全行得通的，所以自己就一直坚持下来。研究就是这样环环相扣，每个突破点都是转折点，就这样循序渐进，一步步地走到了最后。

　　“现在才觉得跟着王老师真的是跟对了，她的想法确实很有前瞻性，很多我们看来不可能的事情，她都能想到，最后也都能做到。”她一位学生这样说。

　　找到“比特追踪法”

　　HASH函数被认为是近15年来密码学研究中最不活跃的领域。然而，王小云却坚定地选择了它，并以独特的方式打破了这种沉闷的局面。

　　雪崩性是衡量HASH函数安全的一个基本标准，如果HASH函数安全的话，雪崩性是非常强的，找不到任何规律。这就像雪顶上有一个东西，突然雪崩了，你根本找不到它。经过不断的分析研究，王小云发现HASH函数没有很强的雪崩性，这说明能够找出一些规律。于是，王小云开始找规律，试图找到一些有效的攻击方法。在不断的摸索和反复的验证中，最后她幸运地找到了“比特追踪法”，也就是目前大家公认的模差分方法，并结合一些其他的新技术，最终使攻击方法变得非常有效。

　　很多人觉得密码学是很玄妙的学问，认为王小云的研究自然也是十分枯燥的。但她并不这么看。

　　“密码学上有些思想是别的学科没有的，比如说可证明安全性的一些思想，利用零知识、知识证明等思想证明某些算法为什么是安全的，是密码学独特的理论体系。刚开始，感觉学习密码算法很简单，后来随着理论越来越深，感觉还是挺难的。但我从未感觉这项工作枯燥，因为密码有实际用途，用它可以解决实际问题。我的研究就像去要攻克一个目标一样，它反而会使你去追求破解它的欲望更强一些，这也是乐趣所在。再者，我们已习惯于用数学方式思维，而一旦养成了这种思维方式，数字在我们眼中就变成了美妙的音符，我们的研究就像音乐创作一样有趣。”王小云说。

　　独创多种分析技术

　　“传统的计算方法有一定的局限性，所以我们在研究过程中不断地摸索，形成了一系列自己的方法，有些想法现在我自己看来都还觉得很神奇，有些不可思议。”

　　王小云在研究过程中，集中精力采用循序渐进的方式进行研究，先从最简单的MD4算法开始。“因为现在世界上通用的密码算法基本上都基于MD4，虽然说各自都有自己的特点，但是基本的架构都是相同的。”

　　但是，随着研究的深入，王小云逐渐地发现，传统的差分方法有一定的局限性，这样走下去根本不可能将密码算法破译出来。因为每个算法都有自己的特点，并不是完全模仿MD4，而这些创新点也就是破译的难点。在认识到了这个问题之后，王小云开始跳出原有的框框，另辟蹊径。

　　“模差分”的应用，在王小云现在看来，都还觉得有些不可思议。国际著名密码学家Eli-Biham认为：“这种独特的模差分的方式是由两种差分来定义的，直接强迫很多数据位被固定，这种限定不仅增加了成功找出碰撞的几率，它还提供了额外的信息。模差分的技术是一个有效并且非常重要的贡献，我预计在不久的将来这种方式将会被广泛运用在许多其他的密码分析学研究上。”

　　破译两种世界上公认安全的密码算法，靠的并不仅仅是“模差分”的作用，王小云还创造了一种十分有效的寻找碰撞路线的方法。在找到HASH函数的碰撞路线的前提下，又独创了提高碰撞概率的明文修改技术等多种分析技术。正是多种独创的分析技术综合形成的系统分析方法才最终实现了自己的目标。

　　■人物档案

　　王小云，女，汉族，一九六六年八月出生，现任山东大学信息安全研究所所长、博士生导师。

　　一九九○年，王小云在山东大学师从著名数学家潘承洞教授攻读数学理论与密码学专业博士。

　　上世纪九十年代末开始进行HASH函数的研究，她带领的于红波、王美琴、孙秋梅、冯骐等组成的密码研究小组，同中科院冯登国教授，上海交大来学嘉等知名学者密切协作，经过长期坚持不懈的努力，找到了破解HASH函数的关键技术，成功的破解了MD5和其它几个HASH函数。王小云分别于一九九○年、一九九三年获得理学硕士、博士学位。先后获得八六三项目资助和国家自然科学基金项目资助，并获得部级科技进步奖一项，撰写论文二十多篇。

　　■链接

　　MD5、SHA-1MD5、SHA-1是当前国际通行的两大密码标准。据了解，MD5由国际著名密码学家、图灵奖获得者兼公钥加密算法RSA的创始人Rivest设计，SHA-1是由美国专门制定密码算法的标准机构———美国国家标准技术研究院(NIST)与美国国家安全局(NSA)设计。这两大算法是目前国际电子签名及许多其它密码应用领域的关键技术，广泛应用于金融、证券等电子商务领域。其中，SHA-1早在1994年便为美国政府采纳，目前是美国政府广泛应用的计算机密码系统。HASH函数与数字签名（数字手印）

　　HASH函数，又称杂凑函数，是在信息安全领域有广泛和重要应用的密码算法，它有一种类似于指纹的应用。

　　在网络安全协议中，杂凑函数用来处理电子签名，将冗长的签名文件压缩为一段独特的数字信息，像指纹鉴别身份一样保证原来数字签名文件的合法性和安全性。在前面提到的SHA-1和MD5都是目前最常用的杂凑函数。

责任编辑:刘家昌