Abstract. This paper presents a study devoted to the application of the probabilistic framework outlined in N. I. Chernova’s textbook “Probability Theory” (Novosibirsk, 2007) to one of the most pressing problems in modern cryptography—cryptanalysis of the ECDSA scheme used in the Bitcoin blockchain. The focus is on the problem of the hidden number (nonce) and methods for recovering the private key through statistical analysis of biases in its generation. This paper is intended for specialists in the fields of cryptography, cryptanalysis, and applied probability theory.
This paper demonstrated that N. I. Chernova’s textbook “Probability Theory” contains fundamental mathematical apparatus that finds direct and non-trivial application in the cryptanalysis of the ECDSA scheme used in the Bitcoin blockchain.
Key findings:
- The Bernoulli distribution and the binomial distribution allow us to formalize the problem of detecting bias in the high-order bits of a nonce and to estimate the number of observations required for a statistically significant conclusion.
- Conditional probability and independence provide a tool for analyzing correlations between nonce bits that may arise due to flaws in random number generators.
- Limit theorems (the law of large numbers, the central limit theorem, Chernoff’s inequality) provide theoretical bounds for estimating the success rate of cryptanalytic attacks.
- The hidden number problem (HNP) is a natural bridge between the probabilistic nonce generation model and lattice key recovery algorithms.
The practical significance of these results is confirmed by real attacks on the Bitcoin blockchain, during which hundreds of private keys were recovered [reference:8]. This demonstrates that even an “economic” course in probability theory contains tools critical to cybersecurity.
1. Introduction
N. I. Chernova’s textbook “Probability Theory,” published by Novosibirsk State University in 2007, contains the full lecture course taught by the author to first-year students in the Economics Department of NSU’s Faculty of Economics.[reference:0] The textbook covers the fundamentals of measure theory, combinatorics, elementary and analytical probability theory, and limit theorems in probability theory.[reference:1] Although the course is aimed at students majoring in economics, its mathematical apparatus proves surprisingly relevant in a field as far removed from economics as the cryptanalysis of digital signatures.
The ECDSA (Elliptic Curve Digital Signature Algorithm) is one of the most widely used digital signature schemes and underlies Bitcoin transaction security. Its cryptographic strength is based on the difficulty of the discrete logarithm problem on an elliptic curve. However, as practice shows, ECDSA security critically depends on the quality of the generation of an ephemeral secret value—the nonce (a single-use number). Any deviation from a uniform nonce distribution, however small, can lead to the complete recovery of the long-term private key.
In this paper, we will demonstrate step by step how the principles of probability theory outlined in Chernova’s textbook are applied to formalize the problem of analyzing nonce biases and constructing effective cryptanalytic attacks.
2. Mathematical foundations of ECDSA and the role of nonce
The ECDSA scheme is defined over a finite field and a group of points of an elliptic curve of order n . The process of generating a signature for a message m with a private key d involves the following steps:
- A random number k is selected from the interval [1, n − 1] – this is the nonce.
- The point kP = ( x ₁, y ₁) is calculated, where P is the base point of the curve.
- Calculate r = x ₁ mod n .
- Calculate s = k ⁻¹( h ( m ) + d · r ) mod n , where h ( m ) is the hash of the message.
- The signature is a pair ( r , s ).
The attack vector considered in this paper is based on the fact that if the nonce k is not uniformly distributed over the interval [1, n − 1] but has some bias, then accumulating a sufficient number of signatures allows one to recover the private key d . This assertion goes back to the fundamental work of Boneh and Venkatesan, who formalized the so-called Hidden Number Problem (HNP) [reference:2].
3. Probabilistic model of nonce generation
In an ideal ECDSA scheme, nonce k should be uniformly distributed over the set {1, 2, …, n − 1}. Let K denote the random variable corresponding to the generated nonce. Then, for any i ∈ [1, n − 1]:
P(K = i) = 1/( n − 1).
However, in practice, ECDSA implementations can tolerate various types of biases. Let’s consider the most common models.
3.1 Bernoulli model for the high-order bits of nonce
The Bernoulli scheme, discussed in detail in Chernova’s textbook (Chapter 5), considers a sequence of independent trials, each of which has only two possible outcomes—”success” and “failure,” with “success” occurring with probability p [reference:3]. Applied to nonce analysis, this means the following.
Let K be a random variable uniformly distributed over the interval [0, 2 L −1], where L is the order of the curve. Let us consider the most significant bit of the number K . Due to the uniformity,
P(most significant bit = 0) = P(most significant bit = 1) = 1/2.
Now suppose that the ECDSA implementation has a defect that causes the high-order bit of the nonce to be zero with some probability p ≠ 1/2. This means that the event “high-order bit = 0” occurs with probability p , and the event “high-order bit = 1” occurs with probability 1 − p . If such observations are made for N independent signatures, then the number of signatures in which the high-order bit of the nonce is zero follows a binomial distribution:
P( X = m ) = C( N , m ) p m (1− p ) N − m ,
where X is the number of “successes” (zero high-order bits), and m is the specific number of observed successes. According to the De Moivre-Laplace theorem, for large N , the distribution of X is approximated by a normal distribution with mean Np and variance Np (1− p ). This allows us to construct statistical tests for detecting bias.
3.2 Conditional Probability and Independence
The most important concept of probability theory, introduced in Chapter 3 of Chernova’s textbook, is conditional probability. The conditional probability of event A given that event B has occurred is called the quantity
P( A | B ) = P( A ∩ B ) / P( B ), for P( B ) > 0.
In the context of nonce analysis, conditional probability allows us to formalize the relationship between observed values and hidden parameters. For example, if the most significant bit of the nonce is known to be zero for a given signature, what is the probability that the second-most significant bit is also zero? In an ideal model, these events are independent, and the answer is 1/2. However, in the presence of bias, the conditional probability can differ significantly from 1/2, providing additional information for an attack.
The property of independence of events, also discussed in the tutorial, means that
P( A ∩ B ) = P( A ) · P( B ).
If the nonce generator has defects that lead to correlation between bits, then the independence condition is violated, and this can be used to construct more effective attacks.
3.3 Nonce Length Distribution
Minerva showed that many ECDSA implementations leak nonce length information through time delays [reference:4]. If K is a random variable uniformly distributed on [0, n − 1], then its bit length L ( K ) = ⌊log₂ K ⌋ + 1 is also random. For uniform K , the probability that L ( K ) = j is 2 j −1 / n for j = 1, 2, …, L max . This is an exponentially decaying distribution: about half of the nonces have the most significant bit equal to zero, about a quarter have the two most significant bits equal to zero, and so on.
If the ECDSA implementation somehow “reveals” the nonce length (for example, through the execution time of the operation), then the attacker gains information about the number of high-order zero bits. This, in turn, creates a bias sufficient to solve the HNP problem.
4. Hidden Number Problem (HNP) and its Probabilistic Nature
The hidden number problem was introduced by Boneh and Venkatesan in 1996 to analyze the bit security of the Diffie–Hellman scheme and has since found widespread application in (EC)DSA cryptanalysis [reference:5]. The formulation of the HNP is closely related to probabilistic concepts.
Let q be a prime number (the order of the group), α ∈ ℤ q be a hidden number (in our case, the private key d ). Given pairs ( t ₁, a ₁), ( t ₂, a ₂), …, ( t ₘ, a ₘ), where aᵢ = MSB l ( tᵢ · α mod q ) are the l most significant bits of the product tᵢ · α modulo q . It is required to find α .
In the context of ECDSA, each signature equation can be rewritten as
tᵢ d + bᵢ ≡ kᵢ ( mod n ),
where tᵢ = sᵢ ⁻¹ rᵢ , bᵢ = sᵢ ⁻¹ h ( mᵢ ), and kᵢ is a nonce that we assume has a bias (e.g., its most significant bits are zero with probability different from 1/2).
The probabilistic nature of the problem is evident in the fact that we don’t know the exact values of kᵢ , but we know their distribution. This allows us to apply methods of mathematical statistics to estimate the unknown parameter d .
5. Lattice and HNP based attacks
The most efficient method for solving HNP in the presence of biased nonces is to reduce the problem to the Shortest Vector Problem (SVP) and apply the LLL (Lenstra–Lenstra–Lovász) algorithm or its improved versions (BKZ)[reference:6].
The idea behind the method is to construct a lattice containing a vector whose coordinates are associated with the unknown kᵢ . If the kᵢ s are biased (for example, their most significant l bits are zero with high probability), then the corresponding vector will be “short” in this lattice, and the basis reduction algorithm will be able to find it.
Probability analysis plays a key role at several stages:
- Estimating the required number of signatures. For a given bias (e.g., the probability p that the most significant bit is zero), one can estimate how many signatures N are required for the LLL algorithm to find the correct key with high probability. This estimate is based on limit theorems of probability theory and an analysis of the distribution of the shortest vector in a lattice.
- Error handling. In real data, some observations may not match the assumed model (for example, due to measurement noise). Mathematical statistics methods allow us to estimate the error rate and adjust decision thresholds.
- Assessing the attack’s success. After constructing the lattice and reducing it, we obtain a set of candidate vectors. The probability that the true key is among them can be estimated using probability inequalities (e.g., Chernoff’s inequality).
In a paper by Breitner and Heninger (2019), this approach was successfully applied to recover hundreds of Bitcoin private keys based on signature analysis on the public blockchain [reference:7]. The authors used a lattice algorithm to solve HNP and were able to calculate private keys used with nonces biased by various implementation bugs.
6. Practical application: step-by-step algorithm
Let us consider a practical scenario for recovering an ECDSA private key based on the analysis of biased nonces.
Step 1: Data Collection
N signatures ( rᵢ , sᵢ ) and the corresponding message hashes h ( mᵢ ) are collected . In the case of Bitcoin, the signatures and hashes are available on the public blockchain, making this step trivial.
Step 2. Formulating the HNP equations
For each signature the following are calculated:
tᵢ = sᵢ ⁻¹ · rᵢ mod n ,
bᵢ = sᵢ ⁻¹ · h ( mᵢ ) mod n .
We obtain a system of comparisons:
tᵢ · d + bᵢ ≡ kᵢ (mod n ), i = 1, …, N .
Step 3. Statistical analysis of nonce
Based on a priori information about the implementation (or on observed data), a bias model kᵢ is determined . For example, if it is known that the nonce generator tends to generate numbers with zero high-order bits, then one can assume that kᵢ < 2 n − l for some l .
Using statistical hypothesis testing methods (χ² test, Kolmogorov-Smirnov goodness-of-fit test, etc.), one can estimate the parameters of the kᵢ distribution and test the hypothesis about the presence of bias.
Step 4. Building the lattice
A lattice of dimension N +1 or N +2 is constructed, the basis of which is formed from the coefficients tᵢ and bᵢ . The standard lattice construction for HNP is:
B = [
[ n , 0, 0, …, 0],
[0, n , 0, …, 0],
…,
[ t ₁, t ₂, …, t ₘ, 1/ n ]
]
The exact design may vary depending on the specific implementation of the algorithm.
Step 5. Lattice reduction
The LLL (or BKZ) algorithm is applied to the constructed lattice. The result is a reduced basis, among whose vectors, with a high probability, is a vector corresponding to the true value of d .
Step 6. Key extraction and verification
Candidates for the private key are extracted from the given basis. Each candidate is checked against known public keys or Bitcoin addresses. If the check is successful, the key is considered recovered.
7. Probability estimates and boundaries
One of the key issues is estimating the minimum amount of data required for a successful attack. The literature provides the following approximate values:
| Displacement type | Required number of signatures | Source |
|---|---|---|
| Leak 1 bit (MSB nonce) | ~500–2100 signatures | Minerva [25] |
| 2 bits leaked | ~200 signatures | Various sources |
| 4 bit leak | ~50 signatures | LLL-based assessments |
| Reusing a nonce | 2 signatures | A trivial case |
These estimates are derived from a combination of theoretical analysis and experimental data. The theoretical bounds can be refined using Chernoff’s inequality, which yields exponential estimates of the probability of large deviations for sums of independent random variables.
8. Conclusion
This paper demonstrated that N. I. Chernova’s textbook “Probability Theory” contains fundamental mathematical apparatus that finds direct and non-trivial application in the cryptanalysis of the ECDSA scheme used in the Bitcoin blockchain.
Key findings:
- The Bernoulli distribution and the binomial distribution allow us to formalize the problem of detecting bias in the high-order bits of a nonce and to estimate the number of observations required for a statistically significant conclusion.
- Conditional probability and independence provide a tool for analyzing correlations between nonce bits that may arise due to flaws in random number generators.
- Limit theorems (the law of large numbers, the central limit theorem, Chernoff’s inequality) provide theoretical bounds for estimating the success rate of cryptanalytic attacks.
- The hidden number problem (HNP) is a natural bridge between the probabilistic nonce generation model and lattice key recovery algorithms.
The practical significance of these results is confirmed by real attacks on the Bitcoin blockchain, during which hundreds of private keys were recovered [reference:8]. This demonstrates that even an “economic” course in probability theory contains tools critical to cybersecurity.
Directions for further research for cryptanalysis based on this area
This study opens several promising directions for further work at the intersection of probability theory and cryptanalysis:
- Developing probabilistic models for new types of nonce leaks. Modern ECDSA implementations can exhibit complex, nonlinear relationships between nonce generation parameters and observable characteristics (time, power consumption, electromagnetic radiation). Constructing adequate probabilistic models of such leaks and assessing their statistical significance is an important task.
- Application of Multivariate Statistical Analysis. Chernova’s textbook examines multivariate distributions and numerical characteristics of the dependence of random variables (Chapters 8–10). These methods can be used to analyze the joint distributions of multiple nonce bits and construct more efficient decision rules.
- Estimating the entropy of nonce generators. Probability theory provides tools for estimating entropy (specifically, differential entropy and Shannon entropy). Applying these tools to real-world nonce generators in cryptocurrency wallets will allow for early detection of vulnerabilities.
- Developing noise-resistant HNP algorithms. In real-world settings, nonce data may contain errors (for example, due to measurement inaccuracies). Robust statistical methods based on probability inequalities and limit theorems can improve the resilience of lattice attacks.
- Analysis of the Impact of Deterministic Nonce Generation Schemes (RFC 6979). Deterministic schemes, such as RFC 6979, eliminate randomness from the nonce generation process but introduce new potential vulnerabilities related to private key compromise. Probabilistic analysis of such schemes represents a separate and interesting area of research.
- Quantum aspects. With the development of quantum computing, new threats to ECDSA are emerging. Research into the probabilistic aspects of quantum algorithms (e.g., Shor’s algorithm) and their interaction with classical cryptanalysis methods is a pressing fundamental problem.
Thus, the symbiosis of classical probability theory and modern cryptanalysis continues to be a fruitful area, promising both theoretical breakthroughs and practically significant results.
This document was prepared based on an analysis of N. I. Chernova’s textbook “Probability Theory” (Novosibirsk, 2007) and modern scientific literature on ECDSA cryptanalysis. All citations and references are provided in the text.
