1
$\begingroup$

El Gamal encryption involves picking $(p,g,b)$ which is our public key. We compute $b=a^x$ $mod$ $p$. Here, $x$ is the private key which we don't know.

What are some efficient and strong algorithms today used to finding this $x$?

I am currently dealing with numbers such as $b=42-60$ digits long and $p=30-50$. So $b$ is anywhere between 42 and 60 digits.

Does anyone know of any program and some attacks to finding this $x$ using our given information?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ The separate limits you give on $b$ and $p$ don't make a great deal of sense. For one, $b < p$, and so if you never have a $p$ more than 50 digits, you'll also never have a $b$ more than 50 digits either. In addition, $b$ acts as a random value between 2 and $p-2$; hence if $p$ is 50 digits, then at least 90% of the time, $b$ will be 49 or 50 digits. $\endgroup$
    – poncho
    Commented Dec 17, 2013 at 5:07
  • $\begingroup$ No, your right about that. I was simply saying how the digits varied for $b,p$. I can see how one would misinterpret that. $\endgroup$
    – user3092043
    Commented Dec 17, 2013 at 5:39

2 Answers 2

Reset to default
2
$\begingroup$

Being new to cryptography is one thing, but you are supposed to do some research on your own before asking questions here (see How to Ask), and D.W. gave you the right directions already.

But since you wanted names and links:

  • The first stop should be discrete logarithm on Wikipedia, and it lists several algorithms on this topic.
  • As a beginner, start with Babystep-Giantstep and Pohlig-Hellman.
  • Your next stop should be Index Calculus.
  • Additionally, there are algorithms based on the NFS, e.g. described in Gordon's paper Discrete Logarithms in GF(p) Using the Number Field Sieve. Current records modulo primes employ this technique.
Improve this answer
$\endgroup$
5
  • $\begingroup$ Your right, that was a stupid thing to comment about. I just got super frustrated because I was not able to find any efficient algorithms on my own. I did try implementing Pohlig-Hellman-Silver on Maple and it wasn't cracking. I also tried Babystep-Giantstep and that was not working either. Just though I was missing something. But I am not asking a question without trying it on my own first. $\endgroup$
    – user3092043
    Commented Dec 17, 2013 at 14:10
  • $\begingroup$ Well, that's no wonder, tbh. Babystep-Giantstep takes $O(\sqrt{n})$ time and space. Your values are just too large to do this on a normal computer: Even if your $p$ just has 30 (decimal) digits, this is approximately $2^{100}$. I don't think you have $2^{50} \cdot (50+150)$ bit of memory (around 21 petabyte), do you? Memory required: for each value up to $\sqrt{n}$, save the value and the according group element. $\endgroup$
    – tylo
    Commented Dec 17, 2013 at 14:40
  • $\begingroup$ Concerning Pohlig-Hellman, this only works on certain groups (when $p-1$ is smooth and you know its factorization). But all of this is listed in those Wikipedia articles, and checking if your implementation works correctly should be done with small test values. $\endgroup$
    – tylo
    Commented Dec 17, 2013 at 14:51
  • $\begingroup$ I have. They all work with smaller cases. But it is the big ones that is my problem. And I am working with a computer that is not super and does not even come close to having 21 PB of memory, although that does sound good right now. I want to try implementing the Index Calculus algorithm. Do you by any change know any Maple code for that because this is the one I am having hard time coding? $\endgroup$
    – user3092043
    Commented Dec 17, 2013 at 14:58
  • 1
    $\begingroup$ Sorry, but I never worked with Maple at all. And I am not sure that it's even possible to get the required performance in Maple for these kind of numbers. Besides, reference requests are usually off-topic. $\endgroup$
    – tylo
    Commented Dec 17, 2013 at 16:20
0
$\begingroup$

Yes. Use any algorithm for solving the discrete log problem. This is well-studied; do a search on "discrete log" problem and you will find lots of information, both on this site and on Wikipedia (eg this list).

Improve this answer
$\endgroup$
0

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.