# ECDH Public Key Recovery - Determine if valid key exists from just signature and message

If I have just the (r,s,v) values of the signature and the message hash, what is the most efficient way to determine if a valid public key exists?

I do not need to know the public key, just that the signature and message hash recover to a public key.

Lets say with the notation:

• 𝑟,𝑠 are the values from the signature.
• ℎ is the hash of the message being verified
• 𝑃 is the public key
• 𝐺 is the group generator
• |𝑄|𝑥 is the x-coordinate of the point 𝑄
• {𝑅,𝑅′} are the two curve points with x-coordinate 𝑟

The recovery would be:

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

My question is if there is a fast way of determining whether P exists, without doing the full expensive calculations to determine P.

I believe that you could check whether $$r$$ is a valid nonzero $$x$$ coordinate; that is, whether it is a part of a solution to curve equation (e.g. if your curve is in Weierstrass form with characteristic > 3, you'd check whether $$x^3 + ax + b$$ is a Quadratic Residue).
If it is (and if it is nonzero), then yes, you could perform the operations to recover $$P$$, and it would come up with two valid points, and so that's your answer.
• @SyedJafri: actually, it'd be $x^3+7$, not $x^3+7m$. In any case, you could compute that, or compute the Legendre symbol (which might not be significantly faster, and is certainly more obscure). – poncho Mar 29 at 20:12