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-49$ digits long and $p=43-50$. So $b$ is anywhere between 42 and 49 digits. Does anyone know of any program and some attacks to finding this $x$ using our given information? I am looking for a program in Maple but I will take the algorithm if anyone knows of any.
[Math] Finding the private key: Attack against El Gamal
cryptographydiscrete mathematicsnumber theory
Best Answer
As you are working with numbers of around 160 bits, the index calculus method is not going to be quick enough, I think. So you will need the number field sieve method, I think. A link to an implementation of that method is here, with a thesis explaining the different methods involved. You'll need the dlog-nfs code.