Join Log in
Score:1
mti avatar Crypto

Secure modification of DSA?

ke flag
mti

In DSA, we compute the signature $(r,s)$ on $m$ by sampling $k\in\{1,...,q-1\}$ and then computing

$r := g^k \bmod p$

$s := k^{-1}*(m+x*r) \bmod q$

During verification, we compute $v:=g^{m*s^{-1}}*y^{r*s^{-1}}\bmod p$ and then check $r=v \bmod q$.

Question: Would it be fine to leave $k^{-1}$ out from the computation of $s$ (i.e., $s := m+x*r$) and then instead check for $g = v$?

42
0 + 0
dsa
Score:3
poncho avatar Crypto
my flag
poncho

Question: Would it be fine to leave $k^{-1}$ out from the computation of $s$ (i.e., $s := m+x*r$) and then instead check for $g = v$?

In other words, the check would then be $g = g^{ms^{-1}}y^{rs^{-1}}$

Now, that would not be secure; suppose we have a valid signature for $m$, that is, we have the values $(m, r, s)$ such that $g = g^{ms^{-1}}y^{rs^{-1}}$

Then, for an arbitrary message $m'$, we can compute $s' = m'm^{-1}s$ and $r' = rs's^{-1}$; We have $g^{m's'^{-1}}y^{r's'^{-1}} = g^{ms^{-1}} y^{rs^{-1}}$, which is $g$ (because the original signature is valid); that is, $(m', r', s')$ is a forgery.

0 + 0
Daniel S avatar
ru flag
Daniel S
Worse yet, we can recover the private key $x$ because $x=(s-m)/r\pmod q$ and $s$, $m$ and $r$ are all public values.
3
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

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.