As part of a security CTF competition, the following variation of the ElGamal signature scheme had to be broken:
Let $q$ be prime and $p = 2q + 1$ also prime. In practice these two primes were hardcoded. The source code of the signature and verficiation algorithm is available as a Gist. The order of the multiplicative subgroup generated by $g = 2$ in $F_p$ has order $q$.
A signature for a message hash $m$ and a private key $x$ is produced as follows:
- Select an integer $k$ "randomly" in the range $[0, q)$
- Compute $r = g^k \ \text{mod}\ p$
- Emit the signature $(s = k^{-1} (m + xr) \ \text{mod}\ q, r \ \text{mod}\ q)$
The difference between this and classic ElGamal is that $m + xr$ is used instead of $m - xr$. The verification is thus also slightly more complicated.
Now we are given the signatures $(s_1, r_1)$ and $(s_2, r_2)$ for the two messages $m_1 =$ sha256("foo") and $m_2 =$ sha256("bar"). $k_1$ is indeed chosen randomly, however we have $k_2 = (a\cdot k_1 + b) \ \text{mod}\ 2^{1024}$ for $a = 713030730552717, b = 123456789$.
The task is to recover the private key $x$ from this information. I know that randomness reuse is a dealbreaker for ElGamal, however I haven't been able to use a similar approach to break the "related randomness" used here. It seems especially tricky that the linear relation between $k_1$ and $k_2$ is only modulo $2^{1024}$, not modulo $q$.
EDIT: OK I think I figured out one step towards the solution: We have (modulo q):
(1) $k \cdot s_1 = m_1 + x\cdot r_1$
(2) $((ak + b) \ \text{mod} \ 2^{1024}) s_2 = m_2 + x\cdot r_2$
Multiply the first equation with $l = r_2 / r_1 \ \text{mod} \ q$:
(1') $lk \cdot s_1 = l\cdot m_1 + x\cdot r_2$
With high probability, we have $(ak + b) \ \text{mod} \ 2^{1024} = ak \ \text{mod} \ 2^{1024} + b$.
Subtracting (2) - (1') we then get:
$((ak \ \text{mod}\ 2^{1024}) s_2 - lk \cdot s_1) = m_2 - m_1 \cdot l - b \cdot s_2$
If the reduction modulo $2^{1024}$ wasn't there, it would be trivial from here to recover $k$ because it is the only unknown value in the equation. With it however, I don't know how to proceed.
Ok, so here is one possible solution, based on this writeup from @nneonneo: We can reformulate the final equation from the question to
$$(ak + b - tN) s_2 - lk \cdot s_1 = m_2 - m_1 \cdot l$$
and thus
$$k = \frac{m_2 - m_1 \cdot l + (tN - b) \cdot s_2}{a \cdot s_2 - l \cdot s_1}$$
Where $N = 2^{1024}$ and $0 \le t \le (ak + b) / N \le a + 1$.
We also know that
$$r_2 \equiv 2^{ak + b - tN} \equiv r_1^a \cdot 2^b\cdot (2^N)^t\pmod{p}$$
and thus
$$(2^N)^t \equiv 2^{ak + b - tN} \equiv r_1^a \cdot 2^b\cdot r_2^{-1} \pmod{p}$$
We are only given $r_1$ and $r_2$ reduced modulo $p$ and then $q$, but we can easily get the values modulo $p$ by just trying all possible options (there are only four). Now since $t \le a + 1$, we can solve the discrete logarithm problem in $\mathcal{O}(\sqrt{a})$ using the baby-step giant-step algorithm and plug $t$ in the first equation to compute $k$. From there it is easy to reconstruct $x$ as well.