From weber@itwm.uni-kl.de Mon Feb 9 20:13:53 1998 Date: Mon, 9 Feb 1998 09:44:08 -0500 From: Damian Weber To: NMBRTHRY@LISTSERV.NODAK.EDU Subject: discrete log: MCCURLEY'S challenge solved MCCURLEY'S 129-digit discrete log challenge solved ================================================== January 25, 1998 Abstract: We provide the secret Diffie-Hellman-Key which is requested by Kevin McCurley's challenge of 1989. The DH-protocol in question has been carried out in (Z/pZ)^* where p is a 129-digit prime. Our method employed the Number Field Sieve. In order to stimulate research concerning the discrete logarithm problem in finite prime fields, Kevin S. McCurley offered a 129-digit-challenge in his 1989 discrete log survey paper [KSM]. The problem is embedded in a communication of two parties using the Diffie-Hellman key exchange protocol. The setup is as follows a=7 b_A=12740218011997394682426924433432284974938204258693 16216545577352903229146790959986818609788130465951 66455458144280588076766033781 b_B=18016228528745310244478283483679989501596704669534 66973130251217340599537720584759581769106253806921 01651848662362137934026803049 p=(739*7^{149}-736)/3 prime q=(p-1)/(2*739) prime |(Z/pZ)^*|=2*739*q Alice computes (using her secret key x_A): 7^x_A = b_A mod p Bob computes (using his secret key x_B): 7^x_B = b_B mod p Kevin McCurley now asks for the common secret key K=7^(x_A*x_B) mod p. Here it is: K=38127280411190014138078391507929634193998643551018670285056375615 045523966929403922102172514053270928872639426370063532797740808 K has been obtained after computing the secret key x_A of Alice by means of the Number Field Sieve Discrete Log algorithm (NFS-DL). x_A=61858690859651883273593331652037904267987643069521713459146222184 9525998156144877820757492182909777408338791850457946749734 (mod p-1) Description of the solution process: ------------------------------------ In 1995 we carried out the precomputation step with the Number Field Sieve [W1]. Luckily, p is of special form, so the special number field sieve could be applied, by using the polynomials f(x)=739X^5-5152, g(X)=X-m, m=7^30, f(m)=0 mod p. Individual logarithms, however, turned out to be a serious problem, since both alternatives a) computing a relation in Z/pZ, where b is expressed by small primes b) abandoning the attractive polynomial f(X) did not seem feasible [SWD]. Nevertheless, by finding the following relation in Z/pZ, approach a) looked indeed promising, since the biggest prime merely consists of 13 decimal digits. Congruence (1): 7^141266132*b_A = 2^3 * 31 * 603623 * 1571562367 * 7575446399 * 265542836371 * 4145488613977 * 4338202139093 / 353 * 165073039 * 1601141623 * 1715568391 * 13166825869 * 371303006453 * 5041332876473 (mod p). This was achieved by computing 7^z mod p for many z's, expressing that by a quotient s/t mod p with s,t<=sqrt(p), an early abort strategy when factoring s,t with trial division and ECM for factors up to 15 decimal digits. --> Integer package: LiDIA 1.2 with libI [LiDIA] The sieving procedure has been carried out by a new generic sieve implementation [W2] which covers most of the current discrete log and factoring algorithms, in particular including the lattice sieve. Running the lattice sieve was necessary to find the discrete logs of the expression (1). One of the experiments was to sieve only with one large prime on both the rational side and the algebraic side. After having found 1408602 partial relations, a simple partial-combiner produced 75592 full relations, leading to a linear system of a 75592 X 60001 matrix A mod q. --> Integer package: LiDIA 1.2 with libI Solving the linear system has been done by carrying out two steps, both of which are discussed in [D]. a) The matrix A was compactified to a 35704 X 35666 matrix A' thereby reducing the running time of step b) by a factor of 2. b) Computing 22 solutions of A'x=0 with the Lanczos algorithm finally yielded the logarithms of the primes in (1). --> Integer packages: FREELIP, libI (with a couple of modifications) The analysis of our version of the NFS-DL algorithm may be found in [S], an earlier version of it appeared in [G]. The complete, detailed description of all steps is contained in the PhD theses [W3], [D]. Running times (rough estimates, details will be published in a paper a.s.a.p.) ------------------------------------------------------------------------------ 1) Finding congruence (1): approx. 4 weeks on 40 Sparc ELC and 20 Sparc 4, using only idle time cycles. 2) Number Field Sieve: 336 h on 30 UltraSPARC processors 3) Lattice Sieve for each of the 12 primes > 353 of (1) approx 3 days on a Sparc 4. 4) Lanczos 2 months on a Sparc 10 by consuming 90 MB main memory (about 3/4 of the work) 7 days on a Sparc Ultra-2 with 300 MHz (remaining 1/4 of the work) ********************************************************************** Damian Weber, Institut fuer Techno- und Wirtschaftsmathematik, Kaiserslautern, Germany (weber@itwm.uni-kl.de) Thomas F. Denny, debis IT Security Services, Bonn, Germany (t-denny@itsec-debis.de) ********************************************************************** We have, of course, notified the author of the challenge and are happy to have his permission to quote his remarks > From MCCURLEY@almaden.ibm.com Thu Feb 5 07:32:55 1998 > ... > I checked x and sure enough it's the correct value. > ... > The choice of p was also made in a non-random fashion, which is > what contributed to its downfall. > I chose the prime p shortly before the number field > sieve was discovered. It soon became clear that the number field > sieve could be used for discrete logarithms, but I was still not sure > that it presented a threat to this challenge because there was a great > deal of work to be done before the number field sieve could be > demonstrated to be practical. Your work finally demonstrates the > folly of my choice, but also raises the spectre that there may > exist other special purpose algorithms yet to be discovered. This > underscores the need to keep searching for mathematically rigourous > proofs of security for cryptographic systems. > > Once again, congratulations! > > Kevin McCurley ********************************************************************** Acknowledgements ---------------- Ulrich Graef, Sun Microsystems / Benchmark Center Germany for providing the computing power for 2) and 4), part II Raimund Seidel, Reinhard Wilhelm, Computer Science Department Universitaet des Saarlandes, Germany for providing the computing power for 1) and 3) Johannes Buchmann, Technische Universitaet Darmstadt, Germany Oliver Schirokauer, Oberlin College, Ohio, USA Joerg Zayer, IDS, Saarbruecken, Germany for fruitful discussions concerning improvements of the NFS-DL algorithm Thomas Setz, Technische Universitaet Darmstadt/Germany for establishing the contact to the Sun Benchmark Center Germany The LiDIA Group, Technische Universitaet Darmstadt/Germany for maintaining an efficient, reliable C++ integer arithmetic Arjen K. Lenstra, Citibank, USA for providing the FREELIP integer package Bibliography ------------ [KSM] author = "K. S. McCurley", title = "The discrete logarithm problem", booktitle = "Cryptology and Computational Number Theory", series = "Proc. Symp. in Applied Mathematics", organization = "American Mathematical Society", pages = "49--74", number = "42", year = "1990" [SWD] author = "O. Schirokauer and D. Weber and Th. F. Denny", title = "Discrete logarithms: the effectiveness of the index calculus method", booktitle = "Algorithmic Number Theory -- ANTS II", editor = "H. Cohen", series = "Lecture Notes in Computer Science", number = "1122", year = "1996" [W1] author = "D. Weber", title = "Computing discrete logarithms with the number field sieve", booktitle = "Algorithmic Number Theory -- ANTS II", editor = "H. Cohen", series = "Lecture Notes in Computer Science", number = "1122", year = "1996" [W2] author = "D. Weber", title = "A general sieving device", note = "in preparation" [W3] PhD-thesis author = "D. Weber", title = "On the computation of discrete logarithms in finite prime fi elds", school = "Universit{\"a}t des Saarlandes/Germany", year = "1997" [DM] author = "Th. Denny and V. M{\"u}ller", title = "On the reduction of composed relations" " from the number field sieve ", booktitle = "Algebraic Number Theory II", series = "Lecture Notes in Computer Science", number = "1122", year = "1996" [D] PhD-thesis author = "Th. Denny", title = "L{\"o}sen grosser d{\"u}nnbesetzter Gleichungssysteme {\"u}b er endlichen Primk{\"o}rpern", school = "Universit{\"a}t des Saarlandes/Germany", year = "1997" [G] author = "D. Gordon", title = "Discrete logarithms in {GF}($p$) using the number field siev e", journal = "SIAM J. Discrete Math.", volume = "6", pages = "124--138", year = "1993" [S] author = "O. Schirokauer", title = "Discrete logarithms and local units", journal = "Phil. Trans. R. Soc. Lond. A 345", pages = "409--423", year = "1993" [LiDIA] author = "I. Biehl and J. Buchmann and Th. Papanikolaou", title = "LiDIA -- A library for computational number theory", institution = "Universit{\"a}t des Saarlandes/Germany", year = "1995"