The Primes Go on Forever

Every time you buy something on the internet with your credit card, you use prime numbers to keep your personal information secure. How? Using RSA cryptography. Read on to learn more. Or, if you are brave, go directly to the challenge problem of decoding the secret message 243689518774052214930089506033.

The task of cryptography (Greek kryptos hidden, graphein to write) is to turn messages into gibberish so that they cannot be read by persons other than the intended recipient. If I send my credit card number and PIN over the internet to an online book store, the book store should be able to read it, but no one else should. A cryptographer starts with plain text such as "ATTACKATDAWN" and produces cipher text such as "OTMMGKLHDTIR." This isencryption. Decryption is the reverse: it produces plain text from cipher text.

In the old days, to send a secret message, you first had to send a key — secretly — to the recipient. This you did by meeting in person, or through a trusted courier. In the example above, the key was "OATMEAL" and the encryption method is due to Vigenère.

But the internet is not a trusted medium, so how do you get started? You can't use the internet to send the key, then your financial information. A bad person could capture your internet traffic with the bookstore. He would use the key to read your credit card number and PIN, and would then charge expensive travel to exotic places to your account.

This dilemma was solved in 1978 by Rivest, Shamir, and Adelman. Their method, now known as RSA, depends on some marvelous properties of prime numbers. One of these is that it is rather easy to generate large prime numbers, but much harder to factor large numbers into primes. Another is Fermat's little theorem.

As an example, to be explained in more detail below, consider the message

243689518774052214930089506033
998596335782879839107051625360
7140448055114932771201027350325,
323915666133187777174633743307
665741495158513587387621667442
84515065903121845841724822236676

It was encrypted using the key

e = 5,
N = 519208104502047440191322024032
461128846299254256408973265508
51544998255968235697331455544257

The number N is the product of two primes, just as 39 is the product of the primes 3 and 13. If you could discover the primes, you could decrypt the message. But this is not so easy to do, and this is one of the reasons why RSA works.

Primes, factorization, and a a secret message to decode

1234567 = 127 x 9721

1020030004000050000060000007 = ? x ? x ? ...

public key = 5, 519208104502047440191322024032 461128846299254256408973265508 51544998255968235697331455544257

secret message = 243689518774052214930089506033 998596335782879839107051625360 7140448055114932771201027350325, 323915666133187777174633743307 665741495158513587387621667442 84515065903121845841724822236676 = ???

Challenge problem. What is the secret message? (The reward is the satisfaction of knowing the answer).

How do you know if your answer is correct? Use the algorithm and the table for converting text to numbers and vice versa. If the result makes any sense at all, you almost certainly have the correct answer.

To decode the secret message, you must first factor the number 5192...4257 of the public key into a product of primes, just as 39 factors as 3 x 13. Then you have to do some standard number theory computations. 

The fact that finding primes is "easy," while factoring into primes is "hard" is what makes RSA work.