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

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.

Link to original

But this plaintext has been padded - didn’t I say the attack only applies to unpadded RSA? This is true for the most part, with the caveat of simple padding schemes (e.g. for $m$ slightly wider than $n^{\frac{1}{e}}$¹). Under such a padding scheme, 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 ↩