Engines of Our Ingenuity

No. 1994:
THEORY AND ENCRYPTION

by

John H. Lienhard presents guest Andrew Boyd

Today, guest scientist Andrew Boyd sends secret messages. The University of Houston presents this series, about the machines that make our civilization run, and the people whose ingenuity created them.

"I shop, therefore I am," reads a popular bumper sticker. Perhaps Descartes, who first uttered the more famous version of this phrase, would not've been amused at the connection with shopping. Yet our ability to buy things on-line depends upon mathematics that was once considered hopelessly devoid of any practical use.

Encryption is the process of scrambling a message so that you need a secret code to unscramble it. Author Marcus du Sautoy observes that, for much of history, encryption was of interest only to govern-ments for sending secret communications. But this has drastically changed with the rise of electronic commerce. When we type our credit card number into the computer, we don't want someone stealing it as it travels through the Internet.

Encryption is like locking a box. Imagine I want you to send me a secret message. If I have two keys, I can deliver one to you along with the box. You then place a message inside, lock it, and send it back to me without fear of someone else reading it. For years, this is how encryption methods worked. The problem is: how do I get your key to you safely in the first place? Someone might steal it along the way and make a copy. After that, the perpetrator could read anything you sent to me.

The answer arrived in 1976 with a paper out of Stanford. It contained a simple yet ingenious idea: construct a key that can lock the box but can't unlock it. Now I don't care who has a copy of your "locking" key. As long as I keep my "unlocking" key safely tucked away, no one can see inside the box except me.

Clever as this idea was, no one could immediately figure out how to construct such a key for computers. If someone has a locking key -- really just a method for scrambling a message -- it seems they must know how to unscramble the message; simply undo what was done to scramble it in the first place.

The last piece of the puzzle came together in a flash of insight from a group at MIT. Their keys are built with results from abstract number theory. Number theory dates back to the ancient Greeks. It deals with the most basic building blocks in all of math -- the whole numbers -- and it gives rise to an amazing collection of difficult and intriguingly beautiful results. (Beauty is the measure of importance in number theory, since mathematicians regard it as much an intellectual/artistic endeavor, as sculpting or writing music.

So it's ironic that number theory plays such a huge role in our lives. Every day, countless billions of dollars in transactions take place on the Internet; transactions that vitally depend on secure communication. Business leaders look to mathematicians to tell them everything is okay, and so far the answer is a resounding "Yes!"

But what about the future? Number theory surely has more secrets to reveal -- secrets that could still topple the world of electronic commerce. And so the hard world of practical business continues its struggles -- upon playing fields of airy abstraction.

I'm Andy Boyd, at the University of Houston, where we're interested in the way inventive minds work.

(Theme music)


Dr. Andrew Boyd is Chief Scientist and Senior Vice President at PROS, a provider of provider of pricing and revenue optimization solutions. Dr. Boyd received his A.B. with Honors at Oberlin College with majors in Mathematics and Economics in 1981, and his Ph.D. in Operations Research from MIT in 1987. Prior to joining PROS, he enjoyed a successful ten year career as a university professor.

This essay was inspired by Marcus du Sautoy, The Music of the Primes, (New York, Harper Collins, 2003).

The breakthrough paper by Stanford researchers is W. Diffie and M. Hellman, New directions in cryptography. IEEE Transactions on Information Theory Vol. 22 (1976), pp. 644-654. See also: http://www.rsasecurity.com/rsalabs/node.asp?id=2248 .

The encryption method from MIT, known as the RSA algorithm after its progenitors Rivest, Shamir, and Adleman, is described in http://en.wikipedia.org/wiki/RSA .

For general information on encryption, see http://en.wikipedia.org/wiki/Encryption .






The Engines of Our Ingenuity is Copyright © 1988-2005 by John H. Lienhard.