<p>The verification equation for ECDSA is</p>
<pre><code>X coordinate of ((z/s)G + (r/s)Q) mod n = r
</code></pre>
<p>Where the divisions happen modulo the order of the curve (<em>n</em>), and <em>z</em> is the message hash (taken modulo <em>n</em> again). Also, while the X coordinate that comes out is a number in the field <em>GF(p)</em> (not <em>GF(n)</em>), it is interpreted as an integer, and then taken modulo <em>n</em> before comparison with <em>r</em>.</p>
<p>If it so happens that you have a pair <em>(r, s)</em> that satisfies this equation, then substituting <em>-s</em> (which equals <em>n-s</em> modulo <em>n</em>) gives:</p>
<pre><code>   ( (z/(-s))G +  (r/(-s))Q)
</code></pre>
<p>Due to the fact that in elliptic curve multiplication it holds that <code>(-a)P = -(aP)</code> (where the first <code>-</code> is an integer negation modulo <code>n</code>, and the second <code>-</code> is elliptic curve point negation), it follows that:</p>
<pre><code>=  (-(z/  s) G + -(r/  s )Q)
= -( (z/  s) G +  (r/  s )Q)
</code></pre>
<p>In other words, the result is the (point) negation of the <code>((z/s)G + (r/s)Q)</code> 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, <code>r</code>, and thus the verification equation will also succeed for the signature with negated <code>s</code>.</p>
<p>Note that in Bitcoin there is a policy rule that every <code>s</code> needs to be between <code>0</code> and <code>n/2</code>, disallowing one of the two variants.</p>

CC BY-SA 4.0
2023-11-02T22:32:28.200Z
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
CC BY-SA 4.0
2023-11-02T20:35:49.360Z
2023-11-02T23:42:18.187Z
2023-11-02T23:42:18.187Z
Pieter Wuille
<p>In the PrivateKey sign() method (Chapter 3 page 70) s is calculated like this</p>
<pre><code># s = (z + re)/k
s = (z + r * self.secret) * k_inv % N 
if s &gt; N / 2:
   s = N - s
</code></pre>
<p>Why does s and N - s work?</p>
<p>Closest I can get is (page 76) &quot;if we know x, we know the y coordinate has to be either y or p - y&quot;, 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.</p>
<p>Thanks in advance.</p>

<signature><secp256k1><programming-bitcoin-book>
In the PrivateKey sign() method why are s and N-s equivalent solutions?
Jon
# In the PrivateKey sign() method why are s and N-s equivalent solutions?

(Asked by: username_0 on 2023-11-02)

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.

**Tags:** signature, secp256k1, programming-bitcoin-book


---

## 1 answers

### Answer by username_1 on 2023-11-02. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  

---

