HackademINT

Club de cybersécurité de Telecom SudParis


PROG.rsa2

Auteur : patate

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

> Enoncé

If not done already, you should probably attempt Part 1 of this challenge (in the Crypto category).

Same player, shoot again.

> Analyse du problème

Fichiers fournis

On nous fournit un script ainsi que son output.

But du challenge

Ce challenge fait suite au challenge de crypto rsa.

Cette fois-ci, au lieu d’effectuer seulement un remplacement, on doit retrouver la valeur initiale de p à partir d’une valeur qui a subi 8 remplacements successifs.

Il s’agit encore une fois 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

Voici ma proposition de script:

import itertools
import gmpy2
import binascii
import pwn

output = open('./output.txt', 'r').read().split('\n')
n = int(output[0])
p = output[1]
c = int(output[2])


replaced = [('59','3E'), ('9E','E0'), ('6B','89'), ('E4','38'), ('09','95'),
            ('5E','FF'), ('33','D4'), ('12','8D')]

possibilities = [p]

def find_possible(possibilities, couple):
    initial, final = couple
    possible = []
    for p in possibilities:
        if final in p:
            times = p.count(final)
            p = p.replace(final, '{}')
            p_possible = list(itertools.product(couple, repeat=times))
            for candidate in p_possible:
                possible.append(p.format(*candidate))
    return possible

# Mon pc pouvant difficilement stocker toutes les possibilités de p,
# j'ai stocké les possibilités jusqu'à l'avant dernier remplacement
# avant de tester les possibilités une par une pour le dernier remplacement

info = pwn.log.progress('Looking for all possibilities')
for couple in replaced[:-1]:
    possibilities = find_possible(possibilities, couple)

tested = 0
for i in range(len(possibilities)):
    possible = find_possible([possibilities[i]], replaced[-1])
    for candidate in possible:
        tested += 1
        info.status('Testing possibility #{}'.format(tested))
        r = int(candidate, 16)
        s = n // r
        found =  False
        if s * r == n:
            found = True
            info.success('ok')
            q = s
            p = r
            break
    if found:
        break

e = 65537
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = binascii.unhexlify(hex(pow(c, d, n))[2:]).decode()
pwn.log.info_once('Here is your flag: {}'.format(m))

Flag

On obtient le flag: INSA{Uh_never_give_4w4y_your_Pr1mes_I_m34n_duhhh}