ECDSA 簽名小於 71 字節的機率是多少

由於 DER 要求 R 和 s 值是最小編碼的有符號整數，因此它們可能小於預期的 32 個字節。對於任何簽名，R 和 s 之一或兩者小於 32 字節的機率是多少？

以下 Python 程序在計算上盡可能準確地計算所有可能的總長度：

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

其輸出包含：

低_r=0 低_s=0

• 擺動 = 64：6.17568333711321e-15
• 擺動 = 65：1.3553741462502e-12
• 擺動 = 66：2.8922197969905e-10
• 擺動 = 67：5.92558535572607e-08
• 擺動 = 68：1.13845453597605e-05
• 擺動 = 69：0.00194549560546875
• 擺動 = 70：0.249996185302734
• 擺動 = 71：0.498046875
• 擺動 = 72：0.25

低_r=0 低_s=1

• 擺動 = 64：1.23444548853768e-14
• 擺動 = 65：2.7089788745549e-12
• 擺動 = 66：5.77990988404053e-10
• 擺動 = 67：1.18395746540045e-07
• 擺動 = 68：2.27394048124552e-05
• 擺動 = 69：0.00388339161872864
• 擺動 = 70：0.498046875
• 擺動 = 71：0.498046875

低_r=1 低_s=0

• 擺動 = 64：1.23444548853768e-14
• 擺動 = 65：2.7089788745549e-12
• 擺動 = 66：5.77990988404053e-10
• 擺動 = 67：1.18395746540045e-07
• 擺動 = 68：2.27394048124552e-05
• 擺動 = 69：0.00388339161872864
• 擺動 = 70：0.498046875
• 擺動 = 71：0.498046875

低_r=1 低_s=1

• 擺動 = 64：2.46750861930545e-14
• 擺動 = 65：5.41441891321881e-12
• 擺動 = 66：1.15507603482001e-09
• 擺動 = 67：2.36559571931139e-07
• 擺動 = 68：4.54194378107786e-05
• 擺動 = 69：0.00775158405303955
• 擺動 = 70：0.992202758789062

計算使用精確分數完成，但列印為浮點數。如果您想要輸出中的分數，請將“%.15g”更改為“%s”。

引用自：https://bitcoin.stackexchange.com/questions/112662