1
$\begingroup$

In DSA signature where signing is done via

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

I understand why if two messages singed by the same private key $x$ use the same $k$ value you can recover the private key

But I've read various comments and answers that say if two messages signed by the same private key have the same $r$ value that is all that is needed to recover the private key, and I don't understand how that is possible

Since $$r = (g^k \mod{p}) \mod{q}$$

how does two $r$'s being equal give you the same $k$? Shouldn't there be something like $\lfloor p/ q\rfloor$ different $k$'s that result in the same $r$ since $g$ is a generator for the cyclic group $\mathbb{Z}_p^*$? They won't all have the same inverse modulo $q$ so how do you solve the two equations since there are three unkowns, $k_1^{-1}, k_2^{-1}, x$

What am I missing?

$\endgroup$

1 Answer 1

2
$\begingroup$

First, note that $g$ is not the generator of the full cyclic group $(\mathbb Z/p\mathbb Z)^*$, but of a cyclic subgroup of order $q$. As such then we can only see at most $q$ possible $r$ values and we expect to see any given $r\pmod q$ value roughly Poisson(1) times.This does mean that we do expect roughly $(1-2/e)q$ $r$ values corresponding to more than one $k$.

However, even if we were guaranteed to always choose different $k$ values with each signature, we would not expect to see a repeated $r$ value until $\sqrt q$ signatures had been generated (by the birthday paradox). In reality, this is a very unlikely number of signatures for a cryptographic sized $q$ and so any repeat is much more likely to be attributable to a repeated $k$ value due to an implementation error of some sort. This is not a theorem, but a reliable rule of thumb.

$\endgroup$
1
  • $\begingroup$ ok, that makes me feel better, I'm not crazy! :) Thanks for taking the time to answer! $\endgroup$ Sep 10, 2021 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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