[clean-list] The ultimate (programming) challenge...
Royi Eltink
royi@eastsite.nl
Thu, 01 Nov 2001 11:04:33 +0100
This is a multi-part message in MIME format.
--------------BB601CDC03F40EA44BCF1E4B
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Or so I'd say...
My suggestion is a perl program wich optimies itself during the
calculation proces...
How about yours?
--
Ro'
---------------------
East Site
http://www.eastsite.nl
---------------------
Random Quote:
"An advantageous situation and staying there.."
- Sun Tzu
--------------BB601CDC03F40EA44BCF1E4B
Content-Type: text/plain; charset=us-ascii;
name="rsachallenge.txt"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="rsachallenge.txt"
The RSA Factoring Challenge
What is the RSA Factoring Challenge?
The RSA Factoring challenge is an effort, sponsored by RSA Laboratories, to learn about the actual
difficulty of factoring large numbers of the type used in RSA keys. A set of eight challenge numbers,
ranging in size from 576 bits to 2048 bits is posted here. Each number is the product of two large
primes, similar to the modulus of an RSA key pair.
Factoring a number means representing it as the product of prime numbers. Prime numbers, such as
2, 3, 5, 7, 11, and 13, are those numbers that are not evenly divisible by any smaller number, except
1. A non-prime, or composite number, can be written as the product of smaller primes, known as its
prime factors. 665, for example is the product of the primes 5, 7, and 19. A number is said to be
factored when all of its prime factors are identified. As the size of the number increases, the
difficulty of factoring increases rapidly.
Factoring 100-digit numbers is easy with today's hardware and algorithms Factoring numbers of more
than 200 digits, however, is not currently feasible. Advances in both computer hardware and number
theory are expected to advance the state of the art. One purpose of this contest is to "track" the
state of the art in factoring.
The first person to submit a correct factorization for any of the challenge numbers is eligible for
a cash prize. Given the amount of computation required for such a factorization, the prizes are
mainly symbolic. They serve as a small incentive for public demonstrations of factoring on a large
scale.
To date, the largest number of this type to be factored is 512 bits. It was factored in 1999 as part
of the previous RSA Factoring Challenge, which this challenge replaces. See the announcement for
information about this factorization. The 576-bit value is likely to be factored in the next year
or so, while RSA-2048 should stand for decades.
--------------------------------------------------------------------------------
How do I get the RSA Challenge numbers?
There are eight RSA challenge numbers, ranging in size from 576 bits to 2048 bits. They are available
from numbers.html. To obtain a single challenge number, select its entry and a page will display
containing the decimal value of the challenge number, its current status (whether or not it has yet
been factored), and the prize awarded for the first factorization. The value may be copied directly
from this page, or downloaded as ASCII text.
If you prefer to obtain all the challenge numbers at once, the URL listed above allows you to download
a single file, in text format, that contains all eight challenge numbers.
--------------------------------------------------------------------------------
How do I submit a completed factorization?
If you have completed the factorization of a challenge number, you must submit the result to RSA Labs
for verification. A submission form is available at http://www.rsasecurity.com/go/factorization.html.
Enter the name(s) of the submitter(s), the challenge number factored, the two factors, and an e-mail
address at which RSA Labs may contact you. In addition, please enter a brief description of the
method and resources used in the factorization.
If RSA Labs successfully verifies the submission and it is the first factorization submitted for
the specified number, you will be contacted by RSA Labs to arrange for the award of the prize money.
--------------------------------------------------------------------------------
What does it mean when a Challenge Number is factored?
Users of the RSA public-key cryptosystem may wonder what the factoring of a challenge number implies
about the security of their keys. Should they immediately replace their keys with larger ones? Should
they stop using RSA altogether?
Clearly, the factoring of a challenge-number of specific length does not mean that the RSA
cryptosystem is "broken." It does not even mean, necessarily, that keys of the same length as the
factored challenge number must be discarded. It simply gives us an idea of the amount of work
required to factor a modulus of a given size. This can be translated into an estimate of the cost of
breaking a particular RSA key pair.
Suppose, for example, that in the year 2010 a factorization of RSA-768 is announced that requires 6
months of effort on 100,000 workstations. In this hypothetical situation, would all 768-bit RSA keys
need to be replaced? The answer is no. If the data being protected needs security for significantly
less than six months, and its value is considerably less than the cost of running 100,000 workstations
for that period, then 768-bit keys may continue to be used.
Applications that require longer-term security or have data with a high financial value should migrate
to longer keys before the factoring of the corresponding challenge number is announced. In either case,
the results of the Factoring Challenge provide real data to help the cryptosystem user choose the
appropriate key size.
RSA Laboratories' Frequently Asked Questions About Today's Cryptography provides more information on
choosing RSA key lengths for various applications. RSA Laboratories Bulletin #13 discusses key length
requirements for various cryptosystems.
--------------------------------------------------------------------------------
How Were the Challenge Numbers Generated?
The RSA challenge numbers were generated using a secure process that guarantees that the factors of
each number cannot be obtained by any method other than factoring the published value. No one, not
even RSA Laboratories, knows the factors of any of the challenge numbers.
The generation took place on a Compaq laptop PC with no network connection of any kind. The process
proceeded as follows:
First, 30,000 random bytes were generated using a ComScire QNG hardware random number generator,
attached to the laptop's parallel port.
The random bytes were used as the seed values for the B_GenerateKeyPair function, in version 4.0 of
the RSA BSAFE library. The private portion of the generated keypair was discarded. The public portion
was exported, in DER format to a disk file.
The moduli were extracted from the DER files and converted to decimal for posting on the Web page.
The laptop's hard drive was destroyed.
The C source code of the programs used to generate and format the challenge numbers are available on
request from the challenge administrator.
Just send e-mail to : challenge-administrator@rsasecurity.com.
--------------------------------------------------------------------------------
How do I know which challenge numbers have been factored?
The status of each of the challenge numbers is available at numbers.html. The status will be shown
as "Not Factored" for values for which no correct factorization has been submitted. If the number has
been factored, the status will identify the submitter and the date of submission.
For challenge numbers that have been factored, the individual page will provide a brief description
of the factoring effort. A pointer to a web site, if available, that has the details of the effort
will also be provided.
--------------------------------------------------------------------------------
What are the best factoring methods?
The best known algorithm for factoring large numbers is the General Number Field Sieve (GNFS).
GNFS consists of a sieving phase that searches a fixed set of prime numbers for candidates that have a
particular algebraic relationship, modulo the number to be factored. This is followed by a matrix
solving phase that creates a large matrix from the candidate values, then solves it to determine the
factors.
The sieving phase may be done in distributed fashion, on a large number of processors simultaneously.
The matrix solving phase requires massive amounts of storage and is typically performed on a large
supercomputer.
More information on factoring algorithms is available on the RSA Laboratories FAQ.
--------------------------------------------------------------------------------
How much does it cost to factor a large number?
The resources required to factor a large number using GNFS consist of both processing power (machines)
and data storage (memory).
The table below provides an estimate of the resources required to factor numbers of various bit lengths
in a time period of one year. The Machines column is the number of 500 MHz Pentium (or comparable)
machines needed.The Memory column is the amount of RAM required in each machine.
Number Length (bits) Machines Memory
430 1 trivial
760 215,000 4 Gb
1020 342,000,000 170 Gb
1620 1.6 x 1015 120 Tb
As shown, to factor a 760-bit number in one year would require 215,000 Pentium-class machines, each with
4 Gigabytes of physical RAM. These are estimates based on today's best factoring technology. It is
possible that new techniques will be developed that may reduce both the number of machines and the
storage per machine. A more detailed description of the cost of factoring, and of breaking keys for
other cryptographic methods is presented in RSA Laboratories Bulletin #13.
--------------------------------------------------------------------------------
The RSA Challenge Numbers
A link to each of the eight RSA challenge numbers is listed below. The numbers are designated
"RSA-XXXX", where XXXX is the number's length, in bits. The values are presented as decimal strings,
with the most significant digit first. Also listed are the number of digits, the decimal sum of the
digits and the dollar amount to be awarded for a successful factorization.
Name: RSA-576
Prize: $10000
Digits: 174
Digit Sum: 785
188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059
Name: RSA-640
Prize: $20000
Digits: 193
Digit Sum: 806
3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609
Name: RSA-704
Prize: $30000
Digits: 212
Digit Sum: 1009
74037563479561712828046796097429573142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359
Name: RSA-768
Prize: $50000
Digits: 232
Digit Sum: 1018
1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
Name: RSA-896
Prize: $75000
Digits: 270
Digit Sum: 1222
412023436986659543855531365332575948179811699844327982845455626433876445565248426198098870423161841879261420247188869492560931776375033421130982397485150944909106910269861031862704114880866970564902903653658867433731720813104105190864254793282601391257624033946373269391
Name: RSA-1024
Prize: $100000
Digits: 309
Digit Sum: 1369
135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
Name: RSA-1536
Prize: $150000
Digits: 463
Digit Sum: 2153
1847699703211741474306835620200164403018549338663410171471785774910651696711161249859337684305435744585616061544571794052229717732524660960646946071249623720442022269756756687378427562389508764678440933285157496578843415088475528298186726451339863364931908084671990431874381283363502795470282653297802934916155811881049844908319545009848393775227257052578591944993870073695755688436933812779613089230392569695253261620823676490316036551371447913932347169566988069
Name: RSA-2048
Prize: $200000
Digits: 617
Digit Sum: 2738
25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357
--------------BB601CDC03F40EA44BCF1E4B--