Why does RSA need two prime numbers?

Question

I'm having a hard time understanding the purpose of having two primes $p,q$ for RSA to work. To illustrate my point, imagine only one prime ($p$) is used.

Alice, the encryptor, can take the public encryption exponent $e$, which Bob, the decryptor, created (along with the private exponent $d$) to satisfy $$ed\equiv 1\pmod{p-1}$$ Alice then encrypts $M$, sending $C=M^e$ (the full value without a modulus) to Bob.

Bob receives $C$ and retrieves the message: $$C^d\pmod p$$ $$=M^{ed}\pmod p$$ $$=M^{(p-1)k+1}\pmod p$$ $$=M\pmod p$$ $$\text{(by Fermat's Little Theorem)}$$ Assuming an attacker cannot guess $p$ from $e$, this should be secure. Instead, RSA creates exponents according to $$ed\equiv 1\pmod{(p-1)(q-1)}$$ and decrypts with $$C^d\pmod p$$ $$=M^{(p-1)(q-1)k+1}\pmod p$$ $$=M\pmod p$$ $$=M\pmod q$$ $$=M\pmod {pq}$$ From this, it seems that the only benefit of using two primes is so that Alice can take a take a modulus before sending the ciphertext. If only one prime is used, Alice could send the ciphertext $\mod p$ and preserve correctness, but then she could use $p$ to derive $d$, whereas in the two prime version, she can still take a $\mod n$ without knowing $p$ or $q$. I suspect modular exponentiation is much cheaper computationally that regular exponentiation, and that perhaps that is why two primes are used in practice. Is this the only reason? And if so why is the concept of factoring a semi-prime number so central to the idea of RSA?

Answer 1

"I suspect modular exponentiation is much cheaper computationally that regular exponentiation, and that perhaps that is why two primes are used in practice."

Yes, modular exponentiation is much faster.

How much do you think a number expands if you perform non-modular exponentiation?

And what's keeping an adversary from just trying all possible inputs, and encrypt them to see which one matches?

You can of course random pad $M$ with e.g. 128 random bits, but then your input will grow even larger, the exponentiation slower and the result even larger.

---

But most importantly, what's hard about calculating $\sqrt[e]C=\sqrt[e]{M^e}=M$ if $e$ is known? I don't think that that's a hard problem even if $e$ is very large. For a large $e$ the calculation really becomes problematic because the result size would be humongous anyway.

Of course, your encryption function needs to be irreversible without the private key value - in this case $d$ - and it isn't.