# Confusion over recovery of privatekey in DSA signature when duplicate value of r occurs

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?

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.