picoCTF 2019: miniRSA

Problem

Solution

Here we have some ciphertext encrypted using (presumably) textbook RSA. It is implied that a low public exponent e was used, which we can exploit to recover the flag. The solution is quite simple, but I’ll first provide some background that will help makes sense of it.

Background

Note

The following only applies to unpadded (i.e. textbook) RSA

Textbook RSA is defined as follows: $c=RS{A}_{n,e}(m)\equiv m^e(\mathrm{mod}n)$ where $n$ is the modulus, $e$ is the public key, and $m$ is the message. If $m^e<n$, then $c=m^e$ (i.e. the modulus doesn’t work its magic) and $m$ can be recovered by computing the $e$th root of $c$ since $c^{\frac{1}{e}}=(m^e{)}^{\frac{1}{e}}=m$.

Computing such a value requires high-precision arithmetic since $c$ is a massive integer. The Python module gmpy2 is great for such circumstances, providing the iroot function for computing the $n$th root of an integer without truncation or rounding.

Script

from gmpy2 import iroot  
  
  
with open("ciphertext", "r") as f:  
	space1, n, e, space2, c = f.readlines()  
	n = int(n[3:])  
	e = int(e[3:])  
	c = int(c[16:])
  
  
m, is_exact = iroot(c, e)  
if is_exact and pow(m, e, n) == c:  
	print(m.to_bytes(256, "big").decode("utf-8").strip("\x00").strip())