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]:

package main

import (
"fmt"
"math/big"
"os"
"strconv"
)

// == From https://rosettacode.org/wiki/Montgomery_reduction#Go
type mont struct {
n uint // m.BitLen()
m *big.Int // modulus, must be odd
r2 *big.Int // (1<<2n) mod m
}
func newMont(m *big.Int) *mont {
if m.Bit(0) != 1 {
return nil
}
n := uint(m.BitLen())
x := big.NewInt(1)
x.Sub(x.Lsh(x, n), m)
return &mont{n, new(big.Int).Set(m), x.Mod(x.Mul(x, x), m)}
}
func (m mont) reduce(t *big.Int) *big.Int {
a := new(big.Int).Set(t)
for i := uint(0); i < m.n; i++ {
if a.Bit(0) == 1 {
a.Add(a, m.m)
}
a.Rsh(a, 1)
}
if a.Cmp(m.m) >= 0 {
a.Sub(a, m.m)
}
return a
}
// ==
func main() { p:=13
a:=5
b:=6
argCount := len(os.Args[1:]) if (argCount>0) {a,_= strconv.Atoi(os.Args[1])}
if (argCount>1) {b,_= strconv.Atoi(os.Args[2])}
if (argCount>2) {p,_= strconv.Atoi(os.Args[3])}
m := big.NewInt(int64(p)) fmt.Printf("a=%d, b=%d, p=%d\n\n",a,b,p)

mr := newMont(m)

x1 := big.NewInt(int64(a))
x2 := big.NewInt(int64(b))

t1 := mr.reduce(new(big.Int).Mul(x1, mr.r2))
t2 := mr.reduce(new(big.Int).Mul(x2, mr.r2))
res := mr.reduce(new(big.Int).Mul(t1, t2))
fmt.Printf("Result: %s*%s (mod %s) = %s\n",x1,x2,m,mr.reduce(res)) mul:=new(big.Int).Mul(x1, x2)
fmt.Printf("Traditional method result = %s\n\n",mul.Mod(mul,m))
prod := mr.reduce(mr.r2)
base := mr.reduce(new(big.Int).Mul(x1, mr.r2))
exp := new(big.Int).Set(x2)
for exp.BitLen() > 0 {
if exp.Bit(0) == 1 {
prod = mr.reduce(prod.Mul(prod, base))
}
exp.Rsh(exp, 1)
base = mr.reduce(base.Mul(base, base))
}
fmt.Printf("\nResult: %s^%s (mod %s) = %s\n",x1,x2,m,mr.reduce(prod)) fmt.Printf("Traditional method result = %s",new(big.Int).Exp(x1, x2, m))

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.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade