Daily Alpacahack 2026 #29 - Linear Coffee Generator

Challenge Overview

Category: Crypto Flag: Alpaca{how_much_sugar_do_you_need}

We’re given a Python script that implements a Linear Congruential Generator (LCG) to produce pseudo-random numbers. The flag is encrypted using AES-CBC, where the key is derived from the LCG parameters (p, a, b, s). Our goal is to recover these secret parameters from the 4 consecutive outputs provided.

Given Files

chall.py - The challenge script:

1
class LCG:
2
    def __init__(self):
3
        self.p = getPrime(64)
4
        self.a = getRandomRange(1, self.p)
5
        self.b = getRandomRange(1, self.p)
6
        self.s = getRandomRange(1, self.p)
7

8
    def serve_coffee(self):
9
        self.s = (self.a * self.s + self.b) % self.p
10
        return self.s

output.txt - The challenge output:

1
#1 order: 4052328936969804578
2
#2 order: 8676271689691567645
3
#3 order: 2647032430467963079
4
#4 order: 6612596210231769351
5
encrypted flag: 0c5355c5bb76b2a86aa7cf53279fb2350883865f2ca7423ff47512278a59a8db1ed85e82e0d84c2fec52e29d0b3aefd97d791f11edf18efdf1febc07ae860b8b

Solution

Understanding the LCG

An LCG generates numbers using the recurrence relation:

$s_{n+1} = (a \cdot s_n + b) \mod p$

Where:

p = modulus (64-bit prime)
a = multiplier
b = increment
s = current state

We have 4 consecutive outputs: s₁, s₂, s₃, s₄

Step 1: Recovering the Modulus `p`

The key insight is that consecutive differences have a multiplicative relationship:

$t_n = s_{n+1} - s_n$

Since:

$s_2 - s_1 = a \cdot s_1 + b - s_1 - a \cdot s_0 - b = a(s_1 - s_0) = a \cdot t_0$
$s_3 - s_2 = a(s_2 - s_1) = a \cdot t_1$
$s_4 - s_3 = a(s_3 - s_2) = a \cdot t_2$

This means: $\frac{t_2}{t_1} = \frac{t_3}{t_2} = a \pmod{p}$

Cross-multiplying: $t_2^2 \equiv t_1 \cdot t_3 \pmod{p}$

Therefore: $t_2^2 - t_1 \cdot t_3 \equiv 0 \pmod{p}$

Computing this value gives us a multiple of p:

1
t1 = s2 - s1  # 4623942752721763067
2
t2 = s3 - s2  # -6029239259223604566
3
t3 = s4 - s3  # 3965563779763806272
4

5
zero_val = t2 * t2 - t3 * t1
6
# = 18015186145068426177274734295463492132

Factoring this value:

1
18015186145068426177274734295463492132 = 2² × 9197623 × 37447334611 × 13076220846716751461

The 64-bit prime factor is our modulus: $p = 13076220846716751461$

Step 2: Recovering the Multiplier `a`

Using the relationship $t_2 = a \cdot t_1 \pmod{p}$ :

$a = t_2 \cdot t_1^{-1} \pmod{p}$

1
a = (t2 * pow(t1, -1, p)) % p
2
# a = 6534081916410610007

Step 3: Recovering the Increment `b`

From $s_2 = a \cdot s_1 + b \pmod{p}$ :

$b = s_2 - a \cdot s_1 \pmod{p}$

1
b = (s2 - a * s1) % p
2
# b = 12854780772490122855

Step 4: Recovering the Initial State `s₀`

From $s_1 = a \cdot s_0 + b \pmod{p}$ :

$s_0 = (s_1 - b) \cdot a^{-1} \pmod{p}$

1
s0 = ((s1 - b) * pow(a, -1, p)) % p
2
# s0 = 12938961673315310206

Step 5: Decrypting the Flag

With all parameters recovered, we can derive the AES key and decrypt:

1
params = (p, a, b, s0)
2
# = (13076220846716751461, 6534081916410610007, 12854780772490122855, 12938961673315310206)
3

4
key = hashlib.sha256(str(params).encode()).digest()
5
cipher = AES.new(key, AES.MODE_CBC, iv=enc_flag[:16])
6
flag = unpad(cipher.decrypt(enc_flag[16:]), 16)

Recovered Parameters

Parameter	Value
`p`	13076220846716751461
`a`	6534081916410610007
`b`	12854780772490122855
`s₀`	12938961673315310206

Full Solver

1
import hashlib
2
from Crypto.Cipher import AES
3
from Crypto.Util.Padding import unpad
4
import sympy
5

6
def decrypt_flag(ct, params):
7
    key = hashlib.sha256(str(params).encode()).digest()
8
    cipher = AES.new(key, AES.MODE_CBC, iv=ct[:16])
9
    return unpad(cipher.decrypt(ct[16:]), 16)
10

11
# Given outputs
12
s1 = 4052328936969804578
13
s2 = 8676271689691567645
14
s3 = 2647032430467963079
15
s4 = 6612596210231769351
16
enc_flag = bytes.fromhex("0c5355c5bb76b2a86aa7cf53279fb2350883865f2ca7423ff47512278a59a8db1ed85e82e0d84c2fec52e29d0b3aefd97d791f11edf18efdf1febc07ae860b8b")
17

18
# Step 1: Recover p
19
t1, t2, t3 = s2 - s1, s3 - s2, s4 - s3
20
zero_val = t2 * t2 - t3 * t1
21

22
factors = sympy.factorint(abs(zero_val))
23
for factor in factors:
24
    if 63 <= factor.bit_length() <= 64 and sympy.isprime(factor):
25
        p = factor
26
        break
27

28
# Step 2-4: Recover a, b, s0
29
a = (t2 * pow(t1, -1, p)) % p
30
b = (s2 - a * s1) % p
31
s0 = ((s1 - b) * pow(a, -1, p)) % p
32

33
# Step 5: Decrypt
34
flag = decrypt_flag(enc_flag, (p, a, b, s0))
35
print(f"Flag: {flag.decode()}")

Flag

1
Alpaca{how_much_sugar_do_you_need}