Can't understand RSA implementation because of large numbers
An answer to this question on Stack Overflow.
Question
I was trying to understand how asymmetric encryption algorithms work. I found out that the most used algorithm is RSA, so I checked how it's works. I actually didn't understand the entire stuff completely, but I know it involves multiplying and modulo operation using astronomical numbers.
I read that RSA is using 4096 or 8192 bit key length. That means the the multiplied value and the exponent value combined should be at most 4096 bits long, right? Let's assume that a 1000 digit integer fit inside this key length. To get that, let's assume 2 500 digit numbers are multiplied.
Here is what I can't understand. A 500 digit number should be, like 2000 bits long, right? A modern computer is 64-bit long. A high performance server can be 128 or even 256 bit long. But 2000 bits? I have never heard of any computer capable of or having ALU that can handle that.
So how multiplication, modulo and other operations are being done on that huge numbers? Or RSA is designed not to actually do the calculation this big(because I don't understand it clearly enough)? Or is it just not possible to do that in ordinary computers, and the keys we use are pre calculated?
Or should I just accept cryptography is hard and leave it?
Answer
If you recall learning multiplication and addition in school, large numbers are calculated by solving simpler problems on the constituent digits of the large numbers. This wiki article has an overview of the grade-school multiplication algorithm. It also shows how to implement that algorithm in code. So the simple answer to your question is that a fancy version of this algorithm is used to perform the maths necessary for working with large numbers.
Since a computer can manipulate 64, 128, or more bits at a time, performing the maths are performed on many digits at once, rather than one digit at a time.
For algorithms like RSA, where speed is appreciated, the maths might be hard-coded several times for specific key lengths. Competitions like the NIST hash function competition place a premium on performance and even consider the difficulty of implementing the math in hardware.
More generally, long maths are performed by libraries like GMP, the Boost Multiprecision Library, and others.