Wed, 27 March 2019 ~ yyyyyyy

## 0CTF Quals 2019: "babyrsa" writeup

This challenge is about a variant of RSA encryption where the integers are replaced by a polynomial ring over $\mathbb F_2$.

Recall that RSA works in a ring $\mathbb Z/n$ where $n=pq$ is a product of two large random primes. To break RSA, it is sufficient to compute the size $\varphi(n)$ of the unit group $(\mathbb Z/n)^\ast$ since this allows one to compute $e$th roots in that group. The owner of the private key can compute $\varphi(n)$ as $(p-1)(q-1)$; without knowing $p$ and $q$ this problem is assumed to be hard.

In this challenge, $\mathbb Z$ is replaced by $\mathbb F_2[x]$ and $n$ is replaced by a big polynomial $f\in\mathbb F_2[x]$ of degree $2049$.

The crucial observation now is that **factoring polynomials over finite fields is easy**, hence we can split $f$ into its two irreducible factors $g,h\in\mathbb F_2[x]$ and by CRT there exists a ring isomorphism
\[
\mathbb F_2[x]/f \;\cong\; \mathbb F_2[x]/g \times \mathbb F_2[x]/h
\,\text.
\]

Now since $\mathbb F_2[x]/g\cong \mathbb F_{2^{\deg g}}$ and similarly $\mathbb F_2[x]/h\cong \mathbb F_{2^{\deg h}}$, we know that
\[
\lvert(\mathbb F_2[x]/f)^\ast\rvert = (2^{\deg g}-1)(2^{\deg h}-1)
\,\text.
\]
Therefore, we can compute $e$th roots in $(\mathbb F_2[x]/f)^\ast$, which breaks `babyrsa`

:

```
#!/usr/bin/env sage
import re
from pubkey import P,n,e
R.<a> = GF(2**2049)
c_int = Integer(open('flag.enc','rb').read().encode('hex'), 16)
c_poly = P(R.fetch_int(c_int))
(g,_), (h,_) = factor(n)
phi = (2**g.degree() - 1) * (2**h.degree() - 1)
d = ZZ(Mod(e,phi)**-1)
m_poly = pow(c_poly, d, n)
m_int = R(m_poly).integer_representation()
m = format(m_int, '0256x').decode('hex')
for flag in re.findall(b'flag{[^}]+}', m):
print(flag)
```

This `sage`

script prints the flag:

```
$ ./pwn.sage
flag{P1ea5e_k33p_N_as_A_inTegeR~~~~~~}
$
```