2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Myria Jun 7 at 20:49
  • 1
    $\begingroup$ @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... $\endgroup$ – poncho Jun 7 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.