El Gamal Signature: Attack to recover private key if $k$ is generated as $k_{i+1}=k_{i}+a$ where $a$ is a large unknown constant

Question

$k_0$ is randomly generated and subsequently $k_{i+1} = k_{i}+a$, where $a$ is a large unknown constant

I've tried formulating an attack as such:

Given 3 Messages $M_0$, $M_1$ $M_2$and with $(r_0,s_0)$, $(r_1,s_1)$ and $(r_2,s_2)$ respectively. We can write $r_0$, $r_1$ and $r_2$ as such:

$$r_0 = g^{k_0} {\ }mod{\ } p $$ $$r_i = g^{k_i} {\ }mod{\ } p = g^{k_0}g^{a*i} {\ }mod{\ } p = r_0g^{a*i} {\ }mod{\ } p$$

$s_0$, $s_1$ and $s_2$ can then be rewritten as the following:

$$s_0k_0 = M_0-xr_0{\ } mod{\ } p-1$$ $$s_1(k_0+a) = M_1-xr_0g^{a}{\ }mod{\ } p-1$$ $$s_2(k_0+2a) = M_2-xr_0g^{2a}{\ }mod{\ } p-1$$

and making $xr_0$ the subject we get the following: $$xr_0 = M_0 - s_0k_0$$ $$xr_0 = g^{-a}(M_1 - s_1(k_0+a))$$ $$xr_0 = g^{-2a}(M_2 - s_2(k_0+2a))$$

But I do not think we can solve this using linear equations because we do not know what is $g^{-a}$ and $g^{-2a}$.

Answer 1

Actually, you can recover $g^{-a}$.

You know that $r_i = g^{k_i} \mod p$ and $r_{i+1} = g^{k_i + a} \mod p = r_i \cdot g^a \bmod p$, hence $g^a = r_{i+1} \cdot r_i^{-1} \bmod p$; from there, computing $g^{-a}$ and $g^{-2a}$ is easy.

With that, the linear equations become easy to solve...