33
$\begingroup$

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?

$\endgroup$
3
  • 9
    $\begingroup$ What research have you done? This is covered in textbooks and courses on cryptography. We expect you to do a significant amount of research before asking, and to show it in the question. See security.stackexchange.com/help/how-to-ask: "Have you thoroughly searched for an answer before asking your question? Sharing your research helps everyone. Tell us what you found and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and above all, it helps you get a more specific and relevant answer!" $\endgroup$
    – D.W.
    Oct 5, 2015 at 18:50
  • 1
    $\begingroup$ See also security.stackexchange.com/q/13674/971 $\endgroup$
    – D.W.
    Oct 5, 2015 at 18:52
  • 3
    $\begingroup$ 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? $\endgroup$ Oct 5, 2015 at 22:53

3 Answers 3

37
$\begingroup$

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.

$\endgroup$
8
  • 14
    $\begingroup$ 0.2s vs 5s!? You are vastly underestimating how fast computers do math. The difference is closer to 0.1ms vs 1ms $\endgroup$ Oct 5, 2015 at 16:26
  • 7
    $\begingroup$ Note: If you don't do the repeated square and multiply trick you'll likely never witness the finish of your RSA signing operation... $\endgroup$
    – SEJPM
    Oct 5, 2015 at 21:02
  • 3
    $\begingroup$ 486 was similarly bloomin' fast. $\endgroup$ Oct 5, 2015 at 23:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Oct 6, 2015 at 19:16
  • 3
    $\begingroup$ 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. $\endgroup$
    – smrt28
    Oct 8, 2015 at 7:34
29
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.