2

In the PrivateKey sign() method (Chapter 3 page 70) s is calculated like this

# s = (z + re)/k
s = (z + r * self.secret) * k_inv % N 
if s > N / 2:
   s = N - s

Why does s and N - s work?

Closest I can get is (page 76) "if we know x, we know the y coordinate has to be either y or p - y", but s is not a y co-ordinate, merely the result of integer arithmetic, there's no elliptic curve math here. Is it purely a property of a prime order field (group)? In the book it's treated as something that should be obvious so perhaps I missed something or am not seeing a connection.

Thanks in advance.

1 Answer 1

2

The verification equation for ECDSA is

X coordinate of ((z/s)G + (r/s)Q) mod n = r

Where the divisions happen modulo the order of the curve (n), and z is the message hash (taken modulo n again). Also, while the X coordinate that comes out is a number in the field GF(p) (not GF(n)), it is interpreted as an integer, and then taken modulo n before comparison with r.

If it so happens that you have a pair (r, s) that satisfies this equation, then substituting -s (which equals n-s modulo n) gives:

   ( (z/(-s))G +  (r/(-s))Q)

Due to the fact that in elliptic curve multiplication it holds that (-a)P = -(aP) (where the first - is an integer negation modulo n, and the second - is elliptic curve point negation), it follows that:

=  (-(z/  s) G + -(r/  s )Q)
= -( (z/  s) G +  (r/  s )Q)

In other words, the result is the (point) negation of the ((z/s)G + (r/s)Q) that appears in the normal formula. Negating an elliptic curve point only changes its Y coordinate, not its X coordinate, so the result will have the same X coordinate, r, and thus the verification equation will also succeed for the signature with negated s.

Note that in Bitcoin there is a policy rule that every s needs to be between 0 and n/2, disallowing one of the two variants.

1
  • 1
    OK, got it. Nice clear explanation, thank you :-) My confusion stemmed from me trying to get from the expression in the prior line (z + re)/k which are all integers, to a value that was being treated like two y-coordinates s and N-s. Cheers.
    – Jon
    Nov 2, 2023 at 22:32

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.