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?

  • 1
    $\begingroup$ "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. $\endgroup$
    – Tassle
    Jan 2 at 17:41
  • $\begingroup$ Let M be a 100 digit number, and e=17, then M^e has 1700 digits. $\endgroup$
    – gnasher729
    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.

  • $\begingroup$ When $e=2$ the RSA turns into Rabin encryption where the description doesn't satisfy the correctness requirement immediately. $\endgroup$
    – kelalaka
    Jan 2 at 18:39
  • 2
    $\begingroup$ Well, this is really beside the point here. $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.