1+1

crypto

---

Challenge

We're given 10 large integers xi and told the flag p was encoded as a number and used as follows:

Where qi are large 512-bit primes and ri are small (444-bit) random integers. So each xi is approximately a multiple of p, with small noise ri. This is the Approximate GCD problem.

The Vulnerability

The key insight: if we compute xi / x0 exactly, the quotients are roughly qi / q0, and the errors are small. This means the integer xi · q0 - x0 · qi is small — it equals ri · q0 - r0 · qi.

We can set up a lattice whose short vectors reveal the hidden quotients qi. Once we have any qi, dividing xi by it recovers p.

The Lattice

Build an n × n matrix where:

• Row 0: [K, x1, x2, ..., xn-1]
• Row i (i ≥ 1): [0, ..., -x0, ..., 0] (only the i-th column is -x0)

Here K = 2444 is a scaling factor chosen to be larger than the noise. A short vector in this lattice has the form:

The first entry is always a multiple of K, so we can read off q0 and recover p = x0 / q0.

Solution

def long_to_bytes(n):
    return n.to_bytes((n.bit_length() + 7) // 8, 'big')

xs = [145857819365885518388888827..., ...]   # 10 values from output

K = 2**444
n = len(xs)

M = Matrix(ZZ, n, n)
M[0, 0] = K
for i in range(1, n):
    M[0, i] = xs[i]
    M[i, i] = -xs[0]

L = M.LLL()

for row in L:
    if row[0] != 0 and row[0] % K == 0:
        q0 = abs(row[0] // K)
        p = xs[0] // q0
        try:
            flag = long_to_bytes(int(p)).decode()
            print("Flag:", flag)
            break
        except Exception:
            pass

Result