Lazy Modulus Attack
Cryptosystem
RSA & DSA
Requirements
Public key with a modulus that is a product of two primes p and q, where p is much smaller than q.
Description
The attacker can recover the private key from the public key if the modulus is poorly generated. If the modulus is a product of two primes p and q, where p is much smaller than q, the attacker can factorize the modulus using the GCD algorithm.
Example
from Crypto.Util.number import getPrime, inverse
p = getPrime(512)
q = getPrime(1024)
n = p * q
e = 65537
d = inverse(e, (p-1)*(q-1))
print(f"p: {p}")
print(f"q: {q}")
print(f"n: {n}")
print(f"e: {e}")
print(f"d: {d}")
# Attacker
def lazy_modulus_attack(n, p):
q = n // p
return p, q
p, q = lazy_modulus_attack(n, p)
print(f"Recovered p: {p}")
print(f"Recovered q: {q}")
assert p * q == n
Real world
In 2012, a research showed that 0.2% of the RSA keys in the internet were vulnerable to this attack.