2
$\begingroup$

For ECDSA, a given signature and its message can be used to recover the public key used to sign it (produce 2 public keys). By making comparison of these recovered public keys against the known public key, one will be able to verify the signature.

Does this method differ from the conventional signature verification? If it does differ, is there any performance difference between these two methods?

$\endgroup$
  • $\begingroup$ Sorry, misunderstood your question and deleted my answer, edited your question instead. Please check correctness of edit. Characters are cheap, please spell out "pubkeys" and such; readability is important on this Q/A site. Couldn't think of shorter title, sorry. $\endgroup$ – Maarten Bodewes Mar 22 '18 at 12:11
4
$\begingroup$

Recovering the two potential public keys and comparing them to the known public key is related to, but distinct from the normal ECDSA signature verification algorithm, and is somewhat more costly.

The notation I'll use:

  • $r, s$ are the values from the signature

  • $h$ is the hash of the message being verified (truncated, if the length of the hash is longer than the group size)

  • $P$ is the public key

  • $G$ is the group generator

  • $|Q|_x$ is the x-coordinate of the point $Q$

  • $\{R, R'\}$ are the two curve points with x-coordinate $r$

Then, the standard verification algorithm is:

$$r \ \overset{?}{=}\ |(hs^{-1}G + rs^{-1}P)|_x$$

To evaluate this requires two point multiplications and one point addition, which with Shamir's trick, can be done in not much more time than one point multiplication.

In contrast, the 'recover the private key, and compare' logic would be:

$$P \ \overset{?}{=} r^{-1}s\{R, R'\} - r^{-1}hG$$

Where you accept the signature if either $R$ or $R'$ satisfies the equation.

This may require three point multiplications (or two applications of Shamir's trick); rather more than the standard logic; even if you get lucky and pick the correct $R, R'$ initially, you're no better off. You could rearrange this to make this more efficient (as you have the potential value $P$ in hand); however if you do, you'll find that you'll arrive back at the standard ECDSA verification logic.

$\endgroup$
  • $\begingroup$ Some nitpcking: if the curve order is slightly greater than the field size, then there could be four points matching a given value $r$. $\endgroup$ – Thomas Pornin Mar 22 '18 at 13:33
  • $\begingroup$ One advantage of using key recovery is that you can replace the public key with a hash of the public key, which may be shorter. I believe this is used in Bitcoin-related settings, where public keys are "addresses" (in their terminology) and they want to keep them as short as possible. $\endgroup$ – Thomas Pornin Mar 22 '18 at 13:34
  • $\begingroup$ @ThomasPornin: yes, you are correct; depending on the curve, there could be four points, however the probability of that happening is negligible (which can be seen as a good thing, as something you can ignore, or as a bad thing, as a corner case that's difficult to test...) $\endgroup$ – poncho Mar 22 '18 at 13:39
  • $\begingroup$ Mmh, I got it reversed: you can have four points when the curve order is slightly lower than the field size. This is the case of, for instance, secp256k1 (the "Bitcoin curve") and secp256r1 (aka NIST curve P-256). $\endgroup$ – Thomas Pornin Mar 22 '18 at 16:15

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.