真随机数很难生成。原因很简单:如果能够被生成一次,就也能够被重新生成;如果能够重新生成一个随机数,它就算不上随机的。
随机数是信息安全的核心要素,它是信息安全最强力的武器——加密的关键,算法使用随机数生成密钥。有一个困扰人们很久的问题:如果攻击者能够重现数字生成的随机算法,他就能重新生成密钥,更方便地破解加密。因此,人们在过去许多年中花费巨额资金,开发“真随机”技术。
位于奥斯汀的德克萨斯州立大学宣称有了突破。计算机科学教授大卫·查克曼 (David Zuckerman) 和研究生Eshan Chattopadhyay将出席六月召开的STOC大会 (Symposium on Theory of Computing) 。这篇论文是已被评为“最佳论文”的三篇系列论文之一,而且,在经过在2015年8月的Electronic Colloquium on Computational Complexity大会上的同业审议之后,该论文已经给外界留下了不少惊喜。
论文名称是《Explicit Two-Source Extractors and Resilient Functions》,文中介绍了一种将两种“弱随机”序列结合在一起,生成一个真随机数的方法。气温和股价等数值均属于弱随机数,经过一定的时间,它们就会显示出可预测的模式。与此相反,真随机数则是完全无法预测的随机数。
20年以来,查克曼一直在他引领的这一领域中工作:从弱随机序列中提取真随机。在该论文出现之前,该过程仍需要一个真随机数,或者两个数字均接近真随机才能成功。
情况已经改变。查克曼说:“这个问题在过去的20年中反复困扰着我。我对解决了它感到非常兴奋。”如今发表的新论文描述了一种通过两个弱随机序列提取一个真随机数的方法。
生成高质量随机数的方法一直存在,但非常消耗计算资源。这种新方法可以用更少的成本,获得更好的质量。“加密中经常出现的问题就是不使用高质量的随机数。因此,通过让高质量随机数更加易得,我们的方法可以提升安全性。”外界普遍认为,该方法将提升所有需要高质量加密领域的安全性,比如信用卡转账、军事通讯等。
外界欢呼,称该研究是信息安全的一大进展。新英格兰微软研究中心的密码学高级研究人员耶尔·卡莱 (Yael Kalai) 说:“我听到这个消息之后,睡不着觉。”他也曾经研究过随机性提取技术。“我太兴奋了。简直无法相信。我上互联网找了这篇论文。它真是一篇杰作。”
文森特·雷曼 (Vincent Rijmen) 是AES加密算法两位开发者之一,他指出查克曼的论文更偏向理论,而不是实际。他对媒体表示:论文“在它自己描述的那个情景下来看可能很重要。它是对随机性和密码学的一个非常理论化的描绘。”来自剑桥大学计算机实验室的教授罗斯·安德森 (Ross Anderson) 也证实了这种关于论文至少目前来看没有太多使用价值的观点:“这是篇理论性的文章。就我来看,没有太多的工程学价值。”
本文转自d1net(转载)