世界上真有不可破解的密码？要看能否找到解开单向函数的算法

在互联网时代，密码是保护个人隐私的关键工具之一。

世间有不可破解的密码吗？这一直是密码学的核心问题，也是互联网时代个人隐私保护的关键。

优睿科新闻网站7月28日刊文称，在一篇论文中，美国康奈尔大学理工学院的研究人员发现了对加密技术是否都能被破解来说至关重要的一个问题，并且找到了与旨在界定和测量随机性的数学概念令人惊讶的相关性。

今年11月16-19日，IEEE计算机科学基础研讨会将在北卡罗林的达勒姆举行。作为合著者，康大计算机科学教授Rafael Pass将在会上发表关于该研究的论文《单向函数和柯氏复杂性》。“我们的发现，不仅揭示了密码学的根本问题，还发现了数学与计算机这两个独立领域之间的密切联系——密码学与算法信息论。上世纪60年代，苏联提出的一个自然计算问题证明了像私钥加密、数字签证和认证这样的基本密码学的可行性。”Pass说。

几千年来，密码学一直不断循环：发明一种密码-密码有效-被人破解-密码无效。20世纪70年代，为了寻找更好的加密理论，研究人员引入了单向函数概念。例如，点燃一根火柴很容易，想要恢复如初却很困难——如果不在原子水平将化学物质复原，就不可能把已经烧着的火柴恢复到点着之前的状态。

Pass说：“从单向概念出发，能很好理解密码学。给消息加密很容易，如果你有密钥，你可以解密它。那些没有密钥的人想要解密，就要‘将点燃的火柴恢复如初’。”

然而，研究人员还没能证明单向函数的存在。最著名的备选方案依赖于整数因数分解。举个例子：两个随机质数相乘如23*47很容易得到1081，但如果只给出乘积1081就很难找到这两个因数。这种方式也是互联网上最常用的加密方案的基础。

Pass说：“也许是研究人员还没找到，目前对公认的大数而言，不存在有效的分解算法。有个核心问题，是否真有一些自然问题可以用来描述单向函数的存在。如果有，那就是问题的根源，如果你有解决这个问题的方法，便可以解开所有的单向函数。倘若不知道如何解决，实际上就可以获得一个无法破解的密码。”

数学家在20世纪60年代发现了柯氏复杂性，它可以对一串数字的随机数量或模式进行量化。一串数字的柯氏复杂性被定义为能够生成这串数字的最短长度的计算机程序。长久以来，这个问题一直吸引着数学家和计算机科学家的关注。

Pass和博士研究生Yanyi Liu证明，如果计算的时间有限，且柯氏复杂性很高，那么单向函数便存在。尽管这只是理论发现，但它对包括互联网安全在内的密码学有着潜在的影响。

Pass说：“如果你能提出一种解决有限时间内柯氏复杂性问题的算法，那么你就能破解所有加密方案、所有数字签名和所有密码。但如果不存在这种算法，就能借助单向函数获得安全的加密方案和数字签名。”

原创编译：攀汗 审稿：西莫 责编：雷鑫宇

原文链接：https://www.eurekalert.org/pub_releases/2020-07/cu-rtc072720.php

版权声明：本文为原创编译，中文内容仅供参考，一切内容以英文原版为准。转载请注明来源。