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

See rsa for a primer

1. Low Public Exponent

For small $e$, the plaintext is trivially recovered by computing the $e$th root of $c$ like as $c^{\frac{1}{e}}=(m^e{)}^{\frac{1}{e}}=m$.

Link to original

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