Application of mathematical statistics (Borovkov A. A., 1984) to calculate the hidden number in the ECDSA signature and recover the Bitcoin private key

25.10.2026

Mathematical statistics, as interpreted by A. A. Borovkov, provides the cryptanalyst with a powerful and rigorous toolkit for attacking ECDSA. Hypothesis testing allows  one to detect  flaws in nonce generation where visual analysis fails. Parameter estimation and confidence intervals provide  a quantitative measure  of vulnerability. Asymptotically optimal tests provide  maximum power  in distinguishing between uniform and biased distributions. Combined with lattice theory methods (LLL/BKZ), statistical analysis allows one to recover the hidden number  k  and, consequently, the private key  d , even when the nonce is not exactly repeated but merely has a statistically significant bias.

The practical significance of this approach is confirmed by large-scale blockchain studies: on Bitcoin alone, thousands of private keys compromised due to faulty nonces have been recovered [reference:8]. The statistical methods outlined in Borovkov’s book remain relevant today, as they do not require knowledge of a specific PRNG implementation—simply a sample of signatures and computational resources for testing hypotheses.

1. Introduction

The ECDSA (Elliptic Curve Digital Signature Algorithm) is the basis for transaction authentication on the Bitcoin network. A critical security parameter of ECDSA is  the nonce  —a one-time random number  k , which must be generated uniformly, unpredictably, and never repeated. As large-scale blockchain analysis shows, even a slight deviation from the uniform distribution of the nonce or partial leakage of its bits allows for the recovery of the long-term private signature key [reference:0].

This paper demonstrates how the fundamental principles of mathematical statistics, systematized in A. A. Borovkov’s classic work, “Mathematical Statistics” (Moscow: Nauka, 1984), can be applied to  detect statistical anomalies in nonce ,  estimate the parameters of the latent distribution  , and  recover the latent number k,  followed by computing the private key. Particular attention is given to hypothesis testing, the maximum likelihood method, confidence intervals, and asymptotically optimal tests—the very sections that form the core of Borovkov’s book [reference:1].

2. Theoretical foundations of ECDSA

Let  E be an elliptic curve  over a finite field  F p  with a generator point  G  of order  n . The signer’s private key is an integer  d ∈ [1, n−1] ; the public key  Q = dG . To sign a message with a hash  z  , a nonce  k ∈ [1, n−1] is generated , the point  R = kG is calculated , and its x-coordinate is taken modulo  n  as  r . Then,

s = k −1 (z + rd) mod n .

The signature is a pair  (r, s) . The key equation for cryptanalysis is:

k = s −1 (z + rd) mod n .

If nonce  k  is known for at least one signature, the private key is calculated immediately:

d = (sk − z) r −1  mod n .

Thus, the problem of reconstructing  d  is reduced to the problem of reconstructing  k  or its significant part. This is where Borovkov’s statistical apparatus proves indispensable: it allows one  to detect the non-randomness of k’s  generation   and  estimate  its hidden bits.

3. The statistical nature of nonce and vulnerability

Ideally,  k  should be uniformly distributed over  {1, …, n−1} . However, in practice, ECDSA implementations allow:

  • Nonce reuse  (the same  k  for different messages) is an instant key compromise[reference:2].
  • Shifting the high or low bits  – for example, generating  k  from a shortened range or fixing some bits to zero[reference:3].
  • Correlating a nonce with a message hash or private key  is a rare but documented class of vulnerability found in the Bitcoin blockchain[reference:4].
  • Weak PRNG  – predictable sequences that lead to statistically detectable patterns[reference:5].

All these deviations leave a “statistical trace” in the signature set. The cryptanalyst’s task is to use mathematical statistics  to reject the uniformity hypothesis  and  estimate the bias parameters .

4. Mathematical apparatus from the book by A. A. Borovkov

A. A. Borovkov’s book “Mathematical Statistics” (1984) contains an exhaustive presentation of the following sections, directly applicable to the cryptanalysis of ECDSA:

Statistics section (according to Borovkov)Application in ECDSA cryptanalysis
Testing statistical hypotheses (§ 1–3 Ch. 4)Formulating the null hypothesis  H 0 : “nonce is uniformly distributed.” Constructing a goodness-of-fit test (chi-square, Kolmogorov–Smirnov) to detect bias.
Estimation of parameters (§ 2 Ch. 3)Estimating the probability of a zero bit appearing in the highest position of a nonce using the maximum likelihood method.
Confidence intervals (§ 4, Chapter 3)Constructing interval estimates for the proportion of “short” nonces and for the magnitude of the bias.
Asymptotically Optimal Tests (Chapter 5)Using likelihood ratio tests to distinguish hypotheses about the distribution of  k  in large samples of signatures.
Method of moments and empirical distributionsEstimation of the mathematical expectation and variance of the empirical distribution of reconstructed (partially known) nonces.

5. Using statistical methods to recover nonce and private key

5.1 Testing the hypothesis of uniformity of nonce

Let there be a sample of  m  signatures  (z i , r i , s i ) . For each signature,  the recovered nonce can be calculated  only if  d is known, but d is initially   unknown. However,  indirect statistics can be analyzed , for example, the distribution of the values  ​​of r i  (the x-coordinates of points  k i G ). For uniform  k,  the values  ​​of r i  must also be uniform on  [1, n−1] .

 According to Borovkov, the Pearson chi-square test is used  to test the simple hypothesis  H 0 : F = F 0  against the complex alternative  H 1 : F ≠ F 0 . We divide the range [1, n−1]  into  L  intervals and calculate the empirical frequencies  ν j . Statistics

χ 2  = Σ j=1 L  (ν j  − mp j ) 2  / (mp j )

as  m → ∞  is asymptotically distributed as  χ 2 L−1 . If the observed value exceeds the critical value, the uniformity hypothesis is rejected—this is the first signal of the presence of a vulnerability.

5.2 Estimation of bias parameters using the maximum likelihood method

Suppose that statistical analysis reveals that the most significant bit of the nonce   is zero  with probability p . Then k  can be represented as

k = 2 t  · u , where  u ∈ [0, 2 n−t −1] ,

that is,  t most significant bits are fixed to zero. If there are m  such signatures  , then the likelihood function

L(p) = p m  (1−p) m

(assuming that there are exactly  m  zero high-order bits in the sample). The maximum likelihood estimate  p̂ = 1  (if all observations are zero), indicating deterministic bias. In the more realistic case where a bit can take the values ​​0 or 1, the estimate  p̂  is calculated as the sample proportion.

Borovkov describes in detail the asymptotic normality of the maximum likelihood estimate, which allows one to construct a confidence interval for  p  and thereby assess  the reliability  of the detected bias.

5.3. Confidence intervals and model adequacy testing

Using Borovkov’s results on the distribution of estimates, one can construct  a (1−α) -confidence interval for the proportion of “short” nonces:

p̂ ± z α/2  √(p̂(1−p̂)/m) .

If the interval does not cover the value  1/2  (characteristic of a uniform distribution), the randomness hypothesis is rejected at significance level  α . This provides the cryptanalyst with  statistically valid  confirmation that the nonce generator is defective.

5.4 Asymptotically Optimal Tests and Likelihood Ratio

Borovkov develops a theory of asymptotically optimal tests for complex hypotheses. In the context of ECDSA, this means that for large  m,  it is possible to construct a test that distinguishes between a uniform distribution and a distribution with a known bias, with an error probability approaching zero. The logarithm of the likelihood ratio

Λ = Σ i=1 m  log [ f 1 (k i ) / f 0 (k i ) ]

serves as the basis for the decision rule. In practice, this allows for  automatic  classification of signatures as “generated by a defective PRNG” with a minimal probability of being missed.

6. Practical implementation: step-by-step algorithm

  1. Data collection.  All ECDSA signatures (fields  r,  s and message hash  z) for a given address or set of addresses are extracted from the blockchain.
  2. Finding duplicates  r.  If two messages are signed with the same  r , this means that nonce k has been reused  . In this case, the private key is calculated directly: k = (z 1  − z 2 ) (s 1  − s 2 ) −1  mod n , d = (s 1  k − z 1 ) r −1  mod n .
  3. Statistical analysis of distribution  r.  We use the chi-square test (Section 5.1) to test for uniformity. We plot a histogram of values  r ​​and visually assess the presence of peaks or valleys.
  4. Estimating the offset of the high-order bits.  For each signature, we calculate an approximate value  of k  using the formula  k ≈ s −1 (z + rd) , but  d  is unknown. However,  a difference method can be used : for two signatures with the same  r  (already found) or for signatures where  z + rd  is small, estimating  k  becomes possible. Alternatively, a lattice attack against the hidden numeric problem (HNP) is used, which exploits  knowledge of several high-order bits  of k [reference:6].
  5. Lattice construction.  A lattice basis is formed whose rows contain the coefficients  s i −1  r i  and the modulus  n . The LLL/BKZ method finds a short vector corresponding to the true private key  d . An example of Python code (using  fpylll) is given below.
  6. Verification.  The resulting  d  is verified using the public key  Q = dG  (compared with the known public key of the address).
from fpylll import IntegerMatrix, LLL, BKZ
from hashlib import sha256

def lattice_attack(signatures, n, known_bits=4):
    """
    signatures: список кортежей (r, s, z)
    n: порядок кривой (secp256k1)
    known_bits: число известных старших битов nonce (обычно 0)
    """
    m = len(signatures)
    # Масштабный коэффициент для балансировки решётки
    B = 2 ** (256 - known_bits)
    # Построение матрицы (m+2) x (m+2)
    M = IntegerMatrix(m + 2, m + 2)
    for i in range(m):
        M[i, i] = n
        M[m, i] = signatures[i][1] * pow(signatures[i][2], -1, n) % n
        M[m+1, i] = signatures[i][0] * pow(signatures[i][2], -1, n) % n
    M[m, m] = B // n
    M[m+1, m+1] = B
    # Редукция базиса
    LLL.reduction(M)
    # Поиск короткого вектора, содержащего приватный ключ
    for i in range(m + 2):
        vec = [M[i, j] for j in range(m + 2)]
        # Кандидат в d: последний элемент вектора, делённый на B
        candidate = vec[-1] // B
        if 0 < candidate < n:
            # Проверка: подходит ли ключ
            if verify_key(candidate, signatures):
                return candidate
    return None

def verify_key(d, signatures):
    """Проверка кандидата d по одной из подписей."""
    r, s, z = signatures[0]
    # Восстанавливаем k из d
    k = (s * d - z) * pow(r, -1, n) % n  # упрощённо
    # Проверяем, что r == x-координата kG (требует реализации EC-арифметики)
    return True  # заглушка

Note:  The code provided is for illustration purposes only. For real-world use, implementation of secp256k1 elliptic curve arithmetic is required, as well as signature preprocessing to obtain  partially known  nonce bits. Complete implementations are available in open source repositories, such as  ecdsa-break [  ecdsa-leakage-attackreference:7].

7. Conclusion

Mathematical statistics, as interpreted by A. A. Borovkov, provides the cryptanalyst with a powerful and rigorous toolkit for attacking ECDSA. Hypothesis testing allows  one to detect  flaws in nonce generation where visual analysis fails. Parameter estimation and confidence intervals provide  a quantitative measure  of vulnerability. Asymptotically optimal tests provide  maximum power  in distinguishing between uniform and biased distributions. Combined with lattice theory methods (LLL/BKZ), statistical analysis allows one to recover the hidden number  k  and, consequently, the private key  d , even when the nonce is not exactly repeated but merely has a statistically significant bias.

The practical significance of this approach is confirmed by large-scale blockchain studies: on Bitcoin alone, thousands of private keys compromised due to faulty nonces have been recovered [reference:8]. The statistical methods outlined in Borovkov’s book remain relevant today, as they do not require knowledge of a specific PRNG implementation—simply a sample of signatures and computational resources for testing hypotheses.

Directions for further research for cryptanalysis based on this area

  1. Adaptive sequential tests.  Developing statistical criteria that enable  real-time  detection of nonce anomalies as new transactions arrive, without the need to accumulate a huge sample. Borovkov’s methodology for asymptotically optimal tests can be extended to sequential analysis.
  2. Multivariate statistical analysis.  Investigation of joint distributions  (r, s, z)  and identification of correlations not apparent in univariate analysis. Application of goodness-of-fit tests for multivariate distributions (e.g., the chi-square test for multivariate contingency tables).
  3. Error-robust statistical estimation.  Development of robust methods for estimating nonce bias parameters under conditions where some signatures are generated correctly and others are defective (the contamination model). Using Borovkov’s ideas on large deviations to analyze the tails of distributions.
  4. Integration of statistics and machine learning.  Application of Bayesian and Monte Carlo methods to posteriorly estimate the probability that a given set of signatures was generated by a vulnerable PRNG. Comparison of the effectiveness of classical statistical tests and neural network anomaly detectors.
  5. Cryptanalysis with incomplete data.  Investigating the situation where only some bits of a nonce are known (e.g., as a result of side-channel attacks). Constructing statistical estimates for the remaining bits using the EM algorithm and maximum likelihood methods with incomplete data.
  6. Information-theoretic bounds.  Determining the minimum signature sample size required to reliably recover a private key for a given nonce bias level. Using the Cramer–Rao inequality and Fisher information to evaluate the effectiveness of statistical procedures.