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 &lt; u&lt; 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.