Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
FakezZ

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

Recommended Posts

Posted · Original PosterOP

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 :D


MacBook Pro 15' 2018 (Pretty much the only system I use)

Link to post
Share on other sites
Posted · Original PosterOP

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 :P


MacBook Pro 15' 2018 (Pretty much the only system I use)

Link to post
Share on other sites

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

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


.

Link to post
Share on other sites
Posted · Original PosterOP

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?


MacBook Pro 15' 2018 (Pretty much the only system I use)

Link to post
Share on other sites

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.


Mini-Desktop: NCASE M1 Build Log
Mini-Server: M350 Build Log

Link to post
Share on other sites
Posted · Original PosterOP

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


MacBook Pro 15' 2018 (Pretty much the only system I use)

Link to post
Share on other sites

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


0b10111010 10101101 11110000 00001101

Link to post
Share on other sites
Posted · Original PosterOP

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 :D


MacBook Pro 15' 2018 (Pretty much the only system I use)

Link to post
Share on other sites

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.

Link to post
Share on other sites

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 :D

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)


0b10111010 10101101 11110000 00001101

Link to post
Share on other sites

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.

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


×