**Tags:** lcg crypto rsa

Rating: 4.0

```

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).