<p>The ECDSA verification algorithm (in general, and as implemented in Bitcoin) unambiguously requires both <em>r</em> and <em>s</em> to be less than the group order, so descriptions of signature generation algorithms usually include taking <em>r</em> to be the X coordinate of <em>R</em> modulo the curve order. In the extraordinaly unlikely case that <em>r</em> falls between <em>n</em> and <em>p - 1</em>, omitting the modulo step would just result in an invalid signature (which all Bitcoin nodes would recognize as invalid).</p>
<p>Note that in the Schnorr signature algorithm as described in <a href="https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki" rel="nofollow noreferrer">BIP340</a>, <em>r</em> is not required to be less than the curve order (meaning it can go up to <em>p - 1</em>).</p>

CC BY-SA 4.0
2024-10-20T23:30:25.130Z
2024-10-20T23:30:25.130Z
Vojtěch Strnad
<p>In the book Programming Bitcoin (2019) by Jimmy Song (pg's 61-72) the ECDSA signing/verification procedure for message hash z, private/public key pair (e, P), generator point G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8), elliptic curve cyclic group order
<br/>
N = |&lt;G&gt;| = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141, field order p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F, and ephemeral private key k is defined by :</p>
<ol>
<li><p>Signature (r, s) created as follows : <br/>
r = x coordinate of the point R = kG (so r is in the range [0, p - 1]), <br/>
s = (z + re) / k mod N (so s is in range [0, N - 1]) <br/></p>
</li>
<li><p>Signature (r, s) is validated as follows : <br/>
Calculate the point Q = (z/s)G + (r/s)P. <br/>
(r, s) is valid if x coordinate of Q equals r <br/></p>
</li>
</ol>
<p>This is implemented in the book code at : <br/>
<a href="https://github.com/jimmysong/programmingbitcoin/blob/master/code-ch13/ecc.py" rel="nofollow noreferrer">https://github.com/jimmysong/programmingbitcoin/blob/master/code-ch13/ecc.py</a> <br/>
in the methods PrivateKey.sign and S256Point.verify.</p>
<p>However in other sources, eg : <br/>
<a href="https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm</a> <br/>
<a href="https://andrea.corbellini.name/2015/05/30/elliptic-curve-cryptography-ecdh-and-ecdsa/" rel="nofollow noreferrer">https://andrea.corbellini.name/2015/05/30/elliptic-curve-cryptography-ecdh-and-ecdsa/</a> <br/>
<a href="https://www.secg.org/sec1-v2.pdf" rel="nofollow noreferrer">https://www.secg.org/sec1-v2.pdf</a> <br/></p>
<p>the algorithm is slightly different :</p>
<ol>
<li><p>r is taken to be mod N (so r is in the range [0, N - 1]),</p>
</li>
<li><p>(r, s) is considered valid if (x coordinate of Q mod N) equals r</p>
</li>
</ol>
<p>My question is which approach does Bitcoin itself adopt ?</p>
<p>If Bitcoin adopts the latter approach then if we sign as in Jimmy's book, and if the x coordinate of R is in the range [N, p - 1], which is possible as N &lt; p, then our r value is in the range [N, p - 1]. However then, on validation using the second approach we compute (x coordinate of Q mod N), which must lie in the range [0, N - 1] and thus it can never equal r, and the validation fails.</p>
<p>The probability of obtaining the x coord of R in the range [N, p - 1] is very small as N is proportionately very close to p, however is it good practice in Bitcoin programming to assume this can never happen ?</p>

<ecdsa><message-signing><programming-bitcoin-book>
Does Bitcoin Core Validate ECDSA Signature Component r Using Mod N?
Crypto L Plate
# Does Bitcoin Core Validate ECDSA Signature Component r Using Mod N?

(Asked by: username_0 on 2024-10-20)

In the book Programming Bitcoin (2019) by Jimmy Song (pg's 61-72) the ECDSA signing/verification procedure for message hash z, private/public key pair (e, P), generator point G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8), elliptic curve cyclic group order
  
N = |<G>| = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141, field order p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F, and ephemeral private key k is defined by :

1. Signature (r, s) created as follows :   
   r = x coordinate of the point R = kG (so r is in the range [0, p - 1]),   
   s = (z + re) / k mod N (so s is in range [0, N - 1])
2. Signature (r, s) is validated as follows :   
   Calculate the point Q = (z/s)G + (r/s)P.   
   (r, s) is valid if x coordinate of Q equals r

This is implemented in the book code at :   
<https://github.com/jimmysong/programmingbitcoin/blob/master/code-ch13/ecc.py>   
in the methods PrivateKey.sign and S256Point.verify.

However in other sources, eg :   
<https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm>   
<https://andrea.corbellini.name/2015/05/30/elliptic-curve-cryptography-ecdh-and-ecdsa/>   
<https://www.secg.org/sec1-v2.pdf>

the algorithm is slightly different :

1. r is taken to be mod N (so r is in the range [0, N - 1]),
2. (r, s) is considered valid if (x coordinate of Q mod N) equals r

My question is which approach does Bitcoin itself adopt ?

If Bitcoin adopts the latter approach then if we sign as in Jimmy's book, and if the x coordinate of R is in the range [N, p - 1], which is possible as N < p, then our r value is in the range [N, p - 1]. However then, on validation using the second approach we compute (x coordinate of Q mod N), which must lie in the range [0, N - 1] and thus it can never equal r, and the validation fails.

The probability of obtaining the x coord of R in the range [N, p - 1] is very small as N is proportionately very close to p, however is it good practice in Bitcoin programming to assume this can never happen ?

**Tags:** ecdsa, message-signing, programming-bitcoin-book


---

## 1 answers

### Answer by username_1 on 2024-10-20. Score: 3 | Accepted answer

The ECDSA verification algorithm (in general, and as implemented in Bitcoin) unambiguously requires both *r* and *s* to be less than the group order, so descriptions of signature generation algorithms usually include taking *r* to be the X coordinate of *R* modulo the curve order. In the extraordinaly unlikely case that *r* falls between *n* and *p - 1*, omitting the modulo step would just result in an invalid signature (which all Bitcoin nodes would recognize as invalid).

Note that in the Schnorr signature algorithm as described in [BIP340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki), *r* is not required to be less than the curve order (meaning it can go up to *p - 1*).


---

