Question of the Week: How can computers calculate exponential math without overflow errors?

July 30, 2012 by kronos. 5 comments

This weeks question of the week comes from Kit-Ho who poses:

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?


For those of you that may not know what this “Overflow” that Kit mentioned, he’s talking about a term Stack Overflow.   Here’s the official “Wiki” definition:


In software, a stack overflow occurs when too much memory is used on the call stack. The call stack contains a limited amount of memory, often determined at the start of the program. The size of the call stack depends on many factors, including the programming language, machine architecture, multi-threading, and amount of available memory. When a program attempts to use more space than is available on the call stack (that is, when it attempts to access memory beyond the call stack’s bounds, which is essentially a buffer overflow), the stack is said to overflow, typically resulting in a program crash.  This class of software bug is usually caused by one of two types of programming errors.    


As pointed out by Dennis (thanks!) I completely got this wrong.  Stack overflow isn’t the issue, but rather integer overflow:

In computer programming, an integer overflow occurs when an arithmetic operation attempts to create a numeric value that is too large to be represented within the available storage space. For instance, adding 1 to the largest value that can be represented constitutes an integer overflow. The most common result in these cases is for the least significant representable bits of the result to be stored (the result is said to wrap). On some processors like GPUs and DSPs, the resultsaturates; that is, once the maximum value is reached, attempts to make it larger simply return the maximum result.  

For example, a mechanical odometer, has a rollover (or reset) after a certain amount of miles:

This is the same as computer integer overflow, where the size of the numbers needed are greater than the object type can hold.  Kit-Ho’s example RSA link exceedes the C#’s max value of 18,446,744,073,709,551,615 of the long type.

Dietrich Epp came up with a great answer as to how computers can calculate these large numerical calculations:

more »

Kon Boot: Getting into a Client’s Computer without using a Portal Gun

March 1, 2012 by bloodphilia. 3 comments

Okay, here you are again. Another computer from another (self-proclaimed) client for you to fix. So, let’s boot this thing and see what’s wrong with it this time. Okay, first obstacle; logging into the client’s user account. Now for me, repairs would usually pause here while I’m waiting for the moment I can get a hold of my client and ask him or her for the correct password. Annoying…

more »

QotW: Filesystem Security

May 23, 2011 by mokubai. 0 comments

Ultimate Fish Battle Royale

Is NTFS really secure?

I have Mac PC, in which I have created a Windows partition and have installed Windows using Boot Camp. If I log in to the Mac OS, I can read all the files from the Windows partition from Mac. If I compare the same scenario from within Windows, Windows claims to secure a user’s private files (stored in My Documents for instance) from other users with equal or less privilege. I was expecting to see the same protection from Mac as well. I was expecting an error message in Mac to show that these files are inaccessible, if I try to see or open them. Can someone explain if my perception is right or am I missing something?

While the question specifically mentions NTFS the answer applies to almost every file system that is able to be accessed by another operating system and has not had native support for that file system built in.

The same would apply to EXT2/3/4 (Linux) support on Windows, HFS (Mac) support on Linux or any combination of file systems that are standard for one system and just barely “supported” on another.

more »

Compression and Encryption: The ZIP Years.

April 2, 2011 by flibs. 1 comments

In a comment to my last post Compression and Encryption, nhinkle asked:

Do you know then how encrypted ZIP files work? Encryption seems to be built into many encryption formats like zip, rar, 7z, etc. Do these usually compress and then encrypt, or somehow do both at once?

Well, ZIP handles this in its own special way. First let’s look at how a ZIP file is made up. A ZIP file consists of one or more ‘file entries’ – blocks of data that make up the actual content of the zip file, followed by a final ‘central directory’:


As you can see each file in the ZIP file has its own local header which contains the information about how the file is compressed. This allows each file in the ZIP file to be compressed in a different way – from “Store” (no compression – ideal for adding pre-compressed files) right up to the maximum and slowest compression available.

more »