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 % NDo 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.
