Montgomery Multiplication in RSA: c=m^e%n

Question

How does Montgomery Multiplication work in speeding up the encryption process for computing c=m^e%n as used in RSA encryption? I understand that Montgomery multiplication can efficiently multiply a*b%n but when trying to find m^e%n, is there a more efficient way of multiplying m*m e number of times than just looping through and computing a Montgomery multiplication each time?

mpz_class mod(mpz_class &m, mpz_class &exp, mpz_class &n) {
        //End goal is to return m^exp%n
//      cout << "Begin mod";
        mpz_class orig_m = m; //the original message
        mpz_class loc_m = m;  //local value of m (to be changed as you cycle through)
        cout << "m: " << m << " exp: " << exp << " n: " << n << endl;

        //Conversion to the montgomery world
        mpz_class mm_xp = (loc_m*r)%n;
        mpz_class mm_yp = (orig_m*r)%n;

        for(int i=0; i < exp-1; i++) //Repeat multiplaction "exp" number of times
        {
                 mm(mm_xp, mm_yp, n); //montgomery multiplication algorithm returns m*orig_m%n but in the montgomery world form
        }

        mm_xp = (mm_xp*r_p)%n; //convert from montgomery world to normal numbers
        return mm_xp;
}

I'm using the gmp libraries so I can work with larger numbers here. r and r_p are being pre-calculated in a separate function and are global. In this example I'm working in powers of 10 (though i realize it would be more efficient to work with powers of 2)

I convert to montgomery form prior the the multiplications and repeated multiply m*m in the for loop, converting back to normal world at the end of the m^e step. I'm curious as to know whether there is another way to compute operation m^e%n in a different way, rather than just cycling through in a for loop? As of now, i believe this to be the bottle neck of the computation however I could very well be wrong.

the actual montgomery multiplication step occurs in the function below.

void mm(mpz_class &ret, const mpz_class &y, const mpz_class &n)
{
        mpz_class a = ret*y;

        while(a%r != 0)
        {
                a += n;
        }
        ret = a/r; //ret*y%n in montgomery form
//      cout << ret << endl;
}

Is this at all how RSA encryption works with the montgomery multiplication optimization?

score 1 · Answer 1 · edited May 23 '17 at 12:31

No, you do not want to do e multiplications of m by itself to compute RSA.

You normally want to do m^e mod n by doing repeated squaring (there are other possibilities, but this is a simple one that's adequate for many typical purposes).

In a previous post on RSA, I included an implementation that used a pow_mod function. That, in turn, used a mul_mod function. Montgomery multiplication is (basically) an implementation of that mul_mod function that's better suited to working with large numbers. To make it useful, however, you just about need something on at least the general order of the pow_mod function, not just a loop to make e calls to mul_mod.

Given the magnitude of numbers involved in real use of RSA, trying to compute m^e mod n just using repeated multiplication would probably take years (quite possibly quite a few years) to complete even a single encryption. In other words, a different algorithm isn't just a nice optimization--it's absolutely necessary for use to be practical at all.

To put this in algorithmic terms, raising A^B using plain multiplication is basically O(B). Doing it with the repeated squaring algorithm shown there, it's basically O(log B) instead. If B is very large at all, the difference between the two is immense.

Montgomery Multiplication in RSA: c=m^e%n

1 Answers1