ElGamal message signatures retrieving the secret value x

Question

If the GCD(r, p-1) is small and the value k is used to sign a message using ElGamal is also small. Then the secret value of x can be determined.

Why is this true? How would one retrieve x?

http://en.wikipedia.org/wiki/ElGamal_signature_scheme

Answer 1

$\newcommand\gcd{\operatorname{gcd}}$Let's have a look at the signature equation:

$$ s = (H(m) - x·r)·k^{-1} \mod (p-1), $$ $$ s·k = H(m) - x·r \mod (p-1), $$ and thus $$ H(m) - s·k = x · r \mod (p-1).$$

$d = \gcd(r, p-1)$ means we find (efficiently, given $r$ and $p-1$, using the extended euclidean algorithm) a $z$ such that $z·r = d \mod (p-1)$ ... this can be regarded as an "almost-inverse" for $r$ if $d$ is small.

If we multiply the equation above by $z$, we get $$ z·(H(m) - s·k) = x·d \mod (p-1)$$

$s$ and $r$ are the signature, $m$ and $y = g^x$ are also known to the attacker, $d$ is a known small divisor of the modulus, and $k$ is also "small", which means that we can brute-force over all possible values of $k$ and for each one see if there is a solution for $x$.

The moral of the story: Use a random $k$, which will most likely not be small.