Conference rusure::math

1404.0. "RSA Factoring Challenge" by GUESS::DERAMO (Dan D'Eramo) Mon Mar 25 1991 12:46

Article        15171
Path: ryn.mro4.dec.com!shlump.nac.dec.com!news.crl.dec.com!deccrl!bloom-beacon!bloom-picayune.mit.edu!athena.mit.edu!burt
From: [email protected] (Burt Kaliski)
Newsgroups: sci.math
Subject: RSA Factoring Challenge
Message-ID: <[email protected]>
Date: 21 Mar 91 13:50:25 GMT
Sender: [email protected] (News system)
Organization: RSA Data Security, Inc.
Lines: 256
 
 
		ANNOUNCEMENT OF "RSA FACTORING CHALLENGE"
		-----------------------------------------
  			    (3/18/91)
 
RSA Data Security hereby announces that it is sponsoring an ongoing
"factoring challenge" (with cash prizes) to encourage research in
computational number theory and the pragmatics of factoring large
integers.  RSA Data Security specializes in cryptographic products,
particularly those based on the RSA public-key cryptosystem.  The
results of this challenge will help users of the RSA public-key
cryptosystem achieve the level of security they desire.
 
The contest is based on two "challenge lists" of numbers.  The first
list, the "RSA List," contains numbers representative of those used in
the RSA cryptosystem.  The second list, the "Partition List," contains
what mathematicians define as "partition numbers."  The idea of using
partition numbers was suggested to Dr. Hendrik W. Lenstra, Jr.
(well-known for his contributions to the art of factoring) by Warren
Smith in a discussion on the topic of finding a set of "standard"
challenge numbers for factoring research.  The shortest number in each
list is 100 decimal digits long (well within the current state of the
art).  The RSA List contains numbers up to 500 digits in length, while
the Partition List contains arbitrarily large numbers.
 
The challenge is to factor the numbers on these lists; that is, to
represent them as products of prime numbers (their "prime factors").
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 (composite) number greater than 1 can always be written as a
product of smaller prime numbers, known as its prime factors.  For
example, the number 665 can be represented as the product of its prime
factors 5, 7, and 19.  Finding all the prime factors of a given number
is known as "factoring" the number.  As the length of the number
increases, the problem of factoring it rapidly becomes more and more
difficult.  Although factoring 100-digit numbers is within the current
state of the art, factoring arbitrary 200-digit numbers is not.  Over
time, advances in computer hardware and computational number theory
are expected to advance the state of the art.  One purpose of this
contest is to "track" the state of the art.
 
The RSA List contain numbers of the kind we believe to be the hardest 
to factor; the numbers on this list should be particularly challenging.
These are the kind of numbers used in devising secure RSA cryptosystems.
 
The Partition List contains numbers that are more-or-less "random";
some of these numbers (even very large ones) may be quite easy to
factor, although others may be quite difficult.  Although RSA Data
Security views the RSA List as the primary and most interesting
challenge list, the Partition List challenge is also provided in order
to encourage work on factoring in general as well as on factoring
numbers of cryptographic interest.
 
If you factor a number on a challenge list, please report it to RSA
Data Security, which maintains an "Honor Roll" naming the first person
to factor each number on each list.  Being placed on an Honor Roll
also makes you eligible to win a prize.
 
Cash prizes are awarded quarterly, beginning with the second quarter
of 1991 (ending June 1991).  For each challenge list, a cash prize of
$1000 is awarded if any previously unfactored numbers from that list
are factored during the quarter.  If more than one such number is
factored, then the cash first prize of $1000 is awarded to the person
factoring the smallest such number, $500 is awarded to the person
factoring the second smallest such number, and $250 if awarded to the
person factoring the third smallest such number (if any).  (The award
system favors factoring the smallest as-yet-unfactored number in order
to focus attention on the boundary between what is easily factorable
and what is not.)  Any unawarded prizes carry over to following quarters 
to increase the values of the prizes above the amounts just indicated.
 
Queries can be addressed to RSA Challenge Administrator, RSA Data
Security. (Address: 10 Twin Dolphin Drive, Redwood City, California
94065; Phone: 1-415-595-8782.  Internet Email address: [email protected]).
 
 
			CONTEST RULES AND INFORMATION
			-----------------------------
 
1. The challenge lists.
 
	The challenge numbers are in two lists, the "RSA List"
	and the "Partition List."  These lists are available from RSA
	Data Security.  They contain numbers of length at least
	100 decimal digits.  Each number is labelled with an
	"identifying tag," such as "RSA-150" (for the 150-digit number 
	from the RSA List), or "p(9721)" (for a number from the
	Partition List). A copy of the RSA List will be sent to you
	automatically if you send an email request to:
		[email protected]
	A copy of the Partition List will be sent to you automatically
	if you send an email request to:
		[email protected].
	You can also request copies of these lists by writing to the
	RSA Challenge Administrator (address below).
 
2. The Honor Rolls
 
	RSA Data Security maintains two Honor Rolls: the RSA Honor
	Roll and the Partition Honor Roll.  These honor rolls specify which
	numbers have been factored (and by whom) and which numbers
	remain unfactored.  Copies of the Honor Rolls may be obtained
	by writing to RSA Data Security or sending Internet email to:
		[email protected].
	The Honor Rolls contain the factorization reports (see below)
	for the first factorization of each challenge number, plus an
	indication as to whether a prize was awarded for that factorization.
 
3. Reporting a factorization
 
	If you factor a number that is listed as unfactored on the
	Honor Roll, you can report it to RSA Data Security.  It is
	preferred that you submit your report by electronic mail to 
		[email protected]
	or on an IBM PC-compatible 3.5" diskette.  These reports 
	will be automatically checked and logged on to the honor rolls, 
	so please use the following format in the body of your message.  
 
	(line from list describing challenge number and	its length)
	Factors: (first prime factor) * (second prime factor) * ... 
	* (last prime factor) 
	Date: (date factorization completed) 
	Method: (a phrase or sentence describing the method used)
	Time: (an estimate of the CPU time used in MIP-years)
	Name: (your name)
	Address: (your mailing address)
	Email: (your email address)
	Phone: (your telephone number)
 
	Here is an sample report claiming the factorization of p(197):
 
	p(197) = 3068829878530 (13 digits)
	Factors: 2 * 5 * 13 * 43 * 257 * 2136131
	Date: January 3, 1807
	Method: Trial division
	Time: 0.00001
	Name: C. F. Gauss
	Address: University of Gottingen
	
	Partition numbers that have at most one prime factor greater than 
	1,000,000 are considered "easy targets"; please do not send in 
	factorization reports for easy targets that are more than 50
	digits longer than the smallest unfactored challenge partition number.
	Note that easy targets are not excluded from the contest;  you 
	can win a prize for factoring an easy target, and factorizations 
	of easy targets will be listed in the honor roll.  However, for ease 
	of administration we request that you not send in factorizations of
	easy targets that are unlikely to win a prize because they are so 
	much larger the smallest unfactored number.
 
	If more than one person is involved in the factorization effort,
	please list the "contact person" first in the Name field.  
 
	The Date, Method, and Time fields are optional, although you
	are encouraged to provide this information so that others
	can more accurately assess how the state of the art is progressing.  
 
	If two reports are received for the same challenge number, RSA
	Data Security will generally give priority to the first report 
	received by RSA Data Security (not necessarily the one with the 
	earlier Date field). However, RSA Data Security reserves the right
	to judge the merits of each claim on a case-by-case basis and
	to make what it judges to be reasonable resolutions of competing
	claims, including making multiple awards, splitting awards,
	or taking other actions.
 
	For the Method field, you may specify the method used with
	standard acronyms and names, such as TD (trial division), ECM
	(elliptic curve method), QS (quadratic sieve), etc., a 
	combination of these, references to the literature, etc.
 
	To clarify the Time field, note that a MIP-year is the 
	computational power supplied by a one-MIP (million-instruction 
	per second) machine running for one year.  For example, if you 
	use a 10-MIP machine half-time for 6 months, you have used 
	2.5 MIP-years of computational power.
	
	The Address, Email, and Phone entries may be omitted if you
	already have a report in the Honor Roll and these values haven't
	changed.
 
	Please give the prime factors in increasing order.
	The prime factors you specify do not need to be "proved"
	to be primes; it suffices if they are "probable" primes.
	RSA Data Security will carefully check the primality of each 
	proposed factor with the Miller-Rabin probabilistic 
	primality-testing routine. (For a description of
	this test see, for example, Chapter 33 of Introduction to
	Algorithms by Cormen, Leiserson, and Rivest (MIT Press, 1990).)
 
	You may give the factor list on one or more lines; white space
	and carriage-return/line-feeds are ignored in the factor list.
	You may also give multiline responses for the other fields.
	(But please start each field on a new line, and don't leave
	blank lines between fields.)
 
4. Prizes
 
	RSA Data Security will award prizes quarterly, beginning with
	the second quarter of 1991 (ending June 30, 1991).  Prizes are
	awarded separately for each challenge list (as if they were 
	two entirely independent contests).  In each contest, up to three
	cash prizes may be awarded each quarter: a First Prize,
	a Second Prize, and a Third Prize.  Each contest maintains
	a separate "fund" from which to award prizes.  RSA adds $1750
	to each fund at the end of each quarter before awarding prizes
	for that quarter, so that a First Prize recipient will receive
	at least $1000, a Second Prize recipient will receive at
	least $500, and a Third Prize recipient will receive at least
	$250.  At the end of quarter, a First Prize recipient will 
	receive 1000/1750 (i.e. 4/7, or 57.14%) of the fund,
	a Second Prize recipient will receive 500/1750 (i.e. 2/7, or
	28.57%) of the fund, and a Third Prize recipient will
	receive 250/1750 (i.e. 1/7, or 14.29%) of the fund.  Any
	unawarded funds are carried over to the next quarter, so that
	the actual amount of the prizes may increase over time.
 
	The prize structure is arranged to encourage work on the
	smallest of the previously unfactored numbers, focusing 
	attention on the dividing line between "factored" and
	"unfactored."  Therefore, if one or more factorization reports
	for previously unfactored challenge numbers are received during 
	a quarter, then First Prize is awarded for the report on
	the smallest of such reported numbers, Second Prize
	for the second smallest, and Third Prize for the third smallest.
	(This implies that First Prize is awarded whenever the factorization
	of previously unfactored numbers is reported, even if the
	smallest previously unfactored number remains unfactored.  
	You win a First Prize if you factor a previously unfactored 
	challenge number during the quarter and nobody else factors a
	smaller previously unfactored challenge number.)
 
5. Administrivia
 
	Employees of RSA Data Security and their relatives are not eligible.
 
	RSA Data Security reserves the right to change the contest rules
	at any time at its sole discretion, without notice, including 
	the right to change or extend the challenge lists, to change the 
	prize amounts, and/or to terminate the contest. RSA Data Security 
	is the sole arbiter and administrator for this contest; the judgement 
	of RSA Data Security in all matters is final. 
 
	For a status report on the contest and a summary of recent
	developments, you can send an email request to:
 
		[email protected].
 
	Queries can be addressed to:
 
		RSA Challenge Administrator
		RSA Data Security
		10 Twin Dolphin Drive
		Redwood City, California 94065
		1-415-595-8782
		Internet email address: [email protected]

	DIR/TITLE=FACTOR
        
    19    HARE::STAN         31-JAN-1984     5  Advances in factoring
    49    HARE::STAN         11-MAR-1984     1  Repunit factorization
    51    HARE::STAN         26-MAR-1984    17  Factorization of M251
    73  AURORA::HALLYB       31-MAY-1984     2  Factoring program
    94    HARE::STAN         12-JUL-1984     5  Factoring Fibonacci Polynomials
    99    HARE::STAN         27-JUL-1984     1  P(x^2) factors
   195   TAV02::NITSAN       27-DEC-1984     1  funny factor. idea - comments?
   237    HARE::STAN         14-MAR-1985     1  New factoring algorithm?
   259   SUPER::MATTHEWS     16-APR-1985     0  Making factoring faster
   268    HARE::STAN         24-APR-1985     0  Factoring Polynomials
   404   TOOLS::STAN         14-DEC-1985     0  "most wanted" factorizations
   433   TOOLS::STAN         21-JAN-1986     0  New book on factoring
   492  LATOUR::JMUNZER      23-MAY-1986     3  factoring
   546  SHEILA::PUCKETT      29-JUL-1986     4  ?? Division/factoring algorithms ??
   558     CLT::GILBERT       7-AUG-1986     9  Factoring factorials
   578     CLT::GILBERT      13-SEP-1986     3  Non-factor Series
   818   33833::PATEL        19-JAN-1988     0  Skill Factor?
   871   37993::COOPER       11-MAY-1988     1  Performance of simple factoring program.
   943  CIRCUS::MSM          12-OCT-1988    12  100 digit factorization
   965   DIODE::CROWELL       2-NOV-1988     7  How to find the secret key w/ factoring?
  1252   DEC25::ROBERTS      12-JUN-1990     4  Backdoor Factorial Needed
  1254  ALLVAX::JROTH        18-JUN-1990     0  2^512 + 1 has been factored!
  1316  CADSYS::COOPER       22-OCT-1990     0  Reply on trinomial factorization in Z[x]

    See also VMSZOO::FACTOR note 46.

By far the majority of partition numbers do have small factors. Only 
the following partition numbers are prime, for (n< 600). 

n	partitions(n)
____	_____________
2	2
3	3
4	5
5	7
6	11
13	101
36	17977
77	10619863
132	6620830889
157	80630964769
168	228204732751
186	1171432692373
188	1398341745571
212	10963707205259
216	15285151248481
302	10657331232548839
366	790738119649411319
417	18987964267331664557
440	74878248419470886233
491	1394313503224447816939
498	2058791472042884901563
525	9035096690829005915201
546	27833079238879849385687

Article 10095 of alt.privacy:
From: [email protected] (Derek Atkins)
Newsgroups: sci.math,sci.crypt,alt.security,alt.security.pgp,alt.security.ripem,comp.security.misc,alt.privacy
Subject: RSA-129
Organization: Massachusetts Institute of Technology (MIT)
Lines: 56

We are happy to announce that

RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429\
          35706935245733897830597123563958705058989075147599290026879543541
        = 3490529510847650949147849619903898133417764638493387843990820577 *
          32769132993266709549961988190834461413177642967992942539798288533


The encoded message published was

968696137546220614771409222543558829057599911245743198746951209308162\
98225145708356931476622883989628013391990551829945157815154

This number came from an RSA encryption of the `secret' message using the
public exponent 9007. When decrypted with he `secret' exponent

106698614368578024442868771328920154780709906633937862801226224496631\
063125911774470873340168597462306553968544513277109053606095

this becomes

200805001301070903002315180419000118050019172105011309190800151919090\
618010705

Using the decoding scheme 01=A, 02=B, ..., 26=Z, and 00 a space between
words, the decoded message reads

THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE



To find the factorization of RSA-129, we used the double large prime
variation of the multiple polynomial quadratic sieve factoring method.
The sieving step took approximately 5000 mips years, and was carried
out in 8 months by about 600 volunteers from more than 20 countries,
on all continents except Antarctica. Combining the partial relations
produced a sparse matrix of 569466 rows and 524338 columns. This matrix
was reduced to a dense matrix of 188614 rows and 188160 columns using
structured Gaussian elimination. Ordinary Gaussian elimination on this
matrix, consisting of 35489610240 bits (4.13 gigabyte), took 45 hours
on a 16K MasPar MP-1 massively parallel computer. The first three
dependencies all turned out to be `unlucky' and produced the trivial
factor RSA-129. The fourth dependency produced the above factorization.

We would like to thank everyone who contributed their time and effort
to this project. Without your help this would not have been possible.

Derek Atkins
Michael Graff
Arjen Lenstra
Paul Leyland
--
         Derek Atkins, SB '93 MIT EE, G MIT Media Laboratory
       Member, MIT Student Information Processing Board (SIPB)
    Home page: http://www.mit.edu:8001/people/warlord/home_page.html
       [email protected]    PP-ASEL     N1NWH    PGP key available