Opel Astra

Platform: miptctf | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-03-14 | Status: Solved Techniques: coppersmith_method, chinese_remainder_theorem, howgrave_graham_lattice, lll_reduction

Summary

Given a SageMath script f.sage that encrypts the flag using a quadratic function over two different RSA moduli.

Opel Astra — MIPT CTF

Description

"Мы продали красный опель. Все вырученные средства ушли на разработку криптографии на этом цтфе."

Given a SageMath script f.sage that encrypts the flag using a quadratic function over two different RSA moduli.

Source Code

 python read-only • copy allowed Copy
import os

flag = b""
m = int.from_bytes(flag + os.urandom(112-len(flag)), 'big')

for i in range(2):
    n = random_prime(2^512) * random_prime(2^512)
    assert m < n
    b = random_prime(n)
    ct = (m*m + b*m) % n
    print(f"c{i}, n{i}, b{i} = ({ct}, {n}, {b})")
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# c0, n0, b0 = (7497905916206657451318276082672477808066624531346426629320317011967948744762114939026860872081702057981022036368541160893319309519378560682853326187900494774265749572340842849620470666456008537972597474573442309197976094420634184183616933264508263916785446445325131733102007940518724025917946738597664555813, 9882699278170237374994819421833015349789706209067972524750330327524305175147048780125952643189032878214158653140723802188483944149877212023339536731221120472040209106923436729887798780314456665364106498658803443664424216392331255378937880175515560776807355478216124996064066911163040264631168566885729894119, 7728371017330739946511422591538450343252840264272773651672758868696611951409328713898098879414295449694507249510811622380192598191278284397395856187275622854541705777239632596458859079812513611975259566608789565919864931485433835065358091868703278397007604960446183299224299110674092318488614110084908301819)
# c1, n1, b1 = (24335482234670477814296725031832461370241939052508356009091692720246854507477088351126563642554975273922365326091053183854066023180304127717397475787121621670065397812162142455513763923953702362980053242983662123534911543760770172675432122381640936420722026054015397766415093898202638873423341394056476557626, 53883843720234757234421902324412116783752950109943211848022871545091733643525054419160394105632252342606904253442314130730582165035242158315393361989197397894393309655024620502310888005215689246556227671781806515936668996101987843571854575257260028723886996687645638838946726267314214027722640138007428974149, 21648306027859345857557828538670312755771557698931254850440399519875658450548610473059058265243548162895631867942584017754389933755654735691946095801755733106794330562594730157838837620618431901076000381680808404470400283089327048035257593846399582638529638264898315086049983526743884169060177521863166312487)

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Analysis

1. Problem structure:

   • Flag m (padded to 112 bytes = 896 bits) is encrypted with a quadratic function ct = m*(m+b) mod n
   • Two different RSA moduli: n0 ≈ 2^1020 and n1 ≈ 2^1023 (each is a product of two ~512-bit primes)
   • We get two congruences with the same unknown m:
     • m² + b0·m ≡ c0 (mod n0)
     • m² + b1·m ≡ c1 (mod n1)

2. Why standard methods don't work:

   • gcd(n0, n1) = 1 — moduli are coprime
   • Factoring n0 or n1 is infeasible (512-bit primes)
   • Solving a quadratic equation over a single modulus requires factorization ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

3. Key observation: CRT + Coppersmith

   • Since gcd(n0, n1) = 1, we can combine two congruences into one modulo N = n0 * n1 ≈ 2^2043
   • For a polynomial of degree d=2 modulo N, Coppersmith's method finds roots up to N^(1/d) ≈ 2^1021
   • Our m ≈ 2^896 < 2^1021 — the method is applicable!

Solution

Step 1: Combining Congruences via CRT

Using the Chinese Remainder Theorem to construct a unified polynomial:

 python read-only • copy allowed Copy
N = n0 * n1
B = CRT(b0, b1, n0, n1)  # Coefficient of m
C = CRT(-c0 mod n0, -c1 mod n1, n0, n1)  # Constant term
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Result: f(x) = x² + B·x + C ≡ 0 (mod N)

Step 2: Coppersmith's Method (Howgrave-Graham)

Building a lattice to find small roots:

• Parameters: m=4, t=1 (9×9 lattice)
• Bound: X = 2^896
• LLL reduction via fpylll

Step 3: Root Extraction

After LLL reduction, search the basis for low-degree polynomials with integer roots.

Solve Script

 python read-only • copy allowed Copy
#!/usr/bin/env python3
from fpylll import IntegerMatrix, LLL
from sympy.ntheory.modular import crt as sympy_crt
from math import isqrt

c0, n0, b0 = (7497905916206657451318276082672477808066624531346426629320317011967948744762114939026860872081702057981022036368541160893319309519378560682853326187900494774265749572340842849620470666456008537972597474573442309197976094420634184183616933264508263916785446445325131733102007940518724025917946738597664555813, 9882699278170237374994819421833015349789706209067972524750330327524305175147048780125952643189032878214158653140723802188483944149877212023339536731221120472040209106923436729887798780314456665364106498658803443664424216392331255378937880175515560776807355478216124996064066911163040264631168566885729894119, 7728371017330739946511422591538450343252840264272773651672758868696611951409328713898098879414295449694507249510811622380192598191278284397395856187275622854541705777239632596458859079812513611975259566608789565919864931485433835065358091868703278397007604960446183299224299110674092318488614110084908301819)
c1, n1, b1 = (24335482234670477814296725031832461370241939052508356009091692720246854507477088351126563642554975273922365326091053183854066023180304127717397475787121621670065397812162142455513763923953702362980053242983662123534911543760770172675432122381640936420722026054015397766415093898202638873423341394056476557626, 53883843720234757234421902324412116783752950109943211848022871545091733643525054419160394105632252342606904253442314130730582165035242158315393361989197397894393309655024620502310888005215689246556227671781806515936668996101987843571854575257260028723886996687645638838946726267314214027722640138007428974149, 21648306027859345857557828538670312755771557698931254850440399519875658450548610473059058265243548162895631867942584017754389933755654735691946095801755733106794330562594730157838837620618431901076000381680808404470400283089327048035257593846399582638529638264898315086049983526743884169060177521863166312487)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

N = n0 * n1
B = int(sympy_crt([n0, n1], [b0, b1])[0]) % N
C = int(sympy_crt([n0, n1], [(-c0) % n0, (-c1) % n1])[0]) % N
X = 2**896

def poly_mul(p1, p2):
    result = [0] * (len(p1) + len(p2) - 1)
    for i, a in enumerate(p1):
        for j, b in enumerate(p2):
            result[i+j] += a * b
    return result

def coppersmith(N, f_coeffs, X, mm, tt):
    dd = len(f_coeffs) - 1
    nn = dd * mm + tt
    f_powers = {0: [1], 1: list(f_coeffs)}
    for k in range(2, mm + 1):
        f_powers[k] = poly_mul(f_powers[k-1], f_powers[1])
    polys = []
    for k in range(mm):
        for j in range(dd):
            fk = f_powers[k]
            shifted = [0]*j + fk
            scale = pow(N, mm - k)
            scaled = [c * scale for c in shifted]
            polys.append(scaled)
    for j in range(tt):
        fm = f_powers[mm]
        shifted = [0]*j + fm
        polys.append(shifted)
    for i in range(len(polys)):
        polys[i] = polys[i][:nn] + [0] * max(0, nn - len(polys[i]))
    M = IntegerMatrix(nn, nn)
    for i in range(nn):
        for j in range(nn):
            M[i, j] = int(polys[i][j] * pow(X, j))
    M = LLL.reduction(M)
    for row_idx in range(nn):
        coeffs = []
        valid = True
        for j in range(nn):
            val = int(M[row_idx, j])
            xj = pow(X, j)
            if val % xj != 0:
                valid = False; break
            coeffs.append(val // xj)
        if not valid or all(c == 0 for c in coeffs): continue
        deg = max((i for i in range(nn) if coeffs[i] != 0), default=0)
        if deg == 1 and coeffs[1] != 0 and (-coeffs[0]) % coeffs[1] == 0:
            root = (-coeffs[0]) // coeffs[1]
            if 0 < root < X: return root
        elif deg == 2:
            a, b, c = coeffs[2], coeffs[1], coeffs[0]
            disc = b*b - 4*a*c
            if disc >= 0:
                sd = isqrt(disc)
                if sd*sd == disc:
                    for sign in [1, -1]:
                        num = -b + sign * sd
                        den = 2 * a
                        if den != 0 and num % den == 0:
                            root = num // den
                            if 0 < root < X: return root
    return None
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

root = coppersmith(N, [C, B, 1], X, mm=4, tt=1)
if root:
    v0 = (root*root + b0*root) % n0
    v1 = (root*root + b1*root) % n1
    if v0 == c0 and v1 == c1:
        flag = root.to_bytes(112, 'big')
        print(f"Flag: {flag}")
# Output: MIPT{REDACTED}

Pitfall

The function sympy.ntheory.modular.crt() returns a tuple (remainder, modulus). Initially, the code used _, B = crt(...), which discarded the remainder and used the modulus as B, leading to C = 0 and a degenerate lattice. Fixing it to B = crt(...)[0] immediately solved the problem. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍