# Perfect SecrecyWe are given a ciphertext `c` in `flag.txt`, a public key with `N` and `e` in `key_pub.pem`.
We can also send a cipher to a server, and it will send back some zero and one-bytes.
The goal is to find `m` such that `m**e % N == c`, i.e., finding the RSA-message.
Inspecting `challenge.py` - what the server does.
It receives two bytes `m0` and `m1`. Then it decrypts (raises to the power of the secret value `d` mod `N`) the next key-size bits we send, and stores it in the variable `dice`.
Then follows this suspiciously looking code:
```pythonfor rounds in range(100):  p = [m0, m1][dice & 1]  k = random.randint(0, 2)  c = (ord(p) + k) % 2  writer.write(bytes((c,)))```
`random.randint(a, b)` generates a uniformly random rumber in the range `[a, b]`, mening that we have probablility `1/3` for each outcome of `k` being `0`, `1` or `2`. `c` will therefore with probability `2/3` be `ord(p)%2`, and with probability `1/3` be `(ord(p)+1)%2`. We therefore expect about 67 of the bytes to be `ord(p)` and 33 to be the other.
We can either calculate the probability of receiving more `(ord(p)+1)%2`-bytes of the `100` bytes sent to us. Or we can experimentally check what we get by letting the server decrypt `1`, which we know will become `1`, and verify that we always get more `m1` than `m0` back, if we let `m0, m1 = '\x00', '\x01'`.
We can hence get the lsb of `c**d` for any `c` by asking the server - we call this function `lsb_cd(c)`. 
```python def lsb_cd(c):    if c in stored:        return stored[c]    back = [0, 0]    r = remote('perfect-secrecy.ctfcompetition.com', '1337')    payload = '\x00\x01' + enc(c) # enc - encodes c to ascii and pads with zerobytes.    r.send(payload)    data = r.recvn(100)    r.close()    for ch in data:        back[ord(ch)] += 1     ret = 0 if back[0] > back[1] else 1    stored[c] = ret    with open('cache', 'a') as f:        f.write('{} {}\n'.format(c, ret))    return ret```
We implemented a simple caching of the results, since the server responded very slowly.
## Reconstructing `m`
So we get the last bit of `m` by sending `c` to the server. Then we'd like to send a `c'` corresponding to `m>>1` to find the next bit. However, this `c'` is not so easy to find. What we can do is to muliply `c` with `inv(2)**e`, which is the `c''` corresponding to `m*inv(2)`. This is `m>>1` if `m` is even, however if `m` is odd, `m*inv(2) = (m+N)>>1`, but this is possible to find `m>>1` by subtracting `N`.
The inverse of `2` mod `N` can be found by the extended euclidean algorithm, given that `gcd(2, N) == 1`, which is true when `N` is used for RSA encryption. 
Consider a function `f(c, k)` that reconstructs the last `k` bits of `c**d`. 
Clearly `f(c, 1) = lsb_cd(c)`. 
If `lsb_cd(c) == 0`, then `f(c, k) = 2 * f(c*inv(2)**e, k-1)`, otherwise `f(c, k) + N%(2**(k+1)) = 2*f(c*inv(2)**e, k-1)`. 
This can be implemented in python in the followig way:
```pythondef f(c, k, N, inv):    if k == 1:        b = lsb_cd(c)         return b    a = f((c*inv)%N, k-1, N, inv)    b = lsb_cd(c)     if b == 0:        return 2*a    else:        lo = 1<<(k+1)        return (2*a - N)%lo```
`m = f(c, key_size, N, inv(2)**e%N)`.
After about an hour of `1024` requests to the server and some restarts, we finally found `m` as an int.
## Extracting the flag.. ..can be done by converting the int to ascii, easiest done going via hex:
```pythondef int2ascii(v):    hx = hex(v)[2:].replace('L', '')    hx = '0' + hx if len(hx)%2 else hx    return hx.decode('hex')```
It turns out that the flag is padded with random bytes, but with those thrown away it's an Adele reference:
`CTF{h3ll0__17_5_m3_1_w45_w0nd3r1n6_1f_4f73r_4ll_7h353_y34r5_y0u_d_l1k3_70_m337}`
Rerunning the code is very fast by doing `python2 solve.py`, given that you have `pwntools` and the `cryptography` libraries installed. If you want to wait an hour for the server to respond instead you can remove the cache ;).