详细内容或原文请订阅后点击阅览
破纪录的 RSA-260 破解背后的技术是什么？
一位研究人员在社交媒体上发布的帖子揭露了如何破解部分流行加密协议，该帖子已在社交媒体上疯传。但他真的只是用“好的旧纸和铅笔”做到了这一点吗？
来源:科学美国人周四一早，技术研究员 Eric Lu 在 X（以前称为 Twitter）上发布了 130 个数字的序列，引发了全世界的兴奋和困惑。一些看似无害的数字引起轩然大波的原因在于它们后面的两个词：“除以RSA-260”。
Lu 是人工智能初创公司 Cognition 的一名工程师，他成功地分解了一个所谓的 RSA 数字——通过两个巨大的秘密素数相乘而创建的笨重的数字字符串。传统思维认为，这两个素数越大，它们的乘法就越难被撤销——这种观点使得 RSA 自近半个世纪前首次亮相以来，成为世界上最受欢迎的加密方案之一。
要使用 RSA 加密消息，只需知道这些数字之一，该数字与 RSA-260 一样只有两个质因数；解密需要知道两个特定的素数。因此，对 RSA 数字进行因式分解就相当于解密，而能够从该数字中找到素数的人也可以破解加密方案。由于这些加密方案构成了我们保护财务、消息和其他形式在线通信安全的基石，因此人们对任何类似于对他们构成威胁的事物都感到非常不安。
关于支持科学新闻
如果您喜欢这篇文章，请考虑通过订阅来支持我们屡获殊荣的新闻事业。通过购买订阅，您将有助于确保有关塑造当今世界的发现和想法的影响力故事的未来。
虽然 Lu 分解的 RSA 数与现代密码学中使用的数字相比很小，但它仍然是迄今为止破解的最大数字。与最近人工智能驱动的数学结果的趋势相反，卢的壮举似乎没有利用任何人工智能（尽管 Cognition 正在开发的人工智能 Devin 提出了一些相互矛盾的报告）。
确认 Lu 的成就非常简单，只需在计算器中输入已知的 RSA-260 数字，然后除以他提供的 130 位数字字符串即可。这就是分解 RSA 数字并解决支撑密码学的其他难题的技巧：破解它们往往在计算上很困难，但检查解决方案是否正确却很容易。
目前，Lu 几乎没有提供有关他如何发现特殊素数的细节，只是提出了一个可疑的说法（也许是开玩笑），即只涉及“好的旧纸和铅笔”。据推测，他不清楚的方法归结为随机采样素数并将每个素数从 RSA-260 中划分出来，直到其中一个素数均匀分布。 （Lu 和 Cognitive 均未回应《科学美国人》的置评请求。）
RSA 密码系统的概念以其创始人计算机科学家 Ron R ivest、Adi S hamir 和 Leonard A delman 的名字命名，于 1977 年出现。三人共同创立了一家名为 RSA Security 的公司，并于 1991 年发布了一份“RSA 数字”列表，每个数字都是通过越来越大的秘密素数相乘而形成的。该清单被视为一项挑战：如果您考虑其中一个数字，您将赢得现金奖励。尽管这场竞赛早在十多年前就结束了，但这并没有阻止 Lu 和其他加密货币爱好者尝试计算剩余的未破解数字，包括 RSA-260。
上次对 RSA 号码进行分解是在 2020 年。那一年，一个团队成功对 RSA-250 进行了分解，它采用与其他 RSA 号码类似的命名约定，具有 250 个基数 10 的数字。在这种情况下，研究人员使用了一种称为筛选的技术，该技术本质上是筛选出非素数，只留下素数进行测试。
据报道，这一早期成果需要几个月的工作，并利用了数万台计算机的力量。根据 Cognition 的另一位工程师的说法，破解 RSA-260 可能需要至少七个月的时间，其中卢“手工”采样和测试素数（即在计算机的帮助下，而不是人工智能的自动认知）。
在没有计算机帮助的情况下实际破解 RSA-260 大小的数字的想法是不可想象的；法国国家数字科学技术研究所 (INRIA) 的研究员 Emmanuele Thomé 是 RSA-250 分解小组的成员，他表示“分解 RSA-260 的[计算]成本预计大约是 RSA-250 的三倍。”托梅说，卢的壮举“当然是可行的”，尽管“并不完全是唾手可得的成果”。
不过，Lu 对于使用计算机进行一些长除法并不陌生。 2019 年，他发现了梅森数的一个因数，证明它不是素数。几个世纪以来，数学家们一直对梅森数是素数还是非素数很感兴趣，陆在这一领域的成就甚至保存在在线排行榜上。在这种情况下，这个数字的长度超过 2500 万位，尽管他发现的因子要小得多。
无论 Lu 这次是否使用了筛选、人工智能或其他东西，RSA-260 的成功分解并不意味着当前基于 RSA 的加密方案的末日，因为使用的素数要大得多。实际上，RSA 至少使用约 2,000 个二进制位，是 RSA-260 长度的两倍多。随着数字的增长，难度呈指数级增长，普通计算机不可能很快破解 RSA 加密。
相反，量子计算的进步比花费数月的计算来测试每个素数更有可能带来问题。虽然当前的量子计算机还不够大，无法处理加密，但研究人员已经知道，量子计算可以让我们实现比没有量子计算快得多的分解速度。目前，任何拥有加密保护秘密的人都可以松口气了；除非在非量子方法上取得一些突破来分解 RSA 数字，像 Lu 这样的项目仍然只是一种好奇，而不是现实的威胁。