# RSyay! (crypto, 396p)
In the task we get the code running on the server:
```pythondef func(bits):    keys = gen_rsa_key(bits, e=65537)    p = keys.p    q = keys.q    m = getPrime(bits + 1)    x = pow(p, m, m) * pow(q, m, m) + p * pow(q, m, m) + q * pow(p, m, m) + p * q + pow(p, m - 1, m) * pow(q, m - 1, m)    text = os.urandom(32)    print('Plaintext (b64encoded) : ', b64encode(text).decode())    print()    print(hex(x)[2:])    print(hex(m)[2:])    print()    ciphertext = input('Ciphertext (b64encoded) : ')    check(ciphertext)```
The idea is pretty simple:
1. There is some random RSA key2. We get some prime `m` longer than RSA modulus at least by a single bit3. We get a special value `x`, calculated using `p` and `q`4. Our goal is to encrypt plaintext provided by the server
Server requires the encryption in form of base64 results of:
```pythondef encrypt(keys, plaintext):    from Crypto.Cipher import PKCS1_OAEP    encryptor = PKCS1_OAEP.new(keys)    return encryptor.encrypt(plaintext)```
This means We need to somehow recover the modulus of the RSA key (exponent is known to be 65537).
For this we have to look at value x:
```x = pow(p, m, m) * pow(q, m, m) + p * pow(q, m, m) + q * pow(p, m, m) + p * q + pow(p, m - 1, m) * pow(q, m - 1, m)```
The key in solving this challenge is to know Euler Totient Theorem `https://en.wikipedia.org/wiki/Euler's_theorem`
Notice that all calculations in `x` are done `mod m`, and `m` is a prime, therefore `phi(m) = m-1`.Notice that according to the theorem `x^phi(m) mod m == 1`.
Let's modify the equation we have, to use `m-1` exponent wherever we can:
```x = pow(p, m, m) * pow(q, m, m) + p * pow(q, m, m) + q * pow(p, m, m) + p * q + pow(p, m - 1, m) * pow(q, m - 1, m)x = (p^m mod m * q^m mod m) + (p*q^m mod m) + (q*p^m mod m) + (p*q) + (p^(m-1) mod m * q^(m-1) mod m)```
For more readability let's take each part separately:
1.```(p^m mod m * q^m mod m)p*p^(m-1) mod m * q*q^(m-1) mod mp*1 * q*1 mod mp*q mod mp*q ```
2. ```(p*q^m mod m)p*q*q(m-1) mod mp*q*1 mod mp*q mod mp*q```
3. ```(q*p^m mod m)q*p*p^(m-1) mod mq*p*1 mod mp*q mod mp*q```
4. ```p*q```
5.```(p^(m-1) mod m * q^(m-1) mod m)1*1 mod m1```
Notice that we know that `m` is larger than `p*q` because it was selected to be at least 1 bit longer, so `p*q mod m = p*q`
Now if we combine all of those we get:
```x = p*q + p*q + p*q + p*q +1 = 4*pq+1x = 4*n+1n = (x-1)/4```
We can verify this quickly by:
```pythondef sanity():    bits = 1024    m = getPrime(bits + 1)    p = getPrime(bits // 2)    q = getPrime(bits // 2)    n = p * q    x = pow(p, m, m) * pow(q, m, m) + p * pow(q, m, m) + q * pow(p, m, m) + p * q + pow(p, m - 1, m) * pow(q, m - 1, m)    assert n == (x - 1) / 4```
Now we can just plug this into the solver:
```pythondef main():    host = "crypto.byteband.it"    port = 7002    s = nc(host, port)    for i in range(32):        data = receive_until_match(s, "Plaintext \(b64encoded\) :  ")        pt = receive_until(s, "\n").decode("base64")        receive_until(s, "\n")        x = int(receive_until(s, "\n").strip(), 16)        m = int(receive_until(s, "\n").strip(), 16)        print('x', x)        print('m', m)        n = recover_n(x, m)        print('recovered n', n)        key = RSA.construct((long(n), long(65537)))        ct = base64.b64encode(encrypt(key, pt))        print('ct', ct)        send(s, ct)    interactive(s)```
And after a moment get get: `flag{RSA_1s_th3_str0ng3st_c1ph3r_ind33d_0_0}`
[complete solver here](https://raw.githubusercontent.com/TFNS/writeups/master/2020-04-12-ByteBanditsCTF/rsyay/solver.py)