Contexte
Nous avons ici deux fichiers :
smolkkey.pyqui est un script python.smolkkey.txtqui contient des informations sûrement en relation avec le flag.
Nous avons aussi une image avec 2 doge mème, un costaud avec un grand nombre $2¹⁶ + 1 = 65537$ et un autre plus petit avec le nombre 3.
Solution
from gmpy2 import powmod as pow
from Crypto.PublicKey import RSA
class Smolkkey:
def __init__(self):
k = RSA.generate(2048, e = 3)
self.pk = (k.n, k.e)
self.sk = (k.n, k.d)
def encrypt(self, m):
n, e = self.pk
c = pow(m, e, n)
return int(c)
def decrypt(self, c):
n, d = self.sk
m = pow(c, d, n)
return int(m)
# Generate a key
E = Smolkkey()
# Encrypt the fag
flag = open("flag.txt", "rb").read()
flag = int.from_bytes(flag, "little")
c = E.encrypt(flag)
# Test decryption
assert flag == E.decrypt(c)
# Output publc values
n, e = E.pk
print(f"{n = }")
print(f"{e = }")
print(f"{c = }")
Ici dans le script nous avons une class Smolkkey avec trois fonctions :
def __init__(self):
k = RSA.generate(2048, e = 3)
self.pk = (k.n, k.e)
self.sk = (k.n, k.d)
Donc ici on génère un constructeur qui produit le couple de clef RSA. Premièrement il génère les informations des clefs avec un module de 2048 bit et un exposant de 3. L’exposant est trop petit il sera possible de casser la clef avec une attaque comme Coppersmith ou des méthodes de racine cubique avec modulo.
- On a
pkla clé publique (chiffrement du message). - On a
skla clé privée (déchiffrement du message).
def encrypt(self, m):
n, e = self.pk
c = pow(m, e, n)
return int(c)
La deuxième fonction permet de chiffrer un message nous avons plusieurs variables :
m : le message en claire envoyer en argument dans la fonction.
n : la clé publique qui est grand (c’est important pour la suite).
e : l’exposant qui est petit.
c : le message chiffré.
On a aussi la formule pour le chiffrement du message qui est : $$c \equiv m^e \pmod{n}$$
Si $n \gt m³$ alors on se retrouvera avec la formule suivante : $$c \equiv m^e$$
car le reste est 0
def decrypt(self, c):
n, d = self.sk
m = pow(c, d, n)
return int(m)
Pour la troisième fonction on se retrouve dans le même cas que la deuxième, ici c’est une fonction qui permet de déchiffrer le message. On effectue l’opération inverse.
# Generate a key
E = Smolkkey()
# Encrypt the fag
flag = open("flag.txt", "rb").read()
flag = int.from_bytes(flag, "little")
c = E.encrypt(flag)
# Test decryption
assert flag == E.decrypt(c)
# Output publc values
n, e = E.pk
print(f"{n = }")
print(f"{e = }")
print(f"{c = }")
Dans le corps principal du programme on fait ceci :
-
On génère les clefs.
-
On chiffre le flag qui se trouve dans le ficher
flag.txt. -
On test le test si le flag a bien été chiffré en le déchiffrant et en comparant avec la valeur original.
-
On affiche les valeurs publiques.
-
Maintenant regardons le fichier :
smolkkey.txt
n = 20828609401338794038836680655046788059251524928933537772275737490132096798900518851229365799426251400151127719543434160180496659560792762761336988343332946920310984844136554433346165529108260963140451576722579583104830933409454682160084747257400706214980238995436388944310800852033141986598424966358149711167942491331040747300866718813771865768701794983365111208518863175847678947437360554933091347604616653687980177405805542214635577758515398014710929022135522835744517328114492844837858920033569071591971676487452812830920525469634367387593309067794509735740140745616085618489218115494716811261406227449967579233657
e = 3
c = 6317668510138686569655374990729607736156413707292408158720036346854309670467296052918552527575331589363290061240725095262980389263184520673983411112154423282089471021996509038472493779143273789325774414352608726252566350689111876373836913240644190951995980896093509379920452743478551321978067299216590452459233562642920123055978471365092000347562228787318105538018723376505390423730687522026043802357456368003656219942603097205774742385485995835519133581552096067468551713114231926639878045212204590071768
Nous des variables publique suivante :
- $n$ : le module qui est très grand.
- $e$ : l’exposant qui est très petit.
- $c$ : le message qui est chiffré.
Si par chance $m³ \lt n$, alors il sera possible de simplifier la formule comme ceci pour trouver c : $$c \equiv m^3$$
Comme on a $c$ il voudra trouver la racine cubique de $m$ pour $c$, il faut aussi une autre condition que $m$ soit un cube parfait.
Un cube parfait à la propriété suivante : $$m^3 = m * m * m$$
A partir de cela on peut lancer une attaque :
from gmpy2 import iroot
# Données fournies
n = 20828609401338794038836680655046788059251524928933537772275737490132096798900518851229365799426251400151127719543434160180496659560792762761336988343332946920310984844136554433346165529108260963140451576722579583104830933409454682160084747257400706214980238995436388944310800852033141986598424966358149711167942491331040747300866718813771865768701794983365111208518863175847678947437360554933091347604616653687980177405805542214635577758515398014710929022135522835744517328114492844837858920033569071591971676487452812830920525469634367387593309067794509735740140745616085618489218115494716811261406227449967579233657
e = 3
c = 6317668510138686569655374990729607736156413707292408158720036346854309670467296052918552527575331589363290061240725095262980389263184520673983411112154423282089471021996509038472493779143273789325774414352608726252566350689111876373836913240644190951995980896093509379920452743478551321978067299216590452459233562642920123055978471365092000347562228787318105538018723376505390423730687522026043802357456368003656219942603097205774742385485995835519133581552096067468551713114231926639878045212204590071768
# Tentative de racine cubique directe
m, exact = iroot(c, 3)
if exact:
flag = int(m).to_bytes((m.bit_length() + 7) // 8, 'little')
print("Flag:", flag.decode())
else:
# Recherche de k
for k in range(1, 1000):
candidate = c + k * n
m, exact = iroot(candidate, 3)
if exact:
flag = int(m).to_bytes((m.bit_length() + 7) // 8, 'little')
print(f"Flag trouvé avec k={k}:", flag.decode())
break
else:
print("Aucun cube trouvé.")
Le programme va essayer d’extraire la racine cubique et vérifie que c’est un cube parfait. Si on trouve une racine cubique directe et que c’est un cube parfait on peut déchiffrer le message.
Voici l’exécution :
python3 a.py
Flag: FCSC{XXX}