The National Security Agency is the largest employer of mathematicians in the US. Maths is a core discipline at the NSA, and mathematicians work on signals intelligence and information security. Why is NSA so interested in mathematics?
Many actions are easy to perform but almost impossible to reverse. For example, we can mix cans of red and yellow paint, burn a document or break a crystal glass, but we cannot reverse these actions. Many mathematical actions are easy to perform but very difficult to invert. Modern cryptography is based on this fact.
The simplest example of computational asymmetry is the multiplication of prime numbers. Recall that a prime is a number that cannot be broken into a product of two smaller numbers. It is easy to compute the product of two prime numbers – just multiply them together – but difficult to find the prime factors of a large number. For example, which two primes multiplied together yield 1,003? The answer requires much greater effort than the production of the number. Mathematical functions that are simple to compute but difficult to invert are called one-way functions.
Cryptographic system
For encryption, we take two very large prime numbers, each having several hundred digits, and multiply them. Given the product, these factors cannot easily be determined. However, if one of the factors is known, the other is obtained by a simple division.
Knowledge of one factor is like a secret trapdoor, allowing anyone who knows it to find the other factor. A one-way trapdoor function can be inverted by the designer, who has a key, but nobody else.
In 1978 three MIT students, Ron Rivest, Adi Shamir and Len Adelman devised a cryptographic system based on the difficulty of factoring large numbers. The RSA algorithm was the first public key system. Each user generates two related key numbers. One is listed in a public key directory. The other is private and known only to the owner. The sender uses the recipient's public key to encrypt a message and send it. The receiver then decrypts the message using the private key known only to him or her.
The technical details of the RSA system, while not trivial, are relatively straightforward. They depend on a result called Fermat’s Little Theorem. This was stated by Pierre Fermat in 1640 and proved by Leonard Euler in 1736. A more general result, the Euler-Fermat theorem, is a cornerstone of modern computer security systems.
Modern cryptography depends on the assumption that nobody can factor primes efficiently. Is this a safe assumption? The difficulty of the problem has not actually been rigorously proven by mathematicians, but centuries of endeavour have failed to produce an efficient algorithm.
Cryptography and coding theory are active fields of current research, with intensive investigations in discrete mathematics, algebra, algebraic geometry and number theory.
A method similar to RSA was independently discovered some years earlier at the British Government Communications headquarters in Cheltenham, but was not declassified until 1997. Given this background, one might wonder what has been discovered at NSA. If a fast method of cracking big numbers into primes has been found, we might not hear about it for some time, but the implications of such a development would be profound.
- Peter Lynch is emeritus professor at the school of mathematics and statistics, University College Dublin. He blogs at thatsmaths.com