头条新闻

RSA-200 已被分解

作者：Eric W. Weisstein

2005年5月10日——5月9日，德国联邦信息技术安全局 (BSI) 的一个团队宣布已分解了 200 位数字的数字

2799783391 1221327870 8294676387 2260162107 0446786955 4285375600 0992932612 8400107609 3456710529 5536085606 1822351910 9513657886 3710595448 2006576775 0985805576 1357909873 4950144178 8631789462 9518723786 9221823983

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

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

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

虽然 RSA-200 比 7,816,230 位数字的巨型梅森素数 M₄₂（这是已知的最大质数）小得多，但它的分解意义重大，因为证明或反驳一个数字是质数（“素性测试”）似乎比实际识别一个数字的因数（“质因数分解”）容易得多。因此，虽然将两个大数 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-150、RSA-155、RSA-160 和 RSA-576 也随后在 1996 年至 2004 年 4 月之间被分解。

最新的 RSA 数字分解涉及 J. Franke 和 T. Kleinjung 使用波恩大学科学计算研究所和纯粹数学研究所、波恩马克斯·普朗克数学研究所和埃森实验数学研究所的硬件完成的“格”筛选；以及 P. Montgomery 和 H. te Riele 在阿姆斯特丹荷兰数学和计算机科学中心 (CWI) 完成的“线”筛选。然后，在 BSI 的支持下完成了此数据的后处理，以构建实际的因数。RSA-200 的分解是使用一种称为一般数域筛法的质因数分解算法完成的，使用此筛法找到的两个 100 位数字的因数是

3532461934 4027701212 7260497819 8464368671 1974001976 2502364930 3468776121 2536794232 0005854795 6528088349 x 7925869954 4783330333 4708584148 0059687737 9758573642 1996073433 0341455767 8728181521 3538140930 4740185467

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

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

后记

虽然许多 RSA 挑战数字仍然未被分解，但 RSA 挑战及其相关的现金奖励此后已停止。