ThatsMaths

The National Security Agency is the largest employer of mathematicians in America. Mathematics is a core discipline at NSA and mathematicians work on signals intelligence and information security (US citizenship is a requirement for employment). Why is NSA so interested in mathematics? [See TM096, or search for “thatsmaths” at irishtimes.com].

Flag of the National Security Agency

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.

One-way Functions

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 1003? 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.

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, and by nobody else.

The RSA Encryption System

Ronald Rivest, Adi Shamir and Leonard Adleman at MIT in the 1970s.

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.

What is known at NSA? 

Modern cryptography depends on the assumption that nobody can determine prime factors 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 HQ 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 may not hear about it for some time, but the implications of such a development would be profound.