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 $d$ 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 $d$, podemos descifrar el texto cifrado como $m = c^d \mod{n}$.
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.