<p>The following Python program computes all the possible total lengths as accurately as computationally feasible:</p>
<pre><code>from fractions import Fraction

P = 2**256 - 2**32 - 977
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

def lentable(table, low, high):
    # For every value v in [low, high], increment table[l], where l is the length
    # of the encoding of v. Returns the number of values in range.
    total = 0
    while low &lt;= high:
        lowlen = 1 + (low.bit_length() // 8)
        maxval = 2**(8*lowlen - 1) - 1
        highnow = min(high, maxval)
        while len(table) &lt;= lowlen:
            table.append(0)
        table[lowlen] += highnow - low + 1
        total += highnow - low + 1
        low = highnow + 1
    return total

def analyze(low_r, low_s):
    # Table of probabilities of S length
    slen = []
    stotal = 0
    if low_s:
        stotal = lentable(slen, 1, N // 2)
        # High s (range n/2 + 1 .. N-1) is just mapped to 1 .. N/2 again.
    else:
        stotal = lentable(slen, 1, N-1)

    # Table of probabilities of R length
    rlen = []
    rtotal = 0
    if low_r:
        rtotal = lentable(rlen, 0, 2**255-1)
        # High r cause a retry until one in 0..2**255-1 is hit.
    else:
        rtotal = lentable(rlen, 0, P-1)

    # Table of signature lengths
    dlen = [0 for _ in range(len(slen) + len(rlen) + 5)]
    for sl in range(len(slen)):
        for rl in range(len(rlen)):
            dlen[sl + rl + 6] += Fraction(slen[sl] * rlen[rl], rtotal * stotal)

    return dlen

for low_r in [0, 1]:
    for low_s in [0, 1]:
        print(&quot;low_r=%i low_s=%i&quot; % (low_r, low_s))
        for dl, freq in enumerate(analyze(low_r, low_s)):
            print(&quot;* siglen=%i: %.15g&quot; % (dl, freq))
        print()
</code></pre>
<p>Its output contains:</p>
<p>low_r=0 low_s=0</p>
<ul>
<li>siglen=64: 6.17568333711321e-15</li>
<li>siglen=65: 1.3553741462502e-12</li>
<li>siglen=66: 2.8922197969905e-10</li>
<li>siglen=67: 5.92558535572607e-08</li>
<li>siglen=68: 1.13845453597605e-05</li>
<li>siglen=69: 0.00194549560546875</li>
<li>siglen=70: 0.249996185302734</li>
<li>siglen=71: 0.498046875</li>
<li>siglen=72: 0.25</li>
</ul>
<p>low_r=0 low_s=1</p>
<ul>
<li>siglen=64: 1.23444548853768e-14</li>
<li>siglen=65: 2.7089788745549e-12</li>
<li>siglen=66: 5.77990988404053e-10</li>
<li>siglen=67: 1.18395746540045e-07</li>
<li>siglen=68: 2.27394048124552e-05</li>
<li>siglen=69: 0.00388339161872864</li>
<li>siglen=70: 0.498046875</li>
<li>siglen=71: 0.498046875</li>
</ul>
<p>low_r=1 low_s=0</p>
<ul>
<li>siglen=64: 1.23444548853768e-14</li>
<li>siglen=65: 2.7089788745549e-12</li>
<li>siglen=66: 5.77990988404053e-10</li>
<li>siglen=67: 1.18395746540045e-07</li>
<li>siglen=68: 2.27394048124552e-05</li>
<li>siglen=69: 0.00388339161872864</li>
<li>siglen=70: 0.498046875</li>
<li>siglen=71: 0.498046875</li>
</ul>
<p>low_r=1 low_s=1</p>
<ul>
<li>siglen=64: 2.46750861930545e-14</li>
<li>siglen=65: 5.41441891321881e-12</li>
<li>siglen=66: 1.15507603482001e-09</li>
<li>siglen=67: 2.36559571931139e-07</li>
<li>siglen=68: 4.54194378107786e-05</li>
<li>siglen=69: 0.00775158405303955</li>
<li>siglen=70: 0.992202758789062</li>
</ul>
<p>The computation is done with exact fractions, but printed as floating point. Change the &quot;%.15g&quot; to &quot;%s&quot; if you want fractions in the output.</p>

CC BY-SA 4.0
2022-03-01T15:59:41.277Z
2022-03-02T00:23:07.670Z
2022-03-02T00:23:07.670Z
Pieter Wuille
<p>Since DER requires R and s values being minimally encoded signed integers, they could be less than the expected 32 bytes. What is the probability that one or both of R and s are less than 32 bytes for any signature?</p>

CC BY-SA 4.0
2022-03-02T08:16:33.290Z
DER (and BER) requires minimal _two's-complement_ so for general ECDSA (without BIP 146's limitation to low-S) each of R and S is nearly 50% 33-bytes, nearly 50% 32-bytes, and about 0.2% shorter. As Pieter's computation shows.
dave_thompson_085
<signature><python><ecdsa>
What is the probability of an ECDSA signature being less than 71 bytes
Ava Chow
# What is the probability of an ECDSA signature being less than 71 bytes

(Asked by: username_0 on 2022-03-01)

Since DER requires R and s values being minimally encoded signed integers, they could be less than the expected 32 bytes. What is the probability that one or both of R and s are less than 32 bytes for any signature?

**Tags:** signature, python, ecdsa

> **Comments:**
> **username_1**: DER (and BER) requires minimal _two's-complement_ so for general ECDSA (without BIP 146's limitation to low-S) each of R and S is nearly 50% 33-bytes, nearly 50% 32-bytes, and about 0.2% shorter. As username_2's computation shows.  

---

## 1 answers

### Answer by username_2 on 2022-03-01. Score: 5 | Accepted answer

The following Python program computes all the possible total lengths as accurately as computationally feasible:

```
from fractions import Fraction

P = 2**256 - 2**32 - 977
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

def lentable(table, low, high):
    # For every value v in [low, high], increment table[l], where l is the length
    # of the encoding of v. Returns the number of values in range.
    total = 0
    while low <= high:
        lowlen = 1 + (low.bit_length() // 8)
        maxval = 2**(8*lowlen - 1) - 1
        highnow = min(high, maxval)
        while len(table) <= lowlen:
            table.append(0)
        table[lowlen] += highnow - low + 1
        total += highnow - low + 1
        low = highnow + 1
    return total

def analyze(low_r, low_s):
    # Table of probabilities of S length
    slen = []
    stotal = 0
    if low_s:
        stotal = lentable(slen, 1, N // 2)
        # High s (range n/2 + 1 .. N-1) is just mapped to 1 .. N/2 again.
    else:
        stotal = lentable(slen, 1, N-1)

    # Table of probabilities of R length
    rlen = []
    rtotal = 0
    if low_r:
        rtotal = lentable(rlen, 0, 2**255-1)
        # High r cause a retry until one in 0..2**255-1 is hit.
    else:
        rtotal = lentable(rlen, 0, P-1)

    # Table of signature lengths
    dlen = [0 for _ in range(len(slen) + len(rlen) + 5)]
    for sl in range(len(slen)):
        for rl in range(len(rlen)):
            dlen[sl + rl + 6] += Fraction(slen[sl] * rlen[rl], rtotal * stotal)

    return dlen

for low_r in [0, 1]:
    for low_s in [0, 1]:
        print("low_r=%i low_s=%i" % (low_r, low_s))
        for dl, freq in enumerate(analyze(low_r, low_s)):
            print("* siglen=%i: %.15g" % (dl, freq))
        print()

```

Its output contains:

low\_r=0 low\_s=0

* siglen=64: 6.17568333711321e-15
* siglen=65: 1.3553741462502e-12
* siglen=66: 2.8922197969905e-10
* siglen=67: 5.92558535572607e-08
* siglen=68: 1.13845453597605e-05
* siglen=69: 0.00194549560546875
* siglen=70: 0.249996185302734
* siglen=71: 0.498046875
* siglen=72: 0.25

low\_r=0 low\_s=1

* siglen=64: 1.23444548853768e-14
* siglen=65: 2.7089788745549e-12
* siglen=66: 5.77990988404053e-10
* siglen=67: 1.18395746540045e-07
* siglen=68: 2.27394048124552e-05
* siglen=69: 0.00388339161872864
* siglen=70: 0.498046875
* siglen=71: 0.498046875

low\_r=1 low\_s=0

* siglen=64: 1.23444548853768e-14
* siglen=65: 2.7089788745549e-12
* siglen=66: 5.77990988404053e-10
* siglen=67: 1.18395746540045e-07
* siglen=68: 2.27394048124552e-05
* siglen=69: 0.00388339161872864
* siglen=70: 0.498046875
* siglen=71: 0.498046875

low\_r=1 low\_s=1

* siglen=64: 2.46750861930545e-14
* siglen=65: 5.41441891321881e-12
* siglen=66: 1.15507603482001e-09
* siglen=67: 2.36559571931139e-07
* siglen=68: 4.54194378107786e-05
* siglen=69: 0.00775158405303955
* siglen=70: 0.992202758789062

The computation is done with exact fractions, but printed as floating point. Change the "%.15g" to "%s" if you want fractions in the output.


---

