Code solution

kRSA_solve.py

from pwn import *
from Cryptodome.Util.number import *
import time

SIZE = 32

conn = connect("krsa.ctf.intigriti.io", 1346)
conn.recvuntil(b"n=")
n=int(conn.recvuntil(b"\n").strip().decode())
conn.recvuntil(b"e=")
e=int(conn.recvuntil(b"\n").strip().decode())
conn.recvuntil(b"ck=")
ck=int(conn.recvuntil(b"\n").strip().decode())

print(f"{n=}")
print(f"{e=}")
print(f"{ck=}")
start = time.time()

# we first make a lookup table for the first half of the key
meetinthemiddle = {}
for i in range(1, 2**(SIZE//2+1)):
    z = pow(i, e, n)
    meetinthemiddle[(ck*inverse(z, n))%n] = i

# then we bruteforce the second half of the key
k = -1
for i in range(1, 2**(SIZE//2+1)):
    if pow(i, e, n) in meetinthemiddle:
        k = i*meetinthemiddle[pow(i,e,n)]
        print("Found key :", k)
        break

print(time.time()-start)

if k == -1:
    print("Key not found, restart script")
    conn.close()
    exit()

conn.send(str(k).encode()+b"\n")
conn.interactive()