Fwd: ~400 bits - New Discrete Log Record due to Joux and Lercier

Thu Apr 19 00:03:33 PDT 2001

120 digits is about 400 bits, and while the computer is respectably fast,
it's just 4 processors.  (Remember that Alpha MHz != Pentium MHz.)
10 weeks of preprocessing, plus about 12 hours per key afterwards.
So 512-bit Diffie-Hellman is pretty close to toast,
at least if you re-use the modulus, and likewise 512-bit El Gamal.

>Date: Wed, 18 Apr 2001 01:09:38 -0400 (EDT)
>From: dmolnar <dmolnar at hcs.harvard.edu>
>To: cryptography at wasabisystems.com
>Subject: New Discrete Log Record due to Joux and Lercier
>
>
> >From the NMBRTHRY at LISTSERV.NODAK.EDU mailing list:
>
>Date:    Tue, 17 Apr 2001 22:52:56 -0400
>From:    Reynald LERCIER <lercier at mail.club-internet.fr>
>Subject: Discrete logarithms in GF(p)
>
>Tuesday, April 17 2001.
>
>We are very pleased to announce a new record for the general discrete
>logarithm problem. We were able to compute discrete logarithms modulo
>a 120 digits prime. This was done in 10 weeks, on a unique 525MHz
>quadri-processors Digital Alpha Server 8400 computer.
>
>The approach we followed for this computation is close to the approach
>we used for computing discrete logarithms modulo a 110 digits prime
>[JoLe01]. It is mostly based on algorithms described in [JoLe00].
>
>Precisely, let
>
>   p = \lfloor 10^{119} \pi \rfloor+ 207819,
>     = 314159265358979323846264338327950288419716939937510582097494\
>       459230781640628620899862803482534211706798214808651328438483,
>
>   g = 2,
>
>and
>
>   y = \lfloor 10^{119} e \rfloor,
>     = 271828182845904523536028747135266249775724709369995957496696\
>       762772407663035354759457138217852516642742746639193200305992.
>
>Then
>
>   y   = g^262112280685811387636008622038191827370390768520656974243035\
>           380382193478767436018681449804940840373741641452864730765082,
>
>and, similarly,
>
>   y+1 = g^39657965519539238631090956325038481900751981791165229696297\
>           421520645832904710912189562251329527994908449750607046857937.
>
>This result was obtained using a now classical algebraic sieve as
>explained, from a theoretical point of view, by Schirokauer
>[Schi93]. So, it was done in three steps:
>   _ the sieving step,
>   _ the linear algebra,
>   _ the final computation of individual logarithms.
>
>Sieving:
>--------
>
>The sieving step consisted in finding couples (a,b) such that the
>principal ideal (a+bt) is of smooth norm in the so-called ``right''
>number field defined by
>
>                         t^3-9*t^2-9*t+9
>
>and such that (ac+bs) is of smooth norm in the so called ``left''
>number field defined by
>
>                         s^2
>                         -7374389167922711279538633461199308033087*s
>                         -333238556260219119547406855509826713348*c
>
>where
>
>                         c = 1201639291188427271122019272295979872125.
>
>The Galois group of the degree 3 polynomial is of order 3. The
>corresponding number field has 2 fundamental units, 1/12*t^2-t+1/4 and
>-1/12*t^2+1/2*t+5/4, its class group is of order 1 and its index is
>equal to 2^6*3^2.
>
>Nothing is really known about the degree 2 polynomial except, of
>course, that the corresponding number field is a real quadratic field.
>
>The sieving was done efficiently following a now traditional ``sieving
>by vector'' with ``special-q'' technique.  It yields many linear
>equations between ``logarithms of ideals'' of norms smaller than
>15485870 (1000000-th prime) in the left number field and of norms
>smaller than 3497870 (250000-th prime) in the right number field.
>
>After a 40 days computation on a quadri-processors alpha server 8400
>computer, we obtained 2685597 equations with 1242551 unknowns.
>
>At this point, it usually remains to add 5 Schirokauer maps to these
>equations. Here, we added only 2 maps (for the left number field) and
>prefer for the right number field, instead of what was done in
>[JoLe01], to add explicitly fundamental units contribution taking
>advantage that any ideal on the right number field is principal.
>
>This step (maps+units) took one day.
>
>Linear algebra:
>---------------
>
>The linear algebra was further divided in two phases.
>
>We first applied structured Gaussian eliminations to reduce our system
>to 271654 equations in 271552 unknowns with 22690782 non null entries
>[LaOd91, JoLe00]. Time needed for this on only one processor was less
>than 1 day.
>
>Then, the critical phase was the final computation via Lanczos's
>algorithm [GoLo89]. Our parallelized version of this algorithm took 30
>days over 4 processors. At the end, we had ``logarithms for ideals''
>of small norms. As a consequence, we had logarithms for small primes.
>
>For instance,
>   3  = g ^ 28812588093314776509699010256332271205911219293533606948309\
>            244629961378102894412283315317373685769257402738003506902138,
>
>   5  = g ^ 21755718305811583829459340786707488931552080300620288049491\
>            6079418842612898727245046247623746814003335266081854116641401,
>
>   7  = g ^ 30620343436458977106289725314901617172209074240481960209355\
>            5007057950445875245076830599652008193628520847056151254242513,
>
>   11 = g ^ 26369065546060570062275123759054389628546695463387446804852\
>            2904503050215021182824543943461120732653168766053846377967922,
>
>etc ...
>
>Individual Logarithms:
>----------------------
>
>We take advantage of the Galois group of t^3-12*t^2-9*t+12 [JoLe00].
>
>Precisely, we found in less than 6 hours, using our very crude
>implementation, two algebraic integers
>       num = 136919628471533453465*t^2
>           - 109185518772042207040*t
>           - 218010383119442982304
>
>and
>
>       den = 90752177247861263294*t^2
>           + 5976502381138861785*t
>           + 161979899979266169279
>
>such that
>
>                          19^2*y = num/den modulo p
>
>and such that,
>
>         in GP-PARI notation, the principal ideal (num) is equal to
>
>[[53, [7, 2, 0]~, 1, 1, [-18, 19, 12]~] 1] *
>[[431, [-20, 2, 0]~, 1, 1, [168, 20, 12]~] 1] *
>[[2179, [140, 2, 0]~, 1, 1, [-502, -300, 12]~] 1] *
>[[16831, [-3928, 2, 0]~, 1, 1, [-1478, 7836, 12]~] 1] *
>[[156781, [-45467, 2, 0]~, 1, 1, [15351, -65867, 12]~] 1] *
>[[7691507, [-3118090, 2, 0]~, 1, 1,
>  [-1592322, -1455347, 12]~] 1] *
>[[5847120361, [-944554227, 2, 0]~, 1, 1,
>  [-2613536996, 1889108434, 12]~] 1] *
>[[7689099923, [-1979641955, 2, 0]~, 1, 1,
>  [-1763503409, -3729816033, 12]~] 1] *
>[[14023824873312563677, [2910448673841826685, 2, 0]~, 1, 1,
>  [-4872413772263364932, -5820897347683653390, 12]~] 1]
>
>         and the principal ideal (den) is equal to
>
>[[2, [2, 0, 0]~, 1, 3, [1, 0, 0]~] 1] *
>[[3, [1, -1, 1]~, 3, 1, [2, 2, 0]~] 3] *
>[[19, [8, 2, 0]~, 1, 1, [-3, 2, -7]~] 1] *
>[[1873, [-237, 2, 0]~, 1, 1, [889, 454, 12]~] 1] *
>[[110359, [36889, 2, 0]~, 1, 1, [-37268, 36561, 12]~] 1] *
>[[2672473789, [-932319595, 2, 0]~, 1, 1,
>  [1125968488, -807834619, 12]~] 1] *
>[[626844366559, [-255501920253, 2, 0]~, 1, 1,
>  [-211702090482, -115840526073, 12]~] 1] *
>[[685495972547, [-197652881054, 2, 0]~, 1, 1,
>  [-276404069769, -290190210459, 12]~] 1] *
>[[641614040507139551, [33835176915624305, 2, 0]~, 1, 1,
>  [159262188369356649, -67670353831248630, 12]~] 1]
>
>Then, using special-q descents, computing discrete ``logarithms for
>the ideals'' of norms 7691507, 5847120361, 7689099923,
>14023824873312563677 and 25465743776843, 160516256694037129 in the
>right number field was (thanks to one hour computation for each ideal,
>on a unique processor) equivalent to compute discrete ``logarithms for
>  ideals'' of norms larger than those of the factor basis in the
>left number field. Time needed for computing the 31 corresponding
>discrete logarithms was at most one hour for each on a unique
>processor.
>
>So, as a conclusion, time that we need for computing discrete
>logarithms modulo a 120 digit prime on a 525 MHz quadri-processor
>alpha server 8400 computer is approximatively 12 hours for each, once
>the sieving step (42 days) and the linear algebra steps (30 days) is
>performed.
>
>Antoine JOUX    (DCSSI, Issy les Moulineaux, France, Antoine.Joux at ens.fr),
>Reynald LERCIER (CELAR, Rennes, France, lercier at celar.fr).
>
>References:
>===========
>
>[JoLe01] A. Joux and R. Lercier, ``Discrete logarithms in GF(p)'',
>          January 19 2001. Announce on the NMBRTHRY Mailing List.
>          Available at http://www.medicis.polytechnique.fr/~lercier.
>
>[JoLe00] A. Joux and R. Lercier, Improvements to the general Number
>          Field Sieve for discrete logarithms in prime fields, acceped
>          for publication at Math. of Comp., 2000. Preprint
>          available at http://www.medicis.polytechnique.fr/~lercier.
>
>[Schi93] O. Schirokauer, Discrete Logarithms and local units. Phil.
>          Trans. R. Soc Lond. A 345, pages 409-423, 1993.
>
>[LaOd91] B.A. Lamacchia and A.M. Odlyzko, Computation of discrete
>          logarithm in prime fields, Designs, Codes and Cryptography,
>          1991, volume 1, pages 47-62.
>
>[GoLo89] G.H. Golub and C.F. van Loan, Matrix computations, chapter 9,
>          The John Hopkins University Press, 1989, Mathematical
>          Sciences.
>
>------------------------------
>
>End of NMBRTHRY Digest - 16 Apr 2001 to 17 Apr 2001 (#2001-56)
>**************************************************************
>
>
>
>
>---------------------------------------------------------------------
>The Cryptography Mailing List
>Unsubscribe by sending "unsubscribe cryptography" to 
>majordomo at wasabisystems.com