The solution of McCurley's discrete log challenge

From MaRDI portal





This paper presents the solution to a challenge made by Kevin McCurley in 1989. McCurley asked for the secret key obtained from the data exchanged by two parties in a Diffie-Hellman key exchange using the finite field of \(p=(739 \cdot 7^{149}-736)/3\) elements. Due to the special nature of the field the authors were able to use a variant of the special number field sieve to solve the challenge. This paper gives a brief summary on the computational task involved. First a discussion on how the original problem of McCurley is reduced to finding logarithms of ``smooth elements in the field of \(p\) elements. Then the choice of field polynomial for the number field sieve is discussed, a degree five polynomial/field was chosen for the rest of the computation. The sieving is then discussed, with some numerical summary data of the effort involved. Finally the linear algebra step is described. The paper gives a large amount of run time data of the overall algorithm. This calculation is particularly impressive and to date is the largest discrete logarithm problem which has been solved. For the entire collection see [Zbl 0895.00067].





Describes a project that uses

Uses Software






This page was built for publication: The solution of McCurley's discrete log challenge

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4249351)