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 distributions | Estimation 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
- Data collection. All ECDSA signatures (fields
r,sand message hashz) for a given address or set of addresses are extracted from the blockchain. - 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 . - Statistical analysis of distribution
r. We use the chi-square test (Section 5.1) to test for uniformity. We plot a histogram of valuesrand visually assess the presence of peaks or valleys. - 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].
- 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. - 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
- 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.
- 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).
- 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.
- 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.
- 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.
- 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.
