Global Information Lookup Global Information

RSA numbers information


In mathematics, the RSA numbers are a set of large semiprimes (numbers with exactly two prime factors) that were part of the RSA Factoring Challenge. The challenge was to find the prime factors of each number. It was created by RSA Laboratories in March 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers. The challenge was ended in 2007.[1]

RSA Laboratories (which is an initialism of the creators of the technique; Rivest, Shamir and Adleman) published a number of semiprimes with 100 to 617 decimal digits. Cash prizes of varying size, up to US$200,000 (and prizes up to $20,000 awarded), were offered for factorization of some of them. The smallest RSA number was factored in a few days. Most of the numbers have still not been factored and many of them are expected to remain unfactored for many years to come. As of February 2020, the smallest 23 of the 54 listed numbers have been factored.

While the RSA challenge officially ended in 2007, people are still attempting to find the factorizations. According to RSA Laboratories, "Now that the industry has a considerably more advanced understanding of the cryptanalytic strength of common symmetric-key and public-key algorithms, these challenges are no longer active."[2] Some of the smaller prizes had been awarded at the time. The remaining prizes were retracted.

The first RSA numbers generated, from RSA-100 to RSA-500, were labeled according to their number of decimal digits. Later, beginning with RSA-576, binary digits are counted instead. An exception to this is RSA-617, which was created before the change in the numbering scheme. The numbers are listed in increasing order below.

Note: until work on this article is finished, please check both the table and the list, since they include different values and different information.

name decimal digits bits announcement prize number factorization first solver notes
date by date algorithm compute power calendar time
RSA-100 40094690950920881030683735292761468389214899724061 * 37975227936943673922808872755445627854565536638199 1991-04-01 ppmpqs by Mark Manasse and Arjen K. Lenstra approx. 7 MIP-Years [3]
RSA-110 6122421090493547576937037317561418841225758554253106999 * 5846418214406154678836553182979162384198610505601062333 1992-04-14 ppmpqs by Arjen K. Lenstra one month on 5/8 of a 16K MasPar [3]
RSA-120 327414555693498015751146303749141488063642403240171463406883 * 693342667110830181197325401899700641361965863127336680673013 1993-06-09 ppmpqs 835 mips years run by Arjen K. Lenstra (45.503%), Bruce Dodson (30.271%), Thomas Denny (22.516%), Mark Manasse (1.658%), and Walter Lioen and Herman te Riele (0.049%) [3]
RSA-129 129 1977-08 Martin Gardner, Mathematical Games, Scientific American $100 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541 3490529510847650949147849619903898133417764638493387843990820577 * 32769132993266709549961988190834461413177642967992942539798288533 1994-04-26 ppmpqs approximately 5000 mips years run by Derek Atkins, Michael Graff, Arjen K. Lenstra, Paul Leyland, and more than 600 volunteers [3]
RSA-130 39685999459597454290161126162883786067576449112810064832555157243 * 45534498646735972188403686897274408864356301263205069600999044599 1996-04-10 General Number Field Sieve with lattice sieving implementations by Bellcore, CWI, and Saarbruecken; and blocked Lanczos and square root by Peter L. Montgomery sieving: estimated 500 mips years, run by Bruce Dodson (28.37%), Peter L. Montgomery and Marije Elkenbracht-Huizing (27.77%), Arjen K. Lenstra (19.11%), WWW contributors (17.17% ), Matt Fante (4.36%), Paul Leyland (1.66%), Damian Weber and Joerg Zayer (1.56%)

matrix (67.5 hours on the Cray-C90 at SARA, Amsterdam) and square root (48 hours per dependency on an SGI Challenge processor) run by Peter L. Montgomery and Marije Elkenbracht-Huizing

the factorization was found in the third trial[3]
RSA-140 3398717423028438554530123627613875835633986495969597423490929302771479 * 6264200187401285096151654948264442219302037178623509019111660653946049 1999-02-02 GNFS with line (by CWI; 45%) and lattice (by Arjen K. Lenstra; 55%) sieving, and a polynomial selection method by Brian Murphy and Peter L. Montgomery; and blocked Lanczos and square root by Peter L. Montgomery polynomial selection: 2000 CPU hours on four 250 MHZ SGI Origin 2000 processors at CWI

sieving: 8.9 CPU-years on about 125 SGI and Sun workstations running at 175 MHZ on average, and on about 60 PCs running at 300 MHZ on average; approximately equivalent to 1500 mips years; run by Peter L. Montgomery, Stefania Cavallar, Herman J.J. te Riele, and Walter M. Lioen (36.8%), Paul Leyland (28.8%), Bruce Dodson (26.6%), Paul Zimmermann (5.4%), and Arjen K. Lenstra (2.5%).

matrix: 100 hours on the Cray-C916 at SARA, Amsterdam

square root: four different dependencies were run in parallel on four 250 MHZ SGI Origin 2000 processors at CWI; three of them found the factors of RSA-140 after 14.2, 19.0 and 19.0 CPU-hours

eleven weeks (including four weeks for polynomial selection, one month for sieving, one week for data filtering and matrix construction, five days for the matrix, and 14.2 hours to find the factors using the square root) the matrix had 4671181 rows and 4704451 columns and weight 151141999 (32.36 nonzeros per row)[3]
RSA-155 102639592829741105772054196573991675900716567808038066803341933521790711307779 * 106603488380168454820927220360012878679207958575989291522270608237193062808643 1999-08-22 GNFS with line (29%) and lattice (71%) sieving, and a polynomial selection method written by Brian Murphy and Peter L. Montgomery, ported by Arjen Lenstra to use his multiple precision arithmetic code (LIP); and blocked Lanczos and square root by Peter L. Montgomery polynomial selection run by Brian Murphy, Peter Montgomery, Arjen Lenstra and Bruce Dodson; Dodson found the one that was used

sieving: 35.7 CPU-years in total, on about one hundred and sixty 175-400 MHz SGI and Sun workstations, eight 250 MHz SGI Origin 2000 processors, one hundred and twenty 300-450 MHz Pentium II PCs, and four 500 MHz Digital/Compaq boxes; approximately equivalent to 8000 mips years; run by Alec Muffett (20.1% of relations, 3057 CPU days), Paul Leyland (17.5%, 2092 CPU days), Peter L. Montgomery and Stefania Cavallar (14.6%, 1819 CPU days), Bruce Dodson (13.6%, 2222 CPU days), Francois Morain and Gerard Guillerm (13.0%, 1801 CPU days), Joel Marchand (6.4%, 576 CPU days), Arjen K. Lenstra (5.0%, 737 CPU days), Paul Zimmermann (4.5%, 252 CPU days), Jeff Gilchrist (4.0%, 366 CPU days), Karen Aardal (0.65%, 62 CPU days), and Chris and Craig Putnam (0.56%, 47 CPU days)

matrix: 224 hours on one CPU of the Cray-C916 at SARA, Amsterdam square root: four 300 MHz R12000 processors of a 24-processor SGI Origin 2000 at CWI; the successful one took 39.4 CPU-hours and the others took 38.3, 41.9, and 61.6 CPU-hours

9 weeks for polynomial selection, plus 5.2 months for the rest (including 3.7 months for sieving, about 1 month for data filtering and matrix construction, and 10 days for the matrix) the polynomials were 119377138320*x^5 - 80168937284997582*y*x^4 - 66269852234118574445*y^2*x^3 + 11816848430079521880356852*y^3*x^2 + 7459661580071786443919743056*y^4*x - 40679843542362159361913708405064*y^5 and x - 39123079721168000771313449081*y (this pair has a yield of relations approximately 13.5 times that of a random polynomial selection); 124722179 relations were collected in the sieving stage; the matrix had 6699191 rows and 6711336 columns and weight 417132631 (62.27 nonzeros per row).[3]
Contents
  • RSA-100
  • RSA-110
  • RSA-120
  • RSA-129
  • RSA-130
  • RSA-140
  • RSA-150
  • RSA-155
  • RSA-160
  • RSA-170
  • RSA-576
  • RSA-180
  • RSA-190
  • RSA-640
  • RSA-200
  • RSA-210
  • RSA-704
  • RSA-220
  • RSA-230
  • RSA-232
  • RSA-768
  • RSA-240
  • RSA-250
  • RSA-260
  • RSA-270
  • RSA-896
  • RSA-280
  • RSA-290
  • RSA-300
  • RSA-309
  • RSA-1024
  • RSA-310
  • RSA-320
  • RSA-330
  • RSA-340
  • RSA-350
  • RSA-360
  • RSA-370
  • RSA-380
  • RSA-390
  • RSA-400
  • RSA-410
  • RSA-420
  • RSA-430
  • RSA-440
  • RSA-450
  • RSA-460
  • RSA-1536
  • RSA-470
  • RSA-480
  • RSA-490
  • RSA-500
  • RSA-617
  • RSA-2048
  See also     Notes     References     External links
  1. ^ RSA Laboratories. "RSA Factoring Challenge". Archived from the original on September 21, 2013. Retrieved August 5, 2008.{{cite web}}: CS1 maint: unfit URL (link)
  2. ^ RSA Laboratories. "The RSA Factoring Challenge FAQ". Archived from the original on September 21, 2013. Retrieved August 5, 2008.{{cite web}}: CS1 maint: unfit URL (link)
  3. ^ a b c d e f g RSA Factoring Challenge Administrator (challenge-administrator@majordomo.rsasecurity.com) (January 30, 2002) [March 5, 1999]. "RSA Honor Roll". challenge-rsa-honor-roll@rsa.com (Mailing list). Archived from the original on September 9, 2023 – via Ray Ontko.

and 21 Related for: RSA numbers information

Request time (Page generated in 0.7963 seconds.)

RSA numbers

Last Update:

In mathematics, the RSA numbers are a set of large semiprimes (numbers with exactly two prime factors) that were part of the RSA Factoring Challenge. The...

Word Count : 4093

RSA Factoring Challenge

Last Update:

cracking RSA keys used in cryptography. They published a list of semiprimes (numbers with exactly two prime factors) known as the RSA numbers, with a cash...

Word Count : 829

RSA

Last Update:

Look up RSA in Wiktionary, the free dictionary. RSA may refer to: Rabbinical Seminary of America, a yeshiva in New York City Regional Science Association...

Word Count : 417

RSA SecurID

Last Update:

RSA SecurID, formerly referred to as SecurID, is a mechanism developed by RSA for performing two-factor authentication for a user to a network resource...

Word Count : 2268

RSA problem

Last Update:

In cryptography, the RSA problem summarizes the task of performing an RSA private-key operation given only the public key. The RSA algorithm raises a message...

Word Count : 681

The Magic Words are Squeamish Ossifrage

Last Update:

breaking the RSA cipher—recovering a plaintext message given a ciphertext and the public key—is connected to the difficulty of factoring large numbers. While...

Word Count : 707

Integer factorization

Last Update:

primality testing is a crucial part of the RSA algorithm, as it is necessary to find large prime numbers to start with. A special-purpose factoring algorithm's...

Word Count : 2924

Digital signature

Last Update:

signature schemes operate on other domains (such as, in the case of RSA, numbers modulo a composite number N). A hash function can be used to convert...

Word Count : 5198

Quadratic sieve

Last Update:

general-purpose algorithm, until NFS was used to factor RSA-130, completed April 10, 1996. All RSA numbers factored since then have been factored using NFS....

Word Count : 4476

Semiprime

Last Update:

RSA Factoring Challenge, RSA Security offered prizes for the factoring of specific large semiprimes and several prizes were awarded. The original RSA...

Word Count : 846

List of numbers

Last Update:

notable numbers and articles about notable numbers. The list does not contain all numbers in existence as most of the number sets are infinite. Numbers may...

Word Count : 3866

Cryptanalysis

Last Update:

start of the 21st century, 150-digit numbers were no longer considered a large enough key size for RSA. Numbers with several hundred digits were still...

Word Count : 5176

Prime number

Last Update:

algorithms, such as RSA and the Diffie–Hellman key exchange, are based on large prime numbers (2048-bit primes are common). RSA relies on the assumption...

Word Count : 14104

Optimal asymmetric encryption padding

Last Update:

Asymmetric Encryption Padding (OAEP) is a padding scheme often used together with RSA encryption. OAEP was introduced by Bellare and Rogaway, and subsequently...

Word Count : 1451

Arjen Lenstra

Last Update:

was also a leader in the successful factorizations of several other RSA numbers. Lenstra was also involved in the development of the number field sieve...

Word Count : 539

PKCS

Last Update:

are a group of public-key cryptography standards devised and published by RSA Security LLC, starting in the early 1990s. The company published the standards...

Word Count : 263

Random number generation

Last Update:

Matthew Green (2013-09-20). "RSA warns developers not to use RSA products". "We don't enable backdoors in our crypto products, RSA tells customers". Ars Technica...

Word Count : 4396

Integer factorization records

Last Update:

semiprimes (and, indeed, most numbers that have no small factors). The first enormous distributed factorisation was RSA-129, a 129-digit challenge number...

Word Count : 1998

NH RSA Title I

Last Update:

as a whole. Like other portions of the RSAs, the Title is divided into Chapters and Sections organized in numbers and subsections organized in lowercase...

Word Count : 1285

PKCS 1

Last Update:

that RSA public and private keys must have. The traditional key pair is based on a modulus, n, that is the product of two distinct large prime numbers, p...

Word Count : 1484

BLS digital signature

Last Update:

key and message, there is only one valid signature (like RSA PKCS1 v1.5, EdDSA and unlike RSA PSS, DSA, ECDSA and Schnorr).[citation needed] BLS12-381...

Word Count : 1009
PDF Search Engine © AllGlobal.net