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

xrbToTheMoon

1/10/23, 4:36 AM

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?

0 + 0

dsa

Score:2

Crypto

Daniel S

1/10/23, 6:39 AM

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.

0 + 0

xrbToTheMoon

1/10/23, 2:43 PM

ok, that makes me feel better, I'm not crazy! :) Thanks for taking the time to answer!

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

TH: ความสับสนในการกู้คืนคีย์ส่วนตัวในลายเซ็น DSA เมื่อค่า r ซ้ำกัน

RO: Confuzie cu privire la recuperarea cheii private în semnătura DSA atunci când apare valoarea duplicată a lui r

RU: Путаница с восстановлением закрытого ключа в подписи DSA, когда происходит дублирование значения r

VI: Nhầm lẫn trong việc khôi phục khóa riêng trong chữ ký DSA khi giá trị trùng lặp của r xảy ra

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.