2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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). $\endgroup$
    – Daniel S
    Mar 23, 2022 at 7:09
  • $\begingroup$ 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. $\endgroup$
    – B.H.
    Mar 23, 2022 at 7:14

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$
    – B.H.
    Mar 23, 2022 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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