頭條新聞

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 挑戰及其相關的現金獎勵此後已停止。