picoCTF 2021: Mini RSA

Problem

Solution

In my writeup for the 2019 edition of this question, I explained the bare necessities of RSA required to solve that problem. The same background is applicable here:

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.

Link to original

But this plaintext has been padded! It’s not quite textbook RSA! Therefore this shouldn’t work!

This, however, is a simple padding scheme, so the same principles should apply given $m$ is only slightly wider than $n^{\frac{1}{e}}$¹. We may enumerate different amounts of padding until we find the correct amount.

Script

from gmpy2 import iroot  
  
  
with open("ciphertext", "r") as f:  
	n, e, space, c = f.readlines()  
	n = int(n[3:])  
	e = int(e[3:])
	c = int(c[16:])  
  
  
for i in range(4096):
	# Pad by a multiple of `n`
	padded, is_exact = iroot(c + (i * n), e)  
	
	if is_exact and pow(padded, e, n) == c:
		print(padded.to_bytes(256, "big").decode("utf-8").strip("\x00").strip())
		break

Footnotes

1. https://crypto.stackexchange.com/questions/6770/cracking-an-rsa-with-no-padding-and-very-small-e/6771#6771 ↩