# ElGamal message signatures retrieving the secret value x

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?

-
Is this a homework task, or from where did you get this assertion? –  Paŭlo Ebermann Nov 27 '11 at 13:42
From an old exam question. Studying for finals –  Bobby S Nov 28 '11 at 19:10

$\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.

-