Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
