Editing Discrete logarithm (section)

== Cryptography ==
There exist groups for which computing discrete logarithms is apparently difficult.  In some cases (e.g. large prime order subgroups of  groups <math>\mathbf{Z}_p^\times</math>) there is not only no efficient algorithm known for the worst case, but the [[average-case complexity]] can be shown to be about as hard as the worst case using [[random self-reducibility]].<ref>{{Cite journal |author-last1=Blake |author-first1=Ian F. |author-last2=Garefalakis |author-first2=Theo |date=2004-04-01 |title=On the complexity of the discrete logarithm and Diffie–Hellman problems |journal=Journal of Complexity |series=Festschrift for Harald Niederreiter, Special Issue on Coding and Cryptography |language=en |volume=20 |issue=2 |pages=148–170 |doi=10.1016/j.jco.2004.01.002 |issn=0885-064X |doi-access=free}}</ref>

At the same time, the inverse problem of discrete exponentiation is not difficult (it can be computed efficiently using [[exponentiation by squaring]], for example).  This asymmetry is analogous to the one between integer factorization and integer multiplication. Both asymmetries (and other possibly [[one-way function]]s) have been exploited in the construction of cryptographic systems.

Popular choices for the group <math>G</math> in discrete logarithm cryptography (DLC) are the cyclic groups <math>\mathbf{Z}_p^\times</math> (e.g. [[ElGamal encryption]], [[Diffie–Hellman key exchange]], and the [[Digital Signature Algorithm]]) and cyclic subgroups of [[elliptic curve]]s over [[finite field]]s (''see'' [[Elliptic curve cryptography]]).

While there is no publicly known algorithm for solving the discrete logarithm problem in general, the first three steps of the [[General number field sieve|number field sieve]] algorithm only depend on the group <math>G</math>, not on the specific elements of <math>G</math> whose finite <math>\log</math> is desired. By [[precomputing]] these three steps for a specific group, one need only carry out the last step, which is much less computationally expensive than the first three, to obtain a specific logarithm in that group.<ref name=imperfectfs/>

It turns out that much [[internet]] traffic uses one of a handful of groups that are of order 1024 bits or less, e.g. cyclic groups with order of the Oakley primes specified in <nowiki>RFC 2409</nowiki>.<ref>{{Cite journal |author-last1=Harkins |author-first1=D. |author-last2=Carrel |author-first2=D. |date=November 1998 |title=The Internet Key Exchange (IKE) |url=https://www.rfc-editor.org/rfc/rfc2409 |journal=Network Working Group |language=en |doi=10.17487/RFC2409 |issn=2070-1721}}</ref> The [[Logjam (computer security)|Logjam]] attack used this vulnerability to compromise a variety of internet services that allowed the use of groups whose order was a 512-bit prime number, so called [[export of cryptography|export grade]].<ref name=imperfectfs/>

The authors of the Logjam attack estimate that the much more difficult precomputation needed to solve the discrete log problem for a 1024-bit prime would be within the budget of a large national [[intelligence agency]] such as the U.S. [[National Security Agency]] (NSA). The Logjam authors speculate that precomputation against widely reused 1024 DH primes is behind claims in [[Global surveillance disclosures (2013–present)|leaked NSA documents]] that NSA is able to break much of current cryptography.<ref name=imperfectfs>{{cite web |author-last1=Adrian |author-first1=David |author-last2=Bhargavan |author-first2=Karthikeyan |author-last3=Durumeric |author-first3=Zakir |author-last4=Gaudry |author-first4=Pierrick |author-last5=Green |author-first5=Matthew |author-last6=Halderman |author-first6=J. Alex |author-last7=Heninger |author-first7=Nadia |author-link7=Nadia Heninger |author-last8=Springall |author-first8=Drew |author-last9=Thomé |author-first9=Emmanuel |author-last10=Valenta |author-first10=Luke |author-last11=VanderSloot |author-first11=Benjamin |author-last12=Wustrow |author-first12=Eric |author-last13=Zanella-Béguelin |author-first13=Santiago |author-last14=Zimmermann |author-first14=Paul |title=Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice |url=https://weakdh.org/imperfect-forward-secrecy.pdf |date=October 2015}}</ref>