4
$\begingroup$

Are there any ongoing or current practical attempts to solve instances of the discrete logarithm problem of the order of magnitude used in cryptographic applications, for example with a 256 bit modulus and 160 bit exponent? I am interested in efforts similar to the work of members of the Mersenne Prime forum and the RSA factoring challenge, but for the discrete logarithm problem.

What principles and techniques are involved? Do any of these solutions yet approach a realistic time frame? I am mainly looking for working software implementations of any attempts.

I checked some links given in Wikipeda's Discrete Logarithm records page, in particular GGNFS. Can someone help compiling and testing it?

I also found a similar question: https://crypto.stackexchange.com/questions/100/modern-integer-factorization-software. Does this software also allow what I want?

Here is some test data (all in decimal form):

  • base: 47
  • modulus: 112624315653284427036559548610503669920632123929604336254260115573677366691719
  • result: 107169838909122878937980510796152643759453843830224828060309998762431169006781

You have to find 160 bit exponent.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ This thread on mersenneforum is required reading. The author of a similar article in that thread is apparently "auditing a security protocol". The modulus is a "safe prime" which possibly represents a valuable real-world problem instance. The parameters are the ones posted here. $\endgroup$
    – ByteCoin
    Commented Oct 16, 2011 at 22:31
  • 2
    $\begingroup$ FWIW, these modulus and base appear in the context of a login protocol apparently used (at some point in time) in a commercial on-line game, as discussed here $\endgroup$
    – fgrieu ♦
    Commented Oct 19, 2011 at 6:54

1 Answer 1

Reset to default
8
$\begingroup$

256-bit discrete logarithms on a prime field are definitely not of the order of magnitude used in cryptographic applications. Secure sizes for this problem are in the thousands of bits, very much like integer factorization.

To break that example discrete logarithm, you probably want to use Index Calculus, more specifically the Linear Sieve. Resorting to the Number Field Sieve is probably overkill for such a small prime field, and GGNFS is not prepared to solve discrete logarithms, although much of it could be reused to do so.

Note that 256-bit sizes are OK for problems with less structure, where only generic discrete logarithm algorithms, like Pollard's Rho, work --- such as elliptic curves over a 256-bit prime.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, but i'm more looking for ready software. $\endgroup$
    – asd
    Commented Aug 29, 2011 at 19:38
  • 2
    $\begingroup$ There are very few public index calculus implementations. One of them is Chris Studholme's, which works but just barely. If your problem is small enough to be solved in 60 seconds, MAGMA has a pretty good solver (it includes both the Linear and Gaussian Integer sieve). $\endgroup$
    – Samuel Neves
    Commented Aug 30, 2011 at 5:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.