# Challenge Name: LEAST COMMON GENOMINATOR?
## Description:> Someone used this program to send me an encrypted message but I can't read it! It uses something called an LCG, do you know what it is? I dumped the first six consecutive values generated from it but what do I do with it?!
## Writeup:The challenge clearly points to the linear congruential generator LCG algorithm### Understanding the LCG:A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the oldest and best-known pseudorandom number generator algorithms. The theory behind them is relatively easy to understand, and they are easily implemented and fast, especially on computer hardware which can provide modular arithmetic by storage-bit truncation.The generator is defined by the recurrence relation:$$ X_{n+1} = (aX_{n} + c) \  mod \ m $$-Wikipedia-### Solution:To decode the `flag.txt` file we need to find the modulus 'm', the multiplier 'a' and the increment 'c'. So I implement the following algorithm:
```pythonfrom functools import reducefrom math import gcdfrom Crypto.Util.number import isPrime, long_to_bytesfrom cryptography.hazmat.backends import default_backendfrom cryptography.hazmat.primitives import serialization
# Read candidate numbers from filewith open('dump.txt', 'r') as f:    candidates = f.read().splitlines()
# Convert candidates to integersknown = [int(i) for i in candidates]
# Extended Euclidean Algorithmdef egcd(a, b):    if a == 0:        return b, 0, 1    else:        g, x, y = egcd(b % a, a)        return g, y - (b // a) * x, x
# Modular inverse using Extended Euclidean Algorithmdef modinv(b, n):    g, x, _ = egcd(b, n)    if g == 1:        return x % n
# Function to crack the modulus 'm'def crack_m(outs):    diffs = [s1 - s0 for s0, s1 in zip(outs, outs[1:])]    zeros = [t2 * t0 - t1 * t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]    m = abs(reduce(gcd, zeros))    return m
# Crack the modulus 'm'm = crack_m(known)
# Function to crack the multiplier 'a'def crack_a(outs, m):    a = (outs[2] - outs[1]) * modinv(outs[1] - outs[0], m) % m    return a
# Crack the multiplier 'a'a = crack_a(known, m)
# Function to crack the increment 'c'def crack_c(outs, m, a):    c = (outs[1] - outs[0] * a) % m    return c
# Crack the increment 'c'c = crack_c(known, m, a)
# Linear Congruential Generator (LCG) classclass LCG:    lcg_m = a    lcg_c = c    lcg_n = m
    def __init__(self, lcg_s):        self.state = lcg_s
    def next(self):        self.state = (self.state * self.lcg_m + self.lcg_c) % self.lcg_n        return self.state
# Set the seed value for LCGseed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635lcg = LCG(seed)primes_arr = []
primes_n = 1while True:    for i in range(8):        while True:            prime_candidate = lcg.next()            # Check if the candidate number is prime            if not isPrime(prime_candidate):                continue            # Check if the candidate number has a bit length of 512            elif prime_candidate.bit_length() != 512:                continue            else:                primes_n *= prime_candidate                primes_arr.append(prime_candidate)                break
    # Check if the product of primes exceeds the bit length of 4096    if primes_n.bit_length() > 4096:        print("bit length", primes_n.bit_length())        primes_arr.clear()        primes_n = 1        continue    else:        break
n = 1for j in primes_arr:    n *= j
# Calculate Euler's totient function (phi)phi = 1for k in primes_arr:    phi *= (k - 1)
# Load public key from filewith open("public.pem", "rb") as pub_file:    public_key = serialization.load_pem_public_key(pub_file.read(), backend=default_backend())
# Get the public exponent 'e'e = public_key.public_numbers().e
# Calculate the private exponent 'd'd = pow(e, -1, phi)
# Read the encrypted content from filewith open("flag.txt", "rb") as flag_file:    content = flag_file.read()    _enc = int.from_bytes(content, "little")
# Decrypt the encrypted contentflag_b = pow(_enc, d, n)
# Convert the decrypted content to bytesflag = long_to_bytes(flag_b)
# Print the flagprint(flag.decode())```
## The Flag:```CTF{C0nGr@tz_RiV35t_5h4MiR_nD_Ad13MaN_W0ulD_b_h@pPy}```