随机性理论能成为网络安全的关键吗？

几千年来，这个问题一直是密码学的核心，也是保护互联网上私人信息的努力的核心。在一篇新的论文中，康奈尔理工大学的研究人员发现了一个问题，这个问题掌握着是否所有加密都可以被破解的关键-以及与一个旨在定义和测量随机性的数学概念之间令人惊讶的联系。

康奈尔理工大学计算机科学教授拉斐尔·帕斯说：“我们的研究结果不仅表明密码学存在天然的‘母亲’问题，还表明数学和计算机科学的两个截然不同的领域--密码学和算法信息论之间存在着深刻的联系。”

Pass是“On-Way Functions and Kolmogorov Complex”一书的合著者之一，该书将于11月16日至19日在北卡罗来纳州达勒姆举行的IEEE计算机科学基础研讨会上发表。

“其结果是，”他说，“20世纪60年代在苏联引入的一个自然计算问题表征了基本密码学的可行性-例如私钥加密、数字签名和身份验证。”

几千年来，密码学被认为是一个循环：有人发明了一种密码，密码有效，直到有人最终破解了它，然后密码变得无效。在20世纪70年代，寻求更好的密码学理论的研究人员引入了单向函数的概念-一个方向上的简单任务或问题，在另一个方向上是不可能的。

例如，点燃一根火柴很容易，但不重新排列原子就不可能将燃烧的火柴恢复到未点燃的状态-这是一项极其困难的任务。

“我们的想法是，如果我们有这样一个单向函数，也许这是理解密码学的一个很好的起点，”帕斯说。“加密信息非常容易。如果你有密钥，你也可以解密它。但是不知道钥匙的人应该做和恢复点燃的火柴一样的事情。“。

但是研究人员还不能证明单向函数的存在。最广为人知的候选方案-也是互联网上最常用的加密方案的基础-依赖于整数因式分解。将两个随机素数相乘很容易，例如23和47，但如果只给出它们的乘积1,081，就很难找到这两个因子。

帕斯说，尽管研究人员可能还没有找到正确的算法，但人们认为对于大数来说，还没有有效的因式分解算法。

“我们要解决的核心问题是：它是否存在？单向函数的存在有没有什么自然的问题？“。他说。“如果是这样，那就是所有问题之母，如果你有办法解决这个问题，你就可以打破所有所谓的单向函数。如果你不知道如何解决这个问题，你实际上可以得到安全的密码术。“。

与此同时，20世纪60年代的数学家们发现了所谓的柯尔莫戈罗夫复杂性，它指的是量化一串数字的随机性或模式。一串数字的Kolmogorov复杂度被定义为可以生成该字符串的最短计算机程序的长度；对于某些字符串，例如1212121212121212121212121212121212121212121212121212121212121212121212，有一个生成它的短程序-交替的1和2。但对于更复杂且明显随机的数字字符串，例如37539017332840393452954329，可能不存在比字符串本身的长度短的程序。

这个问题长期以来一直引起数学家和计算机科学家的兴趣，其中包括沃尔特·R·里德(Walter R.Reed)计算机科学与工程荣誉退休教授尤里斯·哈特马尼斯(Juris Hartmanis)。由于试图生成数字的计算机程序可能需要数百万年甚至数十亿年的时间，20世纪60年代的苏联研究人员，以及80年代的哈特马尼斯和其他研究人员，开发出了限时科尔莫戈罗夫复杂性--可以在一定时间内输出一串数字的最短程序的长度。

在这篇论文中，PASS和博士生刘彦一证明，如果计算有时间限制的Kolmogorov复杂度是困难的，那么单向函数是存在的。

帕斯说：“如果你能想出一个有效的算法来解决很大一部分事情的限时Kolmogorov复杂性问题，那么你就可以破解所有的密码、所有的加密方案、所有的数字签名。”但是，如果不存在解决此问题的有效算法，则可以获得单向函数，因此可以获得安全的加密和数字签名等。

这项研究部分由国家科学基金会和空军科学研究办公室资助，并基于国家情报总监办公室情报高级研究项目活动资助的研究。