0
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

"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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I am using the secp256k1 curve, so the equation is y² = x³+7 If I calculate x³+7m, is there a fast way of determining it is a valid quadratic residue? Would the fastest way be ((x³+7m)^((π‘šβˆ’1)/2)) mod π‘š, where m is 2^256-2^32-977 $\endgroup$ Commented Mar 29, 2020 at 19:44
  • $\begingroup$ @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). $\endgroup$ Commented Mar 29, 2020 at 20:12
  • $\begingroup$ Just to be clear, if I calculate x³+7, I would have a result, but I still need to use Euler's criterion to further check that the result is in-fact a quadratic residue right? $\endgroup$ Commented Mar 29, 2020 at 20:17
  • $\begingroup$ @SyedJafri: that is correct... $\endgroup$ Commented Mar 29, 2020 at 20:26

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.