How does RSA compute such enormous numbers?

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?

-

migrated from security.stackexchange.comOct 6 '15 at 17:25

This question came from our site for information security professionals.

– D.W. Oct 5 '15 at 18:52
Here's a related problem: compute the "ones" decimal digit of eleven raised to the ten billionth power. If you compute eleven to the first, second, third and fourth powers it should become rapidly pretty clear that you do not need to perform ten billion multiplications to answer that question. Now do you see why the computations in RSA are feasible? – Eric Lippert Oct 5 '15 at 22:53
I'm voting to close this question as off-topic because it should be migrated to Cryptography SE. – RoraΖ Oct 6 '15 at 11:38
@RoraΖ Gosh, sorry, I didn't realise such a stack existed! – Luke Oct 6 '15 at 11:45

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.

-
0.2s vs 5s!? You are vastly underestimating how fast computers do math. The difference is closer to 0.1ms vs 1ms – BlueRaja - Danny Pflughoeft Oct 5 '15 at 16:26
Note: If you don't do the repeated square and multiply trick you'll likely never witness the finish of your RSA signing operation... – SEJPM Oct 5 '15 at 21:02
486 was similarly bloomin' fast. – Lightness Races in Orbit Oct 5 '15 at 23:55
Montgomery multiplication does NOT make things significantly faster, certainly not by a factor of 25: the number of elementary operations doe not change asymptotically. It does simplifies estimation of a quotient digit, and avoids the rare case when that's wrong, which is nice to have in general, and avoid a side-channel leakage. – fgrieu Oct 6 '15 at 19:16
Just note the comment about Montgomery was written by someone else. Not sure how this is possible, but it seems some people with really high reputation can modify posts of someone else. Would be nice if they remark that explicitly. – smrt28 Oct 8 '15 at 7:34

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 xd but only in the remainder of the Euclidian division of xd 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 x100 (modulo n), we do not do 99 multiplications by x; instead, we compute:

• x2
• (x2)2 = x4
• (x4)2 = x8
• (x8)2 = x16
• (x16)2 = x32
• (x32)2 = x64
• x64x32x4 = x64+32+4 = x100

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 2k-1 and 2k), 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.

-

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.

-