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.

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?

share|improve this question
2  
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
add comment

2 Answers

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.
share|improve this answer
    
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. –  user3092043 Dec 17 '13 at 14:10
    
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
    
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? –  user3092043 Dec 17 '13 at 14:58
1  
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. –  tylo Dec 17 '13 at 16:20
add comment

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

share|improve this answer
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.