In RSA, how does the CPU deal with this huge modulus (8192 bits)?

Question

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?

Answer 1

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 2³² or 2⁶⁴.

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.

Answer 2

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.

Answer 3

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.

As an aside: if you're multiplying really huge numbers (like millions or billions of digits) there are other methods (e.g., Karatsuba's algorithm) that improve on this--but the numbers you'd normally use for RSA keys aren't nearly large enough to benefit significantly from that.

Answer 4

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.

Answer 5

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.