LCG Warmup

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Easy | OS: N/A | **Author: XESXOR Techniques: lcg_parameter_recovery, modular_arithmetic

Summary

Walkthrough of the CUSTOM Crypto LCG Warmup. Task: Recover parameter c of LCG when multiplier m and modulus n are known. Solution: Use formula c = (x1 - m * x0) mod n with 2 consecutive outputs to find c and predict next value.

Description

A task on recovering the parameter c of an LCG (Linear Congruential Generator) when the multiplier m and modulus n are known.

Analysis

Linear Congruential Generator (LCG)

LCG is one of the simplest PRNGs:

x_{n+1} = (m * x_n + c) mod n

where:

• m — multiplier
• c — increment
• n — modulus
• x_0 — initial state (seed)

Vulnerability

If m, n and two consecutive outputs x0, x1 are known:

x1 = (m * x0 + c) mod n
c = (x1 - m * x0) mod n

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

One equation, one unknown — trivially solvable.

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
from pwn import *

def solve_lcg_level1(x0, x1, m, n):
    """
    Recover c from LCG: x1 = (m * x0 + c) mod n
    """
    c = (x1 - m * x0) % n
    return c

def predict_next(x, m, c, n):
    """Predict the next LCG value"""
    return (m * x + c) % n

# Connect to server
r = remote('crypto-kids20.forkbomb.ru', PORT)

# Get parameters
m = int(r.recvline().decode().split('=')[1].strip())
n = int(r.recvline().decode().split('=')[1].strip())
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Get 2 outputs
x0 = int(r.recvline().decode().split(':')[1].strip())
x1 = int(r.recvline().decode().split(':')[1].strip())

# Recover c
c = solve_lcg_level1(x0, x1, m, n)
print(f"[+] Recovered c = {c}")

# Predict next value
x2 = predict_next(x1, m, c, n)
print(f"[+] Predicted x2 = {x2}")

# Send answer
r.sendline(str(x2))
print(r.recvall().decode())

Math

Given: x1 = (m * x0 + c) mod n
Find: c

Solution:
c = (x1 - m * x0) mod n

Concepts

LCG Parameter Recovery Hierarchy

The difficulty of recovering LCG parameters depends on what is known: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Formula for recovering c

x1 = m * x0 + c (mod n)
c = x1 - m * x0 (mod n)

Important: the result is taken modulo n so that c is in the range [0, n-1]. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key Takeaways / Lessons

• Mastering lcg_parameter_recovery, modular_arithmetic was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-03-09 • CUSTOM • LCG Warmup • Difficulty: Easy