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 To: cryptography@wasabisystems.com Subject: New Discrete Log Record due to Joux and Lercier

...

From the NMBRTHRY@LISTSERV.NODAK.EDU mailing list:

Date: Tue, 17 Apr 2001 22:52:56 -0400 From: Reynald LERCIER 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@ens.fr), Reynald LERCIER (CELAR, Rennes, France, lercier@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@wasabisystems.com