头条新闻

RSA-640 已分解

作者：Eric W. Weisstein

2005 年 11 月 8 日——德国联邦信息技术安全局 (BSI) 的一个团队最近宣布分解了 193 位数字

310 7418240490 0437213507 5003588856 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609

称为 RSA-640（Franke 2005）。负责这次分解的团队与之前分解了 174 位数字 RSA-576（ 头条新闻，2003 年 12 月 5 日）和 200 位数字 RSA-200（ 头条新闻，2005 年 5 月 10 日）的团队是同一个团队。

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

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

虽然 RSA-640 比 7,816,230 位的巨型梅森素数 M₄₂（这是已知的最大素数）小得多，但它的分解意义重大，因为证明或证伪一个数字是素数（“素性测试”）似乎比实际识别一个数字的因子（“素因数分解”）容易得多。因此，虽然将两个大数 p 和 q 相乘很简单，但如果只给出它们的乘积 pq，则确定因子可能极其困难。通过一些巧妙的方法，这种特性可以用于创建实用且高效的电子数据加密系统。

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

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

虽然 RSA-640 的位数略少于之前分解的 RSA-200，但其分解还带来了 RSA 实验室向负责此壮举的团队提供的 20,000 美元现金奖励。

当 R. Rivest、A. Shamir 和 L. Adleman 使用 129 位数字 RSA-129 发布了首批公钥消息之一，并为该消息的解密提供了 100 美元的奖励时（Gardner 1977），RSA 数字受到了广泛关注。尽管当时普遍认为破解 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-150、RSA-155、RSA-160、RSA-200 和 RSA-576 也在 1996 年至 2005 年 5 月之间相继被分解。

最新被分解的 RSA 数字涉及 J. Franke 和 T. Kleinjung 使用波恩大学科学计算研究所和纯粹数学研究所、波恩马克斯·普朗克数学研究所和埃森实验数学研究所的硬件完成的“格”筛法。RSA-640 的分解是使用称为通用数域筛法的素因数分解算法完成的。筛法在 80 个 2.2-GHz Opteron CPU 上完成，耗时 3 个月。矩阵步骤在一个通过千兆网络连接的 80 个 2.2-GHz Opteron 集群上执行，耗时约 1.5 个月。使用此筛法找到的两个 97 位因子是

1634733 6458092538 4844313388 3865090859 8417836700 3309231218 1110852389 3331001045 0815121211 8167511579 x 1900871 2816648221 1312685157 3935413975 4718967899 6851549366 6638539088 0271038021 0449895719 1261465571

这些数字可以很容易地相乘，以验证它们的乘积确实等于原始数字。

如下表所示，RSA-704 至 RSA-2048 仍然未被破解，为那些足够聪明和坚持不懈的人追踪它们提供 30,000 美元至 200,000 美元的奖励。未破解的挑战数字列表可以从 RSA 下载，也可以从 程序包存档中以 Mathematica 程序包的形式下载。