# Pelle's rotor supported arithmetic
## Challenge
```#!/usr/bin/python3from sys import stdin, stdout, exit#from flag import FLAGfrom secrets import randbelowfrom gmpy import next_primefrom Crypto.Util.number import bytes_to_long, long_to_bytes
FLAG = bytes_to_long(b'mf{testowa_flaga_costam_costam}')
p = int(next_prime(randbelow(2**512)))q = int(next_prime(randbelow(2**512)))n = p * qe = 65537
phi = (p - 1)*(q - 1)d = int(pow(e, -1, phi))d_len = len(str(d))
print("encrypted flag", pow(FLAG, 3331646268016923629, n))stdout.flush()
ctr = 0def oracle(c, i):    global ctr    if ctr > 10 * d_len // 9:        print("Come on, that was already way too generous...")        return    ctr += 1    rotor = lambda d, i: int(str(d)[i % d_len:] + str(d)[:i % d_len])    return int(pow(c, rotor(d, i), n))
banner = lambda: stdout.write("""Pelle's Rotor Supported Arithmetic Oracle1) Query the oracle with a ciphertext and rotation value.2) Exit.""")
banner()stdout.flush()
choices = {    1: oracle,    2: exit}
while True:    try:        choice = stdin.readline()        print("c:")        stdout.flush()        cipher = stdin.readline()        print("rot:")        stdout.flush()        rotation = stdin.readline()        print(choices.get(int(choice))(int(cipher), int(rotation)))        stdout.flush()    except Exception as e:        stdout.write("%s\n" % e)        stdout.flush()        exit()
```
## TL;TR;
Encrypting at least 2 sets of messages: $m_3 = m_2\ m_1$, we can find $N$: `k*N = gcd(c1_1*c1_2-c1_3, c2_1*c2_2-c2_3)`, and get ride of `k` by dividing the result by small primes.Having $N$ we retrive $d$ digit by digit:$$ msg^{10\ d_r} = \frac{ c_{i+1}+kN}{msg^{digit}} $$$$ c_i^{10} = msg^{digit\ 10^{digitCount}}\ msg^{10\ d_r} $$
## Solution
I solved this challenge after the CTF.
The script allows us the opportunity to encrypt our messages using d, the modular multiplicative inverse of e. We can encrypt more times than d has digits. This gives us a spare to calculate N. 
How to find N?$$ c_1\ c_2 = m_1^d\ m_2^d = (m_1\ m_2)^d = c_3 $$For modulo operation:$$ (m_1^d)\ mod\ N\ (m_2^d)\ mod\ N = (m_1\ m_2)^d\ mod\ N + kN $$$$ c_1\ c_2 - c_3 =  kN $$
If we choose good messages so that $c_1\ c_2 > N$.Prepare 2 or 3 sets of messages. Using `gcd(k1*N, k2*N)` we should get N. But sometimes `gcd` still returns muiltiple of N. For assurance, one may try to divide it by small primes.
So we have N.
Next d.
"Size" (number of digits) of $d$ cannot be greater than the number of digits of N. We can send the same message to encryption with i = [0... digits count for N] and compare results. When it will be equal to cipher for i=0. And we have the "size" of $d$.
Next, what are adjacent ciphers look like:
$$ d_{i} = digit\ 10^{digitCount-1} + d_r$$$$ d_{i+1} = 10\ d_r + digit $$$$ c_{i} = msg^{d_{i}} = msg^{digit\ 10^{digitCount-1}}\ msg^{d_r} $$$$ c_{i+1} = msg^{d_{i+1}} = msg^{10\ d_r}\ msg^{digit} $$$msg^{digit}$ for small msg is so small that iterating we can find $k$ that would fullfill condition:$$ c_{i+1} + kN\ mod\ msg^{digit} == 0 $$and next:$$ msg^{10\ d_r} = \frac{ c_{i+1}+kN}{msg^{digit}} $$Using $c_1$ to 10th power (**all modulo N**) we can compare cipher with out calculation for choosen $digit$:$$ c_i^{10} = msg^{digit\ 10^{digitCount}}\ msg^{10\ d_r} $$
So I check all digits, which one meets the condition.
Havind $d$ we can calculate $\phi = d\ e-1$ and retrive the flag:
```fi = e*d-1D = pow(flag_power, -1, fi)M = pow(flag_cipher, D, N)print(f"{long_to_bytes(M)}")```
[sol.py](https://github.com/death-of-rats/CTF/blob/master/2022/midnightsun/pelle-rotor/sol.py)