Wani CTF 2023 | fusion

#wani_ctf_2023

from Crypto.PublicKey import RSA

RSAkeys = RSA.generate(2048)
p = RSAkeys.p
q = RSAkeys.q
n = RSAkeys.n
e = RSAkeys.e
m = b"FAKE{<REDACTED>}"
c = pow(int.from_bytes(m, "big"), e, n)

mask = int("55" * 128, 16)
r = p & mask
mask = mask << 1
r += q & mask

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"r = {r}")

RSA。の半分ずつが交互にわかっているので、2bit探索するbranch and pruneで解ける

mask = int("55" * 128, 16)

n = 27827431791848080510562137781647062324705519074578573542080709104213290885384138112622589204213039784586739531100900121818773231746353628701496871262808779177634066307811340728596967443136248066021733132197733950698309054408992256119278475934840426097782450035074949407003770020982281271016621089217842433829236239812065860591373247969334485969558679735740571326071758317172261557282013095697983483074361658192130930535327572516432407351968014347094777815311598324897654188279810868213771660240365442631965923595072542164009330360016248531635617943805455233362064406931834698027641363345541747316319322362708173430359
e = 65537
c = 887926220667968890879323993322751057453505329282464121192166661668652988472392200833617263356802400786530829198630338132461040854817240045862231163192066406864853778440878582265466417227185832620254137042793856626244988925048088111119004607890025763414508753895225492623193311559922084796417413460281461365304057774060057555727153509262542834065135887011058656162069317322056106544821682305831737729496650051318517028889255487115139500943568231274002663378391765162497239270806776752479703679390618212766047550742574483461059727193901578391568568448774297557525118817107928003001667639915132073895805521242644001132
r = 163104269992791295067767008325597264071947458742400688173529362951284000168497975807685789656545622164680196654779928766806798485048740155505566331845589263626813345997348999250857394231703013905659296268991584448212774337704919390397516784976219511463415022562211148136000912563325229529692182027300627232945

def solve(p_, q_, i):
    if p_ * q_ == n:
        return (p_, q_)

    mod = (2**(2*i+2))

    p0 = p_ | (0<<(2*i+1))
    p1 = p_ | (1<<(2*i+1))

    q0 = q_ | (0<<(2*i+0))
    q1 = q_ | (1<<(2*i+0))

    if p0*q0 % mod == n % mod:
        r = solve(p0, q0, i+1)
        if r:
            return r
    if p0*q1 % mod == n % mod:
        r = solve(p0, q1, i+1)
        if r:
            return r
    if p1*q0 % mod == n % mod:
        r = solve(p1, q0, i+1)
        if r:
            return r
    if p1*q1 % mod == n % mod:
        r = solve(p1, q1, i+1)
        if r:
            return r
p, q = solve(r & mask, r & (mask << 1), 0)
d = pow(e, -1, (p-1)*(q-1))
m = pow(c, d, n)
print(bytes.fromhex(hex(m)[2:]))