HyperSonic CTF Writeup CTF/Wargame

HyperSonic CTF 2026 101010101 Writeup

HyperSonic CTF 2026 101010101 문제 풀이HyperSonic CTF 2026 101010101 writeup

Part 1 of 17 4 min read5 min read
#HyperSonic CTF#CTF#Writeup#Crypto
Contents

개요

101010101은 RSA에서 한 소인수 p의 일부 비트를 누출하는 crypto 문제입니다. 제공된 코드는 512비트 소수 p, q를 생성한 뒤 p & mask, n = p*q, mask를 출력하고, 입력값이 특정 RSA 식을 만족하는지 검사합니다.

확인한 조건은 다음과 같습니다.

  • 카테고리: crypto
  • 누출값: p & mask, n = p*q, mask
  • 목표: answer^0x10001 = 0x1337 mod n을 만족하는 값을 제출합니다.

mask가 가리는 비트는 구간마다 다릅니다. 중간 구간의 비트는 모두 공개되고, 양쪽 구간에서는 짝수 위치 비트만 공개됩니다. 이 구조를 이용해 모르는 비트를 두 개의 작은 변수로 묶고, 이변수 작은 해 문제로 p를 복구합니다.

문제 분석

제공된 코드는 매우 짧습니다.

python
from Crypto.Util.number import getPrime
from signal import signal, alarm, SIGALRM

signal(SIGALRM, lambda s, f: exit())
alarm(60)

p, q = getPrime(512), getPrime(512)
mask = sum(
    1 << i
    for i in range(512)
    if i < 96 and i % 2 == 0 or 96 <= i < 416 or i >= 416 and i % 2 == 0
)

print(p & mask, p * q, mask)

if pow(int(input()), 0x10001, p * q) == 0x1337:
    print("HS{REDACTED}")

비트 번호는 최하위 비트를 0번으로 두겠습니다. mask 조건을 정리하면 다음과 같습니다.

text
0 <= i < 96      : 짝수 비트만 공개
96 <= i < 416   : 모든 비트 공개
416 <= i < 512  : 짝수 비트만 공개

따라서 p & mask는 p의 많은 비트를 알려 줍니다. 공개되지 않는 부분은 낮은 쪽 홀수 비트와 높은 쪽 홀수 비트입니다. 다만 p는 512비트 소수이므로 최상위 비트인 511번 비트는 1로 고정됩니다. 이 비트는 mask에 포함되지 않지만 값은 알고 있으므로 상수항에 넣을 수 있습니다.

글에서 사용할 변수를 먼저 정리합니다.

  • L: 출력된 p & mask
  • N: 출력된 p*q
  • B: 2^417
  • x: 1번, 3번, ..., 95번 비트가 만드는 낮은 쪽 미지수
  • y: 417번, 419번, ..., 509번 비트를 417비트만큼 오른쪽으로 민 값
  • base: 이미 알고 있는 비트를 모두 더한 값

관계식은 다음과 같습니다.

text
B      = 2^417
TOP_Y  = 2^94
base   = L + B * TOP_Y
p      = base + x + B * y

여기서 TOP_Y = 2^94는 511번 비트를 의미합니다. 511 - 417 = 94이므로 B * TOP_Y를 더하면 최상위 비트가 반영됩니다.

x, y의 범위도 코드에서 바로 계산됩니다.

text
0 <= x < sum(2^i for odd i in [1, 95]) + 1
0 <= y < sum(2^(2*j) for 0 <= j < 47) + 1

이제 다음 다항식을 생각합니다.

text
f(x, y) = base + x + B * y

실제 미지수 값을 x0, y0라고 하면 f(x0, y0) = p입니다. 따라서 p를 모르는 상태에서도 다음 성질이 성립합니다.

text
f(x0, y0) = 0 mod p
p | N

즉 N의 약수 p를 모듈러로 하는 이변수 작은 해 문제가 됩니다.

핵심 아이디어

모르는 비트를 모두 탐색하면 낮은 쪽 48비트와 높은 쪽 47비트를 봐야 하므로 현실적이지 않습니다. 대신 비트 위치가 듬성듬성 비어 있다는 점을 이용해 미지수를 x, y 두 개로 압축합니다.

이후에는 Herrmann-May 방식의 이변수 Coppersmith 형태로 접근했습니다. 사용한 shift 다항식은 다음 꼴입니다.

text
g_{k,j}(x, y) = y^j * f(x, y)^k * N^max(t-k, 0)

0 <= k <= m
0 <= j <= m-k

참값 (x0, y0)에서 f(x0, y0) = p이고 p | N입니다. k < t이면 N^(t-k)가 p^(t-k)를 제공하고, f^k에서 p^k가 나오므로 전체가 p^t로 나누어집니다. k >= t일 때는 f^k만으로도 p^t가 들어갑니다.

각 다항식의 계수를 격자 행으로 만들고, 단항식 x^i y^j에는 X^i Y^j를 곱해 해의 크기 범위를 반영합니다. 격자 축소 후 짧은 행을 다시 다항식으로 복원하면, 참값에서 정수로 0이 되는 다항식을 얻을 수 있습니다.

실제 풀이에서는 m = 19, t = 5가 잘 동작했습니다. 이때 shift 수와 단항식 수가 모두 210개라서 210 x 210 격자를 줄이게 됩니다.

풀이 과정

Step 1. 누출된 비트 구조 정리

먼저 출력값 L, N, mask를 읽고 mask가 코드에서 계산한 값과 같은지 확인합니다. 그 뒤 p를 다음 형태로 둡니다.

text
p = base + x + B * y

낮은 쪽 미지수 x는 96비트 아래 홀수 위치만 포함합니다.

text
x = p_1*2^1 + p_3*2^3 + ... + p_95*2^95

높은 쪽 미지수 y는 417번부터 509번까지의 홀수 위치를 오른쪽으로 밀어 표현합니다.

text
y = p_417*2^0 + p_419*2^2 + ... + p_509*2^92

이렇게 두면 다항식은 선형입니다.

text
f(x, y) = base + x + B * y

선형 다항식이라 구조는 단순하지만, 모듈러가 p이고 우리는 N = p*q만 알고 있습니다. 따라서 p가 N의 큰 약수라는 조건을 포함해 작은 해를 찾아야 합니다.

Step 2. Herrmann-May 형태의 격자 구성

다음 루틴으로 shift 다항식을 만들었습니다.

python
E = 0x10001
C = 0x1337
B = 1 << 417
TOP_Y = 1 << 94


def low_odd_bound():
    return sum(1 << i for i in range(1, 96, 2)) + 1


def high_odd_tail_bound():
    return sum(1 << (2 * j) for j in range(47)) + 1


X_BOUND = low_odd_bound()
Y_BOUND = high_odd_tail_bound()


def poly_mul(a, b):
    out = {}
    for (ai, aj), av in a.items():
        for (bi, bj), bv in b.items():
            key = (ai + bi, aj + bj)
            out[key] = out.get(key, 0) + av * bv
    return {key: value for key, value in out.items() if value}


def poly_shift_y(poly, amount):
    return {(i, j + amount): value for (i, j), value in poly.items()}


def build_shifts(base, modulus, m=19, t=5):
    f = {(0, 0): base, (1, 0): 1, (0, 1): B}
    shifts = []
    power = {(0, 0): 1}

    for k in range(m + 1):
        if k:
            power = poly_mul(power, f)
        scale = modulus ** max(t - k, 0)
        for y_power in range(m + 1 - k):
            shifted = poly_shift_y(power, y_power)
            shifts.append({
                monomial: coeff * scale
                for monomial, coeff in shifted.items()
            })

    return shifts

다항식은 (x 차수, y 차수) -> 계수 형태의 딕셔너리로 표현했습니다. build_shifts는 위에서 정리한 y^j * f^k * N^max(t-k, 0)를 그대로 생성합니다.

격자 행렬을 만들 때는 단항식별로 X_BOUND^i * Y_BOUND^j를 곱합니다.

python
def build_lattice(base, modulus, m=19, t=5):
    shifts = build_shifts(base, modulus, m, t)
    monomials = sorted({monomial for shift in shifts for monomial in shift})
    weights = [
        (X_BOUND ** i) * (Y_BOUND ** j)
        for i, j in monomials
    ]

    rows = []
    for shift in shifts:
        rows.append([
            shift.get(monomial, 0) * weight
            for monomial, weight in zip(monomials, weights)
        ])

    return rows, monomials, weights

격자 축소 후에는 가중치를 다시 나누어 정수 다항식으로 복원합니다. 나누어떨어지지 않는 행은 버립니다.

python
def reconstruct_polys(reduced_rows, monomials, weights, limit=80):
    polys = []
    for row in reduced_rows:
        poly = {}
        for value, monomial, weight in zip(row, monomials, weights):
            if value == 0:
                continue
            if value % weight != 0:
                poly = {}
                break
            poly[monomial] = value // weight

        if poly:
            polys.append(poly)
        if len(polys) >= limit:
            break

    return polys

이 단계의 출력은 참값 (x0, y0)에서 0이 되는 정수 다항식 후보들입니다. 다음 단계에서는 이 다항식들에서 실제 작은 해를 뽑아냅니다.

Step 3. 유한체 계산과 CRT로 작은 해 복구

복원된 다항식 두 개를 잡으면 resultant나 Groebner basis로 (x, y)를 구할 수 있습니다. 다만 정수 위에서 바로 계산하면 시간이 오래 걸렸습니다. 제공 코드에 60초 제한이 있으므로, 작은 소수별로 먼저 해를 찾은 뒤 CRT로 들어 올렸습니다.

절차는 다음과 같습니다.

text
1. 복원된 다항식 쌍을 하나 고릅니다.
2. 16비트 소수 pmod 위에서 두 다항식을 해석합니다.
3. y를 제거하는 resultant로 x 후보를 구합니다.
4. 각 x 후보마다 gcd를 계산해 y 후보를 구합니다.
5. 여러 pmod에서 얻은 (x, y)를 CRT로 합칩니다.
6. CRT로 합친 모듈러스가 X_BOUND, Y_BOUND를 넘으면 실제 소인수인지 검사합니다.

검사는 단순합니다.

text
candidate = base + x + B * y
N % candidate == 0

이 조건을 통과하면 candidate가 p이고, q = N // p입니다.

Step 4. RSA 입력값 계산

소인수분해가 끝나면 남은 과정은 표준 RSA입니다. 문제는 입력값 answer가 다음 조건을 만족하기를 요구합니다.

text
answer^0x10001 = 0x1337 mod N

p, q를 알고 있으므로 개인 지수 d를 계산하고 0x1337^d mod N을 제출합니다.

text
phi    = (p - 1) * (q - 1)
d      = inverse(0x10001, phi)
answer = 0x1337^d mod N

Exploit / Solver

최종 solver는 세 부분으로 나뉩니다.

  1. 출력된 L, N, mask를 읽고 base, X_BOUND, Y_BOUND를 구성합니다.
  2. m = 19, t = 5로 격자를 만들고 축소한 뒤 정수 다항식들을 복원합니다.
  3. 유한체 resultant와 CRT로 (x, y)를 찾아 p, q를 복구하고 RSA 역원을 제출합니다.

아래는 핵심 흐름만 정리한 코드입니다. 격자 축소 함수와 입출력 래퍼는 환경에 맞게 연결하면 됩니다.

python
from sage.all import GF, PolynomialRing, inverse_mod


E = 0x10001
C = 0x1337
B = 1 << 417
TOP_Y = 1 << 94

PRIMES = [65521, 65519, 65497, 65479, 65449, 65447, 65437, 65423]


def to_sage(poly, ring):
    x, y = ring.gens()
    out = ring(0)
    for (i, j), coeff in poly.items():
        out += ring(coeff) * x**i * y**j
    return out


def roots_mod_prime(poly_a, poly_b, pmod):
    ring = PolynomialRing(GF(pmod), ("x", "y"), order="lex")
    x, y = ring.gens()
    a = to_sage(poly_a, ring)
    b = to_sage(poly_b, ring)

    resultant = a.resultant(b, y)
    if resultant == 0 or resultant.is_constant():
        return []

    roots = set()
    for xr, _ in resultant.univariate_polynomial().roots():
        xr = int(xr)
        common = a(xr, y).gcd(b(xr, y))
        if common == 0 or common.is_constant():
            continue
        for yr, _ in common.univariate_polynomial().roots():
            roots.add((xr, int(yr)))

    return sorted(roots)


def crt_pair(a, m, b, n):
    return int((a + m * (((b - a) * inverse_mod(m, n)) % n)) % (m * n))


def recover_root(polys, base, modulus, pairs):
    for i, j in pairs:
        states = [(0, 0, 1)]
        for pmod in PRIMES:
            residues = roots_mod_prime(polys[i], polys[j], pmod)
            next_states = set()

            for x0, y0, mod in states:
                for xr, yr in residues:
                    new_mod = mod * pmod
                    nx = crt_pair(x0, mod, xr, pmod)
                    ny = crt_pair(y0, mod, yr, pmod)

                    if new_mod > X_BOUND and nx >= X_BOUND:
                        continue
                    if new_mod > Y_BOUND and ny >= Y_BOUND:
                        continue

                    if new_mod > X_BOUND and new_mod > Y_BOUND:
                        factor = base + nx + B * ny
                        if 1 < factor < modulus and modulus % factor == 0:
                            return factor, modulus // factor

                    next_states.add((nx, ny, new_mod))

            states = sorted(next_states)

    raise ValueError("factor not recovered")


leak, n, mask = read_values()
base = leak + B * TOP_Y

rows, monomials, weights = build_lattice(base, n, m=19, t=5)
reduced_rows = reduce_lattice(rows)
polys = reconstruct_polys(reduced_rows, monomials, weights)

p, q = recover_root(
    polys,
    base,
    n,
    pairs=[(1, 2), (1, 3), (2, 3), (1, 4), (2, 4), (3, 4)],
)

d = pow(E, -1, (p - 1) * (q - 1))
answer = pow(C, d, n)
submit(answer)

recover_root는 후보를 찾을 때마다 바로 N % candidate == 0을 검사합니다. 그래서 CRT로 들어 올린 값이 실제 범위 안에 들어오는 순간 바로 멈추고, 불필요한 후보를 오래 들고 가지 않습니다.

결과

최종 실행에서는 m = 19, t = 5로 소인수분해가 성공했고, 계산한 RSA 입력값을 제출해 flag를 확인했습니다.

text
HS{1e5b95ac85582e49cef84d5b90740033}

Flag는 다음과 같습니다.

text
HS{1e5b95ac85582e49cef84d5b90740033}

Overview

101010101 is a crypto challenge that leaks some bits of one prime factor p in RSA. The provided code generates two 512-bit primes p and q, then prints p & mask, n = p*q, and mask, and checks whether the input satisfies a particular RSA equation.

The conditions I confirmed are as follows.

  • Category: crypto
  • Leaked values: p & mask, n = p*q, mask
  • Goal: submit a value satisfying answer^0x10001 = 0x1337 mod n.

The bits that mask hides differ by region. All bits in the middle region are public, while in the two outer regions only the even-position bits are public. Using this structure, we bundle the unknown bits into two small variables and recover p as a bivariate small-root problem.

Challenge analysis

The provided code is very short.

python
from Crypto.Util.number import getPrime
from signal import signal, alarm, SIGALRM

signal(SIGALRM, lambda s, f: exit())
alarm(60)

p, q = getPrime(512), getPrime(512)
mask = sum(
    1 << i
    for i in range(512)
    if i < 96 and i % 2 == 0 or 96 <= i < 416 or i >= 416 and i % 2 == 0
)

print(p & mask, p * q, mask)

if pow(int(input()), 0x10001, p * q) == 0x1337:
    print("HS{REDACTED}")

I will number bits with the least significant bit as bit 0. Organizing the mask condition gives the following.

text
0 <= i < 96      : only even bits public
96 <= i < 416   : all bits public
416 <= i < 512  : only even bits public

So p & mask reveals many bits of p. The parts that are not revealed are the low odd bits and the high odd bits. However, since p is a 512-bit prime, the most significant bit, bit 511, is fixed to 1. This bit is not included in mask, but since we know its value we can fold it into the constant term.

Let me first lay out the variables used in this writeup.

  • L: the printed p & mask
  • N: the printed p*q
  • B: 2^417
  • x: the low-side unknown formed by bits 1, 3, ..., 95
  • y: the value of bits 417, 419, ..., 509 shifted right by 417 bits
  • base: the sum of all the bits we already know

The relation can be written as follows.

text
B      = 2^417
TOP_Y  = 2^94
base   = L + B * TOP_Y
p      = base + x + B * y

Here TOP_Y = 2^94 denotes bit 511. Since 511 - 417 = 94, adding B * TOP_Y accounts for the most significant bit.

The ranges of x and y can be computed directly from the code.

text
0 <= x < sum(2^i for odd i in [1, 95]) + 1
0 <= y < sum(2^(2*j) for 0 <= j < 47) + 1

Now consider the following polynomial.

text
f(x, y) = base + x + B * y

If the actual unknown values are x0 and y0, then f(x0, y0) = p. So even without knowing p, the following property holds.

text
f(x0, y0) = 0 mod p
p | N

In other words, this becomes a bivariate small-root problem modulo p, a divisor of N.

Core idea

Brute-forcing all the unknown bits would require looking at 48 low-side bits and 47 high-side bits, which is impractical. Instead, we exploit the fact that the bit positions are sparsely spaced to compress the unknowns down to just two variables x and y.

From there I approached it as a bivariate Coppersmith of the Herrmann-May form. The shift polynomials used are of the following shape.

text
g_{k,j}(x, y) = y^j * f(x, y)^k * N^max(t-k, 0)

0 <= k <= m
0 <= j <= m-k

At the true value (x0, y0), f(x0, y0) = p and p | N. If k < t, then N^(t-k) supplies p^(t-k) and f^k yields p^k, so the whole thing is divisible by p^t. When k >= t, f^k alone already contains p^t.

We turn each polynomial's coefficients into a lattice row, and multiply the monomial x^i y^j by X^i Y^j to reflect the size bounds of the solution. After lattice reduction, reconstructing the short rows back into polynomials gives polynomials that become integer-zero at the true value.

In the actual solution, m = 19 and t = 5 worked well. In this case both the number of shifts and the number of monomials is 210, so we reduce a 210 x 210 lattice.

Solution

Step 1. Organizing the leaked bit structure

First read the outputs L, N, and mask, and confirm that mask matches the value computed in the code. Then set p in the following form.

text
p = base + x + B * y

The low-side unknown x only includes the odd positions below bit 96.

text
x = p_1*2^1 + p_3*2^3 + ... + p_95*2^95

The high-side unknown y represents the odd positions from bit 417 to bit 509, shifted right.

text
y = p_417*2^0 + p_419*2^2 + ... + p_509*2^92

With this setup the polynomial is linear.

text
f(x, y) = base + x + B * y

The structure is simple because it is a linear polynomial, but the modulus is p and we only know N = p*q. So we have to find the small solution subject to the condition that p is a large divisor of N.

Step 2. Building the Herrmann-May lattice

I built the shift polynomials with the following routine.

python
E = 0x10001
C = 0x1337
B = 1 << 417
TOP_Y = 1 << 94


def low_odd_bound():
    return sum(1 << i for i in range(1, 96, 2)) + 1


def high_odd_tail_bound():
    return sum(1 << (2 * j) for j in range(47)) + 1


X_BOUND = low_odd_bound()
Y_BOUND = high_odd_tail_bound()


def poly_mul(a, b):
    out = {}
    for (ai, aj), av in a.items():
        for (bi, bj), bv in b.items():
            key = (ai + bi, aj + bj)
            out[key] = out.get(key, 0) + av * bv
    return {key: value for key, value in out.items() if value}


def poly_shift_y(poly, amount):
    return {(i, j + amount): value for (i, j), value in poly.items()}


def build_shifts(base, modulus, m=19, t=5):
    f = {(0, 0): base, (1, 0): 1, (0, 1): B}
    shifts = []
    power = {(0, 0): 1}

    for k in range(m + 1):
        if k:
            power = poly_mul(power, f)
        scale = modulus ** max(t - k, 0)
        for y_power in range(m + 1 - k):
            shifted = poly_shift_y(power, y_power)
            shifts.append({
                monomial: coeff * scale
                for monomial, coeff in shifted.items()
            })

    return shifts

Polynomials are represented as dictionaries of the form (x degree, y degree) -> coefficient. build_shifts generates exactly the y^j * f^k * N^max(t-k, 0) laid out above.

When building the lattice matrix, we multiply each monomial by X_BOUND^i * Y_BOUND^j.

python
def build_lattice(base, modulus, m=19, t=5):
    shifts = build_shifts(base, modulus, m, t)
    monomials = sorted({monomial for shift in shifts for monomial in shift})
    weights = [
        (X_BOUND ** i) * (Y_BOUND ** j)
        for i, j in monomials
    ]

    rows = []
    for shift in shifts:
        rows.append([
            shift.get(monomial, 0) * weight
            for monomial, weight in zip(monomials, weights)
        ])

    return rows, monomials, weights

After lattice reduction, we divide out the weights again to reconstruct integer polynomials. Rows that do not divide evenly are discarded.

python
def reconstruct_polys(reduced_rows, monomials, weights, limit=80):
    polys = []
    for row in reduced_rows:
        poly = {}
        for value, monomial, weight in zip(row, monomials, weights):
            if value == 0:
                continue
            if value % weight != 0:
                poly = {}
                break
            poly[monomial] = value // weight

        if poly:
            polys.append(poly)
        if len(polys) >= limit:
            break

    return polys

The output of this step is a set of candidate integer polynomials that become zero at the true value (x0, y0). In the next step we extract the actual small solution from these polynomials.

Step 3. Recovering the small solution via finite-field computation and CRT

Given two reconstructed polynomials, we can obtain (x, y) via resultant or Groebner basis. Computing directly over the integers took too long, though. Since the provided code has a 60-second limit, I first found the solution modulo each small prime and then lifted it with CRT.

The procedure is as follows.

text
1. Pick a pair of reconstructed polynomials.
2. Interpret the two polynomials over a 16-bit prime pmod.
3. Obtain x candidates via a resultant that eliminates y.
4. For each x candidate, compute a gcd to obtain y candidates.
5. Combine the (x, y) obtained over several pmod via CRT.
6. Once the CRT-combined modulus exceeds X_BOUND and Y_BOUND, check whether it is a genuine prime factor.

The check is simple.

text
candidate = base + x + B * y
N % candidate == 0

If this condition passes, then candidate is p, and q = N // p.

Step 4. Computing the RSA input

Once factorization is done, the rest is standard RSA. The challenge requires the input answer to satisfy the following condition.

text
answer^0x10001 = 0x1337 mod N

Since we know p and q, we compute the private exponent d and submit 0x1337^d mod N.

text
phi    = (p - 1) * (q - 1)
d      = inverse(0x10001, phi)
answer = 0x1337^d mod N

Exploit / Solver

The final solver breaks into three parts.

  1. Read the printed L, N, and mask, and construct base, X_BOUND, Y_BOUND.
  2. Build and reduce the lattice with m = 19, t = 5, then reconstruct the integer polynomials.
  3. Find (x, y) via finite-field resultant and CRT, recover p and q, and submit the RSA inverse.

Below is the code with only the core flow. The lattice reduction function and the I/O wrappers can be wired up to match your environment.

python
from sage.all import GF, PolynomialRing, inverse_mod


E = 0x10001
C = 0x1337
B = 1 << 417
TOP_Y = 1 << 94

PRIMES = [65521, 65519, 65497, 65479, 65449, 65447, 65437, 65423]


def to_sage(poly, ring):
    x, y = ring.gens()
    out = ring(0)
    for (i, j), coeff in poly.items():
        out += ring(coeff) * x**i * y**j
    return out


def roots_mod_prime(poly_a, poly_b, pmod):
    ring = PolynomialRing(GF(pmod), ("x", "y"), order="lex")
    x, y = ring.gens()
    a = to_sage(poly_a, ring)
    b = to_sage(poly_b, ring)

    resultant = a.resultant(b, y)
    if resultant == 0 or resultant.is_constant():
        return []

    roots = set()
    for xr, _ in resultant.univariate_polynomial().roots():
        xr = int(xr)
        common = a(xr, y).gcd(b(xr, y))
        if common == 0 or common.is_constant():
            continue
        for yr, _ in common.univariate_polynomial().roots():
            roots.add((xr, int(yr)))

    return sorted(roots)


def crt_pair(a, m, b, n):
    return int((a + m * (((b - a) * inverse_mod(m, n)) % n)) % (m * n))


def recover_root(polys, base, modulus, pairs):
    for i, j in pairs:
        states = [(0, 0, 1)]
        for pmod in PRIMES:
            residues = roots_mod_prime(polys[i], polys[j], pmod)
            next_states = set()

            for x0, y0, mod in states:
                for xr, yr in residues:
                    new_mod = mod * pmod
                    nx = crt_pair(x0, mod, xr, pmod)
                    ny = crt_pair(y0, mod, yr, pmod)

                    if new_mod > X_BOUND and nx >= X_BOUND:
                        continue
                    if new_mod > Y_BOUND and ny >= Y_BOUND:
                        continue

                    if new_mod > X_BOUND and new_mod > Y_BOUND:
                        factor = base + nx + B * ny
                        if 1 < factor < modulus and modulus % factor == 0:
                            return factor, modulus // factor

                    next_states.add((nx, ny, new_mod))

            states = sorted(next_states)

    raise ValueError("factor not recovered")


leak, n, mask = read_values()
base = leak + B * TOP_Y

rows, monomials, weights = build_lattice(base, n, m=19, t=5)
reduced_rows = reduce_lattice(rows)
polys = reconstruct_polys(reduced_rows, monomials, weights)

p, q = recover_root(
    polys,
    base,
    n,
    pairs=[(1, 2), (1, 3), (2, 3), (1, 4), (2, 4), (3, 4)],
)

d = pow(E, -1, (p - 1) * (q - 1))
answer = pow(C, d, n)
submit(answer)

recover_root checks N % candidate == 0 immediately each time it finds a candidate. So it stops the moment a CRT-lifted value falls within the actual range, without carrying unnecessary candidates for long.

Result

In the final run, factorization succeeded with m = 19, t = 5, and submitting the computed RSA input confirmed the flag.

text
HS{1e5b95ac85582e49cef84d5b90740033}

The flag is as follows.

text
HS{1e5b95ac85582e49cef84d5b90740033}
Esc

Search titles, content and code.