Research by M. Nguyen, I. Shparlinski: The Insecurity of the Digital Signature Algorithm with Partially Known Nonces. Theoretical basis for the risks of partially disclosed ECDSA nonces

BY KEYHUNTER 03.09.2026

Research by M. Nguyen, I. Shparlinski: The Insecurity of the Digital Signature Algorithm with Partially Known Nonces. Theoretical basis for the risks of partially disclosed ECDSA nonces

Abstract.  This paper presents a comprehensive analysis of the fundamental research by Phong Nguyen and Igor Shparlinsky (2002), which established that the DSA digital signature algorithm (and its elliptic variant ECDSA) is vulnerable to polynomial-time attacks under the condition of partial disclosure of several consecutive bits of random nonces  k  . The paper considers the theoretical basis for the attack, based on reducing the problem to the Hidden Number Problem (HNP) and subsequent solution using lattice reduction algorithms (LLL, BKZ). Particular attention is paid to quantitative estimates: to recover the DSA secret key, it is sufficient to know just a few bits of the nonce from a number of signatures linearly dependent on the logarithm of a prime modulus  q . Real-world examples of the implementation of similar attacks in the history of cryptanalysis are given, including incidents in the Bitcoin ecosystem and vulnerabilities in the PS3 implementation.

1. Introduction

The Digital Signature Algorithm (DSA) and its elliptic curve variant, ECDSA, are among the most widely used cryptographic primitives for authentication and data integrity. The cryptographic security of these schemes is traditionally based on the computational difficulty of the discrete logarithm problem over a finite field or a group of elliptic curve points.

However, as Phong Nguyen and Igor Shparlinsky demonstrated in their classic 2002 paper, DSA suffers from a fundamental vulnerability related to the generation of the nonce  [  reference:27]. If an attacker obtains information about several consecutive bits of the nonce for a sufficiently large number of signatures, the secret key can be recovered in polynomial time. This result was a turning point in understanding the security of DSA-like schemes and spurred the development of both theoretical and practical cryptanalytic methods.

2. Mathematical foundations of DSA and ECDSA

2.1 DSA Parameters

Let the following be given:

  • p  is a large prime number (for example, 1024 bits long),
  • q  is a prime divisor of  p  − 1 (160 bits long),
  • g  is an element of order  q  in the multiplicative group  F p * ,
  • x  ∈ [1,  q  − 1] is the signer’s secret key,
  • y  =  g x  mod  p  is the public key,
  • H (·) is a cryptographic hash function.

2.2. Signing process

To sign a message  m,  the following steps are performed:

  1. A random one-time number  k  ∈ [1,  q  − 1] is generated.
  2. Calculate  r  = ( g k  mod  p ) mod  q . If  r  = 0, choose a new  k .
  3. Calculate  s  =  k −1  ( H ( m ) +  x  ·  r ) mod  q . If  s  = 0, choose a new  k .
  4. The signature is a pair ( r ,  s ).

The critical element is  the nonce  k . It must be:

  • secret  (unknown to anyone except the signatory),
  • unique  for each signature (repetition  of k  leads to immediate disclosure of the key),
  • unpredictable  (generated from a truly random source).

2.3. ECDSA

In the case of ECDSA, all calculations are performed on a set of points on the elliptic curve. The parameter  r  is calculated as  the x -coordinate of the point  kG , where  G  is the base point of the curve. The equation for  s  remains formally the same, but all operations are performed modulo the order of the base point  n .

3. Hidden Number Problem

The central mathematical tool of the attack is  the Hidden Number Problem (HNP) , first proposed by Boneh and Venkatesan in 1996 to analyze the bit security of the Diffie–Hellman protocol[reference:28].

3.1. HNP formulation

Let  q  be a prime number,  α  ∈  F q  be an unknown element (“hidden number”). For  i  = 1, …,  n,  random  t i  ∈  F q are given  and  the most significant bits  of the numbers are known.

ui = α · ti mod q.

It is required to restore  α .

Boneh and Venkatesan showed that if for each  i  the ⌈log 2  q ⌉ − ⌈log 2  n ⌉ most significant bits of  u i are known , then  α  can be found in polynomial time by reduction to the shortest vector problem in a lattice (SVP)[reference:29].

3.2. Reduction of DSA to HNP

Nguyen and Shparlinsky established that the DSA equation

s = k−1 (H(m) + x · r) mod q

can be transformed into a form that allows the use of HNP[reference:30]. Indeed, we rewrite the equation:

k = s−1 H(m) + x · s−1 r mod q.

Let us designate:

t = s−1 r mod q,    a = s−1 H(m) mod q.

Then:

k = a + x · t mod q.

If an adversary knows the most significant bits of nonce  k , then he knows the most significant bits of  x  ·  t  mod  q  (up to a known value  of a ). This corresponds exactly to the HNP formulation, where  α  =  x  is the secret key and  t i  are known values ​​obtained from signatures [reference:31].

4. Reduction to the problem of finding the shortest vector in a lattice

4.1. Construction of the lattice

Let  n  signatures be known, and for each of them  the ℓ  most significant bits of the nonce  k i are known . This means that there exist integers  h i such that

|ki − hi| ≤ 2log2 q − ℓ.

From the equation  k i  =  a i  +  x  ·  t i  mod  q  we obtain:

x · ti − hi + ai ≡ εi (mod q),

where | ε i | ≤ 2 log 2  q − ℓ  is the small error.

Consider the lattice  L  ⊂ ℤ n +1 generated by the rows of the matrix:

⎛ q   0   ⋯   0 ⎞
⎜ 0   q   ⋯   0 ⎟
⎜ ⋮   ⋮   ⋱   ⋮ ⎟
⎝ t1   t2   ⋯   tn   1/q ⎠

Vector

v = (x t1 − h1 + a1, …, x tn − hn + an, x/q)

belongs to this lattice and has small Euclidean norm, since the first  n  components are bounded by 2 log 2  q − ℓ , and the last component  x / q  is small[reference:32].

4.2. Application of the LLL algorithm

To find a short vector  v  in a lattice  L , the LLL algorithm  (Lenstra–Lenstra–Lovász) or its improved versions (BKZ)  can be used  . The LLL algorithm finds a vector whose length does not exceed 2 ( n − 1)/4  · λ 1 ( L ), where λ 1 ( L ) is the length of the shortest vector in the lattice.

Nguyen and Shparlinsky proved that for  n linearly dependent on log 2  q , and with knowledge of a sufficiently large number of the most significant bits of the nonce, the LLL algorithm with high probability finds exactly the vector  v , which allows one to calculate the secret key  x [reference:33].

4.3. Quantitative assessments

In their work, Nguyen and Shparlinsky showed that for 160-bit DSA (the standard used in the early 2000s), knowing  just three bits  of each nonce from about  100 signatures is enough to recover the secret key in polynomial time[reference:34].

More generally, if  ℓ  of the most significant bits of a nonce are known, then the number of required signatures  n  satisfies:

n ≈ log2 q / ℓ.

5. Extension to ECDSA

In a subsequent paper (2003), Nguyen and Shparlinsky extended their attack to ECDSA[reference:35]. Previously, all results for ECDSA were heuristic in nature, including the pioneering work of Haugrave-Graham and Smart (1999). Nguyen and Shparlinsky were the first to present  a provable  attack on ECDSA with partially known nonces[reference:36].

The peculiarity of ECDSA is that the parameter  r  is  the x -coordinate of the point  kG , not simply the result of modular exponentiation. However, the structure of the equation for  s  remains the same, allowing the same reduction technique to be applied to HNP, albeit with some technical complications.

6. Real-World Examples of Partially Disclosed Nonce Attacks

Nguyen and Shparlinsky’s results did not remain just a theoretical curiosity; they have found practical application in real cryptanalytic attacks on numerous occasions.

6.1 Vulnerability in the PlayStation 3 (PS3) implementation

In 2010, a hacker group (known as fail0verflow) exploited a repeated nonce in the PlayStation 3 ECDSA implementation to recover Sony’s master key. Although this was a  nonce- repetition attack  (rather than a partial disclosure), it demonstrated how critical the correct generation  of k is . Implementations were subsequently found where nonces were generated using weak pseudorandom number generators, making them partially predictable—a direct prerequisite for the Nguyen-Szparlinski attack.

6.2. Attacks on Bitcoin transactions

Numerous vulnerabilities related to ECDSA nonce generation have been discovered in the Bitcoin ecosystem. One of the most well-known cases involves the use of non-random or partially predictable nonces in some wallet implementations. For example, in 2013, it was shown that Android apps with a flawed random number generator (due to an entropy issue) generated nonces that were highly predictable [reference:37].

Researchers, using a methodology based on the work of Nguyen and Shparlinsky, were able to recover private keys and access funds in these wallets.[reference:38] Specifically, nonces of the type  k  with a common structure were discovered in the Bitcoin blockchain, allowing lattice attacks to be used to recover keys.[reference:39]

6.3. Attacks on the MQV Protocol

In 2002, a paper on cryptanalysis of the MQV (Menezes–Qu–Vanstone) protocol with partially known nonces was published, directly building on the results of Nguyen and Shparlinsky [reference:40]. This paper demonstrated that even in authenticated key exchange protocols that do not use digital signatures, partial disclosure of the nonce can lead to the compromise of static private keys [reference:41].

6.4. Side-channel attacks

Numerous side-channel attacks—such as power analysis or electromagnetic radiation—allow an attacker to obtain partial information about the nonce during the signature generation process.[reference:42] For example, when performing an elliptic curve multiplication operation, variations in power consumption can reveal several bits  of k . By combining such leaks with the Nguyen-Szparlinski method, researchers have repeatedly demonstrated the possibility of full key recovery.[reference:43]

7. Practical implications and recommendations

The main conclusion of Nguyen and Shparlinsky’s work is that  even a minor leak of nonce information is a critical threat  to DSA and ECDSA. This requires a reconsideration of nonce generation practices in cryptographic systems.

7.1. Nonce Generation Requirements

Based on the results of the study, the following requirements can be formulated:

  1. True randomness:  nonces must be generated using a cryptographically strong random number generator (CSPRNG) with sufficient entropy.
  2. Deterministic approach (RFC 6979):  An alternative is to use a deterministic scheme where the nonce is calculated as a hash of the secret key and the message. This eliminates the risk of nonce repetition, but requires the hash function to be cryptographically secure.
  3. Protection against side-channel attacks:  The implementation must be resilient to information leaks through side channels (e.g., using masking techniques or constant execution time).

7.2. Transition to sustainable schemes

In the long term, a move to nonce-leak-resistant signature schemes, such as EdDSA (which uses a deterministic nonce) or post-quantum algorithms (e.g., lattice-based ones, where the nonce generation problem is posed differently), is recommended.

8. Conclusion

Nguyen and Shparlinsky’s study, “The Insecurity of the Digital Signature Algorithm with Partially Known Nonces,” is a fundamental contribution to the cryptanalysis of asymmetric signature schemes. The authors proved that DSA and ECDSA are vulnerable to polynomial-time attacks with partial nonce discovery by reducing the problem to a hidden number problem and applying lattice reduction algorithms.

Quantitative estimates show that knowledge of just a few bits of the nonce from a moderate number of signatures is sufficient for the attack to be implemented in practice—a situation that can easily arise from poor random number generation or side-channel leaks.

Real-world examples from the history of cryptanalysis—from PlayStation 3 hacking to attacks on Bitcoin wallets—confirm the relevance and practical significance of these theoretical results. Thus, Nguyen and Shparlinsky’s work remains a cornerstone in understanding the threats posed by nonces in DSA-like schemes and serves as the basis for modern recommendations for secure implementation of digital signatures.

Bibliography

Nguyen-Shparlinski Study: The Insecurity of DSA with Partially Known Nonces:  https://cryptia.ru/nguyen-shparlinski-study-the-insecurity-of-dsa-with-partially-known-nonces/

  1. Nguyen, P. Q., & Shparlinski, I. E. (2002). The Insecurity of the Digital Signature Algorithm with Partially Known Nonces.  Journal of Cryptology , 15(3), 151–176.[reference:44][reference:45]
  2. Nguyen, P. Q., & Shparlinski, I. E. (2003). The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces.  Designs, Codes and Cryptography , 30(2), 151–176.[reference:46]
  3. Boneh, D., & Venkatesan, R. (1996). Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes.  Crypto ’96 .[reference:47]
  4. Howgrave-Graham, N., & Smart, N. P. (1999). Lattice Attacks on Digital Signature Schemes.  Designs, Codes and Cryptography , 23(3), 283–290.[reference:48]
  5. Leadbitter, P. J., & Smart, N. P. (2002). Cryptanalysis of MQV with Partially Known Nonces.  IACR ePrint 2002. [reference:49]