# Attacks against El Gamal private key

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?

• 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. – poncho Dec 17 '13 at 5:07
• No, your right about that. I was simply saying how the digits varied for $b,p$. I can see how one would misinterpret that. – user3092043 Dec 17 '13 at 5:39

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.
• 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. – tylo Dec 17 '13 at 14:40
• 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. – tylo Dec 17 '13 at 14:51