Is DSA still secure without the factor "r"?

B.H.

7/23/23, 4:35 AM

If I understand correctly, the way DSA in a group $G$ with a hash function $H$ works is: Peggy (signer) has a private/public key pair $x$, $g^x$. For signing, she produces a random session key $k$, $g^k$ then computes the signature: $s=\frac{H(m)+xF(g^k)}{k}$ where F is some "reasonably uniform function" $F: G \rightarrow \frac{\mathbb{Z}}{|G|\mathbb{Z}}$. To verify the signature, Victor checks that $g^{\frac{H(m)}{s}}(g^x)^{\frac{F(g^k)}{s}} = g^k$.

My question is about the factor $F(g^k)$ (named $r$ in many expositions, e.g. in Wikipedia). How necessary is it security-wise? More concretely: suppose Peggy were to compute a signature $s=\frac{H(m)+x}{k}$ (and, accordingly, Victor would compute: $g^{\frac{H(m)}{s}}(g^x)^{\frac{1}{s}} = g^k$). Does this make the scheme vulnerable to a specific, known attack?

Duplicate of this question (asked February 2019, no answers). See also this past question, where the answer asserts that a collision in $r$ doesn't allow a cryptographic break.

188

0 + 0

cryptanalysis

dsa

Daniel S

7/23/23, 7:09 AM

May I ask how the question arises and also what form your signature would take (in DSA a signature is a pair $(r,s)$, but in your scheme $r$ no longer exists).

B.H.

7/23/23, 7:14 AM

I suppose the signature would be $(g^k, s)$. The question is purely theoretical, I'm just trying to understand why the algorithm is built the way it is.

Score:3

Crypto

Daniel S

7/23/23, 7:05 AM

This signature scheme is trivial to forge.

Notice that there is $s$ is only used on the right hand side of the verification equation and $g^k$ is only used on the left hand side. Fred the forger is at liberty to choose any $s$; compute the left hand side say $\ell=g^{\frac{h(m)}s}(g^x)^{\frac1s}$ and then publish the signature $(\ell,s)$ which will be accepted by Victor.

0 + 0

B.H.

7/23/23, 7:33 AM

Figures. The attack if $k$ is known/repeated involves extracting the secret key $x$, so it seemed obvious to look for the same sort of attack...