```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?!
solves: 352```
This challenge is first generates p and q using a lcg, then use the p and q generated to encrypted the flag using rsa. Notice that the seed for lcg is provided, and the first 6 output of the lcg is provided. Therefore, if we recover the parameters for lcg, we can re-generate the same p and q from the program, and decrypt rsa accordingly.
While recovering m and c is trivial, recovering n is harder. I found this script and modify it a bit since the modulus end up not being a prime. After recoving the parameters, the rest of the solve are straight forward.
```from math import gcdfrom sage.all import GF, Zmodfrom sage.all import is_prime_powerfrom Crypto.PublicKey import RSAfrom Crypto.Util.number import bytes_to_long, isPrime, long_to_bytes
# https://github.com/jvdsn/crypto-attacks/blob/master/attacks/lcg/parameter_recovery.py# with some modificationdef attack(y, m=None, a=None, c=None):    """    Recovers the parameters from a linear congruential generator.    If no modulus is provided, attempts to recover the modulus from the outputs (may require many outputs).    If no multiplier is provided, attempts to recover the multiplier from the outputs (requires at least 3 outputs).    If no increment is provided, attempts to recover the increment from the outputs (requires at least 2 outputs).    :param y: the sequential output values obtained from the LCG    :param m: the modulus of the LCG (can be None)    :param a: the multiplier of the LCG (can be None)    :param c: the increment of the LCG (can be None)    :return: a tuple containing the modulus, multiplier, and the increment    """    if m is None:        assert len(y) >= 4, "At least 4 outputs are required to recover the modulus"        for i in range(len(y) - 3):            d0 = y[i + 1] - y[i]            d1 = y[i + 2] - y[i + 1]            d2 = y[i + 3] - y[i + 2]            g = d2 * d0 - d1 * d1            m = g if m is None else gcd(g, m)
        #assert is_prime_power(m), "Modulus must be a prime power, try providing more outputs"
    gf = Zmod(m)    if a is None:        assert len(y) >= 3, "At least 3 outputs are required to recover the multiplier"        x0 = gf(y[0])        x1 = gf(y[1])        x2 = gf(y[2])        a = int((x2 - x1) / (x1 - x0))
    if c is None:        assert len(y) >= 2, "At least 2 outputs are required to recover the multiplier"        x0 = gf(y[0])        x1 = gf(y[1])        c = int(x1 - a * x0)
    return m, a, c
lcg = list(map(int, open("dump.txt", "r").read().split()))seed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635lcg = [seed] + lcg
print(lcg)m, a, c = attack(lcg)print(m, a, c)
# verify outputfor i in range(len(lcg) - 1):    assert (a*lcg[i]+c)%m == lcg[i+1]
# taken from generate.pyclass LCG:    global m, a, c    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
# Find prime value of specified bits a specified amount of timesseed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635lcg = LCG(seed)primes_arr = []
dump = Falseitems = 0#dump_file = open("dump.txt", "w")
primes_n = 1while True:    for i in range(8):        while True:            prime_candidate = lcg.next()            if dump:                dump_file.write(str(prime_candidate) + '\n')                items += 1                if items == 6:                    dump = False                    dump_file.close()            if not isPrime(prime_candidate):                continue            elif prime_candidate.bit_length() != 512:                continue            else:                primes_n *= prime_candidate                primes_arr.append(prime_candidate)                break
    # Check bit length    if primes_n.bit_length() > 4096:        print("bit length", primes_n.bit_length())        primes_arr.clear()        primes_n = 1        continue    else:        break
# Create public key 'n'n = 1for j in primes_arr:    n *= jprint("[+] Public Key: ", n)print("[+] size: ", n.bit_length(), "bits")
# now decrypt the flag with p and qprint(primes_arr)phi = 1for k in primes_arr:    phi *= (k - 1)
key = RSA.importKey(open("public.pem", "rb").read())print(key.e, key.n)print(key.n == n)e = key.e
d = pow(e, -1, phi)
c = int.from_bytes(open("flag.txt", "rb").read(), "little")print(c)
print(long_to_bytes(pow(c, d, n)))````CTF{C0nGr@tz_RiV35t_5h4MiR_nD_Ad13MaN_W0ulD_b_h@pPy}`
[link to blog](https://bronson113.github.io/2023/06/26/googlectf-2023-writeup.html#least-common-genominator)