Application of probability theory and stochastic financial mathematics to the cryptanalysis of ECDSA in Bitcoin transactions

23.10.2026

A methodology for private key recovery based on statistical analysis of a hidden number (nonce)
using the framework outlined in the works of A. N. Shiryaev. This paper demonstrates how the fundamental results of probability theory and stochastic financial mathematics outlined in the works of A. N. Shiryaev can be directly applied to the cryptanalysis of ECDSA in Bitcoin transactions. Key findings:

  • The probabilistic nonce model  allows us to formalize the concept of “bias” and estimate its impact on the entropy of the secret number.
  • Statistical tests  (chi-square, Kolmogorov–Smirnov) provide tools for detecting anomalies in the distribution of nonces across publicly available signatures.
  • Stochastic processes and martingales  allow us to model nonce sequences and construct optimal private key estimates using filtering methods.
  • Bayesian inference and sequential analysis  (SPRT) determines the minimum number of signatures required to recover a key with a given strength.
  • Stochastic financial mathematics  provides a ready-made apparatus for analyzing nonce time series, including AR models, GARCH models, and optimal stopping problems.
  • Practical implementation  based on HNP and lattice algorithms allows for the recovery of real Bitcoin private keys in the presence of even a slight nonce bias.

Thus, the synthesis of classical probability theory and modern cryptography opens up powerful cryptanalysis methods that have already been confirmed in real-world attacks on blockchain infrastructure.

Content

1. Introduction

The Elliptic Curve Digital Signature Algorithm (ECDSA) is the foundation of transaction security on the Bitcoin network. Its security is based on the computational difficulty of the discrete logarithm problem on a set of elliptic curve points. However, as practice shows, real-world ECDSA implementations are often vulnerable due to  poor generation of the ephemeral secret number  —  the nonce  (a hidden number), typically denoted by  k. This number must be uniformly distributed, unpredictable, and unique for each signature. Any deviation from these requirements opens the way to statistical attacks that allow recovery of the long-term private key  d.

In this paper, we systematically apply the framework of probability theory and stochastic financial mathematics, developed in the classic works of A. N. Shiryaev, to the problem of ECDSA cryptanalysis. Probability theory provides a language for describing  nonce distributions , testing statistical hypotheses about uniformity, and estimating the probabilities of attack success. Stochastic financial mathematics, in turn, provides powerful tools for analyzing  time series  and  random processes that naturally arise when studying signature sequences in a blockchain.

Key Idea:  The problem of recovering an ECDSA private key given partial information about the nonce can be formulated as  a hidden number problem  (HNP) and solved using methods of probability theory and stochastic analysis, including Bayesian inference, statistical hypothesis testing, and random process filtering.

2. Theoretical Foundations: Probability and Stochastic Analysis in the Context of ECDSA

2.1. Basic concepts of probability theory (according to A. N. Shiryaev)

In his fundamental course “Probability,” A. N. Shiryaev builds a theory on Kolmogorov’s axiomatics, consistently introducing probability space, random variables, independence, conditional probabilities, and limit theorems. The following sections are critical for our purpose:

  • Random variables and their distributions.  A nonce  k in ECDSA is a random variable taking values ​​in the set  {1, ..., n-1}, where  n is the order of the base point of the elliptic curve. Ideally,  k it has a uniform distribution. Any deviation from uniformity is called  bias  .
  • Conditional probabilities and Bayes’ rule.  By observing signatures  (r, s) and knowing the message  z, we can calculate the posterior distribution  k and, consequently, the private key  d. The Bayesian approach allows us to combine information from multiple signatures.
  • Limit theorems (law of large numbers, CLT).  When analyzing a large number of signatures, we can use asymptotic results to estimate nonce statistics and construct confidence intervals.
  • Statistical hypothesis testing.  The main objective is to test a hypothesis  H₀: k ~ Uniform{1, ..., n-1} against an alternative  H₁: распределение k имеет смещение. Goodness-of-fit tests (chi-square, Kolmogorov–Smirnov) allow us to detect anomalies.

The second volume of Shiryaev’s “Probability” is devoted to discrete-time random processes: stationary sequences, Markov chains, and martingales. These objects become central to the analysis of nonce sequences in blockchains.

2.2 Stochastic Models. Discrete Time

In “Fundamentals of Stochastic Financial Mathematics,” Shiryaev develops in detail the theory of stochastic models in discrete time. Of particular interest for ECDSA cryptanalysis are:

  • Stationary random sequences.  If the nonce generator has memory (e.g., a linear congruential generator), the sequence  k₁, k₂, ... can be stationary in the wide sense. Spectral analysis can reveal hidden periodicities.
  • Markov chains.  If the distribution of  kₜ depends on the previous value of  kₜ₋₁, a Markov model arises. Estimating the transition probability matrix from observed signatures provides additional information about the generator.
  • Martingales.  Martingale theory allows one to construct optimal estimates of unobservables (nonces) based on observables (signatures). This is directly related to the filtering problem.

Model of nonce as a random process:
k t  = μ + ε t , where E[ε t ] = 0, Var(ε t ) = σ²,
and {ε t } is a stationary process with autocovariance function R(τ).

3. Hidden number (nonce) as a random variable: ECDSA probabilistic model

3.1 The ECDSA equation and its probabilistic interpretation

The ECDSA signature for a message with a hash  z and a private key  d is calculated as follows:

r = (k · G) x  mod n
s = k −1  · (z + r · d) mod n

Here  G is the base point,  n is the order of the group,  k and is the nonce. We transform the second equation:

s k ≡ z + r d (mod n)
⇒ k ≡ s −1  r d + s −1  z (mod n)

Let us denote   and  . Then:t = s−1 · r mod nb = s−1 · z mod n

k ≡ t · d + b (mod n)

This equation relates  the unobservable k ,  the unknown d  , and  the observables t ,  b. It is in this form that the problem enters the classical formulation  of the hidden number problem  (HNP), introduced by Boneh and Venkatesan.

As noted in the LadderLeak paper, “any small disclosure or shift in the nonce could, in principle, lead to full key recovery: key recovery is then a special case of Boneh and Venkatesan’s hidden number problem”[reference:0].

3.2 Nonce distribution and its bias

If  k is uniformly distributed on  {1, ..., n-1}, then it  d cannot be recovered from a single equation—the system is underdetermined. However, in practice, random number generators often introduce  a bias : the high-order or low-order bits  k are predictable. For example, for the P-521 curve, the output of SHA-512 is always smaller than the field size, so  , and  the nine high-order bits of the nonce are zero [reference:1].k < 2512

Formally, the bias can be described through a probability distribution:

P(k ∈ [0, 2 L )) = 1, where L < log₂(n) − ℓ,

That is,  ℓ the most significant bits are clearly zero. This means that  k is not uniform across the entire range; its entropy is reduced by  ℓ bits. It is this reduction in entropy that makes statistical cryptanalysis possible.

Important:  Even an offset  of less than one bit  may be sufficient to recover the key given a sufficient number of signatures. LadderLeak demonstrates an attack that leaks less than one bit of nonce information (the probability of discovering the most significant bit is < 1) [reference:2].

4. Statistical Analysis of Nonces in the Bitcoin Blockchain

4.1. Statement of the problem of displacement detection

The Bitcoin blockchain provides an ideal testing ground for statistical analysis: all transactions and signatures are publicly available. The cryptanalyst’s task is  to detect statistical anomalies  in nonce sequences corresponding to the same public key.

Formally, for a given public key  , Q = d · G we collect a set of signatures  {(rᵢ, sᵢ, zᵢ)}. From each signature, we calculate   and  . Then, for each  :tᵢ = sᵢ−1 rᵢbᵢ = sᵢ−1 zᵢi

kᵢ = tᵢ d + bᵢ (mod n)

Observed quantities are  tᵢ and  bᵢ. Unobserved quantities are  kᵢ and  d. We want to test the hypothesis that the distribution  kᵢ is not uniform.

4.2. Statistical tests for nonce uniformity testing

4.2.1. Chi-square test

Let’s divide the range of possible values  k ​​into  m intervals. If  k is uniform, the expected frequency of occurrence in each interval is  N/m, where  N is the number of signatures. The observed frequencies  Oⱼ allow us to calculate the following statistics:

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

When valid,  H₀ a statistic has a χ² distribution with  m−1 degrees of freedom. Deviation from this distribution indicates bias.

4.2.2. Kolmogorov–Smirnov criterion

For continuous distributions (or their discrete analogues), one can use the Kolmogorov–Smirnov test, which compares the empirical distribution function   with the theoretical one  :FN(x)F(x)

D N  = sup x  |F N (x) − F(x)|

This criterion is sensitive to any deviations from uniformity and does not require division into intervals.

4.2.3. Checking the most significant bits

If  ℓ the high-order bits of nonce are zero, then  . This can be verified by estimating the proportion of signatures for which the calculated   (given  , if it has already been recovered) falls within the range  . However,   is unknown, so an indirect check is used using statistics   and  .k < 2Lkd[0, 2L)dtᵢbᵢ

Practical results:  Large-scale blockchain studies have shown that approximately 0.48% of Bitcoin transactions contain vulnerabilities related to weak randomness in ECDSA, and that  1,331 private keys have been compromised [reference:3].

4.3. Nonce Reuse Detection

The most trivial, yet extremely effective, case of bias is  reusing the same one k  for two different messages. If  k₁ = k₂ = k, then:

s₁ = k −1 (z₁ + r₁ d) mod n
s₂ = k −1 (z₂ + r₂ d) mod n

Subtracting, we get:

s₁ − s₂ = k −1 (z₁ − z₂ + (r₁ − r₂) d) mod n

From here,  k it is expressed using the known quantities and  d, after which  d it is found from the first equation. This method does not require statistics—algebra is sufficient. However,  statistical analysis  allows us to detect cross-reuse, even if the signatures belong to different “addresses.”

The “Oops…I Did It Again” study found 3,620 private keys across multiple blockchains that were recovered specifically through nonce reuse, with potential losses estimated at up to €101 million[reference:4].

5. Stochastic processes and martingales in the key recovery problem

5.1. Signature sequence as a random process

Consider a sequence of transactions signed with the same key. Each transaction corresponds to a signature  (rᵢ, sᵢ, zᵢ) and, therefore, some implementation of a nonce  kᵢ. If the nonce generator has memory, the sequence  {kᵢ} forms a random process.

In Shiryaev’s terminology, we can consider  {kᵢ} it a  random sequence  (a discrete-time process). Its probabilistic characteristics—the mathematical expectation, variance, and autocovariance function—can be estimated from the observed data if we have a sufficient number of signatures.

5.2 Martingale approach to nonce filtering

Let be  ℱᵢ the σ-algebra generated by the signatures  (r₁, s₁), ..., (rᵢ, sᵢ). We want to estimate  d (or  kᵢ) from observations. In stochastic filtering theory (see Liptser and Shiryaev, “Statistics of Random Processes”), the optimal mean-square estimate is given by the conditional expectation:

d̂ᵢ = E[d | ℱᵢ]

If the sequence  {kᵢ} forms a martingale (or a martingale difference), then recurrent filtering algorithms similar to the Kalman filter can be constructed to successively refine the estimate  d.

5.3 Bayesian Inference and the Posterior Distribution

Suppose the prior distribution  d is known (e.g., uniform on  {1, ..., n-1}). Then, for each signature, the likelihood function is:

P(rᵢ, sᵢ | d, zᵢ) = P(kᵢ = sᵢ −1 (zᵢ + rᵢ d) mod n)

If the distribution  k is known (or estimated), we can compute the posterior distribution   and find its mode or expected value as an estimate  . This is a direct application of the Bayesian paradigm, central to Shiryaev’s probability theory.P(d | ℱN)d

Connection with HNP.  In HNP terms, the posterior distribution  d concentrates around the true value as signatures accumulate. The rate of concentration depends on entropy  k: the stronger the bias, the faster the distribution narrows.

6. Application of stochastic financial mathematics

6.1 Analogy between nonce and financial time series

Shiryaev’s stochastic financial mathematics was originally developed for asset price analysis, but its mathematical framework is universal. A nonce sequence  {kᵢ} can be viewed as  a time series with certain stochastic properties. The central objects in financial mathematics are:

  • Stationary processes  (e.g. ARMA, GARCH) are models that describe autocorrelation and heteroscedasticity.
  • Martingales  are processes in which the conditional mathematical expectation of the future value is equal to the current value. Asset prices are often modeled as martingales (the efficient market hypothesis).
  • Brownian motion and stochastic integrals  are continuous models that can be discretized to analyze discrete sequences.

When applied to nonce, we can use time series models to  predict  the next value  k or to  detect  non-random behavior of the generator.

6.2 AR(1) model for nonce

The simplest first-order autoregressive model:

kᵢ = α · kᵢ₋₁ + εᵢ, εᵢ ~ N(0, σ²)

If the estimates  α̂ and  σ̂² differ significantly from  α = 0 (which corresponds to independent uniform nonces), this indicates a deterministic component in the generator. The AR(1) parameters can be estimated using the least-squares method or the maximum-likelihood method using the “reconstructed” values  kᵢ ​​(which become known after finding  d).

6.3. GARCH models for nonce volatility

If the variance  kᵢ varies over time (heteroscedasticity), GARCH models can be applied. This is especially relevant if the nonce generator has states with different entropies (for example, depending on the system load). Although directly applying GARCH to nonces is unconventional, the mathematical apparatus of stochastic finance allows us to formalize such dependencies.

6.4 Optimal Stopping and Sequential Analysis

In Shiryaev’s financial mathematics, much attention is paid to  optimal stopping  and  sequential analysis problems . In the context of ECDSA cryptanalysis, these methods are applicable to the following problem:  what is the minimum number of signatures required to recover  d?

This is a classic sequential analysis problem: we observe signatures one by one, update the posterior distribution  d , and stop when the error probability falls below a given threshold. The Wald likelihood ratio statistic (SPRT) is a direct application of Shiryaev’s sequential analysis theory.

SPRT:  Λ N  = ∏ i=1 N  [P(rᵢ, sᵢ | d₁) / P(rᵢ, sᵢ | d₀)]

Here  d₀ , α is the hypothesis about the incorrect key,  d₁ α is the hypothesis about the true key. The thresholds  A are  B determined from the given probabilities of type I and type II errors.

7. Practical implementation: from theory to key recovery

7.1. Key recovery algorithm based on statistical analysis

  1. Data collection.  All signatures  (r, s, z)corresponding to a single public key  are extracted from the Bitcoin blockchain Q.
  2. Preprocessing.  For each signature,   and  are calculated .t = s−1 r mod nb = s−1 z mod n
  3. Hypothesis testing.  The chi-square and Kolmogorov–Smirnov tests are used to test the uniformity of the distribution  k (indirectly, through the  t and  statistics b).
  4. Bias detection.  If the uniformity hypothesis is rejected, the nature of the bias is assessed: which bits  k are predictable (high-order, low-order, correlated with  t , or  b).
  5. HNP formulation.  A system of HNP equations is constructed:  kᵢ ≡ tᵢ d + bᵢ (mod n), where  kᵢ belongs to a known subset (for example,  ).kᵢ < 2L
  6. HNP solution.  Lattice algorithms (LLL, BKZ) or Fourier analysis methods (Bleichenbacher) are used to find  d. The number of required signatures depends on the offset value; for example, for a P-521 with nine high-order zero bits, 58–60 signatures are sufficient [reference:5].
  7. Verification.  The result  d is verified against several signatures: it is calculated   and verified that  .k = s−1(z + r d) mod n(k · G)x ≡ r mod n

7.2 Example: Attack based on nine zero-most significant bits (P-521)

Consider the NIST P-521 curve. The order is  . If the nonce generator uses SHA-512 without modulo reduction  , then  , meaning the most significant   bits are zero. This yields   known bits.n ≈ 2521nk < 2512521 − 512 = 9ℓ = 9

A lattice of dimension  ℓ + 2 (or greater, depending on the method) is constructed. After the basis is reduced, the LLL algorithm finds a short vector corresponding to  d. Experiments show that 58 signatures give a success probability > 0.5, and 60 guarantees recovery [reference:6].

Estimated number of signatures:  N ≈ log₂(n) / ℓ · C,
where C is a constant depending on the HNP solution method.

7.3 Software implementation (conceptual pseudocode)

def recover_private_key(signatures, n):
    # signatures: list (r, s, z)
    t_list = [s_inv * r % n for (r, s, z) in signatures]
    b_list = [s_inv * z % n for (r, s, z) in signatures]
    
    # Testing bias hypothesis (e.g. high bits = 0)
    # Build the lattice and run LLL
    lattice = build_hnp_lattice(t_list, b_list, n, known_bits=9)
    reduced = LLL(lattice)
    d = extract_key(reduced, n)
    
    # Verification
    for (r, s, z) in signatures:
        k = inverse(s, n) * (z + r * d) % n
        assert (k * G).x % n == r
    return d
    

Computational complexity.  Lattice reduction methods have complexity polynomial in the lattice dimension, which is proportional to the number of known bits. For  ℓ = 9 a lattice dimension, the complexity is small, and the attack can be performed in seconds on a typical computer.

8. Conclusion

This paper demonstrates how fundamental results in probability theory and stochastic financial mathematics, as outlined in the works of A. N. Shiryaev, can be directly applied to the cryptanalysis of ECDSA in Bitcoin transactions. Key findings:

  • The probabilistic nonce model  allows us to formalize the concept of “bias” and estimate its impact on the entropy of the secret number.
  • Statistical tests  (chi-square, Kolmogorov–Smirnov) provide tools for detecting anomalies in the distribution of nonces across publicly available signatures.
  • Stochastic processes and martingales  allow us to model nonce sequences and construct optimal private key estimates using filtering methods.
  • Bayesian inference and sequential analysis  (SPRT) determines the minimum number of signatures required to recover a key with a given strength.
  • Stochastic financial mathematics  provides a ready-made apparatus for analyzing nonce time series, including AR models, GARCH models, and optimal stopping problems.
  • Practical implementation  based on HNP and lattice algorithms allows for the recovery of real Bitcoin private keys in the presence of even a slight nonce bias.

Thus, the synthesis of classical probability theory and modern cryptography opens up powerful cryptanalysis methods that have already been confirmed in real-world attacks on blockchain infrastructure.

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

  1. Adaptive statistical tests for streaming blockchain analysis.  Developing sequential criteria capable of detecting nonce generation anomalies in real time as new blocks are mined. Using Shiryaev’s optimal stopping theory to minimize detection latency.
  2. Multivariate stochastic nonce models.  Transition from scalar AR(1) models to vector autoregressions (VARs) that account for correlations between nonces of different keys or between nonces and other transaction parameters (commission, input size, etc.).
  3. Bayesian nonparametric methods.  Using Dirichlet and Gaussian processes to model nonce prior distributions without assuming a specific parametric bias.
  4. Martingale methods for side-channel attacks.  Extending the martingale approach to scenarios where not only the signature but also indirect information about the nonce (signature time, power consumption, cache timings) is observed. This will allow for optimal estimation under conditions of partial observability.
  5. Stochastic control for choosing the attack moment.  The problem of choosing the moment when the accumulated information is sufficient for successful key recovery is formulated as an optimal control problem with a Bayesian criterion. Shiryaev’s optimal stopping methods provide a ready-made framework for this.
  6. Cross-chain nonce reuse analysis.  A study of nonce reuse across different blockchains (Bitcoin, Ethereum, Litecoin, etc.) as a two-dimensional point process. Application of point process theory and random measures to assess attack rates and make predictions.
  7. Quantum-Resistant Aspects of Probabilistic Cryptanalysis.  A study of how quantum random number generators affect the statistical properties of nonces and what new probabilistic models arise in the transition to post-quantum signature schemes.
  8. Automated cryptanalysis systems based on stochastic inference.  Development of software systems that combine blockchain data collection, Bayesian inference, lattice algorithms, and sequential analysis in a single pipeline, using Monte Carlo methods to estimate success probabilities.

The document was prepared based on the classical works of A. N. Shiryaev on probability theory and stochastic financial mathematics, as well as modern research on ECDSA cryptanalysis (LadderLeak, Biased Nonce Sense, Oops…I Did It Again, etc.).