[WRITEUP-LOG] [2026-07-13] #ctf

KalmarCTF 2026 RBG+ Writeup — Cracking a Sum-Hidden RSA with Alternating Sums and Polynomial GCD

Target
KalmarCTF 2026 — RBG+ (Crypto, 106pts)
Severity
Info
Vulnerability
Cryptography (RSA + LCG)
BY ICHIBURN Est. 7 MIN READ

Overview

KalmarCTF 2026 Crypto challenge “RBG+” (106pts). It combines RSA with an LCG (linear congruential generator): the flag m is encrypted with RSA, and the exponent e is updated by the LCG. The tricky part is that the output is given as “the sum of two ciphertexts”. Because the two terms are added together, they cannot be separated into individual m^e mod N values, so the RSA structure cannot be used as-is (each value is the integer sum of the two terms taken mod N, and the sum can exceed N. This integrality makes the later argument easier, but the essence of the attack is that the value is “hidden inside a sum”).

How to peel off this “sum” is the crux of the problem.

Problem Structure

N = getPrime(371) * getPrime(371)  # ~742-bit RSA modulus (product of two 371-bit primes; 742-bit for this instance)
e = getRandomRange(731, N)
print(f"{N, e = }")                # N and the initial exponent e_0 are published on the first line of output
lcg = lambda s: (s * 3 + 1337) % N

for i in range(13):
    print(pow(m, e, N) + pow(m, e:=lcg(e), N))

In other words, N and the initial exponent e_0 are public values (the first line of output), and the following 13 lines are given as the sums c_i. The only secret is the flag m.

Organizing this,

  • c_i = m^{e_i} + m^{e_{i+1}} (in sum form. Each term is mod N, but the sum is an integer that can exceed N)
  • e_{i+1} = (3 · e_i + 1337) mod N (exponent update via the LCG)
  • For 13 data points, the unknown values a_j = m^{e_j} mod N number 14

There is one more unknown than data points, but the structure of the LCG supplies a constraint.

Solution

Step 1: Turn each a_j into a linear function of a_0 via an alternating sum

Since c_i = a_i + a_{i+1}, taking an alternating sum makes adjacent terms cancel each other out.

S_k = Σ_{i=0}^{k} (-1)^i · c_i = a_0 + (-1)^k · a_{k+1}

Here, since c_i is an integer that exceeds N, this identity holds exactly over the integers, not mod N. Therefore,

  • k even: a_{k+1} = S_k − a_0
  • k odd: a_{k+1} = a_0 − S_k

That is, every a_j can be written as a first-degree expression in a_0. Effectively only one unknown, a_0, remains.

Step 2: Count the LCG “wrap” occurrences

The mod in e_{i+1} = (3 · e_i + 1337) mod N introduces an offset into the actual difference between exponents.

e_{i+1} − 3 · e_i = 1337 − wraps[i] · N

wraps[i] is how many times 3 · e_i + 1337 crosses over N. Since e_i < N, we have 3 · e_i + 1337 < 3N + 1337, so in theory it can take values from 0 to 3 (in the actual data for this instance it was only 0, 1, 2). For a consecutive pair (i, i+1) with the same wrap value (wraps[i] = wraps[i+1]), the constant term of the exponent lines up:

e_{i+1} = 3·e_i   + (1337 − wraps[i]·N)
e_{i+2} = 3·e_{i+1} + (1337 − wraps[i]·N)   ← same constant term as i

Eliminating the constant term from these two equations gives:

4·e_{i+1} = e_{i+2} + 3·e_i

Lifting the exponents directly onto a = m^e,

a_{i+1}^4 = a_{i+2} · a_i^3   (mod N)

is obtained (if a_i is invertible mod N, it can also be written in ratio form as a_{i+1}/a_i^3 = a_{i+2}/a_{i+1}^3, but this cross-multiplied form does not require invertibility and is more rigorous).

Step 3: Uniquely determine a_0 with a polynomial GCD

In Step 1, every a_j was a first-degree expression in a_0. Substituting these into the equation from Step 2 yields a quartic (4th-degree) polynomial in a_0 (the leading coefficient cancels, so it is effectively cubic).

If there are multiple consecutive pairs with the same wrap value, we can build a polynomial from each. We then compute the polynomial GCD of these mod N. However, because the polynomial ring over the composite N is not a field, the GCD does not necessarily drop cleanly down to first degree. If mod p and mod q pick up different common roots, the CRT can mix them into a spurious linear factor (in fact, for this data the GCD of the two cubic polynomials does not directly give the true a_0, and a spurious root appears). There are two ways to handle this: if, during the GCD division, the GCD of the leading coefficient and N stops being 1, a factor of N is obtained (a bonus; solve separately mod p / mod q and CRT). If no factor turns up, reconstruct all c_i from each candidate root, verify, and pick the true a_0.

# wraps = [2, 0, 2, 0, 0, 1, 0, 1, 2, 0, 0, 1, 0]
# consecutive pairs with the same wrap: (3,4) and (9,10)
# → yields 2 cubic polynomials
# GCD → candidate linear factor (spurious roots are possible in a composite ring)
# → verify by reconstructing all c_i, then fix the true a_0

Step 4: Recover m with the extended Euclidean algorithm

We obtain a_0 = m^{e_0} mod N, together with the ratio a_1 / a_0^3 = m^{1337 − wraps[0]·N} mod N (from here on, we assume m is coprime to N, i.e. invertible; for an RSA flag this holds essentially for certain). Here, if

gcd(e_0, 1337 − wraps[0]·N) = 1

holds (confirmed to hold for this instance; it is not structurally guaranteed for every random e_0, but when it does hold), we use the extended Euclidean algorithm to find s, t satisfying s · e_0 + t · (1337 − wraps[0]·N) = 1, and then

m = a_0^s · ratio^t   mod N

recovers the plaintext (the flag).

Implementing the polynomial GCD mod composite N

Because N is composite, the standard GCD in SageMath or SymPy cannot be used as-is (since it is not a field, an inverse does not always exist). We implement the Euclidean algorithm by hand. If, partway through the division, the GCD of the leading coefficient and N stops being 1, that means we have dug up a factor of N, and as a bonus a factorization can sometimes be obtained.

def poly_divmod_N(p1, p2, N):
    p1 = list(p1)
    while len(p1) >= len(p2):
        if p1[0] == 0:
            p1.pop(0); continue
        g = math.gcd(p2[0], N)
        if g != 1 and g != N:
            return "FACTOR", g        # found a factor of N (bonus)
        inv = pow(p2[0], -1, N)
        coeff = (p1[0] * inv) % N
        for j in range(len(p2)):
            p1[j] = (p1[j] - coeff * p2[j]) % N
        p1.pop(0)
    return p1

This is a fragment that pulls out only the essentials; in practice it assumes the input is already normalized: coefficients are reduced mod N, leading zeros are stripped, and the caller guarantees that the leading coefficient of the divisor p2 is not 0 (mod N) (i.e. gcd(p2[0], N) == N never occurs). Degenerate cases such as the zero polynomial or g == N must be rejected separately.

kalmar{GCD_is_handy_like_always}

Key Insights

  1. Even when the output is in “sum” form, canceling adjacent terms with an alternating sum lets us expand each a_j into a linear function of a_0. Because the output is an integer sum (each term mod N, the sum exceeding N), the alternating sum becomes an exact integer relation; but since the later stage ends up working mod N anyway, even if each output had been folded down to mod N, the linearization itself would still hold mod N. The point is “being able to expand the sum linearly”; whether or not there is a mod is not the essence.
  2. For pairs with the same LCG wrap count, the ratio of exponents becomes equal, and a polynomial equation can be set up between the a values. The determinism of the LCG morphs into a constraint.
  3. A polynomial GCD over the composite N requires a hand-rolled implementation. Unlike over a field, it is not the case that “two polynomials are guaranteed to drop down to first degree”; CRT-derived spurious roots can appear, or a factor of N can tumble out partway through the division (the latter is a bonus). Verify each candidate root by reconstructing all c_i and pick the true a_0.
  4. Thanks to gcd(e_0, 1337 − wraps[0]·N) = 1 holding, we can cancel the exponents with the extended Euclidean algorithm and extract m directly. The flag’s GCD_is_handy was precisely the backbone of this very problem.