hidE===
This RSA encryption service is so secure we're not even going to tell you how we encrypted it
`nc be.ax 31124`
Downloads
- [main.py](https://static.cor.team/uploads/2285a60dd5349ab843e68d34273849e6426817cea84df9421f6189537c64bdee/main.py)
Task analysis===
The challange gave the script running in server (`main.py`):
```python#!/usr/local/bin/pythonimport randomimport timeimport mathimport binasciifrom Crypto.Util.number import *
p, q = getPrime(512), getPrime(512)n = p * qphi = (p - 1) * (q - 1)
flag = open('./flag.txt').read().encode()
random.seed(int(time.time()))
def encrypt(msg):    e = random.randint(1, n)    while math.gcd(e, phi) != 1:        e = random.randint(1, n)    pt = bytes_to_long(msg)    ct = pow(pt, e, n)    return binascii.hexlify(long_to_bytes(ct)).decode()
def main():    print('Secure Encryption Service')    print('Your modulus is:', n)    while True:        print('Options')        print('-------')        print('(1) Encrypt flag')        print('(2) Encrypt message')        print('(3) Quit')        x = input('Choose an option: ')        if x not in '123':            print('Unrecognized option.')            exit()        elif x == '1':            print('Here is your encrypted flag:', encrypt(flag))        elif x == '2':            msg = input('Enter your message in hex: ')            print('Here is your encrypted message:', encrypt(binascii.unhexlify(msg)))        elif x == '3':            print('Bye')            exit()
if __name__ == '__main__':    main()```
Basically two 512-bit primes are generated (`p` and `q`), `n = p*q` and `phi = (p-1)*(q-1)` are set, the `flag` is loaded from file and **the random generator is initialized with `time.time()` as seed**. This seed make possible to us to solve the challenge, since we can bruteforce it (let's back here after).
When we connect to server, there is a menu when we can choose between encrypt the flag or encrypt a known message. For both of them, it is used the same function to encrypt:
```pythondef encrypt(msg):    e = random.randint(1, n)    while math.gcd(e, phi) != 1:        e = random.randint(1, n)    pt = bytes_to_long(msg)    ct = pow(pt, e, n)    return binascii.hexlify(long_to_bytes(ct)).decode()```
See that there is only one of the variables that is random (`e`) and that if `gcd(e, phi) == 1` at first time, we don't need `phi` to encrypt any message locally. We don't know `phi` but we know it is necessarily divisible by 2. A random odd `e` and an even `phi` have a great chance to be coprimes.
Solving the Challenge===
Let's start by getting the `seed`. One way to do so is setting the `seed` as te epoch time before connect the server, encrypt one known message using server and try `seed`'s sequentially until the locally encrypted known message results in the same ciphertext as the message encrypted in the server (assuming only that `phi` is even), so let's use the following encrypt function:
```pythondef encrypt(msg, n):    e = random.randint(1, n)    while e % 2 == 0:        e = random.randint(1, n)    pt = bytes_to_long(msg)    ct = pow(pt, e, n)    return binascii.hexlify(long_to_bytes(ct)).decode()```
And this script to find the `seed`:
```pythonwhile True:    prox = False    seed = int(time.time())    conn = remote('be.ax', 31124)    data = conn.recvuntil(b'option: ').decode()    n = int(re.search(r'is: (\d+)', data).group(1))    print('n =', n)    conn.sendline(b'2')    txt = b'aa'    conn.sendlineafter(b'hex: ', txt)    data = conn.recvline().decode()    print(data)    ctxt = re.search(r'message: ([0-9a-f]+)', data).group(1)    random.seed(seed)    enc = encrypt(binascii.unhexlify(txt.decode()), n)    t0 = time.time()    while enc != ctxt:        seed += 1        random.seed(seed)        enc = encrypt(binascii.unhexlify(txt.decode()), n)        if time.time() - t0 > 10:            prox = True            break    if prox:        conn.close()        continue```
As we are assuming that the only possible common factor between `e` and `phi` is 2, sometimes we won't find the `seed`. To avoid this situation, if it takes more than 10 seconds to find the `seed`, the connection is closed and it tries again.
Found the `seed`, now we can encrypt the flag using the server to get the ciphertext and get the cooresponding `e` using the `seed` locally. 
But how can we find the `flag` given the ciphertext and the `e` if we didn't factorize `n`? That is possible because we know that the original message is the same and the `n` is the same, so we can use the [Common Modulus Attack](https://infosecwriteups.com/rsa-attacks-common-modulus-7bdb34f331a5). Let's see how it works.
First we have to obtain two versions of encrypted flag and the `e` for each of them, so that the `e`'s are coprimes:
```python    random.seed(seed)    encrypt(binascii.unhexlify(txt.decode()), n)    e2 = e1 = random.randint(1, n)    conn.recvuntil(b'option: ')    conn.sendline(b'1')    data = conn.recvline().decode()    cflag2 = cflag1 = bytes_to_long(bytes.fromhex(re.search(r'flag: ([0-9a-f]+)', data).group(1)))    while gcd(e1, e2) != 1:        conn.recvuntil(b'option: ')        conn.sendline(b'1')        data = conn.recvline().decode()        cflag2 = bytes_to_long(bytes.fromhex(re.search(r'flag: ([0-9a-f]+)', data).group(1)))        e2 = random.randint(1, n)        while e2 % 2 == 0:            e2 = random.randint(1, n)```
After we must find `a` and `b` such that `a * e1 + b * e2 == 1` using the extended GCD algorithm:
```pythondef extended_gcd(x, y):    # a*x + b*y = 1    a = 0    b = 1    lasta = 1    lastb = 0    while y != 0:        quo = x // y        x, y = y, x % y        a, lasta = lasta - quo * a, a        b, lastb = lastb - quo * b, b    return lasta, lastb```
After we have `a` and `b`, the flag can be determined with `m == (c1 ** a * c2 ** b) % n`, but one of them will be negative:
```python    a, b = extended_gcd(e1, e2)    if a < 0:        print('a < 0')        cflag1 = inverse(cflag1, n)        a = -a    if b < 0:        print('b < 0')        cflag2 = inverse(cflag2, n)        b = -b    flag = long_to_bytes((pow(cflag1, a, n)*pow(cflag2, b, n)) % n)    if b'corctf' in flag:        print(flag)        break    conn.close()```
It was important to check if the flag was found because of the `e` and `phi` relation discussed before. Now we have the full solver:
```pythonfrom pwn import *from Crypto.Util.number import bytes_to_long, long_to_bytes, inversefrom math import gcd
def extended_gcd(x, y):    # a*x + b*y = 1    a = 0    b = 1    lasta = 1    lastb = 0    while y != 0:        quo = x // y        x, y = y, x % y        a, lasta = lasta - quo * a, a        b, lastb = lastb - quo * b, b    return lasta, lastb
def encrypt(msg, n):    e = random.randint(1, n)    while e % 2 == 0:        e = random.randint(1, n)    pt = bytes_to_long(msg)    ct = pow(pt, e, n)    return binascii.hexlify(long_to_bytes(ct)).decode()
while True:    prox = False    seed = int(time.time())    conn = remote('be.ax', 31124)    data = conn.recvuntil(b'option: ').decode()    n = int(re.search(r'is: (\d+)', data).group(1))    print('n =', n)    conn.sendline(b'2')    txt = b'aa'    conn.sendlineafter(b'hex: ', txt)    data = conn.recvline().decode()    print(data)    ctxt = re.search(r'message: ([0-9a-f]+)', data).group(1)    random.seed(seed)    enc = encrypt(binascii.unhexlify(txt.decode()), n)    t0 = time.time()    while enc != ctxt:        seed += 1        random.seed(seed)        enc = encrypt(binascii.unhexlify(txt.decode()), n)        if time.time() - t0 > 10:            prox = True            break    if prox:        conn.close()        continue    random.seed(seed)    encrypt(binascii.unhexlify(txt.decode()), n)    e2 = e1 = random.randint(1, n)    conn.recvuntil(b'option: ')    conn.sendline(b'1')    data = conn.recvline().decode()    cflag2 = cflag1 = bytes_to_long(bytes.fromhex(re.search(r'flag: ([0-9a-f]+)', data).group(1)))    while gcd(e1, e2) != 1:        conn.recvuntil(b'option: ')        conn.sendline(b'1')        data = conn.recvline().decode()        cflag2 = bytes_to_long(bytes.fromhex(re.search(r'flag: ([0-9a-f]+)', data).group(1)))        e2 = random.randint(1, n)        while e2 % 2 == 0:            e2 = random.randint(1, n)    assert gcd(e1, e2) == 1    a, b = extended_gcd(e1, e2)    if a < 0:        print('a < 0')        cflag1 = inverse(cflag1, n)        a = -a    assert a > 0    if b < 0:        print('b < 0')        cflag2 = inverse(cflag2, n)        b = -b    assert b > 0    flag = long_to_bytes((pow(cflag1, a, n)*pow(cflag2, b, n)) % n)    if b'corctf' in flag:        print(flag)        break    conn.close()```
Running it, after at most a few tries:
```corctf{y34h_th4t_w4snt_v3ry_h1dd3n_tbh_l0l}```
