RSA數

當 RSA公鑰密碼出現以後,尋找和分解更大的半素數 (Semiprime) 成為數學工作者另一工作。所謂半素數,即一合數,但其只是由兩個素因子 (相同或不同亦可) 相乘而來。而 RSA公鑰密碼的相關公司 RSA保安公司 (RSA Security) 會羅列一些這樣的大半素數以挑戰大眾的分解能力,當然有獎金的。這等數便是所謂的 RSA數 (RSA Number)。我們通常用 RSA-n 來表示 RSA數,這個 n 代表該數的數位有多少,例如 RSA-100 則表示該數有 100 個數位、RSA-200 則表示該數有 200 個數位。但較大 n 是以二進制 (Binary) 表示,如 RSA-576 折合實得 174 數位、 RSA-2048 也不過是 617 數位而已。當然該數實際是什麼,還得參看相關網頁: http://www.rsasecurity.com/rsalabs/node.asp?id=2093

相對已知的大素數而言,RSA數「小」得多,大都是由一百至數千數位不等。但分解這些數可能更困難,因為對於數百至數千數位的空間,我們所知的素數是疏離的,即不是每一個這樣的數也被判定了素性,更不用談有一份完整的素數表。

由 RSA實驗室 (RSA Laboratories) 負責資助給予成功分解者的獎金,獎金由數百至數十萬美元不等。當 RSA-129 出現,問題開始受到關注,當時獎金是一百美元。及後數位多了,獎金也多了,若有人成功分解 RSA-2048,可得的獎金是二十萬美元。

最終 RSA-129 於 1994年由數學家路迪維拿 (K. Luetwyler) 成功分解成一個 64數位和另一個 65數位的素數。

RSA-140 於 1999年由拉依迪 (H. te Riele) 領導的小組成功分解成兩個 70 數位的素數。而 2004年,RSA-150也被分解成兩個 75 數位的素數。1999年拉依迪又一次挑戰成功,把 RSA-155 成功分解成兩個 78 數位的素數。在 2003年,德國數學家法蘭克 (Jens Franke 1964 - ) 成功把 RSA-576 成功分解成兩個 87 數位的素數。在 2005年,又是法蘭克,他把 RSA-200 和 RSA-640 成功分解。

到了現在我們尚有 RSA-704 、 RSA-768 、 RSA-896 、 RSA-1024 、 RSA-1536 和 RSA-2048 接受挑戰,數位由 193 至 617 不等,不知各位有沒有興趣呢?

 

參考文獻及網址:

RSA Security.R "RSA Factoring Challenge." http://www.rsasecurity.com/rsalabs/challenges/factoring/.

RSA Security.R "Factorization of RSA-140." http://www.rsasecurity.com/rsalabs/challenges/factoring/rsa140.html.

RSA Security.R "Factorization of RSA-155." http://www.rsasecurity.com/rsalabs/challenges/factoring/rsa155.html.

RSA Security.R "Factorization of RSA-160." http://www.rsasecurity.com/rsalabs/challenges/factoring/rsa160.html.

RSA Security.R "The RSA Challenge Numbers." http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html.

RSA Security.R "What is the RSA Factoring Challenge and What is RSA-129?" http://www.rsasecurity.com/rsalabs/faq/.

Weisstein, E. W. "RSA Number." From MathWorld. http://mathworld.wolfram.com/RSANumber.html.

Weisstein, E. W. "RSA-200 Factored." From MathWorld Headline News. http://mathworld.wolfram.com/news/2005-05-10/rsa-200/

Weisstein, E. W. "RSA-576 Factored." From MathWorld Headline News. http://mathworld.wolfram.com/news/2003-12-05/rsa/

Weisstein, E. W. "RSA-640 Factored." From MathWorld Headline News. http://mathworld.wolfram.com/news/2005-11-08/rsa-640/