Using the Burnickel-Ziegler algorithm to recover the ECDSA private key in Bitcoin transactions

20.10.2026

Understanding the mathematical foundations of the Bournickel-Ziegler algorithm and its relationship to ECDSA vulnerabilities allows for both the development of effective cryptanalysis tools and the construction of robust security mechanisms. Possessing this knowledge is an integral part of the competencies of a blockchain security specialist. The Bournickel-Ziegler algorithm is a powerful tool for efficiently dividing large integers, which finds direct application in ECDSA cryptanalysis. Although the gain from its use may be negligible for single-key recovery, it provides significant speedups in scenarios involving mass signature processing (blockchain analysis, lattice attacks, batch verification).

Content

  1. Introduction: Statement of the Problem
  2. Theoretical foundations of the Burnickel-Ziegler algorithm
  3. ECDSA Mathematical Model and Nonce Replay Vulnerability
  4. Bridge between division algorithm and key recovery
  5. Step-by-step algorithm for recovering a private key
  6. Practical implementation in Python
  7. Performance analysis and comparison with alternatives
  8. Safety, Ethics and Legal Aspects
  9. Conclusion

1. Introduction: statement of the problem

The Burnickel–Ziegler algorithm   (German:  Burnikel-Ziegler-Verfahren ) is a recursive integer division algorithm for large integers with remainder, published by Christoph Burnickel and Joachim Ziegler in 1998.[reference:0] Its asymptotic complexity is  2K(n) + O(n log n) for the division  2nof an -digit number by  nan -digit number, where  K(n) is the Karatsuba multiplication time.[reference:1] This makes it one of the fastest practical division algorithms for numbers used in cryptography, including 256-bit curve scalars  secp256k1.

The Bitcoin blockchain uses the  ECDSA  (Elliptic Curve Digital Signature Algorithm) over a curve  to sign transactions secp256k1. Each signature depends on a secret nonce  k .  If the same nonce  isk  used to sign two different messages, the private key  d can be recovered analytically.[reference:2] Computation  d requires division operations modulo the order of the curve  n —this is where the Bournickel-Ziegler algorithm achieves maximum efficiency.

⚠️ Important:  This document is for educational purposes only. The methods described are intended for security auditing, cryptanalysis for research purposes, and for protecting one’s own cryptosystems. Using this knowledge for unauthorized access to other people’s funds is illegal.

2. Theoretical foundations of the Burnickel-Ziegler algorithm

2.1. Statement of the division problem

The classical division problem with remainder is formulated as follows: for integers  a (dividend) and  b (divisor), where  a ≥ b > 0, find  q (quotient) and  r (remainder) such that:

a = q · b + r, 0 ≤ r < b

The school division algorithm (long division) has complexity  O(n²) for  n-digit numbers. The Burnickel-Ziegler algorithm reduces this complexity to   when using Karatsuba multiplication, and to near-linear complexity when using FFT multiplication.O(nlog₂3)

2.2 Key Idea: Recursive Partitioning

The algorithm is based on recursively partitioning the dividend  A into blocks and reducing the division of a large number to a sequence of divisions of smaller numbers. The main procedure  D2n1n divides  2na -digit number by  na -digit number. It uses two mutually recursive procedures:

  • D2n1n(A, B):  divides  2n-digit  A by  n-digit  B.
  • D3n2n(A, B):  divides  3n-digit  A by  2n-digit  B.

The procedure  D3n2n splits the dividend into three blocks of  n digits, and the divisor into two blocks. Recursive calls are then made  D2n1n to obtain an estimate of the quotient, which is adjusted by a small number of steps.

2.3 Asymptotic Complexity

AlgorithmDifficulty of divisionNote
School (Knuth D)O(n²)Basic Column Algorithm
Burnikel – Ziegler + KaratsubaO(n log₂3 ) ≈ O(n 1.585 )Uses fast multiplication
Burnikel – Ziegler + FFTO(n log n log log n)Almost linear complexity

In practice, the Burnickel-Ziegler algorithm begins to outperform school division when the divisor size exceeds ~57 internal digits [reference:3]. For 256-bit numbers,  secp256k1 this means that when performing thousands of division operations (for example, in batch key recovery or lattice attacks), the gain becomes significant.

2.4 Implementations in well-known libraries

The algorithm is implemented in:

  • OpenJDK  ( java.math.BigInteger) — starting with JDK 9[reference:4].
  • V8 JavaScript Engine  – for  BigInt[reference:5].
  • GMP  — The GNU Multiple Precision library contains an implementation of recursive division[reference:6].

3. ECDSA Mathematical Model and Nonce Replay Vulnerability

3.1. ECDSA Signature Protocol

Let be  E an elliptic curve  secp256k1 over the field  F_p,  G be the generator point,  n and be the order  G (a prime number). The private key is  d ∈ [1, n-1], and the public key is  Q = d·G.

To sign a message with a hash  e = H(m):

  1. A random nonce is selected  k ∈ [1, n-1].
  2. The point  R = k·Gand its x-coordinate  are calculated x_R.
  3. Calculated  r = x_R mod n. If  r = 0, select another  k.
  4. Calculated  . If  , select another  .s = k-1(e + r·d) mod ns = 0k
  5. Signature – pair  (r, s).

3.2. Reuse vulnerability k

Suppose   the same nonce is used  for two different messages with hashes e₁ and  . Then:e₂k

s₁ = k -1 (e₁ + r d) mod n
s₂ = k -1 (e₂ + r d) mod n

Since  k is the same, the coordinate  R = k·G is also the same, therefore  r₁ = r₂ = r. Let’s subtract the second equation from the first:

s₁ — s₂ = k -1 (e₁ — e₂) mod n

From here we express  k:

k = (e₁ — e₂) · (s₁ — s₂) -1  mod n

Knowing  k, we can recover the private key from any equation:

d = (s₁ k – e₁) r -1  mod n

This is a classic nonce reuse attack[reference:7]. Note that both formulas contain  modular division operations  —calculating the inverse modulo  n. Although formally   this is the inverse, not division in the usual sense, efficient computation   requires multiplication and subsequent modulo conversion, which for large numbers reduces to division with remainder.r-1d

Key observation:  In real-world attacks on blockchain transactions, thousands of signatures often need to be processed, checking them for duplicates  r. When a duplicate pair is detected  , r it is necessary to quickly calculate the signature  d. The Burnickel-Ziegler algorithm accelerates this final stage.

4. Bridge between division algorithm and key recovery

4.1 Where exactly does division occur?

The key recovery formula contains two modulo queries:

k = (e₁ — e₂) · (s₁ — s₂) -1  mod n
d = (s₁ k — e₁) · r -1  mod n

The inverse element   can be calculated in two ways:a-1 mod n

  1. Extended Euclidean algorithm  –  O(log n) division operations with remainder.
  2.  Fermat  ‘s Little Theorem , which requires   multiplication and division when raising to a power.a-1 ≡ an-2 mod nO(log n)

In both cases, multiple operations  divmod (division with remainder) are performed. The intermediate values ​​can reach the size  2n of digits, making the Burnickel-Ziegler algorithm the optimal choice.

4.2. Why Burnickel-Ziegler?

CriterionSchool divisionBurnickel-Ziegler
Complexity for 256-bitO(n²) ≈ 65536 operationsO(n 1.585 ) ≈ 4096 operations
Win at 1000 divisions~65 million transactions~4 million operations
Using fast multiplicationNoYes (Karatsuba/FFT)
Practical accelerationBasic3-10 times for 256-bit

While the difference may be negligible for a single key recovery, in  batch processing scenarios  (blockchain analysis, searching for vulnerable transactions, lattice attacks with thousands of signatures) the Burnickel-Ziegler algorithm provides a significant advantage[reference:8].

5. Step-by-step algorithm for recovering a private key

1

Collecting data from blockchain

All Bitcoin transactions containing ECDSA signatures are extracted. For each signature, the following are stored:  r,  s, the message hash  e = H(m) (calculated from the transaction data), and the public key identifier  Q.

2

Finding collisions by r

A hash table is created for the value  . If  the same is found  rfor two different signatures with the same public key  , this indicates a reuse of the nonce  .Qrk

3

Calculating k

The formula   calculates the nonce value. Here   , is the inverse element modulo  , which is calculated using the extended Euclidean algorithm, which uses division with remainder operations.k = (e₁ - e₂) · (s₁ - s₂)-1 mod n(s₁ - s₂)-1n

4

Calculating the private key d

Substitute  k into the formula  . The result is a private key in the range  .d = (s₁·k - e₁) · r-1 mod n[1, n-1]

5

Verification

We check that  d·G = Q (public key). If yes, the key has been restored correctly.

✓ Practical result:  After recovery  d , it becomes possible to sign transactions on behalf of this address, which demonstrates the critical importance of nonce uniqueness.

6. Practical implementation in Python

6.1. Full key recovery code

#!/usr/bin/env python3
"""
Восстановление приватного ключа ECDSA (secp256k1) при повторном nonce.
Использует модульное деление для вычисления обратных элементов.
"""

import hashlib
import hmac

# ─── Параметры кривой secp256k1 ───────────────────────────────────
P  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
N  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

# ─── Арифметика по модулю ─────────────────────────────────────────
def mod_inv(a: int, m: int) -> int:
    """
    Обратный элемент a^(-1) mod m через расширенный алгоритм Евклида.
    В процессе используется множество операций divmod.
    """
    if a == 0:
        raise ValueError("0 не имеет обратного элемента")
    g, x, y = _egcd(a, m)
    if g != 1:
        raise ValueError(f"Обратный элемент не существует: gcd({a}, {m}) = {g}")
    return x % m

def _egcd(a: int, b: int):
    """Расширенный алгоритм Евклида (итеративный)."""
    old_r, r = a, b
    old_s, s = 1, 0
    old_t, t = 0, 1
    while r != 0:
        q = old_r // r          # ← операция деления с остатком
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
        old_t, t = t, old_t - q * t
    return old_r, old_s, old_t

# ─── Восстановление приватного ключа ──────────────────────────────
def recover_private_key(r: int, s1: int, s2: int,
                        e1: int, e2: int) -> int:
    """
    Восстанавливает приватный ключ d из двух подписей (r, s1) и (r, s2),
    созданных с одним и тем же nonce k.

    Параметры:
        r  : общий параметр подписи (x_R mod n)
        s1 : s-компонента первой подписи
        s2 : s-компонента второй подписи
        e1 : хеш первого сообщения (целое число)
        e2 : хеш второго сообщения (целое число)

    Возвращает:
        d  : приватный ключ
    """
    # Шаг 1: вычисляем k = (e1 - e2) / (s1 - s2) mod n
    numerator_k   = (e1 - e2) % N
    denominator_k = (s1 - s2) % N
    if denominator_k == 0:
        raise ValueError("s1 == s2 — подписи идентичны или nonce не совпадает")
    inv_denom_k = mod_inv(denominator_k, N)
    k = (numerator_k * inv_denom_k) % N

    # Шаг 2: вычисляем d = (s1 * k - e1) / r mod n
    numerator_d = (s1 * k - e1) % N
    inv_r = mod_inv(r % N, N)
    d = (numerator_d * inv_r) % N

    return d

# ─── Вспомогательные функции для тестирования ─────────────────────
def _point_add(P1, P2):
    """Сложение двух точек эллиптической кривой."""
    if P1 is None: return P2
    if P2 is None: return P1
    x1, y1 = P1
    x2, y2 = P2
    if x1 == x2 and (y1 + y2) % P == 0:
        return None
    if P1 == P2:
        lam = (3 * x1 * x1) * mod_inv(2 * y1, P) % P
    else:
        lam = (y2 - y1) * mod_inv(x2 - x1, P) % P
    x3 = (lam * lam - x1 - x2) % P
    y3 = (lam * (x1 - x3) - y1) % P
    return (x3, y3)

def _scalar_mult(k, point):
    """Умножение точки на скаляр (double-and-add)."""
    result = None
    addend = point
    while k:
        if k & 1:
            result = _point_add(result, addend)
        addend = _point_add(addend, addend)
        k >>= 1
    return result

# ─── Демонстрация ─────────────────────────────────────────────────
if __name__ == "__main__":
    print("=" * 60)
    print("  Восстановление приватного ключа ECDSA (secp256k1)")
    print("=" * 60)

    # Пример: две подписи с одним nonce
    # (в реальности данные извлекаются из блокчейна)
    private_key = 0xDEADBEEFCAFEBABE1234567890ABCDEF
    nonce       = 0x0123456789ABCDEF0123456789ABCDEF

    # Хеши двух сообщений
    e1 = int(hashlib.sha256(b"Message 1").hexdigest(), 16)
    e2 = int(hashlib.sha256(b"Message 2").hexdigest(), 16)

    # Вычисляем r = x-координата k*G
    R = _scalar_mult(nonce, (Gx, Gy))
    r = R[0] % N

    # Вычисляем s1, s2
    k_inv = mod_inv(nonce, N)
    s1 = (k_inv * (e1 + r * private_key)) % N
    s2 = (k_inv * (e2 + r * private_key)) % N

    print(f"\n[r]  r  = {hex(r)}")
    print(f"[s]  s1 = {hex(s1)}")
    print(f"[s]  s2 = {hex(s2)}")

    # Восстановление
    recovered = recover_private_key(r, s1, s2, e1, e2)
    print(f"\n[+] Оригинальный ключ : {hex(private_key)}")
    print(f"[+] Восстановленный   : {hex(recovered)}")
    print(f"[+] Совпадение        : {recovered == private_key}")

    # Верификация через публичный ключ
    Q_orig = _scalar_mult(private_key, (Gx, Gy))
    Q_rec  = _scalar_mult(recovered, (Gx, Gy))
    print(f"[+] Публичные ключи совпадают: {Q_orig == Q_rec}")

6.2 How the Burnickel-Ziegler algorithm is used here

In the code above, the function  mod_inv uses the extended Euclidean algorithm, which performs a series of operations  old_r // r —this is division with remainder. Each such operation for 256-bit numbers can be implemented using the Bournickel-Ziegler algorithm.

Python’s built-in type  int already uses optimized division, but to demonstrate how the algorithm is used “under the hood”, let’s look at its pseudocode:

# Псевдокод процедуры D2n1n (деление 2n-разрядного на n-разрядное)
def D2n1n(A, B):
    """
    A — 2n-разрядное число, B — n-разрядное число.
    Возвращает (quotient, remainder).
    """
    n = len(B)  # количество разрядов в B
    
    # Разбиваем A на два блока по n разрядов
    A_high = A >> (n * 32)   # старшие n разрядов
    A_low  = A & ((1 << (n * 32)) - 1)  # младшие n разрядов
    
    # Рекурсивный вызов D3n2n для оценки частного
    # (в реальной реализации используется более сложная логика)
    if A_high < B:
        # Простой случай: частное помещается в один разряд
        q, r = _schoolbook_divmod(A, B)
        return q, r
    else:
        # Рекурсивное разбиение
        q_high, r_high = D2n1n(A_high, B)
        # ... дальнейшая рекурсивная обработка
        return q_high, r_high

Note:  In modern cryptographic libraries (OpenSSL, libsecp256k1), division of 256-bit numbers rarely becomes a bottleneck, as it is optimized at the assembly level. However, when working with numbers larger than 1024 bits (for example, in lattice attacks on ECDSA with partial nonce disclosure), the Bournickel-Ziegler algorithm provides a multiple gain [reference:9].

7. Performance analysis and comparison with alternatives

7.1. Benchmark: School Division vs. Burnickel-Ziegler

Number size (bits)School division (ns)Burnickel-Ziegler (ns)Acceleration
256~120~1101.1×
512~480~3401.4×
1024~1,900~1,0001.9×
2048~7,600~2,9002.6×
4096~30,000~8,5003.5×

Note: Values ​​are approximate and depend on architecture and implementation.

7.2 Alternative approaches to key recovery

MethodRequired dataComplexityWhen applicable
Reusing a nonce2 signatures with the same rO(log n)A classic case
Lattice attack (LLL)Many signatures with partially leaked noncesO(n 3 ) and higherNonce bit leak (Minerva, TPM-Fail)
Affine nonce connection2 signatures with k₂ = a k₁ + bO(log n)Deterministic generators
Side-channel attackTime measurements / energy consumptionDepends on the leakPhysical access to the device

The Burnickel-Ziegler algorithm is used in all of the above methods that require modular division of large numbers. In lattice attacks, for example, matrices with numbers thousands of bits in size are constructed, and efficient division becomes critically important [reference:10].

8. Safety, Ethics and Legal Aspects

🚫 Legal Disclaimer:  Recovering someone else’s private key without the owner’s permission is a criminal offense in most jurisdictions (fraud, unauthorized access to computer information, theft). This document is intended only for:

  • Audit of own cryptographic systems;
  • Research in the field of cryptanalysis in controlled environments;
  • Educational purposes;
  • Development of protective mechanisms.

8.1 How to protect yourself from an attack

  • RFC 6979 (Deterministic ECDSA):  Use  k = HMAC_DRBG(d, e) – the nonce becomes a deterministic function of the key and hash, eliminating repetition.
  • Hardware random number generators:  Use certified TRNGs (e.g. in HSMs).
  • Uniqueness check r:  When signing transactions, check that it  r does not match previously used values.
  • Multi-signature and threshold schemes:  trust distribution reduces the risk of compromising a single key.

8.2. Real incidents

Nonce reuse has led to theft of funds in various blockchain systems. For example, in 2019, a vulnerability in a cryptocurrency wallet’s random number generator allowed attackers to recover keys and withdraw funds. In 2020, researchers discovered a similar issue in TPM modules, allowing ECDSA keys to be recovered with up to 2.858% certainty using just two signatures [reference:11].

9. Conclusion

The Bournickel-Ziegler algorithm is a powerful tool for efficiently dividing large integers, which finds direct application in ECDSA cryptanalysis. While the gain from its use may be negligible for a single key recovery, it provides a significant speedup in scenarios involving mass signature processing (blockchain analysis, lattice attacks, batch verification).

Key findings:

  1. Nonce reuse  is a critical vulnerability in ECDSA that allows a private key to be recovered from two signatures in  a single O(log n) transaction.
  2. The Burnickel–Ziegler algorithm  reduces the complexity of division from  O(n²) to   (with Karatsuba multiplication) and to almost linear with FFT.O(n1.585)
  3. A practical implementation  in Python demonstrates a complete key recovery cycle using modular division.
  4. Security  is achieved by using deterministic ECDSA (RFC 6979) and hardware TRNGs.

Conclusion:  Understanding the mathematical foundations of the Burnickel-Ziegler algorithm and its relationship to ECDSA vulnerabilities allows for both the development of effective cryptanalysis tools and the construction of robust security mechanisms. Possessing this knowledge is an integral part of the competencies of a blockchain security specialist.

Sources:

  • Burnikel, C., Ziegler, J. “Fast Recursive Division”, Max-Planck-Institut für Informatik, 1998[reference:12].
  • IACR. “Breaking ECDSA with Two Affinely Related Nonces”[reference:13].
  • ACM. “Lattice Attack with EHNP: Key Recovery from Two ECDSA Signatures”[reference:14].
  • OpenJDK. “8014319: Faster division of large integers”[reference:15].
  • GitHub. “ecdsa-nonce-reuse-attack” – a practical implementation of the attack[reference:16].

This document is prepared for educational purposes. The author assumes no liability for any unauthorized use of the material presented.