In this article, we will examine both the classical RSA attack and its conceptual analogues for ECDSA.
1. Cryptanalysis Research Paper Introduction and Debunking: RSA
The classic Boneh-DeMillo-Lipton (BDL) attack against RSA uses the Chinese Remainder Theorem (CRT). However, the cryptographic meaning of this attack (fault injection) is fundamental and has spawned a whole class of attacks (for example, fault attacks on scalar multiplication in ECDSA) that pose a real threat to hardware wallets.
2. Theoretical background: RSA and the Chinese Remainder Theorem (CRT)
The standard RSA signature computation requires exponentiation modulo \(N = p \cdot q\):
\( s = m^d \pmod N \)
To speed up the process (by about 4 times), the Chinese Remainder Theorem (RSA-CRT) is used in practice, calculating the signature in parts for each of the prime factors:
- \( s_p = m^{d_p} \pmod p \) , where \( d_p = d \pmod{p-1} \)
- \( s_q = m^{d_q} \pmod q \) , where \( d_q = d \pmod{q-1} \)
The parts are then combined using the Ganer coefficients:
\( s = CRT(s_p, s_q) = s_q + q \cdot ( (s_p – s_q) \cdot q^{-1} \pmod p ) \)
3. The Boneh-DeMillo-Lipton Attack
The BDL attack (proposed in 1997) belongs to the class of fault injection attacks . An attacker physically affects the device (e.g., with a laser, a power failure (voltage glitching), or a clock generator glitch) during signature computation.
Mathematical justification
Suppose that a failure occurred during the calculation of \( s_p \) and an erroneous value of \( \hat{s}_p \) was calculated. However, \( s_q \) was calculated correctly.
- \( \hat{s}_p eq m^{d_p} \pmod p \)
- \( s_q = m^{d_q} \pmod q \)
The resulting erroneous signature \( \hat{s} \) has the properties:
- \( \hat{s} ot\equiv s \pmod p\)
- \( \hat{s} \equiv s \pmod q \)
Raising \( \hat{s} \) to the open exponent \( e \), we obtain:
- \( \hat{s}^e ot\equiv m \pmod p \) (therefore, \( p \) does not divide \( \hat{s}^e — m \))
- \( \hat{s}^e \equiv m \pmod q \) (therefore, \( q \) divides \( \hat{s}^e — m \))
Thus, to factorize the modulus \(N \) and extract the secret key, it is sufficient to calculate the greatest common divisor:
\( q = \gcd(\hat{s}^e – m \pmod N, N) \)
Or, if there is a correct and incorrect signature:
\( q = \gcd(s — \hat{s}, N) \)
A historical example from the archives
This attack was initially researched at Bellcore Laboratories . On smart cards from the early 2000s that lacked fault-injection protection, researchers successfully recovered 1024-bit RSA keys in milliseconds by briefly reducing the card’s power supply voltage during a cryptographic operation.
4. Examples of BDL attack implementation in various cryptosystems (PoC)
4.1. Python example
from Crypto.Util.number import getPrime, GCD
# Генерация ключей
p = getPrime(512); q = getPrime(512); N = p * q; e = 65537
d = pow(e, -1, (p-1)*(q-1))
m = 42 # Сообщение
# Нормальное вычисление RSA-CRT
dp = d % (p-1)
dq = d % (q-1)
sq = pow(m, dq, q)
# ВНЕДРЕНИЕ ОШИБКИ (Fault Injection) в sp
sp_faulty = (pow(m, dp, p) ^ 0x01) # Инвертируем 1 бит
# Сборка ошибочной подписи
q_inv = pow(q, -1, p)
h = (q_inv * (sp_faulty - sq)) % p
s_faulty = sq + h * q
# --- АТАКА ---
# Восстановление q: gcd(s_faulty^e - m, N)
q_recovered = GCD(pow(s_faulty, e, N) - m, N)
p_recovered = N // q_recovered
print(f"Attack Success: {p_recovered == p and q_recovered == q}")
4.2. SageMath/Python Example for Cryptanalysts
# SageMath Script
N = 187; p = 11; q = 17 # Пример для малых чисел
e = 3; d = inverse_mod(e, (p-1)*(q-1))
m = 88 # Хэш сообщения
# Fault injection in CRT
sp_faulty = 5 # Вместо правильного pow(m, d % (p-1), p)
sq = pow(m, d % (q-1), q)
s_faulty = crt([sp_faulty, sq], [p, q])
# Attack
extracted_q = gcd(power_mod(s_faulty, e, N) - m, N)
print(f"Extracted Factor: {extracted_q}") # Вернет 17
4.3. Example on Magma
// Magma Computational Algebra System
N := 187; e := 3; m := 88;
s_faulty := 121; // Получена от смарт-карты со сбоем
extracted_factor := Gcd(Modexp(s_faulty, e, N) - m, N);
Print("Recovered prime: ", extracted_factor);
4.4. Example on PARI/GP
\ PARI/GP Script
N = 187; e = 3; m = 88;
s_faulty = 121;
q_extracted = gcd((s_faulty^e) % N - m, N);
print("Recovered Factor: ", q_extracted);
5. Protection parameters and rules
To prevent the Boneh-DeMillo-Lipton attack, cryptographic standards (e.g. FIPS 140-3 for HSM devices) require signature verification before it is issued .
- Law of Safe Output: Never return the result of a modular exponentiation without checking it.
- Signature verification: The device evaluates \(s\), then checks whether \(s^e \equiv m \pmod N\) holds. If not, an exception (error) occurs, and \(s\) is erased from memory.
- Shamir’s Trick: Using random operands in a computation: adding a random number \( r \) to compute modulo \( p \cdot r \) and \( q \cdot r \).
1. Introduction: Why RSA-CRT is vulnerable
The RSA algorithm is widely used for digital signatures and encryption. To speed up computations (by a factor of 3-4), the Chinese Remainder Theorem (CRT) is used, breaking the exponentiation modulo N = p q into two smaller exponentiations modulo p and q . This provides a huge performance boost, but introduces a fatal vulnerability: if even a single-bit error occurs during the calculation of one of the halves ( s p or s q ) , an attacker who obtains the erroneous signature can recover the prime factors p and q , and therefore the secret key.
The attack, proposed by Dan Boneh, Richard DeMiglio and Richard Lipton in 1997, became a classic Fault Injection and is still used in testing secure modules (HSMs, smart cards, TPM).
2. Mathematical derivation of the attack
Let m be a message (or its hash), d be a closed exponent, e be an open exponent, N = p q .
A valid RSA-CRT signature is calculated as follows:
- d p = d mod (p−1) , d q = d mod (q−1)
- s p = m d p mod p , s q = m d q mod q
- s = s q + q · ( (s p − s q ) · q −1 mod p )
Now suppose that the calculation of s p fails, yielding an erroneous value ŝ p ≠ s p (modulo p ). However, s q is calculated correctly. The resulting erroneous signature ŝ satisfies:
- ŝ ≡ s (mod q) (since s q is true)
- ŝ ≠ s (mod p)
Then, when raised to the power e, we obtain:
- ŝ e ≡ m (mod q) (because s e ≡ m (mod N) , and coincides modulo q )
- ŝ e ≠ m (mod p)
Therefore, q divides (ŝ e − m) , but p does not. Therefore, q can be found as the greatest common divisor:
q = gcd(ŝ e − m (mod N), N)
If the attacker has both the correct signature s and the erroneous one ŝ , then it is simpler:
q = gcd(s − ŝ, N)
3. Attack demonstration in Google Colab (Python)
Below are ready-made scripts that can be copied into a Colab notebook and run. They generate keys, simulate a crash, and restore q .
🔹 Basic example (small numbers for clarity)
# Базовый пример атаки BDL на RSA-CRT (для понимания)
import math
# Генерация ключей (маленькие простые)
p, q = 47, 71
N = p * q
e = 17
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
m = 123 # сообщение
# CRT параметры
dp = d % (p-1)
dq = d % (q-1)
# Правильное вычисление
sp = pow(m, dp, p)
sq = pow(m, dq, q)
q_inv = pow(q, -1, p)
h = (q_inv * (sp - sq)) % p
s = sq + h * q
# ----- ВНЕДРЕНИЕ ОШИБКИ (инвертируем младший бит sp) -----
sp_fault = sp ^ 0x01 # или любое другое искажение
h_fault = (q_inv * (sp_fault - sq)) % p
s_fault = sq + h_fault * q
# ----- АТАКА: восстанавливаем q -----
diff = (pow(s_fault, e, N) - m) % N
q_recovered = math.gcd(diff, N)
p_recovered = N // q_recovered
print(f"Исходные: p={p}, q={q}")
print(f"Восстановленные: p={p_recovered}, q={q_recovered}")
print(f"Успех: {p == p_recovered and q == q_recovered}")
🔸 Example with 512-bit primes (more realistic)
# Пример с 512-битными простыми (можно запустить в Colab)
from Crypto.Util.number import getPrime, GCD
import random
# Генерация ключей
p = getPrime(512)
q = getPrime(512)
N = p * q
e = 65537
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
m = random.randint(2, N-1) # сообщение
dp = d % (p-1)
dq = d % (q-1)
sq = pow(m, dq, q)
# Симуляция сбоя: меняем один байт в sp
sp_correct = pow(m, dp, p)
sp_fault = sp_correct ^ (1 << 8) # инвертируем 8-й бит
# Сборка ошибочной подписи
q_inv = pow(q, -1, p)
h_fault = (q_inv * (sp_fault - sq)) % p
s_fault = sq + h_fault * q
# Восстановление q
diff = (pow(s_fault, e, N) - m) % N
q_recovered = GCD(diff, N)
p_recovered = N // q_recovered
print(f"q восстановлен: {q_recovered == q}")
print(f"p восстановлен: {p_recovered == p}")
🔸 Using the correct and incorrect signature (if both are known)
# Если у нас есть и правильная s, и ошибочная s_fault
# то восстановление ещё проще:
q_recovered = GCD(s - s_fault, N)
p_recovered = N // q_recovered
print(f"Успех: {p == p_recovered and q == q_recovered}")
📌 How to run in Colab: Copy any of the blocks to a new cell, after installing them pycryptodome with the command !pip install pycryptodome. All examples work out of the box.
4. Extension to ECDSA and hardware wallets
Although Bitcoin does not use RSA, the idea of fault injection carries over to ECDSA. When signing a transaction, r = (k G) x and s = k − 1 (z + r d A ) mod n are calculated . If an attacker causes a fault in the calculation of k (the nonce), then two signatures can be obtained with the same k but different s , allowing the secret key d A to be calculated .
In recent years, studies have been published on fault attacks on Ledger, Trezor, and other chips —for example, by undervolting or irradiating them with lasers. Therefore, manufacturers are implementing protective checks (double computation, nonce randomization, and signature verification before issuance).
5. Countermeasures and defensive strategies
| Measure | Description |
|---|---|
| Signature verification | Before issuing a signature, the device checks: s e ≡ m (mod N) . If there is a discrepancy, there is an error. |
| Shamir’s method | The calculations are performed modulo p·r and q·r with random r , then the consistency is checked. |
| Infrared/laser protection | Hardware sensors that detect unauthorized external influence. |
| Double computation | Recalculate the signature and compare the results (with some delay). |
6. Conclusion
The Boneh–DeMillo–Lipton attack is a striking example of how a mathematically sound algorithm can be compromised by its physical implementation . It highlights the importance of a holistic approach to security: cryptography is only as strong as the security of its underlying hardware and software.
Although RSA isn’t used in the context of Bitcoin, fault injection principles pose a direct threat to ECDSA wallets. This is why modern HSMs and hardware wallets are certified according to FIPS 140-3 and Common Criteria standards , which include fault tolerance tests.
The Boneh-DeMillo-Lipton attack is a shining example of how a mathematically perfect system (RSA) becomes critically vulnerable in implementation (RSA-CRT) due to physical hardware imperfections. Although Bitcoin uses ECDSA and is not directly vulnerable to this attack, the fault attack paradigm has become the basis for attacks on hardware cryptocurrency wallets, where signature generation failures are similarly provoked (e.g., attacks on ECDSA nonce k ), leading to private key leakage secp256k1.