# What would happen in DSA/ECDSA if there were a collision in $r$ but not $k$?

In DSA, the value of $$r$$ is generated as:

$$r = (g^k \bmod p) \bmod q$$

ECDSA is similar, using the $$x$$ coordinate of the generator $$g$$ scalar-multiplied by $$k$$, again taken modulo $$q$$.

It's well-known, particularly by Sony, that $$k$$ must be different for each message signed, or the private key leaks.

Due to the construction, it is possible, but unlikely, to generate two different $$k$$ values that result in the same $$r$$ value. If you happen to generate two signatures of different messages that have the same $$r$$ value but different $$k$$ values, does it break security?

If you happen to generate two signatures of different messages that have the same $$r$$ value but different $$k$$ values, does it break security?

No, it doesn't break security.

Suppose you happened up use two different $$k$$ values ($$k$$ and $$k'$$) that just happened to result in the same $$r$$. Then, when you publish the corresponding $$s$$ values, you would publish:

$$s = k^{-1} (H(m) + xr)$$

$$s' = k'^{-1} (H(m') + xr)$$

with $$s, s', r, H(m), H(m')$$ known.

That leaves $$k, k', x$$ are three unknown variables; for any possible $$x$$ value (which is the private key), there are $$k, k'$$ values that make these equations fit, hence we cannot deduce the value of $$x$$ from these two equations.

In contrast, if we also knew that $$k = k'$$ (that is, if the actual $$k$$ value was reused), then that drops the number of unknown variables to two; in that case, it's just a pair of linear equations in two variables - quite easy to solve.

• If it were two signatures of the same message (in an implementation using random $k$), this reveals the ratio between $k$ and $k'$: $s's^{-1} \equiv k{k'}^{-1} \pmod q$. I don't know how that would be useful, though. – Myria Jun 7 '19 at 20:49
• @Myria: it wouldn't particularly matter; the attacker is actually interested in $x$, and (by the above logic), all $x$ values are still possible. Now, the attacker will also know the value $z$ such that $(g^x \bmod p) \equiv (g^{zx} \bmod p) \pmod q$; there's no feasible way to use that relation to recover $x$; even if the attacker were given the values $g^{x} \bmod p$, $g^{zx} \bmod p$, it would still be infeasible... – poncho Jun 7 '19 at 21:08