2
$\begingroup$

I learned the Public Key Recovery algorithm for ECDSA, and wonder if we can use it in DSA. The answer seems to be no, but details are welcome.

$\endgroup$

2 Answers 2

2
$\begingroup$

I'm pretty confident that we can't practically recover public key $y$ from one DSA signature $(r,s)$, the corresponding message $M$, and common public group parameters $(p,q,g)$, as we can (with probability about $0.5$) for an ECDSA signature and common curve parameters.

Entropy argument: in a DSA signature $1\le r<q$ and $1\le s<q$, thus $(r,s)$ can carry at most $2\log_2(q-1)$ bit of entropy; further about half of that is arbitrary. Thus a DSA signature $(r,s)$ can contribute at most about $\log_2q$ bit of information towards the recovery of a DSA public key $y$. But such $y$ is $\lceil\log_2p\rceil$-bit, which for typical choice of $(p,q)$ is much larger than $\log_2q$. And we don't know how to practically significantly compress a DSA public key $y$ in a way that does not reveal the private key $x$. Towards such compression, the best practical methods we have essentially omit some bits of $y$, and find them by trial and error using the property $y^q\bmod p=1$.

Alternate entropy argument: in ECDSA with common curve parameters, the $r$ component of the signature is $r=x_R\bmod n$ which reveals a lot of the random point $R$ of the elliptic curve group (within less than $1.001$ bit for all sepcp curves). But in DSA, $r=(g^k\bmod p)\bmod q$ reveals only a small fraction of $g^k\bmod p$, and we know no practical way to get the whole of it.

These entropy arguments extend to when we know much less than $(\log p)/(\log q)$ signatures, e.g. 10 signatures for 3072-bit $p$ and 256-bit $q$. I don't know for more signatures.


Rebuttal of another answer, in that it purports to construct one of many $y$ that could pass as the public key for the given signature $(r,s)$ and message $M$. Problems:

  • Indeed, the verification equation is $g^{s^{-1}H(M)\bmod q}\,y^{s^{-1}r\bmod q}\bmod p\bmod q=r$. Or equivalently: there exists an integer $i$ such that $g^{s^{-1}H(M)\bmod q}\,y^{s^{-1}r\bmod q}\bmod p=r+i\,q$. But problem is, we don't know $y$, thus can't compute the left hand side, and can't find $i$ by division, as stated in the answer.
  • If instead we choose an arbitrary integer $i$ in $[0,\lfloor(p-r-1)/q\rfloor]$, and compute $y=\left(\frac{r+i\,q}{g^{s^{-1}H(m)\bmod q}}\right)^{r^{-1}s\bmod q}\bmod p$ which seems to be what the answer suggests, the verification equation is not satisfied (with overwhelming probability for $p\gg q$). Problem is there is no insurance $(r+i\,q)^q\bmod p=1$.

I have not found how to salvage the idea to compute an $y$ that passes the verification equation even if we restrict to $\gcd(r,p-1)=1$ (which is common enough). Further, we'd need that $y^q\bmod p=1$, because a competent verifier would check that when receiving the public key $y$ (either directly, or by checking a certificate issued by a competent certification authority, which would verify that condition).

Thus "anyone can use the signature† to forge public keys which will verify it" stands unproven. It's however known that anyone can use that and the public key $y$ to forge a public/private key pair $(y',x')$ for related parameters $(p,q,g')$ that matches signature and message, see Thomas Pornin & Julien P. Stern's Digital Signatures Do Not Guarantee Exclusive Ownership, in proceedings of ACNS 2005.

† implicitly: as well as $(p,q,g)$, and $M$ or $H(M)$

$\endgroup$
0
$\begingroup$

In a DSA group $(g, p, q)$, a DSA signature on a message $m$ under public key $y$ is roughly a pair of integers $(r, s)$ such that $$r = (g^{s^{-1} H(m)} y^{s^{-1} r} \bmod p) \bmod q,$$ or in other words, there exists an integer $i$ such that $$r + i q \equiv g^{s^{-1} H(m)} y^{s^{-1} r} \pmod p.$$ Once you've computed $i$ with your favorite division algorithm, just solve for $y$ modulo $p$: $$y \equiv \biggl(\frac{r + i q}{g^{s^{-1} H(m)}}\biggr)^{r^{-1} s} \pmod p.$$

This arithmetic may not produce the original $y$—there will be $O(p/q)$ possibilities for what the original $y$ could have been, around 2⁸⁶⁴ in traditional 1024-bit DSA with SHA-1—but by construction the signature equation will be satisfied.

The public key recovery trick with ECDSA also doesn't tell you what the original public key was either, but of course there are only 2 possibilities in ECDSA and not around 2⁸⁶⁴ possibilities like in 1024-bit DSA with SHA-1 (and worse for modern parameter sizes), so it takes fewer additional bits to identify the original in ECDSA.

Note that this means a known message/signature pair cannot be used to authenticate a public key, because anyone can use the signature to forge public keys which will verify it. So I hope you're using a public key confirmation hash or something!

$\endgroup$
1
  • 2
    $\begingroup$ This does not work. We can't compute the correct $i$ by division because we don't know $y$ in the first place. And the derivation of $y$ from arbitrary $i$ is incorrect. See detailed rebuttal in the second part of my answer. $\endgroup$
    – fgrieu
    Commented Jul 17, 2023 at 11:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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