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

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?

• "I know why but theres no reason to explain it here" I think there is, as this is where your mistake seems to lie. Look up the small Fermat theorem. Jan 2 at 17:41
• Let M be a 100 digit number, and e=17, then M^e has 1700 digits. Jan 12 at 7:39

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.

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.

• When $e=2$ the RSA turns into Rabin encryption where the description doesn't satisfy the correctness requirement immediately. Jan 2 at 18:39
• Well, this is really beside the point here. Jan 2 at 18:40

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.