破解加密密钥的新记录

文章内容

一个由计算机科学家组成的国际团队在两个最重要的计算问题上创造了新的记录，这两个问题是目前在现实世界中使用的几乎所有公钥密码学的基础。

公开密钥密码学用于许多应用程序，包括加密敏感和机密数据以及数字签名。在公钥密码学中，密钥是成对出现的，一个是公钥，一个是私钥，加密或数字签名方案的安全性依赖于这样一个事实，即从公钥计算私钥被认为是难以处理的。因式分解和离散对数是其中两个被认为很难解决的基本问题。

该团队分解了迄今为止最大的一个795位整数，并计算了一个795位整数的离散对数。总的来说，这花费了他们大约3500万小时的计算时间。

这个记录计算所破坏的密钥大小在现代加密应用程序中通常不被使用。但是，为了更新密码安全参数和密钥大小建议，必须实现常规的计算记录。

由于算法的进步，实现这些计算的计算能力比根据以前的记录或摩尔定律估计的要少得多。

在这两种情况下，之前的记录都是768位。之前的分解记录始于2010年，之前的离散对数记录始于2016年。

由于因式分解和离散日志的计算记录是在相同大小的整数和相同的计算硬件上同时实现的，因此这项工作影响了科学界对这两个问题的相对难度的理解。人们普遍认为离散对数问题至少比因式分解难10倍。这项工作表明，这种差异要小得多，大约是三倍的数量级。

该小组由法国Inria Nancy的Aurore Guillevic, Paul Zimmermann和Emmanuel Thome，法国CNRS Nancy的Pierrick Gaudry，加利福尼亚大学圣地亚哥分校的Nadia Heninger和法国利摩日大学的Fabrice Boudot组成。

研究人员使用CADO-NFS进行了计算，CADO-NFS是INRIA Nancy团队开发的免费软件。他们使用了许多计算机集群，包括法国和德国的大学和国家研究集群，以及现在位于加州大学圣地亚哥分校的海宁格管理的计算设备。