As per wikipedia
$$c = m^e \bmod n$$
where $c$ is the cipher text and $m$ is the original message.

To decrypt $$m = (c^d) \bmod n$$ that is $$m = (m^e \bmod n)^d \bmod n$$

My question is how do we have the following equivalence? $$(m^e \bmod n)^d \bmod n \equiv (m^e)^d \pmod n$$


The maths is fairly straightforward.

Replace $m^e$ with $a + bn$, where $a = m^e \bmod n$, and $b$ is an integer (equal to $\lfloor m^e / n \rfloor$).

The binomial expansion of $(m^e)^d$ can then be substituted with the expansion of $(a + bn)^d$ as follows:

$$(a + bn)^d = a^d + c_1a^{d-1}.bn + c_2a^{d-2}.b^2n^2 + \cdots + b^dn^d$$

where $c_1$, $c_2$ etc. are binomial coefficients.

Apart from the first term $a^d$, every term in this expansion is a multiple of $n$ and is therefore equal to zero (mod $n$).

Hence, $(m^e)^d \bmod n \equiv a^d \bmod n \equiv (m^e \bmod n)^d \bmod n$

  • $\begingroup$ Could you also explain how $(m^e)^d$ modn ≡ m mod n $\endgroup$ – Pushparaj Oct 10 '17 at 9:22
  • $\begingroup$ @Pushparaj please read the Handbook of Applied Cryptography. You will find your answer section 8.3 page 5 here $\endgroup$ – Biv Oct 10 '17 at 10:03

Well, in simpler terms, whenever you have two numbers, which can be expressed in an exponential form (with same base), the modular operation (using same number) will not alter the result. As a simple example, consider the below -

$$b ^ e (mod\quad m) = 2 ^ 3 (mod\quad 3) = 2 ^ 5 (mod\quad 3) = 2 \tag{1}$$

To generalize, irrespective of the value of exponential 'e' (where e$ \ge$0, ignoring modular multiplicative inverse for timebeing), as long as the base (b) remains same, the modular operation (mod n) will not vary the final result. This fundamentally is the result of the cyclic property of the modular operation.

By the same notion, the divide and conquer property works as below -

$2 ^ 8 (mod\quad 3) = [2 ^ 3 (mod\quad 3)\quad * \quad2 ^ 5 (mod\quad 3)] \quad(mod 3) = 1 \tag{2}$

Note: The additional 'mod 3' at the tail of equation (2) confines the result to not exceed the modulus value, i.e. 3

Now, let's look at another property of the modulus operation:

$b ^ e (mod\quad m)$ = $b ^ e (mod\quad m)$* $(mod\quad m)$.......* $(mod\quad m)$ $\tag{3}$ So modulus operation applied multiple times again on the result of an earlier modulus operation, will still give the same result.

Now let's look at equation under consideration,

$(m^e\quad mod\quad n)^d\quad mod\quad n$ ≡ $(m^e)^d$($mod$ $n$)

The above should be self-explanatory based on the properties of modulus that we had a look at above.

  • $\begingroup$ I like the sample. $\endgroup$ – bhathiya-perera Mar 15 '18 at 10:45
  • $\begingroup$ The notation $a\pmod m=b\pmod m$ is non-standard. The appropriate one is $a\bmod m=b\bmod m$ (where $\bmod\ $ is an operator), or $a\equiv b\pmod m$ (which means that $m$ divides $b-a$). $\endgroup$ – fgrieu Mar 19 '18 at 19:10
  • $\begingroup$ Further, the statement than in $b^e\pmod n$ [or is it $b^e\bmod n$, that does not matter], "irrespective of the value of exponential $e$ (where $e\ge0$, ignoring modular multiplicative inverse for timebeing), as long as the base ($b$) remains same, the modular operation $\pmod n$ will not vary the final result" is plain wrong. Counterexample: $b=2$, $e=1$ and $e'=2$, any $n>2$ including $n=5$. $\endgroup$ – fgrieu Mar 20 '18 at 8:20

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.