Challenge Context#

The challenge converted the flag to an integer m, generated all primes below 105, and printed two things:

1. m // prod(primes)
2. A list of (m % p, p) residues for each small prime.

Reconnaissance#

The source logic was:

1
m = bytes_to_long(flag)
2
primes = []
3
sieve()
4
residues = [(m % p, p) for p in primes]
5
print(m // math.prod(primes))
6
print(residues)

Vulnerability / Core Idea#

The residues reveal m mod P, where P is the product of all listed primes. The quotient reveals the high part of m:

1
m = quotient * P + (m mod P)

So the problem is a direct Chinese Remainder Theorem reconstruction.

Exploitation#

1
import math
2
from Crypto.Util.number import long_to_bytes
3

4
quotient = 100785
5
residues = [(0, 2), (0, 3), (4, 5), (4, 7), ...]
6

7
P = math.prod(p for _, p in residues)
8
x = 0
9
for r, p in residues:
10
    Mi = P // p
11
    x = (x + r * Mi * pow(Mi, -1, p)) % P
12

13
m = quotient * P + x
14
print(long_to_bytes(m))

The recovered bytes include a trailing newline in the original flag file, but the submitted flag is the text without the newline.

Flag#

1
leet{R3al_F149_HH}

Lesson Learned#

If you publish enough modular residues plus the quotient by the modulus product, you have published the whole integer.

Cover: Wallhaven 8gk26o.