Why is M^e mod N the ciphertext and not just M^e

Question

I watched a video on why the RSA algorithm works and it said that $(M^e \bmod N)^d \mod N = M^{ed} \bmod N$ which makes sense if $M^e$ is smaller than $N$.

Would $M^e$ not be smaller than $N$, the decryption wouldn't work(I know why but there's no reason to explain it here).

So why do we say that the ciphertext is $M^e \bmod N$ when $\bmod N$ falls away anyway.

And I've also seen examples where $M^e$ is way bigger than $N$ which leads me to believe that I misunderstood something.

Can someone help me out here?

Answer 1

If the ciphertext was just M^e, then

• The ciphertext would be much longer (e times more bits)
• Anyone with the public key could decrypt the message by calculating the e-th root, for example using the bisection method.

Answer 2

Suppose that $N = 11$, $M = 10$, and $e = 2$. You can see clearly that $M^e > N$.

What does hold is that $(x \bmod N)^d \bmod N = x^d \bmod N$. This follows from the more general $(x \bmod N)(y \bmod N) \bmod N = xy \bmod N$, which you can try proving from the definitions.

Answer 3

First of all, an encryption scheme must have the correctness requirement $$Dec_k (Enc_k (m)) = m$$ In other words, whatever data you encrypted, you must get it back after the decryption. Otherwise, there is no use.

---

In RSA, we have the relation between public exponent $e$ and private exponent $d$ $$e \cdot d = 1 \bmod \varphi(N)$$ where $\varphi(N)= (p-1)(q-1)$, with $\varphi(N)$ is the Euler's Toitent function.

From Euler theorem we know that $a^x = x^{x \bmod \phi(n)} \bmod N$. This help to calculate the power faster $$M^{ed} \bmod N \equiv M^{ed \bmod \varphi(N)} \bmod N$$

$(M^e \bmod N)^d \bmod N = M^{ed} \bmod N $

To see this, we can use the modulus property $a \equiv b \bmod n$ then there is $k \in \mathbb{Z}$ such that $ a = b + nk$.

With $M^e = t \bmod N$ we have $M^e - N\cdot k = t$ and then with $(M^e - N\cdot k)^d \bmod N$. If we expand the power this simplifies $$M^{ed} \bmod N$$ since, except this term, all others will vanish as they contain at least one $N$.

So, we don't care it is small or not during the calculation, it satisfies the correctness requirement.

---

Note: For TextBook RSA the small $e$ can make big problems like in the case $e=3$ (enables fast encryption or signature verification), this is commonly known as the cube-root attack. In practice, however, the textbook RSA is not used. It must be used with proper encryption paddings like PKCS#1 v1.5 (RSAES-PKCS1-v1_5) or OAEP (RSAES-OAEP). With this padding, there is no problem with using small $e$'s like the common ones. $\{3, 5, 17, 257, 65537\}$. Similarly, for the RSA signature, we have RSASSA-PSS.