“Cryptography: How to Keep a Secret”
December 16, 2010
Modern cryptography, a key technology underlying secure Internet communications and many other facets of today’s information society, is one of the more spectacular applications of theoretical mathematics.
At the MAA Carriage House Distinguished Lecture on December 8, Alice Silverberg, professor of mathematics and computer science at the University of California, Irvine, gave an overview of the history of cryptography and explained some of the mathematics underlying it.
Cryptography, or secret writing, dates back at least as far as 1900 B.C.E., when an Egyptian used nonstandard hieroglyphs to hide a secret message in a carved monument. Nowadays, cryptography plays an important role not only in Internet security but also in FAA collision avoidance systems, mobile phones, flat-screen TVs, and some passports.
One of the oldest and most widely known cryptosystems is the Caesar shift, in which each letter is shifted ahead in the alphabet by the same number of letters. For example, ABACUS shifted three letters forward would become DEDFXV. The secret information needed to encode and decode messages in this system—that the shift is by three—is known as a key.
In a private-key cryptosystem, the same key is used both for encryption and decryption, so it must be agreed upon in advance and kept secret. Cryptographers long assumed that a private key would need to be exchanged before encoding a message, presenting practical limitations.
In a 1976 breakthrough, this assumption was turned on its head with the invention of public-key cryptography. Public-key cryptosystems use one-way functions—those that are easy to do, but hard to undo—to enable two people to exchange secret messages without having communicated beforehand. This arrangement is useful if, for instance, you want to make a secure purchase online with a credit card without first going to the store to create a shared private key.
The first such method, Diffie-Hellman key agreement, enables two people to create a shared private key over an insecure channel, using modular exponentiation as the one-way function. Silverberg explained that we all know modular arithmetic because we tell time. Arithmetic mod 12 is just like arithmetic on a 12-hour clock: 13 is the same as 1, 14 is 2, and so on.
To illustrate the method, Silverberg called upon the canonical Alice and Bob in her example.
In Diffie-Hellman key agreement, Alice and Bob have never communicated previously, Alice has a secret key a, and Bob has a different secret key b. They make x, m, xa (mod m), and xb (mod m) public. With sufficiently large numbers, it would be computationally infeasible for an eavesdropper to determine a, b, or xab (mod m) from this information, but Alice and Bob can easily find xab(mod m) using this information and their private keys. It becomes their shared private key. Silverberg guided the audience through a small example of these computations.
Several new methods improve upon Diffie-Hellman. Torus-based cryptosystems such as LUC, XTR, and CEILIDH—the last of which Silverberg cocreated and named for her cat—are more efficient versions of Diffie-Hellman based on algebraic tori. CEILIDH has appeared on the TV show NUMB3RS, for which Silverberg was a consultant (she wrote about her experience with the show in an MAA FOCUS article, “Alice in NUMB3Rland”).
Invented in 1985, elliptic-curve cryptography uses the same idea in a different context. Elliptic curves, a special type of plane curve, have an addition law: Two points on an elliptic curve add to a third point on an elliptic curve, and this operation has the usual properties of addition. Instead of repeated multiplication of numbers mod m, elliptic-curve cryptography uses repeated addition of points on elliptic curves mod m.
This one-way function is even harder to undo than the modular exponentiation used in Diffie-Hellman, making the same levels of security possible with smaller keys. Elliptic-curve cryptography is therefore widely used in constrained devices, such as mobile phones, smart cards, and even some passports to protect biometric data.
The techniques listed so far address communication between two people. In 2000, a new method, pairing-based cryptography, provided a public-key method for three people to communicate securely in one broadcast, using pairings on elliptic curves. We do not yet know if it is possible for four or more people to communicate securely in one broadcast without sharing keys beforehand, but Silverberg expects that doing so would involve different mathematics.
Like other public-key cryptosystems, pairing-based cryptography relies on the difficulty of undoing a one-way function. Some systems have undergone more scrutiny than others, so perhaps finding an easy way to undo the function is just around the corner. Or maybe not. If you learned enough number theory to undo these one-way functions easily, Silverberg said, “There are good and bad aspects of that, but at least you’d be very famous.” -by Rachel Kirsch
Silverberg's presentation was a part of the MAA's Distinguished Lecture Series, sponsored by the National Security Agency.
Photographs and audio by Laura McHugh