頭條新聞

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 程式包的形式下載。