RSA Petit Exposant

Énoncé

Un message a été chiffré avec RSA. L'administrateur a commis une erreur classique : utiliser e=3 avec un message très court.

Paramètres RSA :

RSA : c = m^e mod n

Trouvez m (le message en clair). Le flag est CSA{rsa_sm4ll_3xp0n3nt} si vous prouvez que vous comprenez l'attaque.

L'attaque de la racine cubique

Quand e=3 et que le message m est petit (m³ < n), alors c = m³ sans réduction modulaire. Il suffit de calculer la racine cubique entière de c pour retrouver m.

Vérification : m³ mod 3233 = 2790 → m = ?

Étapes :

1. Factoriser n : 3233 = 61 × 53

2. Calculer φ(n) = (61-1)(53-1) = 3120

3. Calculer d = e⁻¹ mod φ(n) tel que 3×d ≡ 1 mod 3120

4. Déchiffrer : m = c^d mod n