Breaking ECDSA with Two Affinely Related Nonces
Jamie Gilchrist, William J. Buchanan, Keir Finlow-Bates · 2025
Read Breaking ECDSA with Two Affinely Related Nonces by Jamie Gilchrist, William J. Buchanan, Keir Finlow-Bates (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-13737.txt.
Introduction
Jamie Gilchrist, William Buchanan, and Keir Finlow-Bates show that two signatures can sink the ECDSA scheme when their secret nonces lean on each other, in a 2025 paper. The algorithm signs with a fresh secret number each time; reuse the number and the private key falls out, a known lesson. The trio push further: if the second nonce is any fixed blend of the first, a times it plus a constant, the key still falls.
Two signatures suffice, even over the same message, given the blend is known. The attack is pure algebra, no lattice search or brute force. The authors claim the first closed-form recovery of this kind. Wallets that derive nonces carelessly are on notice.
Catalog record
| CREATOR | Jamie Gilchrist, William J. Buchanan, Keir Finlow-Bates |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 20 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-13737
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Breaking ECDSA with Two Affinely Related Nonces Jamie Gilchrist, William J. Buchanan, Keir Finlow-Bates Abstract The security of the Elliptic Curve Digital Signature Algorithm (ECDSA) depends on the uniqueness and secrecy of the nonce, which is used in each signature. While it is well understood that nonce k k reuse across two distinct messages can leak the private key, we show that even if a distinct value is used for k 2 k_{2} , where an affine relationship exists in the form of: k m = a ⋅ k n + b k_{m}=a\cdot k_{n}+b , we can also recover the private key. Our method requires only two signatures (even over the same message) and relies purely on algebra, with no need for lattice reduction or brute-force search(if the relationship, or offset, is known). To our knowledge, this is the first closed-form derivation of the ECDSA private key from only two signatures over the same message, under a known affine relationship between nonces. 1 Introduction The Elliptic Curve Digital Signature Algorithm (ECDSA) method has been around for over two decades and was first proposed in [ 1 ] . It is a widely used cryptographic method for generating digital signatures. It plays a crucial role in ensuring the authenticity, integrity, and non-repudiation of digital messages or transactions. Based on elliptic curve cryptography (ECC), ECDSA offers strong security with relatively small key sizes, making it more efficient than traditional algorithms like RSA in terms of speed and resource usage. ECDSA is popularly used in a variety of modern digital systems where security and efficiency are critical. In the world of cryptocurrencies, it is used to secure Bitcoin and Ethereum transactions by allowing users to sign transactions with their private keys, proving ownership without revealing sensitive information. ECDSA is also used in secure communication protocols such as TLS (Transport Layer Security), which underpins HTTPS and ensures safe web browsing by verifying the authenticity of websites. Additionally, it is employed in secure email systems through standards like S/MIME, passkey authentication protocols such as FIDO2, and in mobile authentication, particularly within modern smartphones and IoT devices, where its lightweight nature is ideal for constrained environments. ECDSA was standardised by the National Institute of Standards and Technology (NIST) in 2000 and has since remained a widely used digital signature scheme. Alongside, RSA (Rivest, Shamir, Adleman) and EdDSA (Edwards-Curve Digital Signature Algorithm), ECDSA is standardised in FIPS 186-5 [ 2 ] . However, it poses several challenges for inexperienced implementers, most notably the risk of nonce reuse attacks, which can compromise the security of the private key if not properly mitigated. In this paper, we begin with an overview of the mathematics behind ECC and ECDSA. We then proceed to outline a novel method for private key recovery, where only two signatures are needed(even over the same message) when we know there was an affine relationship between any two or more nonces used during independent signatures. 2 Background This section outlines some of the core theory related to elliptic curves. 2.1 Finite integer fields and modular arithmetic Elliptic curve cryptography takes place over a finite integer field (also called a Galois field) of prime order. Given a prime number p , we take the set of all integers from 0 to p-1 , and use addition and multiplication modulo p for our calculations. In mathematics, this is denoted by \mathbb{F}_{p} . Modular multiplication and addition are associative, distributive, and commutative. This is extremely helpful for developers because it means that, provided your programming language implements arithmetic in a manner that supports large enough numbers, you can apply the modulo operations at any convenient point (provided you also remember to apply them at the end of your calculations). Associativity \displaystyle(a\bmod p+b\bmod p)\bmod p=(a+b)\bmod p \displaystyle(a\bmod p\cdot b\bmod p)\bmod p=(a\cdot b)\bmod p Commutativity \displaystyle a\bmod p+b\bmod p=b\bmod p+a\bmod p \displaystyle a\bmod p\cdot b\bmod p=b\bmod p\cdot a\bmod p Distributivity \displaystyle(a\bmod p+b\bmod p)\cdot c\bmod p=(a\cdot c+b\cdot c)\bmod p \displaystyle c\bmod p\cdot(a\bmod p+b\bmod p)=(c\cdot a+c\cdot b)\bmod p In the text that follows, it should be understood that the numbers we are working with are all integers in the range \{0,...,p-1\} , and all operations are conducted modulo the order of the finite field over which mathematical operations take place. 2.2 Elliptic curves Elliptic curves are the subject of a wide and complicated branch of mathematics, finding uses in all sorts of unexpected areas, such as Andrew Wiles’s proof of Fermat’s Last Theorem and, importantly, cryptography. The Elliptic Curve’s application to cryptography was first proposed in the mid-1980s by Neal Koblitz and Victor Miller [ 3 ] [ 4 ] Fortunately, implementing ECC doesn’t require a developer to select optimal curves and parameters from scratch themselves. Standards have emerged which recognise certain elliptic curves with carefully vetted cryptographic properties, which are then used in publicly available software libraries. A list of well-tested elliptic curves and their commonly used parameters can be found at [ 5 ] . For example, Bitcoin and Ethereum use an elliptic curve identified as secp256k1 , and FIDO2 uses secp256r1 . An elliptic curve is the set of solutions (x,y) to an equation of the form: \displaystyle y^{2}=x^{3}+ax+b (1) For ECC, we require a definition of scalar multiplication of a point on the curve. Given two points P and Q on the curve, adding P to Q produces a new point R , also on the curve, using the following definition: Let P=(x_{1},y_{1}) , Q=(x_{2},y_{2}) , and R=P\oplus Q=(x_{3},y_{3}) Operation Formula (mod p ) P\neq Q m=\frac{y_{2}-y_{1}}{x_{2}-x_{1}} P=Q m=\frac{3x_{1}^{2}+a}{2y_{1}} Resulting Point x_{3}=m^{2}-x_{1}-x_{2} , y_{3}=m(x_{1}-x_{3})-y_{1} This allows us to define the scalar multiplication \times of a point P by a scalar value n : \displaystyle n\cdot P=\underbrace{P\oplus P\oplus\cdots\oplus P}_{n\ \text{times}} (2) In cryptographic libraries, scalar multiplication of curve points is implemented using techniques to improve performance, such as with the Montgomery Ladder method [ 6 ] . We need to make sure the multiplication is performed securely and constantly timed to prevent side-channel attacks that could reveal information about the values of the operation, such as for constant time computation [ 7 ] . As we will be using private keys in the scalar multiplication of a specific curve point called the Generator Point , this is important. The Generator Point G is a point on the elliptic curve (an x and y coordinate) which is chosen as the starting point for the point addition. This Generator Point is consistent for any given Elliptic Curve; that is, anyone using the same curve(such as secp256k1, secp256r1, and so on) will also use the same Generator point, as these are part of the standard. Scalar multiplication on elliptic curves is what provides the cryptographic hardness behind ECC. Given a private key scalar priv and the generator point G , we can compute the public key as: \displaystyle pub=priv\cdot G (3) This operation is straightforward to perform using repeated point addition, as we described earlier. However, if we wanted to reverse this(to go back to the private key), that is, given G and pub , attempting to recover priv is known as the Elliptic Curve Discrete Logarithm Problem (ECDLP), which is considered computationally infeasible for sufficiently large fields and secure curves. Unlike multiplication