Challenge

1

RSA challs are always easy, right? Even if N is not a integer.

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)

flag{P1ea5e_k33p_N_as_A_inTegeR~~~~~~}

solve.sage