# someinterersa

Co-authors: @JOHNKRAM @eki

```
一个简单的RSA挑战
```

The attachment contains the following code:

```
from secret import flag
from Crypto.Util.number import * 

while 1:
    p = getPrime(1024)
    q = getPrime(1024)
    if (GCD(p-1,q-1)) == 2:
        break

N = p * q
phi = (p-1)*(q-1) 
e1, e2 = pow(getPrime(880), -1, phi), pow(getPrime(880), -1, phi)
c = pow(bytes_to_long(flag), 65537, N)

print(f"N = {N}")
print(f"e1 = {e1}")
print(f"e2 = {e2}")
print(f"c = {c}")
```

@JOHNKRAM provided the solution: instead of solving `p` and `q`, since `flag**65537` is unchanged, each time we get a pair of `N` and `pow(flag, 65537, N)`. So with enough values we can use CRT to find `flag**65537` to see it has a 65537-th root.

@JOHNKRAM gives the following attack script in sage:

```
from pwn import *

addr = "pwn-3a0101741b.challenge.xctf.org.cn"
port = int(9999)
def work(b):
    ls = b.decode().strip().split('\n')
    N = Integer(int(ls[0].split(' ')[-1]))
    c = Integer(int(ls[3].split(' ')[-1]))
    return N, c

def ask(n):
    r = []
    while n:
        m = min(n, int(16))
        n -= m
        cs = [remote(addr, port, ssl=True) for _ in range(m)]
        r += [work(conn.recvall()) for conn in cs]
        for conn in cs:
            conn.close()
    return r
def solve(r):
    Ns, cs = zip(*r)
    return prod(Ns), CRT(list(cs), list(Ns))
import time
n = int(1)
t0 = time.time()
N, c = solve(ask(n))
print(time.time() - t0)
file = open("result.txt", "w")
while True:
    try:
        m = int(c.nth_root(65537))
        print(m, file=file)
        print(m.to_bytes(m.bit_length() + 7 >> 3, 'big'), file=file)
        break
    except:
        t0 = time.time()
        N1, c1 = solve(ask(n))
        print(n, time.time() - t0)
        t0 = time.time()
        c = CRT(c, c1, N, N1)
        print(n, time.time() - t0)
        N *= N1
        n <<= 1
```

It tries to get enough pair of `(N, pow(flag, 65537, N))` to solve `flag`. However, it is too slow and the server will sometimes return empty string.

Suggested by @JOHNKRAM, I split the file into two parts, the first part is responsible for getting the numbers:

```
from pwn import *
addr = "pwn-f135dd10cc.challenge.xctf.org.cn"
port = int(9999)
def work(b):
    ls = b.decode().strip().split('\n')
    N = Integer(int(ls[0].split(' ')[-1]))
    c = Integer(int(ls[3].split(' ')[-1]))
    return N, c
file = open("temp.txt", "a")
while True:
    cs = [remote(addr, port, ssl=True) for _ in range(128)]
    r = [work(conn.recvall()) for conn in cs]
    for conn in cs:
        conn.close()
    print(str(r), file=file)
    file.flush()
```

And I keep it running in the background and collected more than 20000 pairs. However, solving this large number of CRT is very slow, so we use parallel computation for the second part:

```
from pwn import *
import multiprocessing
import time
from multiprocessing import Process, Queue

def worker_function(nums, q):
    c = CRT([Integer(x[1]) for x in nums], [Integer(x[0]) for x in nums])
    q.put((product([x[0] for x in nums]), c))

if __name__ == "__main__":
    parallel = 16
    while True:
        file = open("temp.txt", "r")
        n = []
        for line in file:
            parts = eval(line.strip())
            n += parts
        n = n[:16384]
        print(len(n))
        t0 = time.time()
        procs = []
        share = len(n) // parallel
        assert len(n) % parallel == 0
        procs = []
        q = Queue()
        for i in range(parallel):
            proc = multiprocessing.Process(target=worker_function, args=(n[i*share:(i+1)*share],q))
            proc.start()
            procs.append(proc)

        res = []
        for i in range(parallel):
            res.append(q.get())

        for i in range(parallel):
            procs[i].join()
        c = CRT([x[1] for x in res], [x[0] for x in res])
        try:
            m = int(c.nth_root(65537))
            print(m)
            print(m.to_bytes(m.bit_length() + 7 >> 3, 'big'))
            print(len(n), time.time() - t0)
            break
        except:
            pass
        print(len(n), time.time() - t0)
```

After \~30s, the flag is shown:

```
13040004482824375304445877421434841626308971715200586505768004087270538364058292355653326461
b'flag{ZwG3smodl18aSbUDRBq1adWh9SEfj4FV}'
```

First blood and the only solve.