Prime Numbers and Encryption

Want to make $250 000?  Find a big prime number, a really big one. It turns out there are organizations  ready to dough out good cash for a really large prime number.  This is because primes are used in  RSA cryptography.

RSA Algorithm

Let's look at the algorithm:

1.      Multiply two large prime numbers p and q to get the product N

2.      Find two numbers e and d, such that ed = 1mod((p-1)(q-1)), where e and N are relatively prime meaning they do not share any prime factors.

3.      Let's call M the original message and C the ciphered message: 

a.      To encrypt: C = M^emod(N)

b.      To decipher: M = C^dmod(N) 

In essence, using the public key (N,e) will transform the original message M to the ciphered message C. On the contrary, applying the private key d on the ciphered message C will result in the original message M. 

Security of Encryption

The beauty of RSA is your public key can be published for anyone to encrypt a message that only you can decipher. This is because only you possess the private key, and it is extremely difficult for others to deduce this from the public key unless they can easily factor N into p and q. Prime factorization of a large number is a tedious process which cannot be automated. One must therefore resort to brute force when attempting to crack the code.

You may have guessed that the size of prime numbers used dictate the strength of the encryption. A message encrypted with 5-digit prime numbers (40-bit encryption) yields about 1.1 trillion possible results.  However using 16-digit numbers (128-bit encryption) generates 340,282,366,920,938,463,463,374,607,431,768,211,456 possible combinations.  Based on today’s computing power, a 40-bit, 56-bit, 64-bit, and 128-bit encryption can be respectively broken in 1 second, 19 hours, 7 months and 11,000 quadrillion years. This is why 128-bit encryption is the standard used world wide to protect financial transactions and sensitive data. Don't get too complacent however, as it has been predicted that 128-bit encryption will be breakable in about 100 years.

How Many Prime Numbers Are Out There?

It is no secret that there are an infinite number of primes. Here is a proof from the famous Euclid:

1.      Assume there is a largest prime number, p. 

2.      Create a new number q, equal to the product of all primes between 2 and p, plus 1.

3.      Our new number q has no factors in the original set of primes (between 2 and p), because dividing by any of them would produce a remainder of 1.

4.      From point (3) we conclude that q is either itself prime, or is composed of prime factors, all of which are larger than p. 

5.      Point (4) falsifies point (1).

We can take comfort that the next prime number is out there. Unfortunately, it will probably take you a long time to find it.  The current largest prime, 2^43112609-1, was discovered in 2008. So just how big is this Mersenne Prime? It has 13 million digits, and will take me 8 weeks to write down the number.

-PTS