1
$\begingroup$

I'm trying to resolve a discrete logarithm equation:

$$y = g^x \bmod p$$

Every parameter is a 512-bit number. I know the values for $g$, $y$ and $p$ and I need to find the $x$ value. Finally, I know that $g$ is a primitive root of $p$.

I tried to look at some related topics about the discrete logarithm, but I can't figure out how to implement an effective algorithm to solve this problem.

Here you can find the value for each parameter: http://pastebin.com/JKvedKNd

I have started to look at how some algorithm works, but I would like to know depending on these value parameters which could be the more efficient.

It is 80 bits from the actual record I think: https://en.wikipedia.org/wiki/Discrete_logarithm_records. So there is something I am missing due to my lack of skills in the mathematics area.

$\endgroup$
  • $\begingroup$ You somehow confused the numbers: The current record is about 600 bits, but this is using highly optimized algorithms and lots of computing power. In your case, it is much easier, as my answer shows. $\endgroup$ – yyyyyyy Jun 24 '15 at 13:02
  • $\begingroup$ @yyyyyyy, IIRC RSA-768 was already factored and the DLP and FACTORING have similar run-time algorithms, so is there a simple reason why there's a 150-bit gap between the two (this may be worth an own question if it's too complex...)? $\endgroup$ – SEJPM Jun 24 '15 at 19:29
3
$\begingroup$

You're right in that there's little chance you can break the logarithm in a well-chosen 512 bit group (using a home computer, in reasonable time — as pointed out by SEJPM, it is possible investing some time and a good amount of money). However, in your case, the parameters are bad: The order of $(\mathbb Z/p\mathbb Z)^\ast$, that is $p-1$, is a smooth number:

$ factor 7863166752583943287208453249445887802885958578827520225154826621191353388988908983484279021978114049838254701703424499688950361788140197906625796305008451718 7863166752583943287208453249445887802885958578827520225154826621191353388988908983484279021978114049838254701703424499688950361788140197906625796305008451718: 2 131 131 131 131 131 173 181 181 181 181 181 347 347 347 347 347 353 353 353 353 353 379 379 379 379 379 461 461 487 487 491 491 547 547 547 547 547 727 727 751 751 751 769 769 769 887 887 887 887 887 907 907 907 907 907 911 911 911 911

Hence, you can apply the algorithm of Pohlig and Hellman to efficiently find logarithms modulo $p$.

$\endgroup$
  • 1
    $\begingroup$ Even if it wasn't smooth, 512-bit is feasible with enough money and time (one week for an EC2 instance IIRC). See the Logjam attack where the authors actually did this for 512-bit numbers. $\endgroup$ – SEJPM Jun 24 '15 at 13:03
  • $\begingroup$ Thank you. I try to understand a bit more what a smooth group is. A group is smooth if its modulus is smooth that's right ? And finally to find if a group is smooth you calculate its order wich is p - 1 and look if it is smooth? $\endgroup$ – zyrkiem64 Jun 24 '15 at 13:08
  • $\begingroup$ @zyrkiem64 I don't think the term "smooth group" is widely used — one usually applies the word "smooth" only to integers (in this context: a group order), where it means "factors into small primes". The group of integers modulo a prime $p$ has order $p-1$, which is indeed the quantity you have to check for smoothness (not the modulus $p$ as you first wrote, which is prime anyway!). $\endgroup$ – yyyyyyy Jun 24 '15 at 13:19
  • $\begingroup$ @SEJPM Logjam concerns SSL/TLS. I can't see how you compute discrete logs for (every) 512-bit prime number. They say that can break the most commons primes of DH with 512-bits used in SSL/TLS. $\endgroup$ – 111 Jul 20 '15 at 13:39
  • $\begingroup$ @111, Logjam works by attacking small DH primes (~ 512-bit). It exploits the fact that the NFS version for DLP solving can do most of the computation before the actual DHE exchange is observed. These pre-computations need approximiately a week on EC2 for a 512-bit prime and 90s on a consumer PC for calculating the actual logarithm. Meaning you can still apply it even if you're not facing many logarithms. (and they provided some actual run-time numbers) $\endgroup$ – SEJPM Jul 20 '15 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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