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

• @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
• @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