本文发表于《大众科学》的前博客网络，反映了作者的观点，不一定代表《大众科学》的观点
一个研究团队成功地将一个 232 位数字分解为其两个复合质数因子，但为时已晚，无法获得曾经与该成就相关的 50,000 美元奖金。这个数字 RSA-768 是由一家著名的计算机安全公司 RSA 实验室赞助的密码学挑战的一部分，该挑战技术上于 2007 年结束。RSA-768 之所以如此命名，是因为它的二进制表示长度为 768 位，是现已失效的挑战中被破解的最大数字。
瑞士洛桑联邦理工学院的 Thorsten Kleinjung 和他的同事在周三发布于《密码学电子预印本档案》的一篇论文中宣布了他们的结果。他和他的同事指出，更大的数字已被分解为质数，但这些数字是允许更简单分解的特殊情况。（质数只能被自身和 1 整除。）
关于支持科学新闻
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道： 订阅。通过购买订阅，您将帮助确保关于塑造我们当今世界的发现和想法的有影响力的故事的未来。
RSA 分解挑战 提供了一系列巨大的半素数（由两个质数因子组成的数字），这些数字代表了 RSA 加密中使用的类型，并为分解这些数字提供了高达 200,000 美元的现金奖励。RSA 表示，这些挑战在计算机安全的早期阶段曾帮助评估加密协议的稳健性，现在对于该领域来说不再必要。“现在，业界对常见算法的密码分析强度有了相当先进的了解，这些挑战不再活跃，”该公司网站上的一份声明写道。
RSA 密码学依赖于将数字分解为大型组成质数是一个困难且耗时的过程这一事实——新的结果需要在单核 2.2 GHz 机器上相当于 2000 年的计算时间。在 RSA 密码学中，一个大的复合数可以公开共享并用于编码加密消息，但只有当知道复合数的质数因子时，才能快速完成消息的解密。
一个著名的演示出现在 1977 年马丁·加德纳在《大众科学》上的“数学游戏”专栏中。加德纳发表了 RSA 密码学发明者 Ronald Rivest、Adi Shamir 和 Leonard Adleman 发出的一条编码消息，以及用于编码该消息的大型复合数（一个 64 位质数和一个 65 位质数的乘积）。当时都在麻省理工学院的 Rivest、Shamir 和 Adleman 提供 100 美元的奖励来破解它，Rivest 估计以当时的技术需要 40 万亿年的时间。但是，1977 年看似不可能的事情在 1994 年完成，当时一个包括业余爱好者和互联网志愿者的联盟获得了该奖项。
Kleinjung 和他的同事在他们的论文中指出，分解 RSA-768 与分解目前广泛使用的 1,024 位加密密钥相去甚远——他们说，这样的分解问题大约困难 1,000 倍。
无论如何，对于那些好奇地想知道 2000 年的计算时间能产生什么结果的人来说，RSA-768 的分解结果如下
1230186684530117755130494958384962720772853569595
3347921973224521517264005072636575187452021997864
6938995647494277406384592519255732630345373154826
8507917026122142913461670429214311602221240479274
737794080665351419597459856902143413
=
3347807169895689878604416984821269081770479498371
3768568912431388982883793878002287614711652531743
087737814467999489
x
3674604366679959042824463379962795263227915816434
3087642676032283815739666511279233373417143396810
270092798736308917
图片：©iStockphoto/kazina