Eazy RSA was an RSA challenge that I, with my limited crypto knowledge, found quite hard to finally grasp. Despite all this, it's extremely satisfying.
All we get is the values of $c$, $e$, $p$ and $q$. You may be tempted to think it's simple RSA decryption:
phi = (p-1) * (q-1)
d = pow(e, -1, phi)
m = pow(ct, d, n)
print(long_to_bytes(m))
But that yielded gibberish. Why?
The problem here is that $e=16$, meaning that the totient of $N$ and $e$ is not coprime, i.e. $$$gcd(\phi (N), e) \ne 1$ and as a result this meant that you cannot uniquely decrypt the message. Consider the following example (from the above link):
Let us say that $N=65,\,e=3$. Therefore $\phi(N)=(p-1)(q-1)=4 \cdot 12=48$. We then notice that $gcd(48, 3)=3 \ne 1$ and therefore they are not coprime.
With this, we can notice that two plaintexts yield the same ciphertext:
$$ 2^3=8 \mod 65 \\ 57^3=8 \mod 65 $$
Thus by reversing it, we have no way of knowing the original $c$.
So what could we possibly do now? After all, there's no possible way to calculate it, right?
You may have noticed that $e=16=2^4$, and while rooting to obscure powers is not possible, there are well-established algorithms for calculating the square root $mod$ an integer. If we can do that four times, we will eventually arrive at the plaintext $M$. Our main problem, therefore, is calculating all possible roots. Let's recap how square rooting works in modular arithmetic.
We'll first start by square rooting $mod \,p$, where $p$ is prime. This is the simplest scenario, and we will build on from here.
If $p \equiv 3 \mod 4$ then the square root $x$ of $a$ can be calculated thus:
$$ x \equiv a^{\frac{p+1}{4}} \mod p $$