“Go” and do it the Montgomery Reduction Way!

Prof Bill Buchanan OBE

Jul 26, 2019·2 min read

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.