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):

This sage script prints the flag:

$ ./pwn.sage