warmup

crypto aja wkwk

chall.py
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
from flag import FLAG
from math import gcd

key = RSA.generate(2048)
p = key.p
q = key.q
n = key.n
e = key.e
phi = (p - 1) * (q - 1)

_ = q * (n - (p + q) + 1)

pt = bytes_to_long(FLAG)
c = pow(pt, e, n)

with open("output.txt", "w") as f:
    f.write(f"c={c}\n")
    f.write(f"n={n}\n")
    f.write(f"_={_}\n")

we were given the c n and _

we can get the q from the _ by

n - p - q + 1 p * q - p - q + 1 (p * q - p) - (q - 1) p(q - 1) -1(q - 1) (q - 1)(p - 1) _ = q * phi(n)

phi(n) = pq - p - q + 1 n - p - q + 1 n - n/q - q + 1

q (n - n/q - q + 1) qn - n - q^2 + q = _ q^2 -qn -q + n - _ = 0 q^2 -(n + 1)q + (n - _) = 0 aq^2 + bq + c = 0 q = (n + 1)/2 +- akar((n+1)^2 - 4 * 1 * (n - _))/2 D = (n - 1)^2 + 4 * _ q = ((n + 1) - sqrt(D)) / 2 p = n/q

from Crypto.Util.number import long_to_bytes, inverse
import math

c = 11665601060578904089239843410225375694820409159682646249179665252868538140942592308238001634946015207806182773645946514639330174073596963565398520984052812107864649042722601501632527387908205197544384349913254159008138197292136321258764747423486946823235609128957524452960014865843501039521715215870481409233163822644173905779182369294926574074559860993002680341523344760620344945438597058952297301238786668292187474586927204408094376608063862929071392549106291260554379095737404811174829081624290601025873096893989889282638926503683027576448053817103472391567044397645990604427817477319552748352542310624328971111224
n = 20745373907683254825049290479805022577698417756745553065502184542440290698675636611211421768628978558536798632884593780484089228918687940040784362096583885762918444510182091023737128509040813180764229301253403461950991005763724240539347285983746713529429194017968452490924072330045377883194031624546110908624207975197728193864733998735366182116283389761918556904685848874101378924898558207815806672111491676015870193395402827343682606599678263521198825549391621181707164197806471775556954603164376754177030602270124987837166089116699351375651725762442815795419402069377433601213536237573445200548516577224983154385131
bonus = 3008402167498686489658046584687250894054805283581595585910627461718404505357580519988257478154170723732195801598192620002626334174481830535485128278276511858099424631496543061198774072622958637733862789870333290644285980870181665552312286278897680441753106657293626554905420259982375733657176710899917039859895817850089768953028685172911328610240422458044543030626862422759694259734614534705301930280236678366230779802305105972029619231686586980300303046553978920455130556261232110533615116834947668222123916762076470140319035627450247512567064155652636242372945159083886013654433917733912881775893574733186600603947663871285527018487051507837543317898530428326302145470131080870627284805693249892024593858399145837368527441729384247075765654298702328429025268308202019015461840160295361403772376945443406115341340052412259293257561437435810602586966870673570323646951094860378389988561936472503866618300378850460619556867200
e = 65537

D = (n - 1)**2 - 4 * bonus
sqrt_D = math.isqrt(D)
q = ( (n + 1) - sqrt_D ) // 2
p = n // q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)

pt = pow(c, d, n)
flag = long_to_bytes(pt)
print(flag.decode())