Bitcoin

python – What is the probability that an ECDSA signature is less than 71 bytes?

The following Python program calculates all possible total lengths as accurately as computationally possible.

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()

Output includes:

low_r=0 low_s=0

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

low_r=0 low_s=1

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

low_r=1 low_s=0

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

low_r=1 low_s=1

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

Calculations are performed as exact fractions, but are printed as floating point. Change “%.15g” to “%s” to display fractions in the output.

Related Articles

Back to top button