# Breaking Elgamal private key

I have been given a task to explain if - given a public key and a portion of a private key (over 300bits) with a remain unknown of 80 bits - the private key can be broken with an algorithm faster than with brute force.

I have been checking some stuff like index calculus and baby steps, but I don’t see any apparent difference (there is but not for standard computers).

## 1 Answer

I have been given a task to explain if - given a public key and a portion of a private key (over 300bits) with a remain unknown of 80 bits - the private key can be broken with an algorithm faster than with brute force.

Check out the Baby Step/Giant Step algorithm - and figure out how it could be adjusted to handle your situation (with the known key bits)

• Hello, thanks for your response. I have checked it, and still don’t see how it would help. Basically baby steps is based on the assumption that x = im + j but for a bounded x there is still nearly infinte possibilites for i and j knowing that m is the square root of p. If you have any thought or extra clue it would be highly appreciated – honte Dec 18 '20 at 21:49
• @honte: with the known key bits, we already know $x = ay + b$ (where $b$ are the known key bits, and $a$ depends on where the unknown key bits are, and $0 \le y < 2^{80}$. How can you modify baby step/giant step to search through that? – poncho Dec 18 '20 at 22:28
• Okay I will check, thanks for that. Just for the record, the remaining bits are located at the end so, thet are the 80 LSB bits – honte Dec 18 '20 at 22:33
• @honte: "end == lsbits" assumes that the encoding is bigendian, which is not universal. On the other hand, having the unknown bits being the lsbits makes $a=1$, which makes things conceptually easier (even if it doesn't make any difference in the complexity of the attack) – poncho Dec 19 '20 at 3:44