The RSA Factoring Challenge was a challenge put forward by
RSA Laboratories
RSA Security LLC, formerly RSA Security, Inc. and doing business as RSA, is an American computer and network security company with a focus on encryption and encryption standards. RSA was named after the initials of its co-founders, Ron Rivest, ...
on March 18, 1991 to encourage research into
computational number theory
In mathematics and computer science, computational number theory, also known as algorithmic number theory, is the study of
computational methods for investigating and solving problems in number theory and arithmetic geometry, including algorithm ...
and the practical difficulty of
factoring large
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s and cracking
RSA keys used in
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
. They published a list of
semiprime
In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers.
Because there are infinitely many prime nu ...
s (numbers with exactly two
prime factor
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s) known as the
RSA numbers
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 i ...
, with a cash prize for the successful factorization of some of them. The smallest of them, a 100-decimal digit number called
RSA-100 was factored by April 1, 1991. Many of the bigger numbers have still not been factored and are expected to remain unfactored for quite some time, however advances in
quantum computer
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
s make this prediction uncertain due to
Shor's algorithm
Shor's algorithm is a quantum algorithm, quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor.
On a quantum computer, to factor an integer N , Shor's algorithm ...
.
In 2001, RSA Laboratories expanded the factoring challenge and offered prizes ranging from $10,000 to $200,000 for factoring numbers from 576 bits up to 2048 bits.
The RSA Factoring Challenges ended in 2007.
RSA Laboratories stated: "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."
When the challenge ended in 2007, only RSA-576 and RSA-640 had been factored from the 2001 challenge numbers.
The factoring challenge was intended to track the cutting edge in integer factorization. A primary application is for choosing the
key length
In cryptography, key size, key length, or key space refer to the number of bits in a key used by a cryptographic algorithm (such as a cipher).
Key length defines the upper-bound on an algorithm's security (i.e. a logarithmic measure of the faste ...
of the
RSA public-key encryption
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
scheme. Progress in this challenge should give an insight into which
key size
In cryptography, key size, key length, or key space refer to the number of bits in a key used by a cryptographic algorithm (such as a cipher).
Key length defines the upper-bound on an algorithm's security (i.e. a logarithmic measure of the faste ...
s are still safe and for how long. As RSA Laboratories is a provider of RSA-based products, the challenge was used by them as an incentive for the academic community to attack the core of their solutions — in order to prove its strength.
The RSA numbers were generated on a computer with no network connection of any kind. The computer's hard drive was subsequently destroyed so that no record would exist, anywhere, of the solution to the factoring challenge.
The first RSA numbers generated, RSA-100 to RSA-500 and RSA-617, were labeled according to their number of
decimal
The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral ...
digits; the other RSA numbers (beginning with RSA-576) were generated later and labelled according to their number of
binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that ta ...
digits. The numbers in the table below are listed in increasing order despite this shift from decimal to binary.
The mathematics
RSA Laboratories states that: for each RSA number ''n'', there exists
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s ''p'' and ''q'' such that
:''n'' = ''p'' × ''q''.
The problem is to find these two primes, given only ''n''.
The prizes and records
The following table gives an overview over all RSA numbers. Note that the RSA Factoring Challenge ended in 2007
and no further prizes will be awarded for factoring the higher numbers.
:''The challenge numbers in white lines are part of the original challenge and are expressed in
base 10
The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numer ...
, while the challenge numbers in yellow lines are part of the 2001 expansion and are expressed in
base 2''
See also
*
RSA numbers
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 i ...
, decimal expansions of the numbers and known factorizations
*
LCS35
*
The Magic Words are Squeamish Ossifrage "The Magic Words are Squeamish Ossifrage" was the solution to a challenge ciphertext posed by the inventors of the RSA cipher in 1977. The problem appeared in Martin Gardner's ''Mathematical Games column'' in the August 1977 issue of ''Scientific ...
, the solution found in 1993 to another RSA challenge posed in 1977
*
RSA Secret-Key Challenge
The RSA Secret-Key Challenge was a series of cryptographic contests organised by RSA Laboratories with the intent of helping to demonstrate the relative security of different encryption algorithms. The challenge ran from 28 January 1997 until May ...
*
Integer factorization records
Integer factorization is the process of determining which prime numbers divide a given positive integer. Doing this quickly has applications in cryptography. The difficulty depends on both the size and form of the number and its prime factors; it ...
Notes
{{DEFAULTSORT:Rsa Factoring Challenge
Integer factorization algorithms
Cryptography contests
1991 establishments in the United States