Quadratic CRT

Author: 0xIDA
Platform: FlagYard · Category: crypto · Difficulty: Medium

Solvers

solve.py

Summary

Flag is encoded as x = f·√(-7) in the ring Z[√(-7)] and reduced modulo two random elements m1, m2. Congruences x ≡ y_i (mod m_i) expand to a pair of integer CRTs on f, solved with standard gcd / modular inverse.

Challenge

K.<a> = QuadraticField(-7)
O = K.maximal_order()
m1 = O(randbits(128)*a + randbits(128))
m2 = O(randbits(128)*a + randbits(128))
x = int.from_bytes(flag) * a   # flag length 64
y1 = x.mod(m1); y2 = x.mod(m2)

Output: y1, y2, m1, m2 (all in basis 1, a=√(-7)).

Math

Write s = √(-7), x = f·s, y1 = A·s, m1 = d1 + c1·s, quotient q = p + r·s ∈ Z[s]:

x - y1 = m1·q
(f - A)·s = (d1 + c1·s)(p + r·s)
          = (d1 p - 7 c1 r) + (d1 r + c1 p)·s

Equating coefficients:

d1 p - 7 c1 r = 0
f = A + d1 r + c1 p

From (1), (p, r) = t·(7 c1, d1)/g with g = gcd(d1, 7 c1), hence

f ≡ A  (mod N(m1)/g),   N(d+cs) = d² + 7 c²

Same for m2:

f ≡ B  (mod N(m2)/g2)

Integer CRT yields f unique modulo lcm(step1, step2) ≈ 2^517. The representative of bit-length 511 / length 64 is the flag.

Solve

from Crypto.Util.number import long_to_bytes
from math import gcd

# parse A,B,c1,d1,c2,d2 from output.txt
def step(c, d):
    g = gcd(d, 7*c)
    return (d*d + 7*c*c) // g

s1, s2 = step(c1, d1), step(c2, d2)
# f = A + t*s1 ≡ B (mod s2)
diff = B - A
G = gcd(s1, s2)
# standard linear congruence...
f = ...  # unique mod lcm
print(long_to_bytes(f))

Flag

FlagY{qu4dr4t1c_1nt3g3rs_ar3_fun_abc360fd85fae6c0b1adf0d678ac41}

Offline recovery from handout files; submitted and accepted on Flagyard.

Key Takeaways

CRT in quadratic integers often reduces to integer CRT on a coefficient after expanding multiplication in Z[√d].
For d = -7, N(p+q√(-7)) = p² + 7q² is the step of the arithmetic progression for the flag integer.
Class-number-1 fields / Euclidean domains guarantee clean theory, but the Z[s] subring already closed under the challenge’s generators.

Tools

Python 3, pycryptodome
Solver: /root/flagyard/quadratic-crt/solve.py