分解 RSA 260

在过去的几周里，我和认知研究团队一直在优化我们的作业调度程序，以更好地使用分类计算。作为概念证明，并且因为在过去十年左右的时间里我一直将数字因式分解作为一种爱好，所以我驱使一群 Devins 获得了 RSA-260 的因式分解。为了做到这一点，我的 Devins 构建了世界上性能最高的 GPU 晶格筛，它能够以比之前公开的最先进技术低 10 倍的成本进行数字分解。这是因式分解： 22112825529529666435281085255026230927612089502470015394413748319 12882294140200198651272972656974659908590033003140005117074220456 08592763579537571859542988389587092292384910067030341246205457845 66413664540684214361293017694020846391065875914794251435144458199 = 43973286548448269237950681025058725717218835265533496595612569245 05973939597593482272505698004801207988043088656411102133523080581 × 50286952068425698646861416182530834166100810900753666747767757065 38324961364412200138116378509733307971876652984898985905923678379 RSA-260（260 位数字）创下了最大的公开解决的 RSA 分解挑战问题的新记录，该问题衡量了破解 RSA 密码系统的可行性。之前的记录 RSA-250 是在 2020 年 2 月创下的。作为参考，最先进的 RSA 公钥包含 2048 位（约 617 位数字）分解问题，而 1024 位（约 309 位数字）RSA 已于 2013 年被弃用。下面我将给出有关如何实现这一目标的一些详细信息，但这里有两个重要的要点：超大规模企业或前沿人工智能实验室可能会分解问题RSA-1024 号码的成本约为每个号码 3000 万美元，而且，如果进行更多优化，可能会大大减少。另一方面，RSA-2048 仍然比 RSA-1024 难大约十亿倍，并且似乎没有受到这项工作的显着影响。 Devin 是一位足够强大的软件工程师，能够解决计算数论和 GPU 性能工程交叉领域的挑战性问题。我的职责主要是确定优先事项、建立基准并识别工作何时偏离轨道。除此之外，Devin 还可以自主处理端到端的测量、集群操作和优化。这取代了高度专业化的领域专家团队可能需要花费数月时间的工作。总之，密码分析工作、更广泛的其他计算数学以及可能最大规模的科学计算研究的进入门槛比以前低得多。任何可以使用编程来解决研究问题的地方都会有令人兴奋的工作。我鼓励所有人雄心勃勃，探索自主软件工程代理应用于这些领域时可以做什么！这是怎么发生的？ # 与一些流传的说法相反，我并没有通过手动猜测和检查 130 位素数来分解 RSA-260。认知公司还没有建造出数千量子比特的量子计算机。 RSA-260 是由 GPU 通用数域筛选 (GNFS) 的新实现分解的，使用 Devin 准备和运行。 GNFS 是已知的最有效的算法，适用于大小大约 100 位以上的（大多数）数字，并且曾用于之前破纪录的 RSA 数字分解。该实现是经过重大修改的 CADO-NFS 。我报告说基本上没有算法上的进步——在 GPU 上实现晶格筛选和稀疏线性系统求解只需要“良好的旧性能工程”来利用 GPU 荒谬的内存系统。成本估算 # 总的来说，我估计这种分解成本约为 4,900 个 GPU 天，或 13.5 个 GPU 年，按当前市场价格计算约为 40 万美元。更详细地说，现代 GNFS 实现由几个顺序运行的阶段组成：多项式选择、晶格筛选和线性系统求解。时间细分为： 643 个 GPU 天进行多项式选择（这基本上是由于操作员无能） 3,813 个 GPU 天筛选 467 个 GPU 天线性系统求解（其中大约 7% 由于崩溃或被更重要的工作抢占而未能取得进展） 我使用集群的个位数百分比将其作为一个副项目，在优化我们的作业调度程序以改善分配时使用分解计算。这对于较大的 RSA 实例意味着什么？ RSA-1024相当于309位数字；根据标准 GNFS 缩放，这仅比 RSA-260 多计算 78 倍。我估计以市场 GPU 价格分解 RSA-1024 的成本约为 3000 万美元，这可以与挂钟时间进行权衡。我知道当前的实施仍然远未达到最佳状态；如果适度的进一步工作可以将 RSA-1024 的因式分解成本降低 2 的倍数，我不会感到惊讶。当然，RSA-1024 不安全的事实并不是新闻。有人猜测，NSA 早在 2000 年代中期就有能力经济地实施 RSA-1024（s