Chebyshev’s Inequality in ECDSA Cryptanalysis: From Measure Theory to Private Key Recovery

21.10.2026

In this paper, we demonstrated that Chebyshev’s inequality—a fundamental result in measure theory and probability theory—has direct and nontrivial applications in ECDSA cryptanalysis. From a measure-theoretic formulation linking the Lebesgue integral and set measure to practical statistical tests for nonce bias and subsequent private key recovery using lattice methods, this line of reasoning demonstrates the profound connection between classical analysis and modern cryptography.

Key results:

  • Chebyshev’s inequality in the form \(\Pr[|X — \mu| \geq \varepsilon] \leq \sigma^2/\varepsilon^2\) allows one to estimate the probability of extreme deviations of nonce from a uniform distribution using only the variance.
  • The embedding \(L_p \hookrightarrow L_{p,\infty}\), proved using Chebyshev’s inequality, provides a tool for analyzing the “heavy tails” of the nonce distribution and estimating the probability of occurrence of anomalously large or small values.
  • Practical tests based on these ideas allow nonce shifts to be detected in the public data of the Bitcoin blockchain, after which lattice attacks (LLL/BKZ) recover the private key.

Thus, Chebyshev’s inequality is not just an abstract mathematical result, but a working tool for a cryptanalyst, allowing one to move from observed data to the hidden parameters of a cryptosystem.

Content

1. Introduction

Cryptanalysis of the Elliptic Curve Digital Signature Algorithm (ECDSA) is traditionally associated with lattice methods, Hidden Number Problem (HNP) attacks, and nonce leakage analysis. However, there is a less obvious but fundamental connection between classical inequalities in measure and probability theory—in particular, Chebyshev’s inequality—and statistical analysis, which allows us to detect anomalies in nonce generation and ultimately recover the private key.

In this paper, we will show step by step how Chebyshev’s inequality in its measure-theoretic formulation (the connection between the Lebesgue integral and the set measure) and probabilistic formulation (Markov’s inequality as an analogue) is applied to:

  • construction of statistical criteria for deviation of nonce distribution from uniform;
  • estimates of the probability of extreme deviations that can be used to reconstruct the hidden number;
  • justifications for embedding spaces \(L_p\) into weak \(L_p\), which provides a tool for analyzing “heavy tails” in the nonce distribution.

We will also provide concrete Python code examples demonstrating the practical application of these ideas, and discuss how theoretical estimates translate into practical attacks on Bitcoin transactions.

2. Chebyshev’s inequality in measure theory and probability theory

2.1. Measure-theoretical formulation

Let \((X, \mathcal{S}, \mu)\) be a measure space, \(f: X \to [0, +\infty]\) be a non-negative measurable function, and \(c > 0\). Then Chebyshev’s inequality states:

\(\mu\{x \in X : f(x) \geq c\} \leq \frac{1}{c} \int_X f \, d\mu\)

This inequality describes the fundamental relationship between the Lebesgue integral and the measure of the set where the function exceeds a given threshold[reference:0]. More generally, for any nonnegative integrable function \(f\) and any \(c > 0\):

\(\mu(\{x : f(x) \geq c\}) \leq \frac{1}{c} \int f \, d\mu\)

The proof is based on the fact that on the set \(A_c = \{x : f(x) \geq c\}\) \(f \geq c\) holds, therefore, \(\int f \geq \int_{A_c} f \geq c \cdot \mu(A_c)\), from which the inequality follows[reference:1].

2.2. Probabilistic formulation (Markov and Chebyshev inequality)

In probability theory, the analogue of Chebyshev’s measure-theoretic inequality is  Markov’s inequality . For a non-negative random variable \(X\) and any \(\varepsilon > 0\):

\(\Pr[X \geq \varepsilon] \leq \frac{\mathbb{E}[X]}{\varepsilon}\)

This is a direct consequence of the measure-theoretic inequality when replacing the measure with a probability measure[reference:2].

From Markov’s inequality,  Chebyshev’s inequality is derived  in probabilistic form. For a random variable \(X\) with finite variance \(\sigma^2\) and mathematical expectation \(\mu\):

\(\Pr[|X — \mu| \geq k\sigma] \leq \frac{1}{k^2}\)

or in more general form:

\(\Pr[|X — \mu| \geq \varepsilon] \leq \frac{\sigma^2}{\varepsilon^2}\)

This inequality estimates the probability of a random variable deviating from its mean using only the second moment (variance). This form is most useful in cryptanalysis, as it allows one to estimate the probability of extreme nonce values.[reference:3]

Important:  Chebyshev’s inequality doesn’t require knowledge of the exact distribution, only its variance. This makes it an ideal tool for analyzing nonces in settings where the distribution is unknown but its moments can be estimated from a sample of signatures.

3. Embedding \(L_p\) into weak \(L_p\) and statistical estimates

Chebyshev’s inequality is also used to prove the embedding of the space \(L_p\) into the weak space \(L_{p,\infty}\). Recall the definition of a weak \(L_p\)-space:

\(\|f\|_{L_{p,\infty}} = \sup_{t > 0} t \cdot \mu(|f| > t)^{1/p} < \infty\)

From Chebyshev’s inequality it follows that if \(f \in L_p\), then \(f \in L_{p,\infty}\), and:

\(\|f\|_{L_{p,\infty}} \leq \|f\|_{L_p}\)

This embedding is fundamentally important for analyzing the “heavy tails” of a nonce distribution. If a nonce distribution has a finite moment of order \(p\), then the probability of a nonce falling into the region of extreme values ​​decreases as \(t^{-p}\). In ECDSA cryptanalysis, this means that even in the presence of “weak” nonces with anomalously large or small values, their contribution to the overall statistics is controlled by the moment of the distribution [reference:4].

Moreover, for practical attacks, this provides a theoretical justification for choosing a cutoff threshold: if we observe a nonce whose value exceeds \(k\) standard deviations, the probability of such an event under a uniform distribution does not exceed \(1/k^2\). This allows us to filter out “normal” signatures and focus on potentially vulnerable ones.

4. ECDSA and the Critical Role of Nonce

4.1. ECDSA Algorithm

Let \(\mathbb{G}\) be an elliptic curve with base point \(G\) of order \(n\). The private key is \(d \in [1, n-1]\), and the public key is \(Q = dG\). To sign a message with hash \(h\):

  1. A random nonce \(k \in [1, n-1]\) is selected.
  2. The point \(R = kG\) is calculated, its x-coordinate \(r = x(R) \bmod n\).
  3. Calculates \(s = k^{-1}(h + rd) \bmod n\).
  4. The signature is a pair \((r, s)\).

4.2. Vulnerability with a misplaced nonce

The security of ECDSA depends entirely on the uniformity and secrecy of \(k\). If \(k\) is not uniformly random, an attacker can recover \(d\). From the signature equation:

\(k = s^{-1}(h + rd) \bmod n\)

If the biases in the distribution of \(k\) are known (e.g., the high-order bits are always zero, or \(k\) lies in a narrow range), then the problem of recovering \(d\) reduces to the hidden number problem (HNP), which is efficiently solved by lattice methods[reference:5].

4.3 Typical sources of nonce bias

  • Nonce reuse  – if the same \(k\) is used for two signatures, then \(d\) is calculated algebraically.
  • The shift of the most significant bits  is due to errors in the random number generator.
  • Correlation with the message hash  – for example, \(k\) is formed from part of the hash and part of the private key[reference:6].
  • Hardware leaks  are timing attacks that allow one to find out a portion of the bits \(k\).

5. Application of Chebyshev’s inequality to nonce analysis

5.1. Statistical nonce model

Suppose we have collected \(m\) signatures \((r_i, s_i, h_i)\) with the same curve. For each signature, we can calculate the “residual”:

\(t_i = s_i^{-1} r_i \bmod n\)

Then from the signature equation it follows:

\(k_i = s_i^{-1} h_i + t_i d \bmod n\)

If nonces \(k_i\) are generated uniformly on \([0, n-1]\), then \(k_i\) can be considered a uniform random variable. However, if the generator is biased, the distribution of \(k_i\) deviates from uniform.

5.2. Estimating bias using Chebyshev’s inequality

Let \(X = k\) be a random variable nonce. If it is known that \(\mathbb{E}[X] = \mu\) and \(\mathrm{Var}(X) = \sigma^2\), then for any \(\varepsilon > 0\):

\(\Pr[|X — \mu| \geq \varepsilon] \leq \frac{\sigma^2}{\varepsilon^2}\)

If nonces are generated uniformly on \([0, n-1]\), then \(\mu = (n-1)/2\) and \(\sigma^2 = (n^2 – 1)/12\). Then the probability that a nonce deviates from the mean by more than \(k\) standard deviations does not exceed \(1/k^2\). For example, for \(k = 10\), this is less than \(1\%\). If we observe an abnormally high proportion of nonces in a sample of signatures deviating by 10 or more standard deviations, this is a statistically significant indication of bias.

5.3. Applying the \(L_p\) embedding to “heavy tails”

If the distribution of nonce has a finite moment of order \(p > 2\), then the embedding \(L_p \hookrightarrow L_{p,\infty}\) implies that:

\(\Pr[|X| > t] \leq \frac{\mathbb{E}[|X|^p]}{t^p}\)

This allows one to estimate the probability of extremely large nonce values ​​even without knowing the exact distribution. In the context of ECDSA, this means that if an attacker can measure the \(p\)th moment of the nonce distribution (for example, by analyzing many signatures), they can predict the probability of a nonce appearing in the dangerous zone.

5.4 Practical Example: Detecting High-Bit Shifts

Consider the scenario where a nonce is generated with the most significant \(b\) bits cleared. Then \(k \in [0, 2^{nb} – 1]\). The expected value of such a nonce is \(\mu’ = (2^{nb} – 1)/2\), which is significantly less than the uniform \(\mu = (2^n – 1)/2\). The variance is also reduced. Chebyshev’s inequality allows one to estimate how much the observed distribution of \(k\) (reconstructed from signatures with known \(d\) or through statistical methods) deviates from the expected uniform distribution.

6. Practical attack: statistical analysis and key recovery

6.1 Data collection

Suppose we have access to the Bitcoin blockchain and can extract multiple ECDSA signatures from a single address. For each signature \((r, s, h)\), we can compute:

\(u_i = s_i^{-1} h_i \bmod n, \quad v_i = s_i^{-1} r_i \bmod n\)

Then \(k_i = u_i + v_i d \bmod n\). If \(d\) is unknown, we cannot calculate \(k_i\) directly. However, we can analyze the statistics of \(v_i\) and \(u_i\), which are related to \(k_i\) linearly.

6.2 Test for uniformity using Chebyshev’s inequality

For a sample of \(m\) signatures, we calculate the empirical mean and variance of \(w_i = v_i\) (or another linear combination). If the nonces are uniform, then \(w_i\) should also be uniformly distributed modulo \(n\). We check whether the proportion of \(w_i\) deviating from the mean by more than \(k\sigma\) exceeds the theoretical limit of \(1/k^2\). If it does, this is a signal of bias.

import numpy as np
from scipy import stats

def analyze_nonce_bias(signatures, n, k_sigma=5):
    """
    signatures: список кортежей (r, s, h)
    n: порядок группы
    k_sigma: порог в стандартных отклонениях
    """
    # Вычисляем v_i = s^{-1} * r mod n
    v = np.array([(pow(s, -1, n) * r) % n for r, s, h in signatures])
    
    # Эмпирическое среднее и дисперсия
    mu_emp = np.mean(v)
    sigma_emp = np.std(v, ddof=1)
    
    # Теоретические значения для равномерного распределения на [0, n-1]
    mu_theor = (n - 1) / 2
    sigma_theor = np.sqrt((n**2 - 1) / 12)
    
    # Доля отклонений более чем на k_sigma стандартных отклонений
    deviations = np.abs(v - mu_theor)
    threshold = k_sigma * sigma_theor
    fraction_outside = np.mean(deviations > threshold)
    
    # Граница Чебышёва
    chebyshev_bound = 1 / (k_sigma ** 2)
    
    print(f"Эмпирическое среднее: {mu_emp:.2f}")
    print(f"Теоретическое среднее: {mu_theor:.2f}")
    print(f"Эмпирическая дисперсия: {sigma_emp**2:.2e}")
    print(f"Теоретическая дисперсия: {sigma_theor**2:.2e}")
    print(f"Доля отклонений > {k_sigma}σ: {fraction_outside:.6f}")
    print(f"Граница Чебышёва (1/{k_sigma}²): {chebyshev_bound:.6f}")
    
    if fraction_outside > chebyshev_bound:
        print("⚠️ ВНИМАНИЕ: Обнаружено статистически значимое смещение nonce!")
        return True
    else:
        print("✅ Смещение не обнаружено (в пределах границы Чебышёва).")
        return False

6.3. Proceeding to private key recovery

Having detected the bias, we can apply lattice methods to solve HNP. If the nonces have a bias in the high-order bits (e.g., \(k_i < 2^{nb}\)), then the problem reduces to finding \(d\) such that:

\(|k_i — u_i — v_i d| \leq 2^{nb}\)

This is the classic formulation of HNP, which is solved using the LLL algorithm. Here’s an example of constructing the lattice:

def build_lattice(signatures, n, B):
    """
    Построение решётки для HNP.
    signatures: список (r, s, h)
    n: порядок группы
    B: граница смещения (например, 2^{n-b})
    """
    m = len(signatures)
    # Матрица размером (m+1) x (m+1)
    M = np.zeros((m + 1, m + 1), dtype=object)
    
    for i in range(m):
        r, s, h = signatures[i]
        M[i, i] = n
        M[m, i] = (pow(s, -1, n) * r) % n  # v_i
        M[i, m] = (pow(s, -1, n) * h) % n  # u_i
    
    M[m, m] = B // n if B > n else 1
    
    return M

After reducing the lattice basis using LLL, the desired vector contains information about \(d\). In practice, for the 256-bit secp256k1 curve, 3–5 signatures leaking 4–5 high-order bits of the nonce are sufficient to successfully recover the key in seconds [reference:7].

6.4. Real-World Example: Bitcoin Wallet Attack

Research by Breitner and Heninger (2018) showed that hundreds of Bitcoin private keys were compromised precisely because of biased nonces. Their work used a statistical analysis of nonce distributions, based on ideas similar to Chebyshev’s inequality, to identify signatures with abnormally short nonces. A lattice attack then recovered the private keys [reference:8].

Key takeaway:  Chebyshev’s inequality provides a theoretical basis for constructing statistical tests that can reliably detect biases in nonce generation. These tests do not require knowledge of the private key and operate exclusively on public blockchain data.

7. Conclusion

In this paper, we demonstrated that Chebyshev’s inequality—a fundamental result in measure theory and probability theory—has direct and nontrivial applications in ECDSA cryptanalysis. From a measure-theoretic formulation linking the Lebesgue integral and set measure to practical statistical tests for nonce bias and subsequent private key recovery using lattice methods, this line of reasoning demonstrates the profound connection between classical analysis and modern cryptography.

Key results:

  • Chebyshev’s inequality in the form \(\Pr[|X — \mu| \geq \varepsilon] \leq \sigma^2/\varepsilon^2\) allows one to estimate the probability of extreme deviations of nonce from a uniform distribution using only the variance.
  • The embedding \(L_p \hookrightarrow L_{p,\infty}\), proved using Chebyshev’s inequality, provides a tool for analyzing the “heavy tails” of the nonce distribution and estimating the probability of occurrence of anomalously large or small values.
  • Practical tests based on these ideas allow nonce shifts to be detected in the public data of the Bitcoin blockchain, after which lattice attacks (LLL/BKZ) recover the private key.

Thus, Chebyshev’s inequality is not just an abstract mathematical result, but a working tool for a cryptanalyst, allowing one to move from observed data to the hidden parameters of a cryptosystem.

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

  1. Generalization to multivariate nonce distributions.  Chebyshev’s inequality admits multivariate generalizations (Chebyshev–Cantelli inequality). Examining joint nonce distributions for multiple signatures can reveal correlations not detectable by univariate methods.
  2. Application to other cryptosystems.  A similar analysis applies to Schnorr signatures, EdDSA, and other schemes where security depends on the uniformity of the secret nonce. Studying the \(L_p\) embeddings for these schemes can yield new statistical criteria.
  3. Adaptive thresholds based on higher-order moments.  Chebyshev’s inequality uses only the second moment. Using higher-order moments (Chebyshev’s inequality for higher moments) can provide more precise bounds on the probabilities of extreme deviations, allowing for the detection of more subtle biases.
  4. Combining with machine learning.  Statistical tests based on Chebyshev’s inequality can be used as features for machine learning models that classify signatures as “normal” or “suspicious.” This opens the way to automated cryptanalysis of large blockchains.
  5. Nonce time series analysis.  If nonces are generated sequentially, Chebyshev’s inequality can be applied to autocorrelation functions and spectral densities, revealing periodicities or long-term dependencies in the random number generator.
  6. Measure-theoretic estimates for side-channel attacks.  Side-channel leakages (timing, power) can be formalized in terms of a measure on the trace space. Chebyshev’s inequality allows one to estimate the probability of a successful attack given the noise level.
  7. A study of \(L_p\) embeddings for weak spaces in the context of post-quantum cryptography.  With the development of post-quantum signature schemes (e.g., on lattices), the question of the statistical stability of their nonces arises. Measure-theoretic methods can be adapted to analyze these new schemes.

Note:  All code examples are provided for illustrative purposes and require adaptation for real-world cryptographic libraries and working with large integers. For practical applications, it is recommended to use specialized libraries, such as those  fpylll for lattice computations and  ecdsa signatures.