Writeup - Symmetric

  • CTF : UIUCTF
  • Catégorie : Cryptanalyse
  • Fichiers fournis : chal.py, output.txt
  • Format du flag : uiuctf{...}
  • Auteur du WriteUp : DonAsako

Contexte

On nous propose un challenge qui chiffre un flag avec RSA, mais au lieu d’utiliser deux nombres premiers comme d’habitude, il y en a quatre :

$$
N = p \cdot q \cdot r \cdot s
$$

Au lieu de fournir les facteurs premiers directement, le challenge nous donne trois indices sous forme de somme de puissances :

  • $$ h_1 = p + q + r + s $$
  • $$ h_2 = p^2 + q^2 + r^2 + s^2 $$
  • $$ h_3 = p^3 + q^3 + r^3 + s^3 $$

Le flag est chiffré avec l’exposant public classique ( e = 65537 ).
Notre objectif est de retrouver les facteurs premiers et déchiffrer le flag.

Observations Clés

  • Les valeurs h1,h2 et h3 sont des sommes symétriques et peuvent être reliées aux polynômes symétriques élémentaires via les identités de Newton.
  • À partir de celles-ci, on peut reconstruire les coefficients du polynôme unitaire dont les racines sont ( p, q, r, s ) :

$$
P(x) = (x - p)(x - q)(x - r)(x - s) = x^4 - a_1 x^3 + a_2 x^2 - a_3 x + a_4
$$

avec :

$$
\begin{cases}
a_1 = h_1 \\ a_2 = \frac{h_1^2 - h_2}{2} \\
a_3 = \frac{h_3 - h_1 h_2 + a_2 h_1}{3} \\
a_4 = N
\end{cases}
$$

Une fois le polynôme construit, on le résout pour retrouver les quatre nombres premiers, puis on déchiffre le flag avec le RSA classique.

Exploitation

Reconstruction du polynôme et recherche des racines

On utilise SymPy pour construire le polynôme :

from sympy import symbols, Poly, solve

x = symbols("x")  
P = Poly(x**4 - a1 * x**3 + a2 * x**2 - a3 * x + a4, x)  
roots = solve(P, x)

Déchiffrement RSA

Une fois que l’on a les quatre nombres premiers ( p, q, r, s ), on calcule :

  • $$ \phi(N) = (p - 1)(q - 1)(r - 1)(s - 1) $$
  • $$ d = e^{-1} \mod \phi(N) $$
  • $$ m = c^d \mod N $$

Puis on décode le flag à partir de l’entier en clair.

🛠 Code de résolution complet

from sympy import symbols, Poly, solve  
from Crypto.Util.number import long_to_bytes

# Valeurs fournies (à remplacer par les données du challenge)  
h1 = ...  
h2 = ...  
h3 = ...  
N = ...  
ct = ...  
e = 65537

# Calcul des coefficients avec les identités de Newton  
a1 = h1  
a2 = (h1 * h1 - h2) // 2  
a3 = (h3 - h1 * h2 + a2 * h1) // 3  
a4 = N

# Construction et résolution du polynôme  
x = symbols("x")  
P = Poly(x**4 - a1 * x**3 + a2 * x**2 - a3 * x + a4, x)  
roots = solve(P, x)  
p, q, r, s = [int(root) for root in roots]

# Déchiffrement RSA classique  
phi = (p - 1) * (q - 1) * (r - 1) * (s - 1)  
d = pow(e, -1, phi)  
pt = pow(ct, d, N)

print(long_to_bytes(pt))

Flag

uiuctf{4_p0ly_n0m14l_70_ru13_7h3m_411}

Conclusion

Ce challenge illustre parfaitement comment une fuite d’information structurelle sur les facteurs premiers d’un RSA (comme leurs sommes ou sommes de puissances) peut totalement casser la sécurité.

🔐 Ne jamais révéler d’information sur les composants de votre clé, même des fonctions symétriques des premiers peuvent suffire à les retrouver.