Bitcoin Stack Exchange is a question and answer site for Bitcoin crypto-currency enthusiasts. It only takes a minute to sign up.
Sign up to join this community
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?
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)).
