A mathematical conundrum is the key to cryptography

Cryptography depends on the assumption that nobody can factor prime numbers efficiently. Is this assumption safe?

Photograph: iStock

Photograph: iStock

 

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
The Irish Times Logo
Commenting on The Irish Times has changed. To comment you must now be an Irish Times subscriber.
SUBSCRIBE
GO BACK
Error Image
The account details entered are not currently associated with an Irish Times subscription. Please subscribe to sign in to comment.
Comment Sign In

Forgot password?
The Irish Times Logo
Thank you
You should receive instructions for resetting your password. When you have reset your password, you can Sign In.
The Irish Times Logo
Please choose a screen name. This name will appear beside any comments you post. Your screen name should follow the standards set out in our community standards.
Screen Name Selection

Hello

Please choose a screen name. This name will appear beside any comments you post. Your screen name should follow the standards set out in our community standards.

The Irish Times Logo
Commenting on The Irish Times has changed. To comment you must now be an Irish Times subscriber.
SUBSCRIBE
Forgot Password
Please enter your email address so we can send you a link to reset your password.

Sign In

Your Comments
We reserve the right to remove any content at any time from this Community, including without limitation if it violates the Community Standards. We ask that you report content that you in good faith believe violates the above rules by clicking the Flag link next to the offending comment or by filling out this form. New comments are only accepted for 3 days from the date of publication.