Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:26
Vin McLellan (vin@shore.net)
Thu, 4 Feb 1999 12:06:35 -0500
X-Authentication-Warning: goya.WPI.EDU: christof owned process doing -bs
Date: Thu, 4 Feb 1999 11:09:47 -0500 (EST)
From: Christof Paar <christof@ece.wpi.edu>
To: "WPI.Crypto.Seminar":;
Subject: RSA140 broken
MIME-Version: 1.0
The next RSA challenge, RSA140, has just been factored. RSA140 is a 140
decimal digit number (or about 465 bit). Details below.
Christof
>>> WORKSHOP ON CRYPTOGRAPHIC HARDWARE AND EMBEDDED SYSTEMS (CHES) <<<
>>> WPI, August 12 & 13, 1999 <<<
>>> check http://ece.wpi.edu/Research/crypt/ches <<<
***********************************************************************
Christof Paar, Assistant Professor
Cryptography and Information Security (CRIS) Group
ECE Dept., WPI, 100 Institute Rd., Worcester, MA 01609, USA
fon: (508) 831 5061 email: christof@ece.wpi.edu
fax: (508) 831 5491 www: http://ee.wpi.edu/People/faculty/cxp.html
***********************************************************************
---------------------------------------------------------------------
Subject: Factorization of RSA-140 with the Number Field Sieve
From: herman@cwi.nl (Herman J.J. te Riele)
Date: 02/04/1999 04:52 AM Eastern Standard Time
Message-id:
On February 2, 1999, we found that
RSA-140 =
2129024631825875754749788201627151749780670396327721627823338321538194\
9984056495911366573853021918316783107387995317230889569230873441936471
can be written as the product of two 70-digit primes:
3398717423028438554530123627613875835633986495969597423490929302771479
*
6264200187401285096151654948264442219302037178623509019111660653946049
Primality of the factors was proved with the help of two different primality
proving codes. An Appendix gives the prime decompositions of p +- 1.
The number RSA-140 is taken from the RSA Challenge list
(http://www.rsa.com/rsalabs/html/factoring.html).
This factorization was found using the Number Field Sieve (NFS) factoring
algorithm, and beats the 130-digit record that was set on April 10, 1996,
also with the help of NFS [Cetal].
The amount of computer time spent on this new 140-digit NFS-record is
prudently estimated to be equivalent to 2000 mips years.
For the old 130-digit NFS-record, this effort is estimated to be
1000 mips years.
For both numbers, lower "could-have-done-it-in" estimates,
based on a better use of the lattice siever, are:
500 mips years for RSA-130 and 1500 mips years for RSA-140.
For information about NFS, see [LL]. For additional information,
implementations and previous large NFS factorizations, see [DL, E1, E2,
GLM].
We used the two polynomials
F_1(x,y) = 43 96820 82840 x^5
+ 39031 56785 38960 y *x^4
- 7387 32529 38929 94572 y^2*x^3
- 19 02715 324374 29887 14824 y^3*x^2
- 6 34410 25694 46461 79139 30613 y^4*x
+ 31855 39170 71474 35039 22235 07494 y^5
F_2(x,y) = x - 3 44356 57809 24253 69517 79007 y .
They were selected with the help of a new polynomial search method
developed by Peter Montgomery and Brian Murphy (The Australian
National University, Canberra).
The polynomial F_1(x,y) was chosen to have a good combination of
two properties; being unusually small over its sieving region and
having unusually many roots modulo small primes (and prime powers).
The effect of the second property alone gives F_1(x,y) a smoothness
yield comparable to that of a polynomial chosen at random for an
integer of 121 decimal digits.
The selection took 2000 CPU hours on four 250 MHz SGI Origin 2000 processors
at CWI. Calendar time for the polynomial selection was four weeks.
Sieving was done on about 125 SGI and Sun workstations running at 175 MHz
on average, and on about 60 PCs running at 300 MHz on average.
The total amount of CPU-time spent on sieving was 8.9 CPU years.
For the purpose of comparison, two sieving methods were used:
lattice sieving and line sieving.
Lattice sieving was introduced by Pollard [P] and the code used is based
on the implementation described in [GLM, Cetal].
For the lattice sieving, a rational factor base of 250 000 elements
(the primes <= 3 497 867) and an algebraic factor base of 800 000 elements
(ideals of norm <= 12 174 433) were chosen.
For the line sieving, different factor base bounds were chosen, namely:
a rational factor base consisting of the primes < 8 000 000 and an
algebraic factor base with the primes < 16 777 215 = 2^24 - 1.
For both sieves the large prime bounds were: 500 000 000 for the rational
primes and 1 000 000 000 for the algebraic primes.
A total of 66 933 395 relations were generated, 55% of them with lattice
sieving (L), 45% with line sieving (C). Among them, there were 10 327 897
duplicates, partially because of the simultaneous use of the two sievers.
Sieving was done at five different locations with the following
contributions:
36.8 % Peter L. Montgomery, Stefania Cavallar, Herman J.J. te Riele,
Walter M. Lioen (C,L at CWI, Amsterdam, The Netherlands)
28.8 % Paul C Leyland (L at Microsoft Research Ltd, Cambridge, UK)
26.6 % Bruce Dodson (C,L at Lehigh University, Bethlehem, PA, USA)
5.4 % Paul Zimmermann (L at Inria Lorraine and Loria, Nancy, France)
2.5 % Arjen K. Lenstra (L at Citibank, Parsippany, NJ, USA, and
at the University of Sydney, Australia)
Sieving started the day before Christmas 1998 and was completed one month
later. The relations were collected at CWI and required 3.7 Gbytes of
memory.
The filtering of the data and the building of the matrix were carried out
at CWI and took one calendar week.
The resulting matrix had 4 671 181 rows and 4 704 451 columns,
and weight 151 141 999 (32.36 nonzeros per row). With the help of
Peter Montgomery's Cray implementation of the blocked Lanczos algorithm
(cf. [M95]) it took almost 100 CPU hours and 810 Mbytes of central memory
on the Cray C916 at the SARA Amsterdam Academic Computer Center to find 64
dependencies among the rows of this matrix.
Calendar time for this job was five days.
During February 1-2, 1999, four different square root (cf. [M93]) jobs were
started in parallel on four different 250 MHz processors of CWI's SGI Origin
2000, each handling one dependency. After 14.2 CPU hours, one of the four
jobs
stopped, giving the two prime factors of RSA-140. Two others also expired
with
the two prime factors after 19 CPU hours (due to different input parameter
choices). Only one of the four jobs expired with the trivial factors.
Herman te Riele, CWI, February 3, 1999
with Stefania Cavallar
Bruce Dodson
Arjen Lenstra
Paul Leyland
Walter Lioen
Peter Montgomery
Brian Murphy
Paul Zimmermann
Acknowledgements are due to the contributors, and to the Dutch National
Computing Facilities Foundation (NCF) for the use of the Cray-C916
supercomputer at SARA.
[Cetal] James Cowie, Bruce Dodson, R.-Marije Elkenbracht-Huizing,
Arjen K. Lenstra, Peter L. Montgomery and Joerg Zayer,
A world wide number field sieve factoring record: on to 512 bits,
pp. 382-394 in: Kwangjo Kim and Tsutomu Matsumoto (editors),
Advances in Cryptology - Asiacrypt '96, Lecture Notes in
Computer Science # 1163, Springer-Verlag, Berlin, 1996.
[DL] B. Dodson, A.K. Lenstra, NFS with four large primes: an
explosive experiment, Proceedings Crypto 95, Lecture Notes
in Comput. Sci. 963, (1995) 372-385.
[E1] R.-M. Elkenbracht-Huizing, Factoring integers with the
Number Field Sieve, Doctor's Thesis, Leiden University,
1997.
[E2] R.-M. Elkenbracht-Huizing, An implementation of the number
field sieve, Exp. Math. 5, (1996) 231-253.
[GLM] R. Golliver, A.K. Lenstra, K.S. McCurley, Lattice sieving
and trial division, Algorithmic number theory symposium,
Proceedings, Lecture Notes in Comput. Sci. 877, (1994) 18-27.
[LL] A.K. Lenstra, H.W. Lenstra, Jr., The development of the
number field sieve, Lecture Notes in Math. 1554, Springer-
Verlag, Berlin, 1993
[M93] Peter L. Montgomery, Square roots of products of algebraic
numbers, in Proceedings of Symposia in Applied Mathematics,
Mathematics of Computation 1943-1993, Vancouver, 1993,
Walter Gautschi, ed.
[M95] Peter L. Montgomery, A block Lanczos algorithm for finding
dependencies over GF(2), Proceedings Eurocrypt 1995,
Lecture Notes in Comput. Sci. 921, (1995) 106-120.
[P] J.M. Pollard, The lattice sieve, pages 43-49 in [LL].
Appendix
--------
3398717423028438554530123627613875835633986495969597423490929302771479
3398717423028438554530123627613875835633986495969597423490929302771478
2 7 7649 435653 396004811
183967535370446691250943879126698812223588425357931
3398717423028438554530123627613875835633986495969597423490929302771480
2 2 2 3 3 5 13 8429851 33996935324034876299
2534017077123864320746970114544624627539
6264200187401285096151654948264442219302037178623509019111660653946049
6264200187401285096151654948264442219302037178623509019111660653946048
2 2 2 2 2 2 61 135613 3159671789
3744661133861411144034292857028083085348933344798791
6264200187401285096151654948264442219302037178623509019111660653946050
2 3 5 5 389 6781 982954918150967
16106360796654291745007358391328807590779968869
-----
Vin McLellan + The Privacy Guild + <vin@shore.net>
53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548
-- <@><@> --
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:26