# In the PrivateKey sign() method why are s and N-s equivalent solutions?

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.

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.

• 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
Commented Nov 2, 2023 at 22:32