# Crypto - LEAST COMMON GENOMINATOR?
![LCG](https://themj0ln1r.github.io/assets/img/post_img/googlectf23_lcg.png)
Attached File : [generate.py,dump.txt,flag.txt,public.pem]
`generate.py`
```pythonfrom secret import configfrom Crypto.PublicKey import RSAfrom Crypto.Util.number import bytes_to_long, isPrime
class LCG:    lcg_m = config.m    lcg_c = config.c    lcg_n = config.n
    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
if __name__ == '__main__':
    assert 4096 % config.it == 0    assert config.it == 8    assert 4096 % config.bits == 0    assert config.bits == 512
    # Find prime value of specified bits a specified amount of times    seed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635    lcg = LCG(seed)    primes_arr = []     dump = True    items = 0    dump_file = open("dump.txt", "w")
    primes_n = 1    while True:        for i in range(config.it):            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() != config.bits:                    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")
    # Calculate totient 'Phi(n)'    phi = 1    for k in primes_arr:        phi *= (k - 1)
    # Calculate private key 'd'    d = pow(config.e, -1, phi)
    # Generate Flag    assert config.flag.startswith(b"CTF{")    assert config.flag.endswith(b"}")    enc_flag = bytes_to_long(config.flag)    assert enc_flag < n
    # Encrypt Flag    _enc = pow(enc_flag, config.e, n)
    with open ("flag.txt", "wb") as flag_file:        flag_file.write(_enc.to_bytes(n.bit_length(), "little"))
    # Export RSA Key    rsa = RSA.construct((n, config.e))    with open ("public.pem", "w") as pub_file:        pub_file.write(rsa.exportKey().decode())```
`dump.txt`
```text216677167559518406933910736590837715770116448582098140999392527951219912341837403427546559000484813594667145408422073164509928674625130832365314436306338567292729504676254562984546782196130904672548246793189930522945875701534249352673649718272771375219292027836215534219585337611236538241354723781337652361152230396903302352921484704122705539403201050490164649102182798059926343096511158288867301614648471516723052092761312105117735046752506523136197227936190287457884778773614375685082340716851911217526009260147681053983079265656874713660425014685811141870505413826619334816923975104677901047492436707298989537779275783329794790865466374690369484825511512400998038122359499971478928710979822930172564751895044479551473994057918753954508142972640399083614726032569216122550420443270381003007873520763042837493244197616666667768397146110589301602119884836605418664463550865399026934848289084292975494312467018767881691302197```
And the `flag.txt` is an encrypted flag.
Observations:
	1. The actual flag was encrypted with the RSA	2. The primes are generated using a Linear Congruential Generator	3. The seed is known	4. First 6 generated random values of LCG are known
The LCG works on equation : 
$$ X_{n+1} = (a \times X_{n}+c) mod p $$
Where, - $$X(n)$$ is a sequence of pseudo random values.- $$p$$ is modulo defined as $$0 < p$$- $$a$$ is the multiplier defined as $$0 < a < p$$- $$c$$ is the increment $$0 <= c < p$$ ( if $$c = 0$$ the LCG is called Multiplicative Congruential Generator)
We can see the generate.py implementation.
`lcg_m = alcg_c = clcg_n = p`
We have total generated values of lcg including seed.
We can find the `n(modulus)` by making the 4 $$2 \times 2$$ matrices from $$ X_1,X_2,X_3,X_4,X_5,X_6,X_7$$ and finding the GCD of the determinant values of these 7 values.
The 4 $$2 \times 2$$ matrices,$$\begin{bmatrix} 	X_1 - X_0 & X_2 - X_1\\	X_2 - X_0 & X_3 - X_1\end{bmatrix}\begin{bmatrix} 	X_2 - X_0 & X_3 - X_1\\	X_3 - X_0 & X_4 - X_1\end{bmatrix}$$
$$\begin{bmatrix} 	X_3 - X_0 & X_4 - X_1\\	X_4 - X_0 & X_5 - X_1\end{bmatrix},\begin{bmatrix} 	X_4 - X_0 & X_5 - X_1\\	X_5 - X_0 & X_6 - X_1\end{bmatrix}$$
Finding determinant of these all and then finding the GCD of them will give us the modulus(n) used in lcg.
With $$n$$ we can find $$a$$ by solving these equations.
$$X_1 = (a \times X_0+c) mod p\\X_2 = (a \times X_1+c) mod p\\$$
$$X_2 - X_1 = (a \times X_1+c - (X_0 \times a+c)) mod p\\X_2 - X_1 = (a \times X_1 - (X_0 \times a)) mod p\\X_2 - X_1 = (X_1 - X_0) \times a mod p\\\frac{X_2 - X_1}{X_1 - X_0} = a mod p \\a = \frac{X_2 - X_1}{X_1 - X_0} mod p\\a = ((X_2 - X_1)) \times InverseMod(X_1 - X_0,p) mod p\\$$
Lets solve for $$c$$,
$$X_1 = (a \times X_0+c) mod p\\X_1 - c = (a \times X_0) mod p\\-c = (a \times X_0 - X_1) mod p\\c = (X_1 - a \times X_0) mod p$$
So, with `n,c,m` we can generate entire series which is used to generate primes in the encryption.
The python implementation to find `n,c,m`
```pythonimport math
def calc_det(i, j, X):    a1 = X[i] - X[0]    b1 = X[i + 1] - X[1]    a2 = X[j] - X[0]    b2 = X[j + 1] - X[1]    det = a1 * b2 - a2 * b1    return abs(det)
def GCD(a, b):
    a = abs(a)    b = abs(b)    while a:        a, b = b % a, a    return b
def modInverse(a, m):    if GCD(a, m) != 1:        return None  #if not releatively prime no modinv    u1, u2, u3 = 1, 0, a    v1, v2, v3 = 0, 1, m    while v3 != 0:        q = u3 // v3         v1, v2, v3, u1, u2, u3 = (            u1 - q * v1,            u2 - q * v2,            u3 - q * v3,            v1,            v2,            v3,        )    return u1 % m
def main():    while True:        try:            X = [                211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635,                2166771675595184069339107365908377157701164485820981409993925279512199123418374034275465590004848135946671454084220731645099286746251308323653144363063385,                6729272950467625456298454678219613090467254824679318993052294587570153424935267364971827277137521929202783621553421958533761123653824135472378133765236115,                2230396903302352921484704122705539403201050490164649102182798059926343096511158288867301614648471516723052092761312105117735046752506523136197227936190287,                4578847787736143756850823407168519112175260092601476810539830792656568747136604250146858111418705054138266193348169239751046779010474924367072989895377792,                7578332979479086546637469036948482551151240099803812235949997147892871097982293017256475189504447955147399405791875395450814297264039908361472603256921612,                2550420443270381003007873520763042837493244197616666667768397146110589301602119884836605418664463550865399026934848289084292975494312467018767881691302197,            ]
            Det_X = []            Det_X.append(calc_det(1, 2, X))            Det_X.append(calc_det(2, 3, X))            Det_X.append(calc_det(3, 4, X))            Det_X.append(calc_det(4, 5, X))
            found_p = math.gcd(math.gcd(Det_X[0], Det_X[1]), math.gcd(Det_X[2], Det_X[3]))
            # To find 'a' and 'c' we need to solve the             mod_inv_a = modInverse((X[2] - X[3]), found_p)             found_a = ((X[3] - X[4]) * mod_inv_a) % found_p             found_c = (X[4] - found_a * X[3]) % found_p             print("n = %d\nm = %d\nc = %d\n" % (found_p, found_a, found_c))            break        except TypeError:            pass
if __name__ == "__main__":    main()
#Output# n = 8311271273016946265169120092240227882013893131681882078655426814178920681968884651437107918874328518499850252591810409558783335118823692585959490215446923# m = 99470802153294399618017402366955844921383026244330401927153381788409087864090915476376417542092444282980114205684938728578475547514901286372129860608477# c = 3910539794193409979886870049869456815685040868312878537393070815966881265118275755165613835833103526090552456472867019296386475520134783987251699999776365```
With these values as input we can find the modulus used in the encryption, `n`, `phi` and followed by `d`.
Or we can just import the `public.pem` to find `e,n` used in the encryption.
Here is the final solution script to get the flag.
```pythonfrom Crypto.PublicKey import RSAfrom Crypto.Util.number import bytes_to_long, isPrime,long_to_bytes
class LCG:    lcg_m = 99470802153294399618017402366955844921383026244330401927153381788409087864090915476376417542092444282980114205684938728578475547514901286372129860608477    lcg_c = 3910539794193409979886870049869456815685040868312878537393070815966881265118275755165613835833103526090552456472867019296386475520134783987251699999776365    lcg_n = 8311271273016946265169120092240227882013893131681882078655426814178920681968884651437107918874328518499850252591810409558783335118823692585959490215446923
    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
if __name__ == '__main__':
    it = 8    bits = 512
    # Find prime value of specified bits a specified amount of times    seed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635    lcg = LCG(seed)    primes_arr = []     dump = True    items = 0
    primes_n = 1    while True:        for i in range(it):            while True:                prime_candidate = lcg.next()                if not isPrime(prime_candidate):                    continue                elif prime_candidate.bit_length() != bits:                    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    # Calculate totient 'Phi(n)'    phi = 1    for k in primes_arr:        phi *= (k - 1)
    # Read the public key from the "public.pem" file    with open("public.pem", "rb") as pub_file:        rsa_key = RSA.import_key(pub_file.read())    # Extract the values of e and n from the RSA key    e = rsa_key.e    n = rsa_key.n
    # Calculate private key 'd'    d = pow(e, -1, phi)
    with open("flag.txt", "rb") as flag_file:        flag_data = flag_file.read()
    _enc = int.from_bytes(flag_data, "little")     # decrypt flag    flag = pow(_enc,d,n)    print(long_to_bytes(flag))
# b'CTF{C0nGr@tz_RiV35t_5h4MiR_nD_Ad13MaN_W0ulD_b_h@pPy}'
```
> `Flag : CTF{C0nGr@tz_RiV35t_5h4MiR_nD_Ad13MaN_W0ulD_b_h@pPy}`
***
# [Original Writeup](https://themj0ln1r.github.io/posts/googlectf23)