# Vulnerability of low value generated key

I have read here that Elgamal is resistant to brute-force attack, because the group to where the key is selected is very large. But since the key generation is random, (i assume)there is a chance that the key generated is lower than the recommended.

example, the recommended keylength is 1024 bits, but the key generated ($$x$$) was really small, way under 512 bits. The adversary can see that the $$g^x$$ is indeed small (smaller than $$g^{2^{1024}}$$ and $$g^{2^{512}}$$), limiting his/her search.

My question is, would a public key encryption be vulnerable to brute-force attack the moment it generated a low value key ? If it is, what are the countermeasures ?

• Elgamal (like much other asymmetric crypto) uses modular arithmetic: g^x mod p. You can't see from the residue whether x is smaller than 2^512 -- that's the meaning of the words 'Discrete Logarithm Problem' -- and even bruteforcing 2^512 would take far far longer than the Earth will exist – dave_thompson_085 Oct 13 '19 at 5:38

The chance that such a key is generated randomly is negligibly low. These 512 bits of security are for both the higher order and lower order bits. The chance of generating such a value is one in $$2^{512}$$ (each time you try, assuming that each value in the 1024 bit number is about equally valid). That means you can try forever before getting such a low value.