Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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: 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.

share|improve this question
2  
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. –  ByteCoin Oct 16 '11 at 22:31
2  
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 –  fgrieu Oct 19 '11 at 6:54
add comment

1 Answer

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.

share|improve this answer
    
Thanks, but i'm more looking for ready software. –  asd Aug 29 '11 at 19:38
2  
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). –  Samuel Neves Aug 30 '11 at 5:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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