How does RSA compute such enormous numbers?

Question

So I have been reading and learning a lot about cryptography lately and in particular asymmetric ciphers such as RSA.

One thing that I am curious about but never seems to be mentioned is how the cipher algorithm manages to compute such enormous numbers in reasonable amounts of time.

This example shows what I mean. Such enormous numbers, and powers of enormous numbers no less. What kind of algorithm can handle computing 35052111338673026690212423937053328511880760811579981620642802346685810623109850235943049080973386241113784040794704193978215378499765413083646438784740952306932534945195080183861574225226218879827232453912820596886440377536082465681750074417459151485407445862511023472235560823053497791518928820272257787786 to the power of 89489425009274444368228545921773093919669586065884257445497854456487674839629818390934941973262879616797970608917283679875499331574161113854088813275488110588247193077582527278437906504015680623423550067240042466665654232383502922215493623289472138866445818789127946123407807725702626644091036502372545139713 in a useful amount of time?

Answer 1

Surprisingly, very basic algorithms which the children learn at the basic schools are used. For instance:

http://www.wikihow.com/Do-Long-Multiplication

You can find a similar algorithm for sum, sub and division. Try to ask google for: "division on paper"

The "power of" is little tricky. In cryptography you don't really need the "real power of". Instead you need:

(a ^ b) mod c

It is easy to compute a^(power of 2) mod c

a * a mod c= a^2 mod c
(a^2)^2 mod c= a^4 mod c
(a^4)^2 mod c= a^8 mod c
...
(a^512)^2 mod c= a^1024  mod c

And if you need a^5

(a^5) = a^2 * a^2 * a

thanks to "mod c" you keep the numbers no higher than c.

For example:

c = 10

2^2 = 4
2^4 mod 10 = (4^2) mod 10 = 16 mod 10 = 6
2^8 mod 10 = ((4^2)^2) mod 10 = (6^2) mod 10 = 36 mod 10 = 6
2^16 mod 10 = (6^2) mod 10 =....

etc..

There are many tricks how to make the calculation faster. For example, Montgomery multiplication algorithm is often used for that. But even without those tricks the implementation would be fast enough. I would estimate RSA instead of 0.2s would take 5s or so.

Answer 2

There are two reasons by which such "huge" numbers can be computed in reasonable time.

The first one is that we do not raise one integer x to some big exponent d. What we do is that we compute x raised to power d modulo an integer n. The modulo means that we are not interested in the final integer x^d but only in the remainder of the Euclidian division of x^d by n. The good part here is that all involved numbers will reside between 0 and n-1; thus, they will fit in a few thousands of bits, instead of becoming (much) larger than the entire Universe.

The second reason is that the exponentiation is done through the square-and-multiply algorithm. As an example, to compute x¹⁰⁰ (modulo n), we do not do 99 multiplications by x; instead, we compute:

• x²
• (x²)² = x⁴
• (x⁴)² = x⁸
• (x⁸)² = x¹⁶
• (x¹⁶)² = x³²
• (x³²)² = x⁶⁴
• x⁶⁴x³²x⁴ = x^64+32+4 = x¹⁰⁰

Thus a grand total of 6 squarings and 2 multiplications, i.e. way fewer than the 99 multiplications of the naive algorithm. In all generality, if the exponent fist on k bits (the exponent value lies between 2^k-1 and 2^k), then the square-and-multiply algorithm will need k-1 squarings and at most k-1 multiplications (possibly much less than that with "window" optimizations).

If you want full details on such things, have a look at the Handbook of Applied Cryptography, especially chapter 14.

Answer 3

We can compute $m^e \bmod n$ using the binary exponential method.

In this method, you should first compute the binary form of $e$. Let $\ell$ be the number of bits in $e$, and let $e_i$ denote the $i$-th bit of $e$, so that $e=\sum\limits_{i=0}^\ell e_i \cdot 2^i$.

Now, with the algorithm below, you can compute $c$:

$z:=1$
$\text{for } i:= \ell \text{ down to } 0 \text{ do}$
$\quad z:=z^2\cdot m^{e_i} \bmod n$
$\text{return } z$

You can do this easily in Programs such as the "MAGMA" with Modexp(m,e,n); in a second.