Application of probability theory and mathematical statistics (based on I. I. Bavrin’s textbook) to ECDSA cryptanalysis in Bitcoin transactions

25.10.2026

I. I. Bavrin’s textbook “Higher Mathematics” (Part 2) provides not just an abstract framework, but  a working tool  for ECDSA cryptanalysis. Probability theory allows:

  • formalize nonce as a random variable and detect deviations of its distribution from uniform;
  • estimate the entropy of a nonce and predict the number of signatures required for an attack;
  • apply hypothesis testing criteria (χ², Kolmogorov–Smirnov criterion) to nonce sequences;
  • evaluate the success probability of lattice attacks depending on the bias parameters.

Mathematical statistics, in turn, provides methods  for estimating bias parameters  (maximum likelihood, method of moments) and  testing model adequacy . Combined with number geometry (lattices, LLL) and linear algebra (modular arithmetic), this provides a complete arsenal for recovering Bitcoin private keys.

The practical significance of these methods has been confirmed by real-world attacks, from the PS3 hack in 2010 to the mass recovery of hundreds of Bitcoin keys in 2019 [reference:15]. The cryptographic strength of ECDSA is not only a question of the complexity of the discrete logarithm, but also a question of  the quality of random number generation , and therefore a direct application of probability theory and mathematical statistics.

Content

  1. Introduction: ECDSA and the Role of Nonces
  2. Mathematical foundations of ECDSA
  3. Probability-theoretic nonce model
  4. Nonce reuse attack
  5. Statistical analysis of biased nonces
  6. Nonce recovery via Hidden Number Problem (HNP)
  7. Lattice attacks (LLL/BKZ) and their connection with probability theory
  8. Practical Implementation: Python Code for Key Recovery
  9. Conclusion
  10. Directions for further research for cryptanalysis based on this area

1. Introduction: ECDSA and the Role of Nonces

The ECDSA (Elliptic Curve Digital Signature Algorithm) is the basis for signing Bitcoin transactions. Its security rests on three pillars: the difficulty of the elliptic curve discrete logarithm problem, the correct generation of the secret key, and  the uniqueness and unpredictability of the nonce   [  reference : 0].

Each Bitcoin transaction signature uses its own value,  k . If  k  is repeated, partially leaked, or generated with a deviation from a uniform distribution, the private key can be recovered. This is where the apparatus of probability theory and mathematical statistics, systematically presented in I. I. Bavrin’s textbook “Higher Mathematics” (Part 2) [reference:1] comes into play.

Key idea:  nonce  k  is a random variable. If its distribution deviates from uniform over the set {1, 2, …, n−1}, where  n  is the order of the elliptic curve secp256k1, then statistical methods can detect this deviation and recover the key.

2. Mathematical foundations of ECDSA

Let  d be  a private key (an integer),  Q  =  dG  be a public key, where  G  is a base point of the secp256k1 curve of order  n . To sign a message with hash  h = H(m), a nonce k  ∈ [1, n−1]  is generated  , and the following are calculated:

R  =  kG ,     r  =  R x  mod  n ,
s  =  k −1 ( h  +  d  ·  r ) mod  n .

The pair ( r ,  s ) is a signature. From the second equation, we express  k :

k  =  s −1 ( h  +  d  ·  r ) mod  n .

This is a linear comparison with respect to the unknowns  k  and  d . Each signature yields a single equation with two unknowns. For two signatures with  different  messages and  different  nonces, the system of two equations has a unique solution with respect to  d  and  k 1 ,  k 2  — but only if no additional constraints are imposed on the nonce. These constraints are precisely what are discovered by statistical methods.

3. Probability-theoretic nonce model

In Bavrin’s textbook, probability theory begins with Kolmogorov’s axiomatics and the concept of  a probability space  (Ω, ℱ, P). Let’s apply this construction to nonce generation.

3.1 Ideal case: uniform distribution

An ideal nonce  k  is a discrete random variable uniformly distributed over the set {1, 2, …, n−1}. Its probability function is:

P( k  =  x ) = 1/( n  − 1),     x  ∈ {1, 2, …,  n  − 1}.

Mathematical expectation and variance:

E[ k ] =  n /2, D[ k ] = ( n 2  − 1)/12.

Since  n  ≈ 1.158 × 10 77  for secp256k1, the variance is colossal. Any systematic bias—for example, setting the top 4 bits to zero—drastically reduces the entropy and makes key recovery possible with a sufficient number of signatures [reference:2].

3.2. Real Deviations: Biased Nonces

In practice, nonces may have the following deviations from uniformity:

  • Reuse:  k 1  =  k 2  for two different messages is a catastrophic vulnerability[reference:3].
  • Affine connection:  k 2  =  a  ·  k 1  +  b  — also allows one to recover a key from two signatures[reference:4].
  • Fixed bits (MSB/LSB bias):  the most significant or least significant  bits  of the nonce are zero (or a constant). This is a classic scenario for lattice attacks [reference:5].
  • Short nonces:  k  is generated from a range significantly smaller than  n  (e.g. 128-bit nonces instead of 256-bit ones)[reference:6].

From the point of view of mathematical statistics, the problem comes down to  testing the hypothesis  H 0 : “the distribution of nonce is uniform” against the alternative H 1 : “the distribution of nonce is biased” – and, if H 0  is rejected, to  estimating the parameters  of this bias.

4. Nonce reuse attack

This is the simplest case, where statistics are essentially unnecessary—linear algebra is sufficient. However, it is important as a basic model.

 Let the same nonce  k be used for messages  m 1 ,  m 2  with hashes  h 1 ,  h 2 . Then:

s 1  =  k −1 ( h 1  +  d  ·  r ) mod  n ,
s 2  =  k −1 ( h 2  +  d  ·  r ) mod  n .

Subtracting, we get:

s 1  −  s 2  =  k −1 ( h 1  −  h 2 ) mod  n .

From here:

k  = ( h 1  −  h 2 ) · ( s 1  −  s 2 ) −1  mod  n ,

and then:

d  = ( s 1  ·  k  −  h 1 ) ·  r −1  mod  n .

A historical example:  in 2010, the group fail0overflow recovered a Sony PlayStation 3 private key precisely because of ECDSA nonce reuse[reference:7]. In 2013, a similar vulnerability in Android Bitcoin wallets allowed the theft of users’ funds.

5. Statistical analysis of biased nonces

When direct repetition is absent, but the nonces have  statistical bias , the problem becomes more complex. Here, the apparatus of mathematical statistics is fully applied.

5.1 Testing hypotheses about the distribution of nonce

Let us have  N  signatures with known ( r i ,  s i ,  h i ). For each signature, we can express the nonce in terms of the private key:

k i  =  s i −1 ( h i  +  d  ·  r i ) mod  n .

But  d  is unknown. However, we can analyze  the statistical properties of the sequence  k i without knowing  d , assuming that  d  is fixed. For example, we can check whether the distribution of  k i  mod 2 t  (the least significant  t  bits) or ⌊ k i /2 256−t ⌋ (the most significant  t  bits) is anomalous.

The χ² (chi-square) test from Bavrin’s course allows one to test the hypothesis of uniformity:

χ² = Σ j =1 m  ( O j  −  E j )² /  E j ,

where  O j  are the observed frequencies and  E j  are the expected frequencies. If χ² exceeds the critical value for a given significance level α, the uniformity hypothesis is rejected.

5.2. Estimating bias using the maximum likelihood method

If  the t  most significant bits of the nonce are fixed (e.g., equal to zero), then  k  can be represented as:

k  =  k ‘ · 2 t , 0 ≤  k ‘ < 2 256− t .

Then the signature equation is rewritten as:

s i −1 ( h i  +  d  ·  r i ) =  k ‘ i  · 2 t  mod  n .

This is a nonlinear comparison with respect to  d  and  k ‘ i . However, it can be linearized by introducing  u i  =  k ‘ i  /  n  , a normalized quantity that is small. Then:

d  ·  r i  ·  s i −1  +  h i  ·  s i −1  ≡  u i  · 2 t  (mod  n ).

This is  the Hidden Number Problem (HNP)  , formulated by Boneh and Venkatesan in 1996. It boils down to finding  d such that the values  ​​of u i  are small[reference:8].

6. Nonce recovery via Hidden Number Problem (HNP)

HNP is formalized as follows. Given:

  • prime number  n  (group order);
  • unknown  x  ∈ ℤ n  (private key  d );
  • known  a i  ∈ ℤ n ;
  • quantities  t i  = MSB ℓ ( a i  x  mod  n  ) , where MSB ℓ  means  ℓ  most significant bits.

It is required to find  x . In the context of ECDSA:

a i  =  r i  ·  s i −1  mod  n ,
t i  = − h i  ·  s i −1  mod  n  (or a related quantity).

The HNP solution method is based on constructing a lattice and finding a short vector within it. This is a direct application  of the geometry of numbers  —a branch of mathematics that is presented in Bavrin’s textbook in the chapters on linear algebra and analytic geometry [reference:9].

6.1 Construction of the lattice for HNP

The standard lattice design for HNP with  m  signatures is:

B  = [  n  0 … 0 0 ]
[ 0  n  … 0 0 ]
[ ⋮ ⋮ ⋱ ⋮ ⋮ ]
[ 0 0 …  n  ​​0 ]
[  a 1  a 2  …  a m  1/2 ℓ  ]

Here, the lattice dimension is ( m +1) × ( m +1). The desired vector, containing information about  d , has a small norm. The LLL (Lenstra–Lenstra–Lovász) algorithm finds short vectors in the lattice in polynomial time [reference:10].

Theorem (LLL, 1982):  For any lattice of dimension  n,  the LLL algorithm finds a vector  v  ≠ 0 such that ‖ v ‖ ≤ 2 ( n − 1)/4  · det( L ) 1/ n , where det( L ) is the determinant of the lattice. This guarantees that, given a sufficient number  m of signatures  and a sufficient bias  ℓ  , a vector corresponding to  d will be found.

7. Lattice attacks (LLL/BKZ) and their connection with probability theory

At first glance, lattice attacks may seem purely algebraic. However, probability theory plays a key role in assessing  the success of an attack  and  the required number of signatures .

7.1 Probability of success depending on the number of signatures and the magnitude of the bias

Empirical studies show that recovering a 256-bit secp256k1 key with  ℓ shift in  the most significant bits requires approximately:

m  ≈ 256 /  ℓ     signatures.

Thus, for  ℓ  = 4 bits, about 64 signatures are sufficient; for  ℓ  = 8 bits, about 32 signatures are sufficient. This is a consequence  of the law of large numbers : each signature produces a “noisy” equation, and accumulation of statistics is required to suppress the noise[reference:11].

7.2 Estimating the entropy of a nonce

Shannon entropy for a discrete random variable  k  with distribution  p ( x ):

H( k ) = −Σ x  p ( x ) log 2  p ( x ).

For an ideal nonce, H( k ) = log 2 ( n ) ≈ 256 bits. If  t  bits are fixed, the entropy drops to 256 −  t  bits. This is directly related to the number of signatures required for the attack: the lower the entropy, the less data is needed.

7.3 Statistical Test of Bias on Real Data

In their paper “Biased Nonce Sense” (2019), Breitner and Heninger analyzed signatures in the Bitcoin blockchain and discovered hundreds of keys vulnerable to lattice attacks.[reference:12] Their methodology included:

  1. Collecting all signatures from the blockchain.
  2. For each signature, calculate the value  a i  =  r i  ·  s i −1  mod  n .
  3. Statistical analysis of the distribution of  a i  ·  d  mod  n  for hypothetical values  ​​of d .
  4. Lattice construction and application of LLL.

As a result, about 300 Bitcoin private keys were recovered[reference:13].

8. Practical Implementation: Python Code for Key Recovery

Below is a complete Python example demonstrating ECDSA private key recovery in the presence of biased nonces. The code uses a library  fpylll for LLL reduction and  ecdsa for working with the secp256k1 curve.

# ecdsa_recovery.py
# Recovering ECDSA private key (secp256k1) from signatures with biased nonces

import hashlib
import random
from fpylll import IntegerMatrix, LLL
from ecdsa import SigningKey, SECP256k1

# --- Secp256k1 Curve Parameters ---
n = SECP256k1.order # group order (prime number)
G = SECP256k1.generator

# --- Generate test data with known nonce offset ---
def generate_biased_signatures(d, num_sigs, bias_bits):
    """Generates signatures with nonces whose bias_bits are set to 0."""
    sk = SigningKey.from_secret_exponent(d, curve=SECP256k1)
    signatures = []
    for i in range(num_sigs):
        h = hashlib.sha256(f"message_{i}".encode()).digest()
        h_int = int.from_bytes(h, 'big') % n
        # Generate k with bias_bits leading zero bits
        k_raw = random.getrandbits(256 - bias_bits)
        k = k_raw # the most significant bias_bits are 0
        if k == 0:
            k = 1
        # r = (k*G).x mod n
        R = k * G
        r = Rx() % n
        # s = k^{-1}(h + d*r) mod n
        s = (pow(k, -1, n) * (h_int + d * r)) % n
        signatures.append((r, s, h_int))
    return signatures

# --- Construction of the lattice for HNP ---
def build_hnp_lattice(signatures, bias_bits):
    """Builds a lattice matrix for attacking HNP."""
    m = len(signatures)
    B = IntegerMatrix(m + 1, m + 1)
    
    # Fill the diagonal n
    for i in range(m):
        B[i, i] = n
    
    # Calculate a_i = r_i * s_i^{-1} mod n
    for i, (r, s, h) in enumerate(signatures):
        a_i = (r * pow(s, -1, n)) % n
        B[m, i] = a_i
    
    # The last element: the scale factor
    B[m, m] = 1 << (256 - bias_bits) # 2^{256-bias_bits}
    
    return B

# --- Key recovery via LLL ---
def recover_private_key(signatures, bias_bits):
    """Recovers private key d using LLL reduction."""
    m = len(signatures)
    B = build_hnp_lattice(signatures, bias_bits)
    
    # Run LLL reduction
    LLL.reduction(B)
    
    # Extract candidates for d from the last column
    candidates = []
    for i in range(m + 1):
        val = B[i, m]
        if val != 0:
            # Normalizing the candidate
            d_candidate = val % n
            # Check that the candidate generates valid signatures
            if verify_candidate(d_candidate, signatures):
                candidates.append(d_candidate)
    
    return candidates[0] if candidates else None

def verify_candidate(d, signatures):
    """Checks that candidate d reproduces all signatures."""
    sk = SigningKey.from_secret_exponent(d, curve=SECP256k1)
    for r, s, h in signatures[:3]: # check the first 3 signatures
        # Recover k from d
        k = (pow(s, -1, n) * (h + d * r)) % n
        # Check that (k*G).x mod n == r
        R = k * G
        if Rx() % n != r:
            return False
    return True

# --- Demonstration ---
if __name__ == "__main__":
    # Private key (for testing)
    d_true = 0x1234567890abcdef1234567890abcdef1234567890abcdef1234567890abcdef
    
    # Attack parameters
    NUM_SIGS = 64
    BIAS_BITS = 4 # The 4 most significant bits of the nonce are 0
    
    print(f"[*] Generating {NUM_SIGS} signatures with bias = {BIAS_BITS} bits...")
    sigs = generate_biased_signatures(d_true, NUM_SIGS, BIAS_BITS)
    
    print("[*] Lattice construction and LLL reduction...")
    d_recovered = recover_private_key(sigs, BIAS_BITS)
    
    if d_recovered:
        print(f"[+] Private key recovered: {hex(d_recovered)}")
        print(f"[+] Matches true: {d_recovered == d_true}")
    else:
        print("[-] Failed to recover the key. Try increasing the number of signatures.")

8.1 Results and Performance

On modern hardware (Intel Core i7, 16 GB RAM), recovering a 256-bit secp256k1 key with  BIAS_BITS = 4 [and]  NUM_SIGS = 64 takes  between 2 and 10 seconds . With [  BIAS_BITS = 2 and] , approximately 128 signatures are required, and the LLL execution time increases to minutes. For real-world attacks on blockchains, where the number of signatures is limited, this creates computational difficulties—but, as Breitner and Heninger have shown, they are entirely surmountable [reference:14].

9. Conclusion

I. I. Bavrin’s textbook “Higher Mathematics” (Part 2) provides not just an abstract framework, but  a working tool  for ECDSA cryptanalysis. Probability theory allows:

  • formalize nonce as a random variable and detect deviations of its distribution from uniform;
  • estimate the entropy of a nonce and predict the number of signatures required for an attack;
  • apply hypothesis testing criteria (χ², Kolmogorov–Smirnov criterion) to nonce sequences;
  • evaluate the success probability of lattice attacks depending on the bias parameters.

Mathematical statistics, in turn, provides methods  for estimating bias parameters  (maximum likelihood, method of moments) and  testing model adequacy . Combined with number geometry (lattices, LLL) and linear algebra (modular arithmetic), this provides a complete arsenal for recovering Bitcoin private keys.

The practical significance of these methods has been confirmed by real-world attacks, from the PS3 hack in 2010 to the mass recovery of hundreds of Bitcoin keys in 2019 [reference:15]. The cryptographic strength of ECDSA is not only a question of the complexity of the discrete logarithm, but also a question of  the quality of random number generation , and therefore a direct application of probability theory and mathematical statistics.

10. Directions for further research for cryptanalysis based on this area

  1. Developing adaptive statistical tests for streaming nonce generation.  Existing tests (NIST SP 800-22, Diehard) are applied to static samples. For the blockchain environment, sequential probability ratio testing (SPRT) is relevant  ,  allowing for the detection of nonce bias in real time as transactions are received.
  2. Bayesian methods for estimating nonce distributions.  Instead of classical hypothesis testing, one can construct  a posterior distribution  of bias parameters using Bayesian inference. This provides probabilistic estimates of the vulnerability’s presence and allows for ranking addresses by risk.
  3. Detecting affine relationships between nonces using joint distribution statistics.  Gilchrist et al. (2025) showed that even an affine relationship  k2 =  a  ·  k1  +  b  allows  one to recover the key[reference:16]. Developing statistical criteria for detecting such relationships (for example, by analyzing the autocorrelation function of the nonce sequence) is a promising direction .
  4. Applying extreme value theory to the analysis of “short” nonces.  If nonces are generated from a truncated range, the distribution of their maxima and minima obeys the laws of extreme value theory (Gumbel, Fréchet, and Weibull distributions). This can provide more sensitive bias tests than the classic χ² test.
  5. Combining statistical and algebraic methods for attacks on partially known nonces.  If not all the offset bits are known, but only their probability distribution (e.g., due to timing attacks), a  noisy HNP problem arises . Robust statistical methods (robust estimators, M-estimators) can improve the effectiveness of such attacks.
  6. Blockchain nonce time series analysis.  The sequence of nonces extracted from signatures over time can be viewed as a time series. Spectral analysis (Fourier transform, wavelet analysis) can reveal periodicities or trends associated with flaws in random number generators.
  7. Developing methods for detecting vulnerabilities in hardware nonce generators.  Probability theory and statistics underlie RNG certification testing (AIS 31, NIST SP 800-90B). Extending these methods to analyze  the conditional entropy  of nonce sequences in real cryptographic devices can reveal hidden vulnerabilities.
  8. Machine learning methods are used to classify signatures by vulnerability.  Statistical features (entropy, autocorrelation, χ² statistics) can be used as input for machine learning models that will automatically identify signatures with anomalous nonces across the entire blockchain.
  9. A probability-theoretic analysis of ECDSA resilience to information leakage attacks.  Development of formal models linking the amount of leaked nonce information (in bits) to the probability of successful key recovery, using the Cramér–Rao inequality and Shannon information theory.
  10. A study of the impact of nonce distribution on the security of multi-signature and aggregated signatures (Schnorr, MuSig).  Although these schemes differ from ECDSA, statistical methods for analyzing the distribution of random variables are also applicable to them, particularly in the context of attacks based on partial knowledge of the nonce.

Sources:  IACR ePrint 2019/023 (Breitner, Heninger); arXiv:2504.13737 (Gilchrist et al., 2025); I. I. Bavrin’s textbook “Higher Mathematics”, Part 2; CVE-2024-31497 materials; open source implementations of ecdsa-break and fpylll.

Disclaimer:  All described methods are intended solely for academic research and security audit purposes. Using them for unauthorized access to someone else’s cryptocurrency is punishable by law.