Overview
We are given 100 linear equations with minor noise, generated by 12 secret 64-bit ingredients. Recovering the ingredients allows us to determine the internal state of a custom PRNG (based on Elementary Cellular Automaton Rule 30) and step it backward to find the initial seed and decode the flag.
Reconnaissance
The problem generates equations of the form:
Where the modulus M is approx 80 bits, the ingredients are 64 bits, and the noise is bounded by 37 bits. This is a classic Hidden Number Problem (HNP) / Learning With Errors (LWE).
Exploitation Strategy
Step 1: Lattice Reduction (LLL)
We construct a lattice matrix using SageMath or SymPy with Kannan Embedding. By running the LLL lattice reduction algorithm, we discover the shortest vector, which exposes the 12 secret ingredient integers.
Step 2: Rule 30 PRNG Analysis
Analyzing the PRNG source shows that the next state is generated using Rule 30: next_state = Right ^ (Center | Left).
Step 3: Z3 SAT Solving
Since we have the state at steps 513-1280 (from the recovered ingredients), we set up Z3 boolean variables and constraints to solve the pre-image of the state at step 512.
Step 4: Stepping Rule 30 Backward
With Z3, we step the 64-bit state backward 512 times to recover the initial random sequence. XORing this sequence with the output integer reveals the flag.
Solution Code
# 1. Use LLL algorithm to solve HNP and get ingredients
# 2. Reconstruct state at index 512
# 3. Step state backward 512 times using Z3 to retrieve RNG seed:
# ...
# FLAG_int = potions_count ^ rng_output
# print(FLAG_int.to_bytes(...).decode())
# Output Flag: CrackOn{Its_A_Hard_Challenge}Flag
CrackOn{Its_A_Hard_Challenge}