3

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?

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 Pieter's computation shows. Mar 2, 2022 at 8:16

1 Answer 1

4

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.