How can encryption algorithms use numbers bigger than 64-bit?

[FakezZ]

I know that this may sound like a stupid question to some, but recently I came across this video: https://www.youtube.com/watch?v=M7kEpw1tn50 from Numberphile where they talk about encryption and big numbers. The thing is that they talk about like 1048-bit numbers and such, however when I make a program I can't really use numbers bigger than 64-bit (or 32-bit if I use my old netbook). So they say that every time I make a purchase online with my credit card, my computer has to do the described computations in the video, but HOW? How can it suddenly handle such HUGE numbers? Can anyone explain this to me? Thanks in advance

[AlwaysFSX]

Lots and lots of math and switching data to and from the memory.

[FakezZ]

Lots and lots of math and switching data to and from the memory.

So I guess it would probably be impossible for a mortal like me to use such big numbers then... Bummer

[AlwaysFSX]

So I guess it would probably be impossible for a mortal like me to use such big numbers then... Bummer

Not unless you're dedicated...or have a computer :lol:

[MrSuperb]

BigInteger or just simple arrays?!

[FakezZ]

BigInteger or just simple arrays?!

How would you like cube the whole thing then, if it is just an array? Is there a way to do calculations that treat the whole array as a single number?

[MrSuperb]

How would you like cube the whole thing then, if it is just an array? Is there a way to do calculations that treat the whole array as a single number?

 

no. but isn't that what programming is about? finding solutions to problems.

This one should be rather easy.

[FakezZ]

no. but isn't that what programming is about? finding solutions to problems.

This one should be rather easy.

Finding a solution to a programming problem about using huge numbers? Thanks, no sleep for me tonight.. :c

[WanderingFool]

FakezZ Well an important thing I would like to point out first is a 32 bit system actually has a 64 bit number (long long if my memory serves me right).

 

In terms of the internet encryption...your Ethernet chip-set likely has hardwired methods that actually implement the 2048-bit encryption (as it is easy for them to expand the adders and such to handle 2048+ bits and makes it more efficient).  In terms of how your CPU does it, well there are a few ways.  The most basic way is to treat it like paper and pencil type of concept...ie 1234567890 is stored in 10 bytes "1" "2" "3" ...etc....you then do the math like a normal person would with paper and pencils...this is wildly inefficient and time consuming though.

 

Another way is to represent the number as an array of bytes

char array[2048];

as an example....from there you could work at the byte level.

 

e.g.

char array1[2048] = ...;char array2[2048] = ....;char res[2048] = ...;int tmpRes = array1[0] + array2[0];res[0] = (tmpRes%256); //So you essentially store the partial solutiontmpRes = tmpRes/256; //tmpRes now equals the carry over portionfor(int i = 1; i < 2048; i++) {    tmpRes = array1[i] + array2[i] + tmpRes; //Essentially loop through adding together   res[i] = tmpRes%256;   tmpRes /= 256;}return res;

There are likely flaws in the logic, but this is just a quick example of how adding could be done.

 

With that said, if you want to implement the big numbers in your own code, I recommend just using a library.  There are a few out there, such as http://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library

Or if you want the general wiki article look here http://en.wikipedia.org/wiki/Bignum

[FakezZ]

FakezZ Well an important thing I would like to point out first is a 32 bit system actually has a 64 bit number (long long if my memory serves me right).

 

In terms of the internet encryption...your Ethernet chip-set likely has hardwired methods that actually implement the 2048-bit encryption (as it is easy for them to expand the adders and such to handle 2048+ bits and makes it more efficient).  In terms of how your CPU does it, well there are a few ways.  The most basic way is to treat it like paper and pencil type of concept...ie 1234567890 is stored in 10 bytes "1" "2" "3" ...etc....you then do the math like a normal person would with paper and pencils...this is wildly inefficient and time consuming though.

 

Another way is to represent the number as an array of bytes

char array[2048];

as an example....from there you could work at the byte level.

 

e.g.

char array1[2048] = ...;char array2[2048] = ....;char res[2048] = ...;int tmpRes = array1[0] + array2[0];res[0] = (tmpRes%256); //So you essentially store the partial solutiontmpRes = tmpRes/256; //tmpRes now equals the carry over portionfor(int i = 1; i < 2048; i++) {    tmpRes = array1[i] + array2[i] + tmpRes; //Essentially loop through adding together   res[i] = tmpRes%256;   tmpRes /= 256;}return res;

There are likely flaws in the logic, but this is just a quick example of how adding could be done.

 

With that said, if you want to implement the big numbers in your own code, I recommend just using a library.  There are a few out there, such as http://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library

Or if you want the general wiki article look here http://en.wikipedia.org/wiki/Bignum

I just tried that and the res array is consisted mostly of letters and numbers. It uses the ASCII values when from char it is converted to int. For example 5+3 makes res[0] equal "h" with an ASCII value of 104 (51 which is the ASCII value of 3 + 53 which is the ASCII value of 5)... And btw I prefer sticking with the standard libraries and building what I can from there

[reiderj8]

If you encrypting numbers using only and, or and xor operators, you can just break the number down. For example, if you want to and two 128 bit numbers, just and two sets of 64 bit numbers. A simple math function can display the 128 bit result as a decimal for the user to see. I hope this doesn't sound confusing, but it's easier than what you might think.

[WanderingFool]

I just tried that and the res array is consisted mostly of letters and numbers. It uses the ASCII values when from char it is converted to int. For example 5+3 makes res[0] equal "h" with an ASCII value of 104 (51 which is the ASCII value of 3 + 53 which is the ASCII value of 5)... And btw I prefer sticking with the standard libraries and building what I can from there

The intent was to show that you don't need to use 32-bit or 64-bit numbers...in this case it was 2048 bytes....I used char because I was brought up with ansi-c which uses char's as bytes.  The idea is you would read in the 2048 byte numbers into the char arrays, and then if you wanted the real number you would have to write a program to export it (or just dump the entire thing as hex values)

[Kiwi00000]

To use huge numbers, you can think of them as a bunch of smaller numbers.

If you are an objected orientated programmer, then you can use a class to make a 'big number' object. Then you can use a linked list to tie them together.