Alpacahack Daily 30

Challenge Overview

• CTF: Alpacahack Daily
• Challenge: RBG
• Category: Crypto
• Description: RBG stands for RSA + SBG + LCG! To learn about them, please check out lecture1.mp4.
• Challenge file : chall.py and output.txt
• Solve script : sol.py

TL;DR

RSA but the exponent changes every time using an LCG. Because the LCG wraps mod N, consecutive ciphertexts are related by a factor that depends on a small carry (k ∈ {0,1,2}). By dividing out c_i^3, all ratios fall into three values only. Those values leak m^1337 and m^{-N}, which we recombine using extended GCD to recover m and the flag.

Initial Analysis

We’re given:

• a standard RSA modulus N = p * q
• 13 ciphertexts
• no fixed public exponent Instead, the exponent evolves using this LCG:

  e = (3 * e + 1337) % N
  

  And each round encrypts the same message:

  c_i = pow(m, e_i, N)
  

  So what we actually see is:

  c_1 = m^{e_1} mod N
  c_2 = m^{e_2} mod N
  ...
  c_13 = m^{e_13} mod N
  

  where the exponents are linked together by the LCG. and here comes an important detail: the LCG modulus is N, not phi. That’s where the whole thing breaks open.

Task Analysis

• What we have

  • N (composite, product of two ~137-bit primes).

  • A short sequence c0..c12 of m^{e_i} [N] values.

  • The LCG rule e_{i+1} ≡ 3·e_i + 1337 [N].

• What we want
  • Recover m (the integer flag) from the given data.
• What we need for the exploit

  • The LCG update before reduction is 3·e_i + 1337. The true integer value 3·e_i + 1337 differs from its reduction modulo N by a small multiple k_i·N where k_i = floor((3·e_i + 1337)/N). Because e_i < N, 3·e_i + 1337 < 3N + 1337, so each k_i ∈ {0,1,2}. That small bounded set of possible carries (0,1 or 2) is the crucial leverage.

  • This bounded carry produces only a few multiplicative possibilities between consecutive ciphertexts, which we can detect and use to extract algebraic objects built from m (specifically m^{1337} and m^{-N}), and from those we can recombine to get m.

The Attack

We’ll index ciphertexts as c_i = m^{e_i} [N] with i = 0..12 . Using the LCG relation on exponents :

Relate consecutive exponents

The LCG before reduction gives:

e_{i+1} = 3·e_i + 1337 − k_i·N

for some integer k_i = floor((3·e_i + 1337)/N). As noted, k_i ∈ {0,1,2} because 3·e_i + 1337 < 3·N + 1337.

Raise m to both sides and rewrite in terms of ciphertexts

Take m to that exponent and reduce modulo N:

c_{i+1} = m^{e_{i+1}} ≡ m^{3·e_i + 1337 - k_i·N} (mod N).

Factor this:

c_{i+1} ≡ (m^{e_i})^3 × m^{1337} × (m^{-N})^{k_i}  (mod N).

Substitute c_i = m^{e_i} and define:

• X := m^{1337} (mod N)
• Z := m^{-N} (mod N) (so Z^k = (m^{-N})^k)

Then:

c_{i+1} ≡ c_i^3 × X × Z^{k_i}  (mod N).

Compute the ratio that removes the c_i^3 and isolates X and powers of Z

Compute

R_i := c_{i+1} * inverse(c_i^3, N)  (mod N).

Then

R_i ≡ X × Z^{k_i}  (mod N).

Since each k_i ∈ {0,1,2}, all R_i values belong to the set { X, X·Z, X·Z^2 }.

Cluster the R_i values

From the 12 ratios (c1→c2, c2→c3, …) you will observe at most three unique residues modulo N. In the provided data you indeed get exactly 3 unique values. Call them A,B,C and sort them (or just identify which one is the geometric middle).

They must form a geometric progression:

start = X
middle = X*Z
end = X*pow(Z,2)

Recover X and Z

X = start #iterate over others
Z = (middle * inverse(start, N))  % N

From X and Z to m

We have:

• X ≡ m^{1337} (mod N)
• Z ≡ m^{-N} (mod N) so Z^{-1} ≡ m^{N} (mod N) and we have 1337 and N are coprime. So according to bezout there exist u and v such that 1337·u + N·v = 1. Raising m to both sides gives us :

  m = m^{1337·u + N·v} = (m^{1337})^u × (m^{N})^v  (mod N).
  

  Substitute the values we have:

• m^{1337} ≡ X (this is known)
• m^{N} ≡ Z^{-1} (just compute `inverse(Z,n)) Then finally :

  m ≡ (pow(X,u) * pow(pow(Z,-1,N),v,N)) % N
  

Conclusion

Below is the solving script I used . it uses standard number-theory helpers like inverse from Crypto.Util.number and gmpy2.gcdext to compute Bezout coefficients.and long_to_bytes from Crypto.Util.number to get the flag in bytes after getting the integer m.

from Crypto.Util.number import long_to_bytes,inverse
from gmpy2 import gcdext
N=9288011389664837847963670837039196937548434573294469245501561784245642854634445047
ciphertexts = [
    7827437377925724428078233147899924081225364249930858942421079276821876942757073519,
    8887391738833944793881713037947023989163050343070393147424888589467627754249865604,
    8081548039727189478984198619032683177557008617453299085364096689176320484341697433,
    2275794279542811986322743644529192750108107184530803067791576158460846098638595919,
    6253142316263707598596838911072529989608774170182629190175128689020135811837569575,
    4733751513227945548879795301848782446340444473234631092994528819564169644364997232,
    7059294752711247585748476830322929650455626597483726834273561488576645863895400850,
    3416115616735235302679100710807631760495960686259891905227746706138654756842094326,
    8925820570540264143648581237815478995705636946118008059750128065916255778832895553,
    2892105289971843001930724217759034130633547138605066058109243908372747042621581984,
    314392853155476706788704773868088966795343394149871206877830575819199838027511362,
    4327945167964771727885647567828770187834470062965467452997985192630056416939883267,
    5004179351047061632898561578033712835850283897910028694457603173176131447102750100
]    
rs = []
for i in range(len(ciphertexts) - 1):
    c_current = ciphertexts[i]
    c_next = ciphertexts[i+1]
    c_cubed = pow(c_current, 3, N)
    c_cubed_inv = inverse(c_cubed, N)
    R = (c_next * c_cubed_inv) % N
    rs.append(R)
abc = sorted(list(set(rs)))
middle = None
others = []
A, B, C = abc
if pow(A, 2, N) == (B * C) % N:
    middle = A
    others = [B, C]
elif pow(B, 2, N) == (A * C) % N:
    middle = B
    others = [A, C]
elif pow(C, 2, N) == (A * B) % N:
    middle = C
    others = [A, B]
candidates = []
for start_val in others:
    X_candidate = start_val 
    Z_candidate = (middle * inverse(start_val, N)) % N 
    candidates.append((X_candidate, Z_candidate))
g, u, v = gcdext(1337, N)
for i, (X, Z) in enumerate(candidates):
    Z_inv = inverse(Z, N) 
    term1 = pow(X, u, N)
    term2 = pow(Z_inv, v, N)
    m = (term1 * term2) % N
    flag = long_to_bytes(m)
    if b"Alpaca" in flag:
        print(flag)

So a small recap : The LCG’s reduction by N injects a small unknown integer (k_i ∈ {0,1,2}) into the exponent recurrence. That small set produces at most three multiplicative possibilities between successive ciphertexts. By factoring out the c_i^3 term, we isolate X = m^{1337} multiplied by Z^{k_i} and thus detect X and Z. Once X and Z are known, simple exponent arithmetic via bezout gives m.

that’s it, the challenge was cool 🔥