# Random Keys — Solution
We are given a file called `server.py` along with a connection string to theremote server. When we connect to the server, we receive the following data:
![Chall](img/chall.png)
Looks like we need to mount a [chosen plaintextattack](https://en.wikipedia.org/wiki/Chosen-plaintext_attack) against theencryption scheme from the challenge. Let's inspect `server.py` to find outmore about the encryption being used.
```pythonclass LCG:    def __init__(self):        self.m = 128        self.state = bytes_to_long(os.urandom(1))        self.a = bytes_to_long(os.urandom(1))        self.b = bytes_to_long(os.urandom(1))
    def next(self):        self.state = (self.a * self.state + self.b) % self.m        return self.state
class RSA:    BITS = 512
    def __init__(self):        self.primes = [getPrime(self.BITS) for _ in range(128)]        self.gen = LCG()
    def encrypt(self, msg):        p = self.primes[self.gen.next()]        q = self.primes[self.gen.next()]        N = p * q        e = 0x10001        return (N, e, hex(pow(msg, e, N)))```
The `LCG` class obviously implements a [Linear CongruentialGenerator](https://en.wikipedia.org/wiki/Linear_congruential_generator) withnon-standard parameters. More precisely, the modulus is fixed $m = 128$, whilethe *multiplier* $a$ and *increment* $b$ are randomly generated by invoking`os.urandom(1)`, which basically returns a random byte.
The `RSA` class also implements the[RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)) in a non-standard way.In its constructor, it generates a list of $128$ large prime numbers andinstantiates a random number generator based on previously-mentioned `LCG`implementation.
Inspecting the `encrypt` function reveals that a *new* public key is generatedon the spot. More precisely, its modulus is the product of two primes chosen bythe `LCG`-based random generator. The remainder of the function performsstandard RSA encryption.
Let's inspect what happens in the main function of `server.py`.
```pythondef main():    signal.signal(signal.SIGALRM, handler)    signal.alarm(300)
    myprint(BANNER)
    myprint("Try to defeat our new encryption service using a chosen plaintext attack with at most 10 queries:")    myprint("    1) Encrypt arbitrary message")    myprint("    2) Encrypt flag and exit")    myprint("")
    print("Initializing service... ", end="", flush=True)    cipher = RSA()    myprint("DONE!")    myprint("")
    for _ in range(10):        action = input("> ")        if action == '1':            message = bytes_to_long(bytes.fromhex(input("Message (hex): ")))            result = cipher.encrypt(message)            myprint(f"Result (N, e, ct): {result}")        elif action == '2':            flag = bytes_to_long(open("flag.txt", "rb").read())            result = cipher.encrypt(flag)            myprint(f"Result (N, e, ct): {result}")            exit(0)
```
The user basically has $10$ attempts to either:  * obtain a ciphertext for a chosen plaintext  * obtain the encrypted flag
Since the mere existence of the `LCG` implementation is suspicious, let'sanalyze it further. It is very easy to see that any LCG, regardless of how wechoose its parameters, will eventually end up in a cycle for any given seedvalue. In general, we want the length of that cycle, also known as the seedperiod, to be as large as possible. It should also be obvious that not allchoices of parameters will ensure that property.
At this point, you may bring out your trusty pen and paper and calculate the[expected](https://en.wikipedia.org/wiki/Expected_value) seed period given thevalue $m$, and the fact that all parameters (including the seed) are generateduniformly at random. An easier approach is to simply test this LCGimplementation and see what happens.
```python#!/usr/bin/python3
from Crypto.Util.number import *
import os
class LCG:    def __init__(self):        self.m = 128        self.state = bytes_to_long(os.urandom(1))        self.a = bytes_to_long(os.urandom(1))        self.b = bytes_to_long(os.urandom(1))
    def next(self):        self.state = (self.a * self.state + self.b) % self.m        return self.state
def main():    for _ in range(20):        gen = LCG()        nums = []        for _ in range(10):            nums.append(gen.next())        print(nums)
if __name__ == '__main__':    main()```
Running this code gives us
![LCG Test](img/lcg_test.png)
We can see that in $6$ out of $20$ experiments, the our generator ends up in acycle of length $1$. This is a serious flaw in the context of the challenge,because it means that the last few encryptions will be done with an RSA modulus$N = p^2$, which is obviously trivial to factorize. This completely breaks thesecurity of the encryption scheme.
More precisely, we can solve the challenge by:  * Spamming the encryption oracle $9$ times hoping that the generator ends up    in a cycle of length $1$.  * Obtaining the encrypted flag in the $10$-th query.  * Attempting to factorize $N$ by taking the square root. If it turns out that    $N \ne p^2$, we simply try again.  * Decrypt the flag by calculating the private key $d$ as the multiplicative inverse    of $e$ modulo $\varphi$, where $\varphi = p(p - 1)$.
Putting it all together in the solve script
```pythonfrom Crypto.Util.number import *from gmpy2 import isqrtfrom pwn import *
r = remote("0.cloud.chals.io", 24473)print(r.recvuntil("Initializing service...").decode("utf-8"))
l = log.progress('Waiting for prompt')r.recvuntil(b"> ")l.success('Done')
l = log.progress('Spamming encryption oracle')for i in range(9):    r.sendline(b"1")    r.recvuntil(b"Message (hex): ")    r.sendline(b"ab")    r.recvuntil(b"> ").decode("utf-8")l.success('Done')
l = log.progress('Getting encrypted flag')r.sendline(b"2")(N, e, ct) = eval(r.recvline().decode("utf-8").split(":")[-1])ct = int(ct, 16)l.success('Done')
l = log.progress('Decrypting flag')
p = int(isqrt(N))if p * p != N:    l.failure('N is not a perfect square, try again!')    exit(0)phi = p * (p - 1)d = inverse(e, phi)flag = long_to_bytes(pow(ct, d, N)).decode("utf-8")l.success(flag)```
After a few attempts, this reveals the flag: `TBTL{L1n3ar_C0ngru3n71al_Gen3r4t0r5_W17h_R4nd0m_P4ram3t3r5_5uck!}`.