# 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.

With the RSA and the Diffie-Hellman method we perform large exponential calculations, such as:

*C*=*M^e *(mod *N*)

and where we will continually multiply large integers by an exponent to get a result. If we were to just calculate *x^y *and then take (mod *N*) it would take a while to produce the result (possibly minutes for large numbers). Thus we use **Montgomery modular multiplication**, and which significantly reduces the time to compute the result. In a traditional multiplication of two value (*x* and *y*) for a modulus of *N*, we multiply *x* times *y* and then divide by *N* to find the remainder. The number of bits in the multiplication with this be the number of bits in *x* added to the number of bits in *y*. In Montgomery reduction we add multiples of *N *in order to simplify the multiplication.

An example of this is here, and a sample run for *x*=10, *y*=5 and *N*=29 is [here]:

a=10, b=5, p=29Result: 10*5 (mod 29) = 21

Traditional method result = 21

Result: 10^5 (mod 29) = 8

Traditional method result = 8

In this case we get 50 (mod 29) which is 21, and 105 (mod 29) which is 8.

The sample code is [here]:

## Conclusions

And there you go. If you are into Python, don’t do this:

`C = m**e % N`

Do this:

`C = pow(m,e,N)`

and it will use the Montgomery method. In this article I’ve used Go, and you can see how I use big.Int. In Python, we automatically cast to Big Ints, when we need them.