Challenge: Simple crypto is the best crypto.
For this crypto chall we have to download 1 file. A sage one.
def generate():
p = random_prime(2^1024, lbound=2^1023)
x=randint(1,2^16)
y=randint(1,2^256)
a=randint(2^1023,2^1024)
q=random_prime(2^1024)
n=p*q
return x,a,y,n,p
x,a,y,n,p = generate()
k = x * y + a * p
e=65537
print(f"x = {x}")
print(f"a = {a}")
print(f"n = {n}")
print(f"k = {k}")
m = b'L3AK{<Redacted>}'
flag = int.from_bytes(m, byteorder='big')
c= pow(flag, e, n)
print(f"c = {c}")
'''
x = 54203
a = 139534605978199350449870348663594126359773246906906418074945064315708552206952695156472923968554408862426942537522569163756593332601739006413404986641247624386522169136633429464195370373009454673819688653512479919153332504769835621608305089536245284458011218876474599059184828911301976396971466368457267831713
n = 12909957208634846878337953184362917609451224905637563117148705894888627434882610771803126452504238664471840340722310690445704139825753660053450331966698205860077330083433391290469454571152366284661640391190008258576947840075212180965738595761925516686689797153224716140447515370184846067654512660266993573880775530634588475842083212670090415716860925772115834314563453955681012820960922892736520042799257599331942717963921797157341454739255402633419216921702659541513141028779948257696746810146033667942181244847983610429227387863821351416689099862418820999250005071861968501333899759899513283613946626413863922604073
k = 24474689179117620559916890529357882261493825442019850679598519081287156822984032786458479363048845076078220151760752906879055457682971398809768604333650029141164831566127754715775782823279839766009120238777348170982471623193652714921064243946655726118484337862412275391615166714375745390409664610412156281691721978732319253694004232933156865189917761521085635692596755802274763409871937618659197646864593743015558828475450200247766980008744319676783526158213931581034209356092026748307730083927225249093712227456855972520574747646873074625455900058136458828591335711677741591552501530047335481073272381631524755666119
c = 11185314040721202177044508537272244264288033276739579716599246665772965854249656943282002695659011960313245796587834222078633141747802754149848079632693280265262199729548775879612614113828267471629389698999657686858047585254549801752634049341009476489652456620836030696102393122618822021082792763848220677651608135328630551380537642144416978955966827336280510774254681264136102268730343853559751471313539810499170669215479225898738527316798768622089152851154959800113070358637984124299357803777453137311143202502153552192970732744885328421213081964363890280109214401691255867427694709196120824176729643585687319321473
'''
With just a simple look we can see that this is RSA. So once we are aware of that, we know that in order to decipher RSA we need d, the private key. If you don’t understand or are not very familiar with RSA I would suggest checking this: https://www.geeksforgeeks.org/computer-networks/rsa-algorithm-cryptography/ , that will give you a brief summary in order to understand the following equations.
One of the ways to compute d in python is the following:
d = pow(e, -1, phiN)
But we dont have phiN, and for phiN we also need p and q. So how do we address this challenge?
We need to solve k = xy + ap. With some math we can reorder this so that we can calculate it with the variables we have. k = xy + ap
k - xy = ap
k - xy ≡ 0 (mod a) (Modular congruence property)
y = k/x (mod a)
y = x⁻1 k (mod a)
We can calculate this in python as:
y = pow(x⁻1, k, a)
For some more clarity this: x = pow(4, 3, 5) means: (4x4x4)%5
So the script to solve the challenge would be the following:
from Crypto.Util.number import *
x = 54203
a = 139534605978199350449870348663594126359773246906906418074945064315708552206952695156472923968554408862426942537522569163756593332601739006413404986641247624386522169136633429464195370373009454673819688653512479919153332504769835621608305089536245284458011218876474599059184828911301976396971466368457267831713
n = 12909957208634846878337953184362917609451224905637563117148705894888627434882610771803126452504238664471840340722310690445704139825753660053450331966698205860077330083433391290469454571152366284661640391190008258576947840075212180965738595761925516686689797153224716140447515370184846067654512660266993573880775530634588475842083212670090415716860925772115834314563453955681012820960922892736520042799257599331942717963921797157341454739255402633419216921702659541513141028779948257696746810146033667942181244847983610429227387863821351416689099862418820999250005071861968501333899759899513283613946626413863922604073
k = 24474689179117620559916890529357882261493825442019850679598519081287156822984032786458479363048845076078220151760752906879055457682971398809768604333650029141164831566127754715775782823279839766009120238777348170982471623193652714921064243946655726118484337862412275391615166714375745390409664610412156281691721978732319253694004232933156865189917761521085635692596755802274763409871937618659197646864593743015558828475450200247766980008744319676783526158213931581034209356092026748307730083927225249093712227456855972520574747646873074625455900058136458828591335711677741591552501530047335481073272381631524755666119
c = 11185314040721202177044508537272244264288033276739579716599246665772965854249656943282002695659011960313245796587834222078633141747802754149848079632693280265262199729548775879612614113828267471629389698999657686858047585254549801752634049341009476489652456620836030696102393122618822021082792763848220677651608135328630551380537642144416978955966827336280510774254681264136102268730343853559751471313539810499170669215479225898738527316798768622089152851154959800113070358637984124299357803777453137311143202502153552192970732744885328421213081964363890280109214401691255867427694709196120824176729643585687319321473
e=65537
# k = x*y + a*p
# k - x*y = a*p
# k - x*y =_ 0 (mod a)
# y =_ (x⁻1)*k (mod a)
x_inv = pow(x, -1, a)
y = (x_inv * k) % a
p = (k-(x*y))//a
q = n//p
phiN = (p-1)*(q-1)
d = pow(e, -1, phiN)
m = long_to_bytes(pow(c,d,n))
print(m.decode())
L3AK{u_4ctu4lly_pwn3d_LLL_w1th_sh0rt_v3ct0rs_n1c3}