How to implement c=m^e mod n for enormous numbers?

Question

Hi,

I'm trying to figure out how to implement RSA crypto from scratch (just for the intellectual exercise), and i'm stuck on this point:

For encryption, c = m^e mod n

Now, e is normally 65537. m and n are 1024-bit integers (eg 128-byte arrays). This is obviously too big for standard methods. How would you implement this?

I've been reading a bit about exponentiation here but it just isn't clicking for me:

http://en.wikipedia.org/wiki/Exponentiation_by_squaring

http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf (see section 14.85)

Thanks.

edit: Also found this - is this more what i should be looking at? http://en.wikipedia.org/wiki/Modular_exponentiation

Answer 1

Exponentiation by squaring:

Let's take an example. You want to find 17²³. Note that 23 is 10111 in binary. Let's try to build it up from left to right.

           // a      exponent in binary

a = 17     //17^1          1

a = a * a  //17^2         10

a = a * a  //17^4        100
a = a * 17 //17^5        101

a = a * a  //17^10      1010
a = a * 17 //17^11      1011

a = a * a  //17^22     10110
a = a * 17 //17^23     10111

When you square, you double the exponent (shift left by 1 bit). When you multiply by m, you add 1 to the exponent.

If you want to reduce modulo n, you can do it after each multiplication (rather than leaving it to the end, which would make the numbers get very large).

65537 is 10000000000000001 in binary which makes all of this pretty easy. It's basically

a = m
repeat 16 times:
    a = a * a
    a = a mod n
a = a * m
a = a mod n

where of course a, n and m are "big integers". a needs to be at least 2048 bits as it can get as large as (n-1)².

Answer 2

If g(x) = x mod 2^k is faster to calculate for your bignum library than f(x) = x mod N for N not divisible by 2, then consider using Montgomery multiplication. When used with modular exponentiation, it avoids having to calculate modulo N at each step, you just need to do the "Montgomeryization" / "un-Montgomeryization" at the beginning and end.