Applying Markov’s Inequality to ECDSA Cryptanalysis. Recovering a Bitcoin Private Key via Nonce Analysis.

21.10.2026

Markov’s inequality, one of the simplest results in probability theory, plays  a fundamental role in the cryptanalysis of ECDSA . It provides a rigorous mathematical framework for:

  • detection of statistical anomalies in the distribution of nonces across public signatures;
  • estimates of the probability of false positives in statistical testing;
  • determining the minimum number of signatures required for a reliable attack;
  • analysis of the stability of lattice methods to random fluctuations.

The practical significance of these theoretical results has been confirmed  by mass recovery of Bitcoin private keys  in real-world conditions, making the problem of high-quality nonce generation one of the critical vulnerabilities in modern cryptocurrency systems.

Understanding the relationship between abstract probabilistic inequalities and specific cryptographic attacks allows us not only to effectively identify existing vulnerabilities, but also

Content

1. Introduction

ECDSA (Elliptic Curve Digital Signature Algorithm) is the cornerstone of transaction security in the Bitcoin network and many other cryptocurrencies. However, contrary to popular belief, the strength of ECDSA depends not only on the difficulty of the elliptic curve discrete logarithm problem (ECDLP) but also on  the quality of the generation of the ephemeral secret number —  the   so-called  nonce . Any deviation  from a uniform  kdistribution   creates a statistical vulnerability that can be exploited to recover the long-term private key.k[1, n-1]

Markov’s inequality, a fundamental result in probability theory, allows one to estimate the probability of large deviations in a random variable, knowing only its expected value. It is precisely this  minimal requirement for prior data  that makes Markov’s inequality an exceptionally valuable tool in cryptanalysis: by observing only public outputs of ECDSA signatures, an attacker can obtain statistical estimates that, through Markov’s inequality, are transformed into strict probability bounds sufficient to detect nonce drift and subsequently recover the key.

2. Markov’s inequality: mathematical essence

Markov’s inequality  (in probability theory) states that if  X is a non-negative random variable with finite mathematical expectation  E[X], then for any  a > 0:

P(X ≥ a) ≤ E[X] / a

Equivalent form of writing via parameter  ε > 0:

P(X ≥ ε · E[X]) ≤ 1/ε

Markov’s inequality is  the most elementary tail inequality : it requires only the existence of the first moment and imposes no restrictions on the distribution [reference:0]. Many stronger inequalities (Chebyshev’s, Chernoff’s, Hoeffding’s) are obtained by applying Markov’s inequality to suitably transformed random variables [reference:1].

In a cryptographic context, Markov’s inequality allows one to solve the inverse problem: using the observed  sample mean of a  random variable to estimate the probability that the true value (or the associated secret) lies within a certain range. This ability makes it a key tool for  statistical distinguishing attacks  —attacks aimed at distinguishing between distributions.

The key idea behind its application in cryptanalysis is  that if an observed statistic (for example, the sample mean of some function of signatures) significantly exceeds the expected value under the hypothesis of a uniform nonce, Markov’s inequality provides a strict upper bound on the probability of such an excess,  assuming randomness . A small value of this bound allows one to reject the uniformity hypothesis and proceed to an attack.

3. ECDSA and the Critical Role of Nonce

The ECDSA algorithm over an elliptic curve with order  n and base point  G works as follows. To sign a message with a hash  z and a private key  d:

  1. An ephemeral secret  k ∈ [1, n-1] (nonce) is generated.
  2. The point is calculated  R = kG, and  r = x(R) mod n.
  3. Calculated  s = k⁻¹(z + rd) mod n.
  4. Signature – pair  (r, s).

From the signature equation follows the fundamental relationship:

k ≡ s⁻¹ · z + s⁻¹ · r · d (mod n)

or, in a more convenient form for attacks:

d ≡ r⁻¹ · (s · k − z) (mod n)

Thus,  knowledge of even one nonce  k completely reveals the private key d [reference:2]. Moreover, even  partial  leakage of information  k (for example, a shift in the high-order bits) can be recovered  d with a sufficient number of signatures. ECDSA is extremely sensitive to the quality of the nonce: even a shift of less than one bit can lead to complete key recovery [reference:3].

In Bitcoin, hardware random number generators (RNGs) or deterministic schemes (RFC 6979) are often used to generate nonces. However,  software bugs, weak RNGs, and side-channel leaks  have repeatedly resulted in biased nonces appearing in real transactions, making mass private key recovery possible[reference:4].

4. Application of Markov’s inequality to nonce analysis

Let us consider how Markov inequality is applied to  detect nonce bias  and  estimate the required number of signatures  for an attack.

4.1. Biased Nonce Model

Let nonce  k be generated not uniformly, but rather according to some distribution skewed toward small values. A typical example:  truncation  —generating  k a random number from  [1, 2^m] instead of  [1, n-1], where  m < log₂ n. Then  k has the expected value  E[k] ≈ 2^m / 2 = 2^{m-1}, which is  significantly less than n/2 .

Let us define an indicator random variable:

X = 1, если k < n/2 (то есть старший бит k равен 0);
X = 0 в противном случае.

For uniform  k on ,  [1, n-1] we have  P(X=1) ≈ 1/2 and  E[X] ≈ 1/2. If  k is biased toward small values, then  P(X=1) > 1/2, and the sample mean  X̄ for  N signatures will systematically exceed  1/2.

4.2 Markov’s inequality for estimating the probability of a false rejection

We apply Markov’s inequality to a random variable  Y = (X - 1/2)²that is non-negative and has a mathematical expectation  E[Y] = Var(X) ≤ 1/4 (since it  X is Bernoulli). Then, for any  a > 0:

P( (X̄ - 1/2)² ≥ a ) ≤ E[(X - 1/2)²] / (N · a) ≤ 1 / (4 N a)

This provides  a tight upper bound on the probability  that the observed deviation of the sample mean from  1/2 will exceed  √a , given that the nonce was uniform . If this deviation is large for real data and the calculated bound is small (e.g.,  10⁻⁶), the uniformity hypothesis is rejected with high statistical significance.

4.3 Estimating the number of signatures for an attack

Let  δ = |P(X=1) - 1/2| be the magnitude of the bias. With  N signatures, the sample mean  X̄ is concentrated around the true mean  P(X=1) with a standard deviation of  σ = √(P(1-P)/N) ≤ 1/(2√N). To reliably detect the bias  δ (e.g., with a margin of  3σ), it is necessary:

δ > 3 / (2√N) ⟹ N > 9 / (4 δ²)

This is  a necessary condition , which follows from Markov’s inequality and its corollaries. For example, detecting a bias  δ = 0.01 (a 1% deviation from uniformity) requires  N > 22 500 signatures. In practice, attacks on Bitcoin keys often collect tens of thousands of signatures, which is consistent with this estimate [reference:5].

5. Statistical attacks: Bleichenbacher’s method

Historically, the first method to exploit biased nonces was  a purely statistical attack by Daniel Bleichenbacher  (2000), based on Fourier analysis and not requiring lattice computations[reference:6].

5.1. The idea of ​​the method

The signature equation  k ≡ s⁻¹(z + rd) mod n implies that for a true key,  d the values  k ​​form a “correct” sequence. If the nonce is biased (for example, the most significant bits are more often 0), then for  the correct  candidate  , d the calculated values  k ​​will exhibit this bias, while for incorrect candidates, they will appear uniform.

Bleichenbacher proposed using  the discrete Fourier transform  to detect periodicity in a distribution  k. For each candidate,  d' the following statistic is calculated:

B(d') = | (1/N) Σ_{i=1}^N exp(2πi · (s_i⁻¹(z_i + r_i d') mod n) / n) |

If true,  d the value  B(d) significantly exceeds the values ​​for random candidates.  Markov’s inequality  allows us to estimate the probability that such an excess arose by chance, and thus establish a threshold for candidate selection.

5.2 Connection with Markov’s inequality

The statistic  B(d') is the sample mean of complex exponential functions. Its mathematical expectation  k is zero for a uniform distribution. Apply Markov’s inequality to  |B(d')|²:

P( |B(d')|² ≥ a ) ≤ E[ |B(d')|² ] / a = (1/N) / a

Thus, the probability of a false peak decreases as  1/(N a). This provides a strict criterion: if for some  d' value  |B(d')|² of exceeds  N · a, the randomness hypothesis is rejected with an error probability of no more than  1/a. In practice, Bleichenbacher’s method allowed recovery of 384-bit ECDSA keys with a 5-bit nonce leak from 4000 signatures [reference:7].

5.3. Advantages and disadvantages

AspectCharacteristic
Required data volumeLarge (thousands–tens of thousands of signatures)
Error toleranceHigh (works with leak errors)
Computational complexityO(N · n) for exhaustive search; optimized via FFT
Minimum displacementLess than 1 bit (theoretically any δ > 0)

6. Lattice attacks and the hidden number problem (HNP)

A more powerful and efficient approach is to reduce the ECDSA key recovery problem with a known nonce bias to  the Hidden Number Problem (HNP)  and solve it using lattice basis reduction (LLL, BKZ) methods [reference:8].

6.1. HNP staging for ECDSA

Let’s assume that for each signature  i the nonce  k_i lies in a certain interval  [0, 2^ℓ) (that is,  ℓ the most significant bits are zero). Then:

k_i = s_i⁻¹(z_i + r_i d) mod n, причём 0 ≤ k_i < 2^ℓ

This can be rewritten as:

| s_i⁻¹ r_i d − s_i⁻¹ z_i + n · t_i | < 2^ℓ

for some integers  t_i. This is a system of linear inequalities with respect to the unknown  d and auxiliary variables  t_i. Such systems are naturally formulated as problems of finding a short vector in a lattice.

6.2 Lattice construction and the LLL algorithm

A lattice of dimension  N+1 (where  N is the number of signatures) is constructed with basis vectors:

B = [ n    0    ...  0    0
      0    n    ...  0    0
      ...
      0    0    ...  n    0
      α₁   α₂   ...  α_N  B/n ]

where  α_i = s_i⁻¹ r_i mod n, and  B is a scaling parameter (usually  B ≈ 2^ℓ). Using the  LLL  (Lenstra–Lenstra–Lovász) algorithm or its more powerful variant,  BKZ,  finds short vectors in this lattice. One of them, with high probability, contains the desired private key  d[reference:9].

The role of Markov’s inequality  here is to estimate the probability of success: the length of the desired vector is proportional to  2^ℓ, and the length of the random vectors is  n. Markov’s inequality allows us to rigorously demonstrate that for sufficiently large  N and small ,  ℓ the probability that the random grid contains a vector shorter than the desired one is exponentially small.

6.3 Comparison with statistical attacks

CriterionStatistical Attack (Bleichenbacher)Lattice attack (LLL/BKZ)
Number of signaturesVery large (10⁴–10⁵)Moderate (10²–10³)
Minimum displacementAny (even < 1 bit)Typically ≥ 2–3 bits
Computational complexityFFT, O(N log N)LLL/BKZ, polynomial in N
Error toleranceHighAverage

7. Practice: Bitcoin Key Recovery

The most famous example of the practical application of the described methods is the work  “Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies”  (2019), in which the authors analyzed millions of signatures in the Bitcoin and Ethereum blockchains and  recovered hundreds of private keys [reference:10].

7.1. Mechanisms for the emergence of biased nonces in Bitcoin

  • Nonce reuse:  If two signatures have the same  k, the key is calculated directly:  d = (s₁z₂ − s₂z₁) / (r₁s₂ − r₂s₁) mod n. This is a classic example of the complete failure of ECDSA.
  • Weak RNGs:  Some wallets used predictable generators (e.g. time-based or counter-based), which resulted in systematic bias  k.
  • Implementation errors:  for example, generation  k with truncation to 128 bits instead of 256, which gives  ℓ ≈ 128 known zero high bits.

A 2019 paper showed that even  a 128-bit nonce truncation  (i.e.  ℓ = 128) with ~30 signatures allows the key to be recovered in seconds using LLL[reference:11].

7.2. Step-by-step attack scenario

  1. Data collection:  All transactions signed by the same public key are extracted from the blockchain. For each signature, the  (r, s, z).
  2. Bias detection:  Using statistical tests (based on Markov inequalities), the hypothesis of uniformity is tested  k. If bias is detected, proceed to the next step.
  3. HNP formulation:  a system of inequalities is constructed  0 ≤ k_i < 2^ℓ.
  4. LLL/BKZ solution:  construct a lattice and apply basis reduction. The resulting short vector yields a candidate for  d.
  5. Verification:  Checks that  d · G it matches the public key.

Real-world result:  In 2019, researchers recovered  over 300 Bitcoin private keys  and dozens of Ethereum, Ripple, SSH, and HTTPS keys using exclusively public blockchain data[reference:12].

8. Limitations and countermeasures

8.1 Limitations of the methods

  • Statistical attacks  require very large amounts of data (tens of thousands of signatures), which is not always available.
  • Lattice attacks  are effective for  ℓ ≥ 2–3 bits of known bias; for  ℓ < 1 LLL/BKZ bits they may fail, requiring hybrid methods[reference:13].
  • If the nonce is generated  by a cryptographically strong RNG  and does not leak, attacks are impossible.

8.2. Countermeasures

  • RFC 6979:  Deterministic nonce generation based on HMAC-SHA256 from a private key and a message hash. This eliminates the dependence on RNG and makes it  k pseudo-random with guaranteed quality [reference:14].
  • Hardware RNGs with post-processing:  using certified generators (FIPS 140-2) with entropy estimation.
  • Range checking:  Rejects  kout-of-range  [1, n-1] or abnormally structured bits.
  • Blockchain monitoring:  Regularly scanning transactions for recurring  r or statistical anomalies.

9. Conclusion

Markov’s inequality, one of the simplest results in probability theory, plays  a fundamental role in the cryptanalysis of ECDSA . It provides a rigorous mathematical framework for:

  • detection of statistical anomalies in the distribution of nonces across public signatures;
  • estimates of the probability of false positives in statistical testing;
  • determining the minimum number of signatures required for a reliable attack;
  • analysis of the stability of lattice methods to random fluctuations.

The practical significance of these theoretical results has been confirmed  by mass recovery of Bitcoin private keys  in real-world conditions, making the problem of high-quality nonce generation one of the critical vulnerabilities in modern cryptocurrency systems.

Understanding the relationship between abstract probabilistic inequalities and specific cryptographic attacks allows us not only to effectively identify existing vulnerabilities, but also to design more secure signature schemes that are resistant to statistical and lattice cryptanalysis.


Directions for further research for cryptanalysis based on this area

  1. Developing adaptive statistical tests using Markov inequalities for nonstationary nonce distributions.  Existing methods assume a fixed bias. However, in real systems, the distribution  k may change over time (for example, due to RNG degradation). Applying Markov inequalities to sliding observation windows will allow for the detection of evolving leaks.
  2. Combining Markov inequality with machine learning methods to identify hidden patterns in nonces.  Neural network models can detect nonlinear relationships that are undetectable by classical statistics. Markov inequality can serve as a theoretical basis for assessing the validity of the inferences of such models.
  3. Analysis of Markov Inequality for Quantum Nonce Distributions.  With the development of quantum computing and quantum random number generators, new distribution models are emerging. Studying the behavior of Markov inequalities in a quantum context may reveal new classes of attacks against post-quantum signature schemes.
  4. Applying Markov’s inequality to the analysis of side-channel leaks in hardware wallets.  Power consumption and electromagnetic radiation can provide statistical information about the nonce. Markov’s inequality allows for a rigorous assessment of the probability that the observed fluctuations are due to the secret and not noise.
  5. Developing hybrid statistical-lattice attacks for the case of less than 1 bit of bias.  Although Bleichenbacher demonstrated the feasibility of the attack for arbitrarily small biases, practical effectiveness  δ < 2⁻¹⁰ remains low. Combining ideas from Markov inequality with modern lattice reduction algorithms (e.g., G6K) can improve this situation.
  6. A study of Markov inequality in the context of attacks against deterministic nonce schemes (RFC 6979).  Although RFC 6979 is considered secure, it may be vulnerable to attacks based on linked messages. Markov inequality can help estimate the success rate of such attacks.
  7. Building formal verification frameworks for assessing the security of ECDSA implementations based on probabilistic inequalities.  Automated security proofs using Markov inequalities as a basic tool will enable the creation of certified implementations resistant to statistical cryptanalysis.

This document is based on an analysis of scientific publications on ECDSA cryptanalysis and probability theory.
All methods mentioned are intended solely for educational and research purposes in the field of information security.