<- IMAGINARYCTF

Relatively Small Arguments

1 minuto de lectura

Se nos proporciona el código en Python utilizado para cifrar la flag:

#!/usr/bin/env python3

from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p - 1) * (q - 1)
d = getPrime(32)
e = pow(d, -1, phi)
m = bytes_to_long(open('flag.txt', 'rb').read())
c = pow(m, e, n)

print(f'{n = }')
print(f'{e = }')
print(f'{c = }')

'''
n = 134872711253918655399533296784203466697159038260837702891888089821702090938512308686613559851138816682269099219724900870388583883202954112422023894133671598222066489215524613014212242490437041258588247678792591072443719118562580052842727775772283919113007499992167089258075609504428713653013187230671841726369
e = 50920242742169837294267124730818234703309561711363177522992049271988492365017092545331352650316729342598781520444569769450329777448285534584484096179230968844630486688656705514759778561817709539781927624692111848722199024819005269510690240743887870339853351421726436719236180272680237157536332997570569192069
c = 133155317855020316110137499609990113815646625767974277474197900721563685454745247616867035013963212538345727281661922602291072931578581035070345294335733120033652413487827994383327148598029065495228796201084369245315585407592741900307825557286213370482646401885352854920924352919398804532780740979273692054391
'''

El criptosistema utilizado es RSA, pero la implementación es errónea. El problema es que el número privado es relativamente pequeño (un número primo de 32 bits). Por tanto, podemos romper el cifrado con el ataque de Wiener.

Podemos implementar este ataque en Python con una librería llamada owiener (que se puede instalar con pip). Una vez que tenemos , podemos descifrar el texto cifrado como .

Este es el script en Python que soluciona el reto:

#!/usr/bin/env python3

import owiener


def main():
    n = 134872711253918655399533296784203466697159038260837702891888089821702090938512308686613559851138816682269099219724900870388583883202954112422023894133671598222066489215524613014212242490437041258588247678792591072443719118562580052842727775772283919113007499992167089258075609504428713653013187230671841726369
    e = 50920242742169837294267124730818234703309561711363177522992049271988492365017092545331352650316729342598781520444569769450329777448285534584484096179230968844630486688656705514759778561817709539781927624692111848722199024819005269510690240743887870339853351421726436719236180272680237157536332997570569192069
    c = 133155317855020316110137499609990113815646625767974277474197900721563685454745247616867035013963212538345727281661922602291072931578581035070345294335733120033652413487827994383327148598029065495228796201084369245315585407592741900307825557286213370482646401885352854920924352919398804532780740979273692054391

    d = owiener.attack(e, n)

    m = pow(c, d, n)
    print(bytes.fromhex(hex(m)[2:]).decode())


if __name__ == '__main__':
    main()

Y obtenemos la flag:

$ python3 solve.py
ictf{have_fun_at_ICTF_22!!!_559543c1}

El script completo se puede encontrar aquí: solve.py.