TL;DR

The server only provides $n = pq$ and calls RSA.constrcut((n, e, d)), which tries to recover $p, q$ ; the challenge proceeds only if this recovery throws an exception. The recovery routine tests only bases $a = 2,4,...,98$ By choosing for each $p$ a prime $q$ such that all small bases behave identically modulo $p$ and $q$ , the recovery always fails, and after 32 failures the flag is printed.

Analysis

Each round the server prints a 1024-bit prime $p$ , reads a prime $q$ , and computes

$n=pq,\quad e\leftarrow \text{64-bit prime},\quad d\equiv e^{-1}\pmod{(p-1)(q-1)}$

Then it calls RSA.construct((n,e,d)), If it succeeds, the program exits. If it raises, the server prints error! and continues to the next round. After 32 failures, it prints the flag.

When only $(n,e,d)$ are provided.

1
ktot = d*e - 1
2
# ktot = t * 2^s (t odd)
3
t = ktot
4
while t % 2 == 0:
5
   t //= 2
6
for a in range(2, 100, 2):  # only a = 2,4,...,98
7
   k = t
8
   while k < ktot:
9
       cand = pow(a, k, n)
10
       if cand != 1 and cand != n-1 and pow(cand, 2, n) == 1:
11
           p = gcd(cand + 1, n)  # non-trivial sqrt(1) => factor
12
           ...
13
       k *= 2
14
raise ValueError("Unable to compute factors p and q from exponent d.")

So it searches for a non-trivial square root of 1 modulo $n$ among $a^t, a^{2t}, a^{4t}, \dots$ for each small base $a$ .

If $\text{cand}^2\equiv 1\pmod{n}$ but $\text{cand}\not\equiv \pm 1\pmod{n}$ , then by CRT

$\text{cand}\equiv 1\pmod{p}$

$\text{cand}\equiv -1\pmod{q}$

In that case gcd(cand+1, n) reveals one prime factor immediately.

Therefore, to make the routine fail, we want all tested values to stay in the same sign cases

$\text{cand}\equiv \pm 1\pmod{p}$

$\text{cand}\equiv \pm 1\pmod{q}$

The routine only tries $a=2,4,\dots,98$ .

Every such $a$ factors over $2$ and odd primes $\le 47$ (e.g. $94=2\cdot 47$ , $98=2\cdot 7^2$ ).

Define

$L = \prod_{r\le 47,\ r\ \text{odd prime}} r$ If we make the relevant 2-adic residue behavior match for $2$ and for all odd primes dividing $L$ , then every tested $a$ behaves the same modulo $p$ and modulo $q$ .

We have $k_{\text{tot}} = ed-1 = h\,\varphi(n)=h(p-1)(q-1)$ Let $t$ be the odd part of $k_{\text{tot}}$ .

Since $t$ always contains the odd parts of $(p-1)$ and $(q-1)$ , the values $a^t$ land in the 2-Sylow subgroup.

Multiplying $t$ by an extra odd factor (which depends on the random $e$ ) is an automorphism on that subgroup, so it does not change the same-sign vs split-sign phenomenon we care about.

Let $s=v_2(p-1)$ .

Case A: $s=1$ (i.e., $p\equiv 3\pmod{4}$ ) Then the 2-Sylow subgroup modulo $p$ has size $2$ , so matching quadratic characters is enough.

We search for a 1024-bit prime $q$ such that $q \equiv p \pmod{8L}$

This forces $\left(\frac{2}{p}\right)=\left(\frac{2}{q}\right)$ and, by quadratic reciprocity plus $q\equiv p$ modulo every odd prime $r\le 47$

also $\left(\frac{r}{p}\right)=\left(\frac{r}{q}\right)$

By multiplicativity, every tested base $a$ has the same Legendre symbol modulo $p$ and $q$ , so the recovery loop never finds a split sign.

Case B: $s\ge 2$ (i.e., $p\equiv 1\pmod{4}$ ) Now higher 2-power residue information (quartic, etc.) matters.

work in Gaussian integers $\mathbb{Z}[i]$ .

For $p\equiv 1\pmod{4}$ we can write $p=x^2+y^2,$ and in $\mathbb{Z}[i]$ it splits as $p=(x+iy)(x-iy)$

Exploit

compute $s=v_2(p-1)$ generate candidates $q$ using Case A or Case B filter by bit-length and primality locally check that RSA.construct((n,e,d)) fails send $q$ to the server

1
from Crypto.Math.Primality import *
2
from Crypto.PublicKey import *
3

4

5
ODD_PRIMES_LE_47 = (3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47)
6

7

8
def v2(n: int) -> int:
9
    return (n & -n).bit_length() - 1
10

11

12
def legendre_symbol(a: int, p: int) -> int:
13
    x = pow(a, (p - 1) // 2, p)
14
    return -1 if x == p - 1 else x
15

16

17
def sqrt_minus_one_mod_p(p: int) -> int:
18
    if p % 4 != 1:
19
        raise ValueError("p must be 1 (mod 4)")
20
    while True:
21
        a = random.randrange(2, p - 1)
22
        if legendre_symbol(a, p) == -1:
23
            r = pow(a, (p - 1) // 4, p)
24
            if (r * r + 1) % p == 0:
25
                return r
26

27

28
def sum_of_two_squares_for_prime(p: int) -> tuple[int, int]:
29
    if p % 4 != 1:
30
        raise ValueError("Prime does not split in Z[i]")
31
    t = sqrt_minus_one_mod_p(p)
32
    r0, r1 = p, t
33
    while r1 * r1 > p:
34
        r0, r1 = r1, r0 % r1
35
    x = r1
36
    y2 = p - x * x
37
    y = isqrt(y2)
38
    if y * y != y2:
39
        raise RuntimeError("Cornacchia failed")
40
    return x, y
41

42

43
def rsa_construct_fails(p: int, q: int) -> bool:
44
    n = p * q
45
    phi = (p - 1) * (q - 1)
46
    e = 65537
47
    if gcd(e, phi) != 1:
48
        # Extremely unlikely; pick another odd exponent.
49
        e = 3
50
        if gcd(e, phi) != 1:
51
            return False
52
    d = pow(e, -1, phi)
53
    try:
54
        RSA.construct((n, e, d))
55
        return False
56
    except Exception:
57
        return True
58

59

60
def build_L() -> int:
61
    L = 1
62
    for r in ODD_PRIMES_LE_47:
63
        L *= r
64
    return L
65

66

67
L = build_L()
68

69

70
def find_q_for_p(p: int, min_bits: int = 1024) -> int:
71
    s = v2(p - 1)
72

73
    if s == 1:
74
        modulus = 8 * L
75
        t_min = ((1 << (min_bits - 1)) - p + modulus - 1) // modulus
76
        attempts = 0
77
        while True:
78
            attempts += 1
79
            t = t_min + random.getrandbits(64)
80
            q = p + modulus * t
81
            if q.bit_length() < min_bits:
82
                continue
83
            if test_probable_prime(q) != PROBABLY_PRIME:
84
                continue
85
            if rsa_construct_fails(p, q):
86
                # print(f"[s=1] attempts={attempts} q_bits={q.bit_length()}", flush=True)
87
                return q
88

89
    # s >= 2: work in Z[i] with q = X^2 + Y^2 and (X,Y) ≡ (x,y) mod (L, 2^{s+1})
90
    x, y = sum_of_two_squares_for_prime(p)
91
    step = L * (1 << (s + 1))  # forces q ≡ p (mod 2^{s+1}) and (mod L)
92

93
    # Pick k,l so X,Y end up around sqrt(2^min_bits) ≈ 2^(min_bits/2).
94
    half_bits = (min_bits + 1) // 2
95
    k_bits = max(64, half_bits - step.bit_length() + 64)
96

97
    attempts = 0
98
    while True:
99
        attempts += 1
100
        k = random.getrandbits(k_bits)
101
        l = random.getrandbits(k_bits)
102
        X = x + step * k
103
        Y = y + step * l
104
        q = X * X + Y * Y
105
        if q.bit_length() < min_bits:
106
            continue
107
        if test_probable_prime(q) != PROBABLY_PRIME:
108
            continue
109
        if rsa_construct_fails(p, q):
110
            return q
111

112

113
@dataclass
114
class BufferedSocket:
115
    sock: socket.socket
116
    buf: bytearray = field(default_factory=bytearray)
117

118
    def recv_until(self, marker: bytes) -> bytes:
119
        while marker not in self.buf:
120
            chunk = self.sock.recv(4096)
121
            if not chunk:
122
                break
123
            self.buf.extend(chunk)
124
        idx = self.buf.find(marker)
125
        if idx == -1:
126
            data = bytes(self.buf)
127
            self.buf.clear()
128
            return data
129
        end = idx + len(marker)
130
        data = bytes(self.buf[:end])
131
        del self.buf[:end]
132
        return data
133

134
    def recv_all(self) -> bytes:
135
        out = bytearray(self.buf)
136
        self.buf.clear()
137
        while True:
138
            chunk = self.sock.recv(4096)
139
            if not chunk:
140
                break
141
            out.extend(chunk)
142
        return bytes(out)
143

144
    def sendline(self, line: str) -> None:
145
        self.sock.sendall(line.encode() + b"\n")
146

147

148
P_RE = re.compile(rb"p = ([0-9]+)\nq: $")
149

150

151
def run_session(host: str, port: int, rounds: int, max_s: int) -> str | None:
152
    with socket.create_connection((host, port), timeout=600) as s:
153
        bs = BufferedSocket(s)
154

155
        for i in range(rounds):
156
            chunk = bs.recv_until(b"q: ")
157
            m = P_RE.search(chunk)
158
            if not m:
159
                raise RuntimeError(f"Unexpected prompt: {chunk!r}")
160
            p = int(m.group(1))
161
            s_p = v2(p - 1)
162
            print(f"[{i+1:02d}/{rounds:02d}] p_bits={p.bit_length()} s={s_p}", flush=True)
163
            if s_p > max_s:
164
                print(f"         s={s_p} too large; restarting", flush=True)
165
                return None
166
            q = find_q_for_p(p)
167
            print(f"         q_bits={q.bit_length()}", flush=True)
168
            bs.sendline(str(q))
169

170
        tail = bs.recv_all()
171
        return tail.decode(errors="replace")
172

173

174
def main() -> None:
175
    host = os.environ.get("HOST", "yukari.seccon.games")
176
    port = int(os.environ.get("PORT", "15809"))
177
    rounds = int(os.environ.get("ROUNDS", "32"))
178
    max_s = int(os.environ.get("MAX_S", "5"))
179

180
    for attempt in range(1, 21):
181
        print(f"[session {attempt}] max_s={max_s}", flush=True)
182
        out = run_session(host, port, rounds, max_s)
183
        if out is not None:
184
            print(out, end="")
185
            return
186

187
    raise RuntimeError("Too many retries")
188

189

190
if __name__ == "__main__":
191
    main()

[SECCON CTF 14] yukari writeup

TL;DR

Analysis

Define

Exploit