Prime numbers and the National Security Agency
|
The National Security Agency (NSA) wants to be able to send email in such a way that if somebody intercepts the message, they will not be able to read the message. And at the same time, the person for whom the message was intended should be able to read the message. |
|
In order to send a message that nobody but the intended party can read, the sender and receiver need to agree upon some kind of code so that a message can be scrambled and un-scrambled. The message "meet in prague on oct eleven at ten", for example, could be scrambled to read "teem ni eragup no tco nlevee ta net". Here, the first and last letters were switched. If this scrambled message were intercepted, its contents would not be immediately obvious. But, it probably wouldn't take long for somebody to break the code and decipher the message.
The NSA, therefore, needs a code that makes it is easy for the sender to encode a message, and for the receiver to decode the message, but that is very difficult for anybody else to decode.
A commonly used code for sending secure messages is known as RSA encryption. There are three basic steps:
- Generate "keys"
- select two large prime numbers, p and q
- compute the product of the two primes, n = pq
- compute the following product, m = (p-1)(q-1)
- choose a number e so that the greatest common divisor of e and m is 1
- compute d so that 1 < d < e and ed mod m = 1 (ed mod m is the remainder of dividing ed by m as many times as evenly possible)
- Scramble message (encryption)
- convert each letter of the alphabet to a number (a=1, b=2, c=3, ..., z=26, A=27, ..., Z=52)
- replace each letter of the message, x, with y = x^e mod n (^ means raise x to the power e)
- send the scrambled message, y
- Unscramble message (decryption)
- replace each letter of the received message, y with y^d mod n
- the result will be the original text message
What is amazing about RSA encryption is that everyone knows the code! But, only the people with all of the "keys" n, e, d can encrypt and decrypt the message. This code, however, is not perfect. Given the number n, the code can be broken by computing its prime factors, p and q. But, for sufficiently large prime numbers, even the most powerful computers would require hundreds of years (or more) to break this code.
Mathematicians and computer scientists have figured out a clever code for sending secrets that, for now at least, is very very difficult to break. The code relies on the simple numerical property that it takes computers a very very long time to factor large numbers into a product of prime numbers.
The NSA (and others) is, by the way, trying to develop a special type of computer known as a quantum computer that, if it can be built, will be able to break this code.