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?

Shaun
  • 35
  • 3

1 Answers1

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

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