1
$\begingroup$

When recovering the public key from ECDSA signature (r, s), the first step is recovering the point R.

You do this by plugging in (r + xn) into the curve equation where n is the order of the basepoint and x is some integer

my question is how do you find this x value, say for secp256k1 but also the general case

I have a vauge notion that this may be related to the cofactor of the curve (usually working with secp256k1 this shouldnt be important). But im failing to find more info on it.

$\endgroup$

1 Answer 1

1
$\begingroup$

my question is how do you find this x value, say for secp256k1 but also the general case

Well, in the case of secp256k1, we have $n \approx p$, and so (with extremely high probability) $r + n > p$, and so we have $x = 0$.

Now, for curves with non-1 cofactors, we have $n \approx p/h$ (where $h$ is the cofactor), and so there may be several possible $x$ values for which $r + xn < p$, and so in the general case, this needs to be considered.

$\endgroup$
4
  • $\begingroup$ Uh, I have trouble recognizing the question's "plugging in $(r + xn)$ into the curve equation where $n$ is the order of the basepoint" in the ECDSA signature verification steps. Where exactly would that be ? $\endgroup$
    – fgrieu
    Mar 20, 2023 at 19:24
  • 1
    $\begingroup$ @fgrieu: actually, he's referring to the 'Public key recovery' section of the ECDSA wikipage en.wikipedia.org/wiki/… $\endgroup$
    – poncho
    Mar 20, 2023 at 20:52
  • $\begingroup$ @poncho thank you for the response and sorry for my late one... I guess I was just confused about if all of the possible r' values (r' = (r + xn)) correspond to actual curve points (not true), and the nature of the points when x > h. is there a chance this is a field element? $\endgroup$
    – nuhhtyy
    Mar 21, 2023 at 2:36
  • $\begingroup$ @poncho and last question 😭 can two points that satisfy (x) mod n = r both be in the same subgroup, ie both multiples of G ? $\endgroup$
    – nuhhtyy
    Mar 21, 2023 at 4:20

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.