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?

0
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)).

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 '19 at 3:14
  • Yes, p and n are both very close to 2^256, but n is slightly smaller. – Pieter Wuille Jul 11 '19 at 3:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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