Relatively Small Arguments

1 minute to read

We are given the Python source code used to encrypt the 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
'''

The encryption type is RSA, but the implementation is wrong. The issue is that the private number $d$ is relatively small (a 32-bit prime number). Hence, we can break the encryption with Wiener’s attack.

We can implement this attack in Python with a library called owiener (the installation can be done with pip). Once we have $d$, we can decrypt the ciphertext as $m = c^d \mod{n}$.

This is the solution script in Python:

#!/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()

And we obtain the flag:

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

The full script can be found in here: solve.py.