RSA and Big Integer Calculations of Exponents

Question

I am learning about the RSA algorithm. I perform the algorithm on very small prime numbers and use online Big Integer calculators to perform the encryption and decryption and everything works just fine.

My question is about the size of the exponent we create and when it comes to bigger numbers, it seems infeasible to calculate.

For example, the algorithm starts with picking two prime numbers p and q. You compute n=pxq and then the totient of n. Next you pick a number 'e' such that 1

Then to perform an encryption you take say like the ASCII character 'A' which is 65 and you raise it to the power of e. (65^e)

The online big integer calculator started getting very slow and sluggish (over a minute to calculate) when e was bigger than about 100,000 (6 digits)

My question is then, for the working RSA algorithm, what size (number of digits) number does that algorithm pick?

One thought I had was it was possible the online calculator that I was using was not using the best method for exponents? This is the calculator I am using: http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm

Answer 1

Two optimizations speed up the process:

First, when you compute $m^e \bmod n$ you don't do it by computing $m^e$ then reducing it $\bmod n$. You do it by reducing $\bmod n$ after each multiplication in the computation of $m^e$.

Second, you don't work your way up from $m$ to $m^e$ by stepping through all the powers of $m$. You compute $m^2$ with one multiplication, then $m^4 = m^2 m^2$ with another multiplication, then $m^8 = m^4 m^4$, and so on, reaching $m^{2^k}$ after $k$ steps. Using the binary representation of $e$, you select a subset of $\{m, m^2, ..., m^{2^k}\}$ whose product is $m^e$. This is called the "square and multiply" method.

Every intermediate result in the computation is immediately reduced modulo $n$, and the only operation you perform is multiplication, so you never see a number bigger than $n^2$, which is way smaller than the unreduced $m^e$ when the numbers are of the size needed for practical cryptography.

Some programming languages contain a "modular exponentiation" function which takes the 3 arguments $m$, $e$, and $n$ and returns $m^e \bmod n$ using the above method. When working with a lower-level language that doesn't include it, you will write it first. (It's not hard if you already have the big integer multiplication taken care of.) Since I see this question originated on the mathematica site, here's the function in mathematica: PowerMod

I don't see a modexp button on your javascript calculator, so it's really not the right tool to use here (unless you want to work your way through the square and multiply method by hand - maybe that's good to do once to get the idea burned into your brain, but after that it'll be boring)

Answer 2

The online calculator is quite slow. I just typed $65^{65537}$ into Alpha and it calculated all $118813$ digits very quickly. That is the most common exponent used in RSA. In usual RSA you would do it modulo $n$ and only need about $1000$ decimal digits. RSA doesn't have to be fast. It is known to be a slow encryption algorithm, so is usually used to exchange the key for a faster one. You then use the faster one to encrypt the long message.