Maojui

## 0CTF 2019 - Baby RSA (Crypto, 74)

2019-03-30

### Challenge

file : flag.enc, pubkey.py, rsa.sage

### Some Facts and Definitions From Algebra

• Every polynomial $f(x)$ with coefficients in $GF(2)$ having $f(0) = 1$ divides $xm + 1$ for some $m$.
$\Rightarrow$ The smallest $m$ for which this is true is called the period of $f(x)$
• An irreducible (can not be factored) polynomial of degree $n$ has a period which divides $2^{n} - 1$.
• An irreducible polynomial of degree $n$ whose period is $2^{n} - 1$ is called a primitive polynomial.

### Solution

1. factor(n) to get p,q

2. calculate two period : $2^{\ p.degree()}-1$, $2^{\ q.degree()}-1$

3. The product of two period is multiple of phi.

4. calculate d : inverse_mod(e,phi)

5. recover m_poly : pow(c_poly, d, n)

solve.sage