Take the 2-minute tour ×
Super User is a question and answer site for computer enthusiasts and power users. It's 100% free, no registration required.

Studying some RSA encrypt/decrypt methods, I found this article: An Example of the RSA Algorithm

It requires this to decrpyt this message enter image description here

The total result of enter image description here is so big, for a 64-bit/32-bit machine, I don't believe it can hold such a big value in one register. How does the computer do it without an overflow?


This question was a Super User Question of the Week.
Read the blog entry for more details or contribute to the blog yourself

share|improve this question
6  
I wonder if you would get a better answer if this got migrated over to cs.stackexchange.com. This seems like it might fit better on a CS/Math site which are a lot more focused on the actual details of low things are down at a really low level. –  Zoredache Jul 23 '12 at 18:07
1  
This is valid enough for Super User. –  KronoS Jul 23 '12 at 22:03

5 Answers 5

up vote 39 down vote accepted

Because the integer modulus operation is a ring homomorphism (Wikipedia) from ℤ -> ℤ/nℤ,

(X * Y) mod N = (X mod N) * (Y mod N) mod N

You can verify this yourself with a little bit of simple algebra. (Note that the final mod on the right-hand side appears due to the definition of multiplication in a modular ring.)

Computers use this trick to calculate exponentials in modular rings without having to compute a large number of digits.

               / 1                            I = 0,
               |
(X^I) mod N = <  (X * (X^(I-1) mod N)) mod N  I odd,
               |
               \ (X^(I/2) mod N)^2 mod N      I even & I /= 0.

In algorithmic form,

-- compute X^I mod N
function expmod(X, I, N)
    if I is zero
        return 1
    elif I is odd
        return (expmod(X, I-1, N) * X) mod N
    else
        Y <- expmod(X, I/2, N)
        return (Y*Y) mod N
    end if
end function

You can use this to compute (855^2753) mod 3233 with only 16-bit registers, if you like.

However, the values of X and N in RSA are much larger, too large to fit in a register. A modulus is typically 1024-4096 bits long! So you can have a computer do the multiplication the "long" way, the same way we do multiplication by hand. Only instead of using digits 0-9, the computer will use "words" 0-216-1 or something like that. (Using only 16 bits means we can multiply two 16 bit numbers and get the full 32 bit result without resorting to assembly language. In assembly language, it is usually very easy to get the full 64 bit result, or for a 64-bit computer, the full 128-bit result.)

-- Multiply two bigints by each other
function mul(uint16 X[N], uint16 Y[N]):
    Z <- new array uint16[N*2]
    for I in 1..N
        -- C is the "carry"
        C <- 0
        -- Add Y[1..N] * X[I] to Z
        for J in 1..N
            T <- X[I] * Y[J] + C + Z[I + J - 1]
            Z[I + J - 1] <- T & 0xffff
            C <- T >> 16
        end
        -- Keep adding the "carry"
        for J in (I+N)..(N*2)
            T <- C + Z[J]
            Z[J] <- T & 0xffff
            C <- T >> 16
        end
    end
    return Z
end
-- footnote: I wrote this off the top of my head
-- so, who knows what kind of errors it might have

This will multiply X by Y in an amount of time roughly equal to the number of words in X multiplied by the number of words in Y. This is called O(N2) time. If you look at the algorithm above and pick it apart, it's the same "long multiplication" that they teach in school. You don't have times tables memorized out to 10 digits, but you can still multiply 1,926,348 x 8,192,004 if you sit down and work it out.

Long multiplication:

    1,234
  x 5,678
---------
    9,872
   86,38
  740,4
6,170
---------
7,006,652

There are actually some faster algorithms around for multiplying (Wikipedia), such as Strassen's fast Fourier method, and some simpler methods which do extra addition and subtraction but less multiplication, and so end up faster overall. Numerical libraries like GMP are capable of selecting different algorithms based on how big the numbers are: the Fourier transform is only the fastest for the largest numbers, smaller numbers use simpler algorithms.

share|improve this answer
    
+1, but you're missing an extra mod N at the end of the Chinese Remainder Theorem. ((16 mod 5) is not equal to (4 mod 5) * (4 mod 5): the former is 1, the latter is 16.) –  ruakh Jul 23 '12 at 20:16
    
@ruakh: Corrected. Although I really want to say, R/kR is isomorphic to R/k1R x R/k2R x ... R/knR, where k1..kn are pairwise coprime, their product is k, and R is a principal ideal domain. I've been overloading * for so long that it's hard to see it as anything but modular. In other words, under my usual notational conventions the mod is superfluous. –  Dietrich Epp Jul 23 '12 at 20:20
1  
@Synetech: But I love those four words so much: "Exercise for the reader." –  Dietrich Epp Jul 24 '12 at 4:11
1  
(X * Y) mod N = (X mod N) * (Y mod N) mod N is true, but it doesn't have anything to do with the Chinese Remainder Theorem. –  Dennis Jul 30 '12 at 17:57
1  
@Dennis: I clarified the structure of the codomain in the answer now. (It's never ambiguous to me, since I wrote it...) –  Dietrich Epp Jul 30 '12 at 21:27

The simply answer is that they can't, not on their own. Indeed, if you take the concept of an x-bit machine, then there is a limited number of numbers which can be represented by a limited number of bits, just like there is a limited number of numbers which can be represented by 2 digits in the decimal system.

That being said, computer representation of very large numbers is a large component of the field of cryptography. There are many ways of representing very large numbers in a computer, each as varied as the next.

Each of these methods have different advantages and disadvantages, and while I do not / can not list all methods here, I will present a very simply one.

Suppose an integer can only hold values from 0-99. How could one represent the number 100? This may seem impossible at first, but that is because we only consider a single variable. If I had an integer called units and one called hundreds, I could easily represent 100: hundreds = 1; units = 0;. I could easily represent a larger number, like 9223: hundreds = 92; units = 23.

While this is an easy method, one can argue that it is very inefficient. Like most algorithms which push the boundaries of what a computer can do, it is usually a tug-o-war between power (represent large numbers) and efficiency (fast retrieval/storage). Like I said earlier, there are many ways of representing large numbers in computers; just find a method and experiment with it!

I hope this answered your question!

Further Reading: This article and this one may come in handy for more information.

share|improve this answer

The way that this can be done (there are much faster ways involving repeated squaring and the like) is by multiplying, and after every multiplication take the modulus. So long as the modulus squared is less than 2^32 (or 2^64) this will never have an overflow.

share|improve this answer

The same way you can.

I'm going to guess that you don't know offhand what 342 * 189 is. But you do know the following facts:

9 * 2 = 18
9 * 4 = 36
9 * 3 = 27
8 * 2 = 16
8 * 4 = 32
8 * 3 = 24
1 * 2 = 2
1 * 4 = 4
1 * 3 = 3

18 + 360 + 2700 + 160 + 3200 + 24000 + 200 + 4000 + 30000 = 64638

By knowing these simple facts, and having learned a technique to manipulate them, you can do arithmetic that you otherwise couldn't.

By the same token, a computer that can't handle more than 64 bits of math at a time can easily break larger problems up into smaller pieces, do those smaller pieces, and put them back together to form the answer to the larger, previously unanswerable problem.

share|improve this answer

As far as addition and subtraction are concerned, many CPUs have a "carry bit" that is set if the arithmetic operation has overflowed. So if a result will require 8 bytes to store, and the CPU is 32-bits (which equls 4 8-bit bytes), it can do two addition operations, first on the "low word" and then on the "high word" with the carry bit taking care of the overflow. Necessary to clear the carry bit first. This is one reason why higher bit CPUs increase performance because this does not have to be done as much.

Of course this is from my limited assembler experience with 8-bit CPUs. I don't know how the carry bit works with modern CPUs with multiply and divde instructions. Non-Intel RISC CPUs may also behave differently.

I don't know very much about floating point math, but basically the bytes represent a fixed number of places, but not specific places. That's why it's called "floating" point. So, for example, the number 34459234 would consume roughly the same memory space as 3.4459234, or 3.4459234E+20 (that's 3.4459234 x 10 ^ 20).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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