Maojui

0CTF 2019 - Baby RSA (Crypto, 74)

2019-03-30

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