头条新闻

RSA-576 已分解

作者：Eric W. Weisstein

2003 年 12 月 5 日——12 月 3 日，在大互联网梅森素数搜索于 12 月 2 日宣布发现已知最大素数（ 头条新闻，2003 年 12 月 2 日）后的第二天，德国联邦信息技术安全局 (BSI) 的一个团队宣布分解了 174 位数字

1881 9881292060 7963838697 2394616504 3980716356 3379417382 7007633564 2298885971 5234665485 3190606065 0474304531 7388011303 3967161996 9232120573 4031879550 6569962213 0516875930 7650257059

称为 RSA-576。

RSA 数字是具有正好两个 素因子（即所谓的 半素数）的 合数，这些数字已在 RSA Security^® 的因数分解挑战赛中列出。

虽然合数被定义为可以写成较小数字（称为 因子）乘积的数字（例如，6 = 2 x 3 是合数，因子为 2 和 3），但 素数 没有这种分解（例如，7 除了 1 和自身之外没有任何因子）。因此，素因子代表给定正整数的基本（且唯一的）分解。RSA 数字是特殊类型的合数，特意选择难以分解，并且通过它们包含的位数来识别。

虽然 RSA-576 比本周早些时候宣布的 6,320,430 位怪兽 梅森素数 小得多，但它的分解意义重大，因为数字具有一个奇特的属性，即证明或反驳一个数字是素数（“素性测试”）似乎比实际识别一个数字的因子（“素因数分解”）容易得多。因此，虽然将两个大数 p 和 q 相乘在一起是微不足道的，但如果仅给出它们的乘积 pq，则确定因子可能极其困难。通过一些巧妙的方法，此属性可用于创建实用且高效的电子数据加密系统。

RSA 实验室赞助 RSA 因数分解挑战赛，以鼓励对计算数论和分解大整数的实际难度进行研究，并且因为它有助于 RSA 加密 公钥密码算法的用户选择适合的安全级别的密钥长度。现金奖励将颁发给第一个分解每个挑战数字的人。

RSA 数字最初以 10 个 十进制 数字的间隔分布在一到五百位数字之间，奖金根据复杂的公式颁发。这些原始数字根据十进制数字的数量命名，因此 RSA-100 是一个百位数字。随着计算机和算法变得更快，未分解的挑战数字从奖金列表中删除，并替换为一组具有固定现金奖励的数字。此时，命名约定也发生了变化，因此尾随数字表示数字的 二进制 表示中的位数。因此，RSA-576 有 576 个二进制数字，转换为十进制为 174 位数字。

当 R. Rivest、A. Shamir 和 L. Adleman 使用 129 位数字（称为 RSA-129）发布最早的公钥消息之一，并为该消息的解密提供了 100 美元的奖励时，RSA 数字受到了广泛关注 (Gardner 1977)。尽管当时普遍认为破解 RSA-129 编码的消息需要数百万年，但它在 1994 年被分解，使用分布式计算，利用遍布全球的网络计算机执行多项式 二次筛法 (Leutwyler 1994)。所有集中式数字运算的结果是对编码消息的解密，产生了深刻的明文消息“The magic words are squeamish ossifrage.”（ossifrage 是一种罕见的食腐猛禽，在欧洲的山区发现。）

在 RSA-129 分解之后，又分解了 RSA-100、RSA-110 和 RSA-120。挑战数字 RSA-130、RSA-140、RSA-155 和 RSA-160 也在 1996 年至今年 4 月之间相继分解。（有趣的是，RSA-150 在从 RSA 挑战列表撤回后显然仍然未分解。[但是，请参阅附言。]）

12 月 2 日，Jens Franke 发布了一封电子邮件，宣布分解了最小的奖金数字 RSA-576。该分解是使用一种称为通用数域筛法的 素因数分解算法 完成的。使用此筛法找到的两个 87 位因子是

3980750 8642406493 7397125500 5503864911 9906436234 2526708406 3851895759 4638895726 1768583317 x 4727721 4610743530 2536223071 9730482246 3291469530 2097116459 8521711305 2071125636 3590397527

并且可以轻松地将它们相乘来验证它们是否确实给出了原始数字。

Franke 的注释详细介绍了分解过程，其中“格子”筛选由 J. Franke 和 T. Kleinjung 在波恩大学科学计算研究所和纯数学研究所、波恩马克斯·普朗克数学研究所和埃森实验数学研究所使用硬件完成；“线”筛选由 CWI 的 P. Montgomery 和 H. te Riele、F. Bahr 及其家人以及 NFSNET（当时由 D. Leclair、P. Leyland 和 R. Wackerbarth 组成）完成。然后，在 BSI 的支持下完成了此数据的后处理，以构建实际因子。

由于他们的努力，该团队将获得 RSA Security 提供的 10,000 美元现金奖励。但是，寻求奖励的人不必气馁。如下表所示，RSA-640 至 RSA-2048 仍然开放，为那些足够聪明和坚持不懈地追踪它们的人提供 20,000 美元至 200,000 美元的奖励。开放挑战数字的列表可以从 RSA 下载，也可以从 包存档中以 Mathematica 包的形式下载。

附言 2004 年 8 月 24 日添加：RSA-150 已被 Aoki 等人分解为两个 75 位素数，见日期为 2004 年 4 月 16 日的 预印本。