The challenge is a simple "mail encryption" service written in Javascript and Python. Encryption, decryption and key generation (if a user-supplied key isn't used) happen on the client-side in Javascript.

## First Flag

The first fishy thing when looking at the client-side code is the key generation:

```js
onmessage = (msg) => {
let [user, randbytes] = msg.data;

let p = nextprime(new BigInteger(randbytes, 16));
let q = p;
while (true) {
p = q;
q = nextprime(q.add(BigInteger.ONE))
let phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
let n = p.multiply(q);

let e = nbv(3);
let d = e.modInverse(phi);
if (d.equals(BigInteger.ZERO)) {
continue;
}

postMessage([user, n.toString(16), e.toString(16), d.toString(16)]);
break;
}

}
```

While the `isprime()` (not shown here) check is itself also not good (it just does one [Fermat primality test](https://en.wikipedia.org/wiki/Fermat_primality_test) to base 5 and thus is vulnerable to Fermat pseudoprimes), this should not matter greatly when really given random numbers, as those pseudoprimes are somewhat rare. Much more concerning is the way that `p` and `q` are generated themselves: `p` is the next prime after the integer given by `randbytes` - but then `q` is just simply taken to be `nextprime(p)` (unless this leads to a non-invertible value of `e`, in which case the `nextprime` call is interated).

This means in practice that `p` and `q` tend to be very close (with a differnence of maybe a few hundred). This makes the key very fulnerable to [Fermat factorization](https://en.wikipedia.org/wiki/Fermat's_factorization_method):
Let $u := (q-p)/2$ (we always have $q>p$ by the convention of the code) and $v := (p+q)/2$. Then
$$N = p\cdot q = p\cdot (p+2u) = (v+u)\cdot (v-u) = v^2-u^2$$
or $N+u^2 = v^2$.

Thus, if we just guess the very small value $u$, we can recover $v$ as $\sqrt{N+u^2}$ (which will be integral if and only if our guess was right - $v$ is always an integer as $p$ and $q$ are both odd). Subsequently, we can simply recover $p$ and $q$ as $p=v-u$ and $q=v+u$. At this point, we have successfully factored the RSA key and are able to easily recover the secret key $d$ and decrypt all emails for the user:

```python3
import math
import requests
user = ...
HOST = ...
def is_square(a):
return math.isqrt(a)**2 == a
pubkey = requests.get("http://["+HOST+"]:5555/pubkey/"+user).json()
n = int(pubkey[0],16)
e = int(pubkey[1],16)
for u in range(10000):
if is_square(n+u**2):
v = math.isqrt(n+v**2)
p = v-u
q = v+u
assert p*q==n
break
else:
print("Could not factor")
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
inbox = requests.get("http://["+HOST+"]:5555/inbox/"+user).text
inbox = json.loads(inbox)
for msg in inbox:
msg = int(msg,16)
msg = pow(msg,d,n)
print(msg.to_bytes(msg.bit_length()//8+2,"big").decode(errors="ignore"),flush=True)
```

This method works for all e-mails sent to users who don't supply their own keys and rely on the built-in key generation.

### Patch

The patch is somewhat simple (although hampered by Javascripts lackluster APIs for generating randomness): Simply generate $q$ independently from $p$.

## Second Flag

There were some additional users generated by the gameserver which did supply their own keys, rendering the first attack useless. However, there were also some flag IDs that were different: instead of a single number describing the single receipient of the email, those have a comma-seperated list with a list of receipients.

For these flags, a second fact became relevant: The user-supplied keys - much like the generated ones - all used the public exponent $e=3$. If the same message (without any padding) is then sent to at least $e=3$ users, this is a classic case of [Håstad's broadcast attack](https://en.wikipedia.org/wiki/Coppersmith%27s_attack#H%C3%A5stad's_broadcast_attack):

Let $N_1, N_2, N_3$ be the public moduli of three of the users, and let $c_1, c_2, c_3$ be the corresponding ciphertexts. As the public exponent $e$ is $3$ for all users, it follows that, for the plaintext message $m$, we have:
$$c_1 \equiv m^3 \bmod N_1$$
$$c_2 \equiv m^3 \bmod N_2$$
$$c_3 \equiv m^3 \bmod N_3$$
It is safe to assume that $N_1, N_2, N_3$ are pairwise co-prime, as for proper key generation the chance of sharing a prime factor would be negligible (and that case disasterous anyway). Therefore, the [Chinese remainder theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem) lets us compute an integer $C$ (more precisely, a residue class modulo $N_1\cdot N_2\cdot N_3$ - this lets us assume that $0\leq C