4 February 1999

    Date: Thu, 4 Feb 1999 12:06:35 -0500
    To: cryptography@c2.com, coderpunks@toad.com
    From: Vin McLellan <vin@shore.net>
    Subject: <fyi> RSA140 factored!
    Cc: jya@pipeline.com

    [Forward]

    Date: Thu, 4 Feb 1999 11:09:47 -0500 (EST)
    From: Christof Paar <christof@ece.wpi.edu>
    To: "WPI.Crypto.Seminar":;
    Subject: RSA140 broken

    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
                             -- <@><@> --