[Hacktoday Qual 2022] – Looks Easy

attachment: chall.py

from Crypto.Util.number import *

def Fn(e):
    return 2**(2**e) +1

def txt(txt):
    with open (txt,”rb”) as f:
        m = f.read().strip()
        m = bytes_to_long(m)
        p,q,r = getPrime(0x400), getPrime(0x400),getPrime(0x400)
        f.close()
        return m,p,q,r

def abc(a,b,c):
    x,y,z = (a+b), (b+c), (a+c)
    return x,y,z

def stu(s,t,u):
    v,w,x = s*t, t*u, s*u
    return v,w,x

def main():
    m,p,q,r = txt(“flag.txt”)
    n = p*q*r
    m1,m2,m3 = abc(p,q,r)
    n1,n2,n3 = stu(m1,m2,m3)
    e = Fn(4)
    c = pow(m,e,n)
    with open(“output.txt”, “w”) as f:
        f.write(f”{c = }\n”)
        f.write(f”{e = }\n”)
        f.write(f”{n1 = }\n”)
        f.write(f”{n2 = }\n”)
        f.write(f”{n3 = }\n”)


if __name__ == “__main__”:
  main()

Diberikan sebuah codingan enkripsi RSA yang menggunakan 3 faktor prima p, q, r yang nilainya dikalkulasi lagi menjadi n1, n2, dan n3 yang diberikan. Secara garis besar, operasinya adalah seperti ini.

m1 = p+q, m2 = q+r, m3 = r+p
n1 = m1*m2, n2 = m2*m3, n3 = m3*m1

Kita mulai dulu dari mencari nilai m1, m2, m3. Saya mengambil contoh m1 yang dapat dicari dengan cara berikut:

m2 = (n1/m1)

m3 = (n3/m1)

n2 = (n1/m1)*(n3/m1)

n2 = ((n1*n3)/(m1)**2)

m1 = sqrt((n1*n3)/n2)

Setelah m1 didapatkan, substitusikan pada persamaan lainnya untuk mencari m2 dan m3. Kemudian untuk mencari p, q, dan r akan kita gunakan m1, m2, dan m3 dengan cara berikut:

p = m1 – q

p = m3 – r

m1 – m3 = q – r

m2         = q + r

============+

m1 – m3 + m2 = 2q

q = (m1 – m3 + m2)/2

Setelah q didapatkan, substitusikan pada persamaan lainnya untuk mencari p dan r. Kemudian tinggal mengkonstruk d menggunakan p, q, r yang telah didapatkan dan decrypt flagnya. Beginilah kodingan yang kami buat:

c = 436960412072214045096180530700843502515012171384802652493773913644527833532417721196944881891505953361033846945439625815223097860875636697306228782175257814533303540209958142456784309856802021263613466082204663740579825078844544224329239857245480651439695870935835917116395751056302475392413911267142422954002574548888573955030475638170284512613952466074276907419902043262265358188092997929312303780246039783490478232310525033325043397198995502334285142446834574097000450048776195804096965333272087613172206134275600528607762447899062959963933595166494890908094985357344569476797163636030302583401080100434204470836082247486384977710762720498658667569465724946784061808383386313732062368380002805607639463566159795832365831361536900175110006358523857952990331352135348329579269797604877762823747576426140569419263532828320365331557114516036980320590302346517935629346930555239781736215331683368236420686077784003820171247525
e = 65537
n1 = 43419909416946913767825842373711181675652566160611835722171044487156915062490683071171980325526009804083865038071149560498669280701834718918453025664539241272868303962700103840609809873716285474972931268891717272515028356070896040849417280111716117899812116188105563344261751263860570984848489543153958979824488384073837375227652070399455272072089098948209424043547795869328716099012512207745242768470726791070758702027115950056777024596991878665289097251715196749028476682590710623285014369851651209358733790856518798956452305404287572467887162501082433794652451400315517939964156360641100796764180081723666863836368
n2 = 48742842150444626504690269163492197199090568569745469085813370700858537952993856155241792828979896371238271607532375483161129023420288793341152217175049230041771513558006187847703613815379557383561795243587907812244240908949286426777080928761849637111777544603802340255291257864305520173834355223339260476562118612479398589815531622588965088318189464798826816922627359604839054003031760764192836614908804783537221708818146298469252484979002179011238664935065848020611179483405860417304014498047326915983068685329845344768224685943681281105133408957910585585080898959738912582306016864063369322704053348125204908380800
n3 = 47866974927401612170586712722713456471257739633432395239947023223335073746244231358918684959348494255798189036788306551897703579200020539480578807734578441624886957561975253106153096414684934138317074392924305664128000529094082563902251410427386906926013620310775351035745249626346882919580446618124765390933537136813004050581183091396590269131896013970558712912378301833432358794485265487211999932859629428043149518103773537233108967139721009547049131859008765208765365189650105287645272355811107324523741626244726877589710507350589606944548543546538994479729492004741112038872169088244327488569146315299600131290400

import gmpy2

m2, _ = gmpy2.iroot((n1*n2)//n3, 2)
print(m2)
m3 = n2//m2
print(m3)
m1 = n1//m2
print(m1)
assert n1 == m1*m2 and n2 == m2*m3 and n3 == m1*m3

r = (m2 – m1 + m3)//2
print(r)
q = m2 – r
print(q)
p = m3 – r
print(p)
assert m1 == p+q and m2 == q+r and m3 == r+p

n = p*q*r
phi = (p-1)*(q-1)*(r-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

Output:

Flag = hacktoday{L00k_H0w_34zy_1t_1s_469617261}

Leave a Reply

Your email address will not be published. Required fields are marked *