RSA Encryption

Securely encrypting sensitive information is a difficult problem in this age of computers that can perform billions of calculations per second. The way all good encryptions work these days is by finding that fine line between a mathematical formula that is complex enough to not be solved without the encryption key, or cracked, by a computer’s raw processing power but still simple enough that it can still be used by those who have the key.

RSA encryption, one of the most common in use today, relies on the fact that factoring large numbers is a difficult task. I have always thought of numbers in the millions or billions as “large numbers,” and assumed that these were the types of numbers used in RSA encryption. Anything larger than a million isn’t a number we can really wrap our minds around.

About a year ago I wrote a crude program that could factor numbers in the simplest way I could devise and was surprised to note that it could factor numbers in the millions in less than a second. Since then I have written a better program that can factor far larger numbers. Here are some tests of some of the largest numbers it can handle:

3,290,349,129,589,134,157 = 1,600,856,429 × 2,055,368,033
4,611,686,039,902,224,373 = 2,147,483,647 × 2,147,483,659

It found the factors of the first number in about 3 minutes, or 5 seconds if a pre-calculated list of the first 100 million primes is used, and the second number was factored in about 3 1/2 minutes, or 7 seconds with the primes list.

These numbers are 63 bit coprimes, composed of two 31 bit prime numbers. It seems that RSA encryption normally uses 1024 bit numbers or larger, which would have about 300 digits. When encryption specialists talk about “large numbers,” they mean numbers longer than this paragraph when written out.