1

In the answer to this question, it is stated that:

Rearranging this equation you get rP = sR - mG, or P = (s/r)R - (m/r)G. Thus, it seems we can just compute the public key from the message and the signature. Unfortunately, there can be up to 4 different points R for which R.x mod n = r (in practice, the number is almost always 2).

How is it possible that there could be up to 4 different points for R? And why would it most often be 2 different points?

Improve this question
0

1 Answer 1

Reset to default
2

Negating an elliptic curve point means negating its Y coordinate (modulo the field size p), so -(x,y) = (x,-y). This implies that if you have a point R for which R.x mod n = k (where n is the curve order), then the same will be true for -R.

Furthermore, and with negligable probability, it is possible that both R.x and R.x + n are valid X coordinates (only when R.x < p-n). In that case, there are 4 possible points ((r, y1), (r,-y1),(r+n,y2),(r+n,-y2)).

Improve this answer
2
  • Then, is the reason that R.x + 2n, R.x + 3n, etc. are not possible X coordinates because of a size constraint (I'm guessing they would be larger than 256 bits)? Perhaps this is also the reason for why R.x < p-n?
    – Shaun
    Jul 11, 2019 at 3:14
  • Yes, p and n are both very close to 2^256, but n is slightly smaller.
    – Pieter Wuille
    Jul 11, 2019 at 3:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.