39
$\begingroup$

Whilst I understand how the RSA algorithm works, I don't understand how the CPU operates when it needs to use the mod function with a huge number $n$, for example.

$n = 8192$ bits;

$c = m^e \mod n$;

In essence my question is how does the CPU deal with this huge modulus?

$\endgroup$
  • 1
    $\begingroup$ What do you mean? Are you asking if the computation takes a long time? or how the bignumbers are managed into memory? for the first question you can try to play with a key (openssl genrsa 8192 will generate a big key) $\endgroup$ – ddddavidee May 26 '16 at 9:02
  • 2
    $\begingroup$ Hardware is designed to work for integer computations with numbers of fairly small limited sizes only, e.g. 32 or 64 bits. Appropriate software do the work of reducing your computations with huge numbers to those of small numbers that suit the hardware. In some modern programming languages like Python, you can very conveniently express integer computations with numbers of practically arbitrarily large sizes. (See e.g. my RSA software in s13.zetaboards.com/Crypto/topic/7234475/1/) $\endgroup$ – Mok-Kong Shen May 26 '16 at 9:43
  • 1
    $\begingroup$ See here for a relatively small class that performs 32 bit operations on a 16 bit Java VM. Please note that you should not directly implement RSA with any BigNum library; you'd need side channel protection as well. $\endgroup$ – Maarten Bodewes May 26 '16 at 12:14
  • 16
    $\begingroup$ How do you handle numbers bigger than 9? $\endgroup$ – CodesInChaos May 26 '16 at 17:52
  • $\begingroup$ There are many tricks to make modular arithmetic fast. For example, suppose I asked you the last base ten digit of 11 to the one millionth power. Could you figure it out without multiplying 11 by itself a million times? Most of the time when solving modular arithmetic problems the number stay relatively small. $\endgroup$ – Eric Lippert May 29 '16 at 6:22
85
$\begingroup$

It (or rather, the software running on it) will use arbitrary-precision ("bignum") arithmetic. The way this works is basically the same way in which you (probably) learned to do arithmetic on paper at school.

The arithmetic taught to us humans at school is base-10 arithmetic — that is, we represent numbers as strings made up of ten different digits, from "0" to "9", where each digit alone represents a different small number below 10, and where placing a digit to the left of another digit multiplies its value by 10.

Assuming you didn't totally sleep through grade school, you probably remember having to memorize the addition and multiplication tables for single-digit numbers: 1 + 1 = 2, 7 + 7 = 14, 6 × 4 = 24, and so on. Those are the basic "atomic" operations for base-10 arithmetic, and once you know how to do them, you can combine them to calculate things with larger numbers.

(You don't have to have the basic operations all perfectly memorized, of course; if you, say, forget what 7 × 6 is, but still remember that 6 × 6 = 36, you can just count six more numbers up from that to end up at 42. And even if you were to forget what e.g. 7 + 7 is, you could, say, count on your fingers to arrive at 14. It just turns out that, for us humans, memorizing those basic single-digit operations — i.e. implementing them with the human equivalent of a look-up table — makes arithmetic a lot faster than working them out from first principles every time. For computers, the tradeoff may be different.)

For example, depending on how math was taught at your school, you may remember writing down an addition problem on paper something like this:

Exercise: 12345 + 67890 = ______

             <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
             <-- result

and the working it out digit by digit, from right to left. Here, you'd start with 5 + 0 = 5 (with no carry):

       0     <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
        5    <-- result

and then proceed to 4 + 9 = 13 (i.e. write down 3, carry 1):

      10     <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
       35    <-- result

and then 1 + 3 + 8 = 4 + 8 = 12 (i.e. write down 2, carry 1), and so on all the way to:

    1110     <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
    80235    <-- result

You may have also learned similar pencil-and-paper algorithms for other elementary arithmetic operations, like subtraction, multiplication and even long division (which can also be used for modular reduction). The important thing to realize is that all these calculation methods are based on rules for manipulating strings of digits, and on simple arithmetic operations on single digits. As long as you can do the basic single-digit operations, and know the algorithm for combining them together, you can do arithmetic on paper with numbers as large as you want (or need) to!

So how do computers do it, then? They could of course use exactly the same decimal arithmetic rules as we do, but that would be pretty inefficient. A typical CPU already has fast circuitry to add or multiply together any two 32 or 64 bit (and possibly even larger) numbers with a single machine code instruction, so it makes a lot more sense to treat 32 or 64 bit arithmetic as the basic building block.

Thus, a typical computer implementation of bignum arithmetic effectively works with "digits" that are 32 or 64 bit integers, and represents larger numbers as strings of those smaller integers. The algorithms used are very similar to those we'd use for pencil-and-paper calculation, except that instead of base 10, a computer is far more likely to use base 232 or 264.

For example, let's calculate the sum of two random 128-bit numbers (written in hexadecimal for convenience):

Exercise: 3d96d3e9d019665051ecf94e4c0c697b +
          a80314053a779df7464ea2feebf771be = ______

A modern CPU might be able to calculate that directly, but let's assume that we only have a 32-bit CPU available. Fortunately, we can break up our numbers into 32-bit chunks and use the same addition algorithm we used before:

                                         <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
                                         <-- result

So first, we need to calculate 4c0c697b + ebf771be, which our CPU easily tells us is 13803db39 (i.e. 32-bit result 3803db39, plus carry 1):

                             1           <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
                               3803db39  <-- result

Next we ask our CPU to calculate 51ecf94e + 464ea2fe, and to increment the result by one because of the carry, which yields 983b9c4d (and no carry for the next position):

                    0        1           <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
                      983b9c4d 3803db39  <-- result

We can then proceed with the remaining two 32-bit additions in the same way, getting d0196650 + 3a779df7 = 10a910447 (i.e. 0a910447 and carry 1) and 3d96d3e9 + a8031405 + 1 = e599e7ef:

  0        1        0        1           <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
    e599e7ef 0a910447 983b9c4d 3803db39  <-- result

And there we have our result!

I used addition for this simple example, but similar algorithms can be used for other arithmetic operations, including exponentiation and modular reduction (which one would normally combine into a single modular exponentiation algorithm, since it's much more efficient to do them together rather that to first exponentiate and then reduce).

Also note that the arithmetic algorithms used for cryptography tend to be somewhat specialized, since in crypto it's often important to avoid timing attacks and other types of side-channel attacks by making sure that the algorithm takes the same amount of time to run (and consumes roughly the same amount of power, etc.) regardless of what the numbers being added (or multiplied or raised to a power, etc.) are.

$\endgroup$
  • 11
    $\begingroup$ +1 for the beautiful demonstration of adding in "base-2^32" and showing the carries. Now I'm thinking of Tom Lehrer's classic "New Math" (youtube.com/watch?v=wIWaJ0sy03g for those who haven't had the pleasure). $\endgroup$ – Monty Harder May 26 '16 at 19:58
  • 1
    $\begingroup$ "Assuming you didn't totally sleep through grade school, you probably remember having to memorize the addition and multiplication tables for single-digit numbers" I cried on that mention $\endgroup$ – user36300 Jun 22 '16 at 13:15
  • $\begingroup$ and possibly even larger Yep, modern processors can operations on up to 128-bit numbers in xmm registers from MMX, 256-bit numbers on ymm registers from SSE, and 512-bit operations on zmm registers from AVX512. SIMD operations can make crypto way faster. $\endgroup$ – forest Nov 8 '18 at 3:32
8
$\begingroup$

Of course the processor cannot process such large numbers directly; this is done though a library such as GMP. See Wikipedia for a list of such libraries, and a good textbook such as that of Gerhard and von zur Gathen for the underlying ideas. The freely available Handbook of Applied Cryptography also talks about this, especially in Chapter 14.

$\endgroup$
4
$\begingroup$

As others have noted, you typically use some sort of arbitrary precision integer library. I feel obliged to point out, however, that extending multiplication to large integers is decidedly non-trivial compared to addition. With addition, you have a single bit of carry from one word to the next, and on a typical processor you even have an instruction dedicated to carrying out an addition that takes the carry bit into account, so it becomes a simple loop from least significant to most significant to get the result.

With multiplication, things aren't so simple though. Let's consider the same same kind of example as @Ilmari used, with 128-bit numbers and a 32-bit CPU (but, obviously, multiplying instead of adding the numbers).

Two things render this non-trivial. In addition, bit 0 of the result depends solely upon bit 0 of each of the two inputs. Bit 1 of the result depends solely on bit 1 of the two inputs and the carry from bit 0 (and so on). With multiplication, you don't get nearly that "neat" of a segmentation.

The situation isn't hopeless though. For the moment, let's consider multiplying two 64-bit operands on a 32-bit computer. We can break the operands up into two pieces, one consisting of the lower 32 bits, and the other consisting of the upper 32 bits. Then we apply the distributive property:

(A + B)(C + D) = AC + BC + AD + BD

Since each of these inputs has only 32 significant bits, we can carry out each individual multiplication on a 32-bit process without any problems. That gives us 4 intermediate values to add together--so now we have the (relatively) easy case that @Ilmari already outlined.

$\endgroup$
  • $\begingroup$ No, multiplication of two 32-bit numbers is a 64-bit operation, therefore you technically have 8 intermediate values. $\endgroup$ – yo' May 27 '16 at 15:10
  • 1
    $\begingroup$ @yo': Essentially every "32-bit" CPU can multiply two 32-bit numbers to produce a 64-bit result. For example on an x86, mult ecx multiplies eax by ecx giving a result in edx:eax. I wouldn't view that as two separate intermediate results, but I guess if you want to there's nothing I can do to stop you. $\endgroup$ – Jerry Coffin May 27 '16 at 15:41
  • 2
    $\begingroup$ Multiplication of arbitrary-precision numbers is completely trivial conceptually, It's just expensive (O(N*M) in the length of the inputs). Now, division, that's complicated. Of course, it's not intractable either. you learned "estimate multiply subtract bring-down" in primary school, and it turns out the "estimate" stage is downright trivial in binary. But all that repetition gets expensive. $\endgroup$ – Random832 May 27 '16 at 21:52
  • 1
    $\begingroup$ @Random832: Division isn't particularly complex either. It's fairly easy to reduce it to shift simple bit-wise operations (primarily shift and subtract). stackoverflow.com/a/5387432/179910. The repetition basically means you produce one bit per iteration with the simplest algorithms. You can produce (for example) 4 bits per iteration, at some cost in complexity. $\endgroup$ – Jerry Coffin May 27 '16 at 21:56
  • $\begingroup$ @JerryCoffin Sure, but in arbitrary precision those operations each have a cost that scales with the size of the operands, as does the number of them you have to perform. $\endgroup$ – Random832 May 27 '16 at 22:00
3
$\begingroup$

While other answers approach the problem from the simpler question, "How do computer handle large number computation" the specific question is how computers handle large modulus numbers, and the answer is that there are algorithms and techniques specifically for handling large modulus calculations.

Wikipedia provides a short list of terms and algorithms one should look into when doing this:

Since modular arithmetic has such a wide range of applications, it is important to know how hard it is to solve a system of congruences. A linear system of congruences can be solved in polynomial time with a form of Gaussian elimination, for details see linear congruence theorem. Algorithms, such as Montgomery reduction, also exist to allow simple arithmetic operations, such as multiplication and exponentiation modulo n, to be performed efficiently on large numbers.

Some operations, like finding a Discrete logarithm or a Quadratic congruence appear to be as hard as Integer factorization (some even are, provably) and thus are a starting point for Cryptographic alogrithms and Encryption. These problems might be NP-intermediate.

Solving a system of non-linear modular arithmetic equations is NP-complete.

Modular Arithmetic isn't widely taught, and so many are left to discover it for themselves when they are seeking out simpler solutions to specific types of problems within discrete mathematics.

$\endgroup$
-2
$\begingroup$

One important aspect to keep in mind, which I do not see in the other answers, is that in binary modulus 8192 is very easy, as 8192 is simply 2^13.

If you take modulus in "normal" base 10, you'd call %100 simple. 1237659%100=59. You simply cut off everything before the last 2 digits.

In binary, the same is true for %8192, or, written in binary, 10000000000000. You simply take your number, for instance 1001100001000010111000100010001001, and only use the last 13 digits, and get 0100010001001.

Edit:

Excuse me. Just after posting this answer, I read through your question again, and realized it's %8192bit, or ~1*10^2466. Though my "answer" is still true, it has far from any notable impact.

$\endgroup$
  • 7
    $\begingroup$ He's not asking how arithmetic modulo $8192$ is done, he's asking how it's done modulo $N \approx 2^{8192}$ $\endgroup$ – poncho May 26 '16 at 13:51
  • 1
    $\begingroup$ even $2^{8192}$ would be "easy". A random prime number between $2^{8191}$ and $2^{8192}$ is worse... $\endgroup$ – pipe May 26 '16 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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