# Find private key from knowing random exponents are an arithmetic series

Let $p$ be a large prime and $g$ a primitive root modulo $p$, and $h$ a collision-resistant hash function.

Person A chooses a random integer $1 < u< p$ and $y \equiv g^u \pmod p$ is publicly known.

The ElGamal signature scheme using exponent $k$ for a message $m$ is an ordered pair $(r,s)$ satisfying:

$r \equiv g^k \pmod p$

$h(m) \equiv ur + ks \pmod {p-1}$

Suppose now that person A chooses the exponents for the signature scheme to increase by two for every message she sends. For example if she sends messages $m_1, m_2, m_3$ then she uses exponents $k, k+2, k+4$ respectively.

Suppose that she sends a finite number of messages and such has a finite number of exponents, and that she makes her initial choice of $k$ so that all the following keys are coprime to $p-1$.

If we know that she does this, how might we be able to deduce $u$ if we intercept two consecutive signed messages?

If the messages are $m_1, m_2$ then we have signatures $(r_1,s_2),(r_2,s_2)$ such that:

$h(m_1) \equiv ur_1 + ks_1 \pmod{p-1}$

$h(m_2) \equiv ur_2 + (k+2)s_2 \pmod {p-1}$

$\Rightarrow s_1h(m_2) - s_2h(m_1) \equiv u(s_1r_2 - s_2r_1) + 2s_2s_1 \pmod {p-1}$

This is where I get stuck because I'm not sure what I can do here that is really that helpful. We don't know if $s_1r_2 - s_2r_1$ is coprime to $p-1$ so we can't immediately get $u$, but is it true that it would be coprime? If so how could you prove it? What concerns me the most is that this doesn't really seem to use the fact that the exponents used differ by $2$.

Any help would be greatly appreciated, thank you!

We don't know if $s_1r_2−s_2r_1$ is coprime to $p−1$ so we can't immediately get $u$, but is it true that it would be coprime?

I don't believe coprimality is guarranteed, however we don't need it.

If they're not coprime, it means that there are multiple solutions to the linear equations we have; however:

• The number of solutions are likely to be small; bounded by $\text{gcm}( s_1r_2−s_2r_1, p-1)$

• We can list all those solutions efficiently

So, what we do is go through the list of possible $u, k$ solutions, plug each one into the $r_1 = g^k \pmod p$ relation, and see which one satisfies it; our work is done.

• Thank you for your response. I understand that in principle this would work but by what method are you finding possible $(u,k)$ solutions? I.e. how are you finding these candidates? – user366818 Apr 14 '18 at 18:47
• @user366818: first, let us simplify the linear equation to $au \equiv b \pmod n$, for known $a, b, n$ and which $a, n$ need not be coprime. This is equivalent to finding integer solutions to $au = b + zn$ in $\mathbb{Z}$; if we denote $g = \text{gcd}(a, n)$, then this is the same as $(a/g)u = (b/g) + z(n/g)$ (and if $b/g$ is not an integer, there are no solutions); we can find an initial solution $u_0$ (as $a/g$, $n/g$ are coprime); and the rest of the solutions are $u_0 + i (n/g)$ for $i \in \{0, 1, ..., g-1\}$ – poncho Apr 14 '18 at 19:23