AmateursCTF 2023 - You get extra information 1

Description

Category: Cryptography

Downloads:

• main.py
• output.txt

Resolution

The goal is to recover p and q used to encrypt the flag thanks to the provided information:

• main.py: gives information about how extra_information is defined;
• output.txt: contains the integers.

Let $x$ be extra_information. Then we have this system of equations:

\[\begin{cases} n = p * q\\ x = 2p + q \end{cases}\]

We solve it using z3:

from z3 import *

n = 83790217241770949930785127822292134633736157973099853931383028198485119939022553589863171712515159590920355561620948287649289302675837892832944404211978967792836179441682795846147312001618564075776280810972021418434978269714364099297666710830717154344277019791039237445921454207967552782769647647208575607201
c = 55170985485931992412061493588380213138061989158987480264288581679930785576529127257790549531229734149688212171710561151529495719876972293968746590202214939126736042529012383384602168155329599794302309463019364103314820346709676184132071708770466649702573831970710420398772142142828226424536566463017178086577
e = 65537
x = 26565552874478429895594150715835574472819014534271940714512961970223616824812349678207505829777946867252164956116701692701674023296773659395833735044077013

s = Solver()

p = Int('p')
q = Int('q')

s.add(
    n == p*q,
    x == 2*p+q
)

assert s.check() == sat

p_ = s.model()[p].as_long()
q_ = s.model()[q].as_long()

Once we recovered p and q, we can recover the private key:

phi = (p_-1)*(q_-1)
d = pow(e, -1, phi)

And finaly decrypt the flag:

import binascii
m = pow(c, d, n)
flag = binascii.unhexlify(hex(m)[2:])
print(flag)

We get the flag: amateursCTF{harder_than_3_operations?!?!!}

External ressources

• Solution base on this writup: Sum-O-Primes by WhatTheFuzz - CTFtime