Never Use (M**e) for Ciphers

“Go” and do it the Montgomery Reduction Way!

Our world of public key cryptographic is build within finite fields. We take a prime number N, and then all our operations are done with (mod N). The basic security of our systems are then determine by the number of bits in N. If N has 1,024 bits or more, we are normally fairly secure. Many of our operations are then done with multiplication or with exponential, such as:

Cipher = M^e (mod N)

or with:

Cipher = ab (mod N)

In our labs I see quite a quite few students then doing this:

Cipher = (M**e % N)

And while it will work with relatively small values, it will never work in production, as the calculation of M^e will take a long time. For example, let’s take an e value of 65,637 (the most common value for e in RSA is 65,537), and M as 11, and see the size of the number we produce:

And so if we do M^e and then (mod N) it is going to be rather inefficient.