Le challenge
On nous fournit trois chiffrés RSA du même message en clair, chacun chiffré avec un exposant public e = 3 mais des moduli différents. Pas de padding OAEP, pas de randomisation — les conditions parfaites pour l’attaque de Håstad.
Théorie : l’attaque de Håstad
Quand le même message m est chiffré avec e = 3 et trois clés publiques différentes (n1, n2, n3), on obtient :
c1 ≡ m³ (mod n1)c2 ≡ m³ (mod n2)c3 ≡ m³ (mod n3)
Par le théorème des restes chinois (CRT), on peut retrouver m³ mod (n1·n2·n3). Si m < min(n1, n2, n3), alors m³ < n1·n2·n3 et il suffit de calculer la racine cubique entière.
from sympy import integer_nthroot
from functools import reduce
def crt(remainders, moduli):
N = reduce(lambda a, b: a * b, moduli)
result = 0
for ri, ni in zip(remainders, moduli):
Ni = N // ni
_, xi, _ = extended_gcd(Ni, ni)
result += ri * Ni * xi
return result % N
m_cubed = crt([c1, c2, c3], [n1, n2, n3])
m, exact = integer_nthroot(m_cubed, 3)
assert exact
print(bytes.fromhex(hex(m)[2:]))Résultat
La racine cubique nous donne directement le message en clair, converti en bytes pour révéler le flag.
Flag : flag{h4st4d_br04dc4st_n0_p4dd1ng}