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 $\phi (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 $\phi (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^{\mathrm{deg}g}}$ and similarly ${\mathbb{F}}_2[x]/h\cong {\mathbb{F}}_{2^{\mathrm{deg}h}}$, we know that $$|({\mathbb{F}}_2[x]/f{)}^{\ast }|=(2^{\mathrm{deg}g}-1)(2^{\mathrm{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~~~~~~}
$