HackademINT

Club de cybersécurité de Telecom SudParis


CRYPTO.rsa

Auteur : patate

----------------------------------

> Enoncé

Buy an encrypted flag, get a (almost intact) prime factor for free !

You can find a harder version of this challenge in the Programming category.

> Analyse du problème

Fichiers fournis

On nous fournit un script ainsi que son output.

But du challenge

Le script génère deux nombres premiers p et q très grands dont le produit correspond au N = p * q qui a servi à chiffrer le flag par le chiffrement RSA. Toutefois, on remarque que tous les ‘9F’ de l’héxadécimal de p ont été remplacés par des ‘FC’.

Il s’agit donc de retrouver la valeur de N qui a servi au chiffrement et de déchiffrer le flag avec la formule m=pow(c, d, n).

Proposition de script de résolution

Nous utilisons la librairie itertools pour générer toutes les possibilités de valeur pour p sachant que ‘FC’ peut soit être ‘9F’ soit ‘FC’ dans le p initial.

Puis nous tentons de diviser N par chacune de ces possibilités jusqu’à trouver la valeur p pour laquelle N / p est bien un entier. Cet entier correspond à q et il y aura bien unicité du résultat puisque N est un produit de deux nombres premiers.

Voici ma proposition de script:

import itertools
import gmpy2
import binascii

output = open('./output.txt', 'r').read().split('\n')

n = int(output[0])
times = output[1].count('FC')
p = output[1].replace('FC', '{}')
c = int(output[2])

p_possible = [int(p.format(*candidate), 16) for candidate in list(itertools.product(['9F', 'FC'], repeat=times))]

for r in p_possible:
    s = n // r
    if s * r == n:
        q = s
        p = r
        break

e = 65537
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = binascii.unhexlify(hex(pow(c, d, n))[2:]).decode()

print(m)

Flag

On obtient le flag: INSA{I_w1ll_us3_OTp_n3xT_T1M3}