```
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 gcd
from sage.all import GF, Zmod
from sage.all import is_prime_power
from Crypto.PublicKey import RSA
from 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 modification
def 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 = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635
lcg = [seed] + lcg

print(lcg)
m, a, c = attack(lcg)
print(m, a, c)

# verify output
for i in range(len(lcg) - 1):
assert (a*lcg[i]+c)%m == lcg[i+1]

# taken from generate.py
class 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 times
seed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635
lcg = LCG(seed)
primes_arr = []

dump = False
items = 0
#dump_file = open("dump.txt", "w")

primes_n = 1
while 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 = 1
for j in primes_arr:
n *= j
print("[+] Public Key: ", n)
print("[+] size: ", n.bit_length(), "bits")

# now decrypt the flag with p and q
print(primes_arr)
phi = 1
for 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)

Original writeup (https://bronson113.github.io/2023/06/26/googlectf-2023-writeup.html#least-common-genominator).