サーバ側で何やら素数（？）を2つ生成して、さらにそれを加工した値をあたかもRSAのとして扱ってくれるので、そのを使って暗号化されたフラグを復号せよ、という問題です。 より具体的には以下のような処理を実行するスクリプトでした。

validity checkに答えるのがなかなか難しくて、これを通過できないとだめなので、どうにかしての具体的な値を知る必要がありそうです。まず最初に考えたのはとしてを送りをもらってとからを求める方法でしたが、これは多項式のGCDがタイムアウトに微妙に届かなかったので不採用になりました。

次に考えたのはとしてを送りとする方法で、これはとする近似がうまく行きました。当然も計算できるし、validity checkも通過できます。

あとはこのmodulus でが復号できれば良いので、が素数になるまでガチャを回しました。

solution scriptはこちら

from ptrlib import Socket, Process
from random import randrange
from Crypto.Util.number import long_to_bytes, isPrime
from hashlib import sha256
from itertools import product as iterprod
from gmpy2 import iroot

def POW(sock):
    b_postfix = sock.recvlineafter("b = ").decode()[6:].strip()
    h = sock.recvlineafter(" = ").decode().strip()
    for brute in iterprod('0123456789abcdef', repeat=6):
        b_prefix = ''.join(brute)
        b_ = b_prefix + b_postfix
        if sha256(bytes.fromhex(b_)).hexdigest() == h:
            sock.sendlineafter(b' > ', b_prefix.encode())
            return True

    assert 0, "Something went wrong.."

while True:
    try:
        
        sock = Socket("nc 43.200.47.102 9001")
        POW(sock)
        SERVER_N = int(sock.recvlineafter("SERVER_N = "))
        SERVER_E = int(sock.recvlineafter("SERVER_E = "))

        
        for p in [2,3,5,7,11,13]:
            cands = [1] + [-1-x for x in range((p + 1) // 2 - 1)]
            sock.sendlineafter(" > ", " ".join([str(x) for x in cands]))

        
        for p in [2,3,5,7,11,13]:
            if p == 2:
                cands = [0] + [-1-x for x in range((p + 1) // 2 - 1)]
            else:
                cands = [1] + [-1-x for x in range((p + 1) // 2 - 1)]
            sock.sendlineafter(" > ", " ".join([str(x) for x in cands]))

        p1_enc = int(sock.recvlineafter("p1_enc = "))
        q1_enc = int(sock.recvlineafter("q1_enc = "))
        r = randrange(2**1536)

        X = [ pow(p1_enc, 4, SERVER_N) ]
        sock.sendlineafter("X > ", " ".join([str(x) for x in X + [0 for _ in range(12  - len(X))]]))

        N = int(sock.recvlineafter("N = "))  
        p, _ = iroot(N, 4)
        q = (N - p**4) // p

        assert pow(p, SERVER_E, SERVER_N) == p1_enc, "p"
        assert pow(q, SERVER_E, SERVER_N) == q1_enc, "q"
        assert N == p*(p**3 + q), "N"

        for _ in range(20):
            b = int(sock.recvlineafter("b = "))
            digest = sha256(long_to_bytes(pow(b, N - (p+q) + 1, N))).hexdigest()
            sock.sendlineafter("digest > ", digest)
            line = sock.recvline()
            assert b"good" in line

        c = int(sock.recvlineafter("FLAG_ENC = "))
        if isPrime(p**3 + q) and (p**3 + q) > 2**(127 * 8):
            print(p)
            print(q)
            print(N)
            print(c)

            d = pow(65537, -1, p**3 + q - 1)
            m = pow(c, d, p**3 + q)
            print(long_to_bytes(m))

            quit()
    except AssertionError as e:
        print(e)
        continue

がで満たすべき値を制御できたのはなんの意味があったんだろう…