From Euclid and Euler to public-key codes


An extensive web reference for public-key codes and their mathematics is A Short Course in Cryptography posted by Frank Beatrous (University of Pittsburgh). For more information on prime numbers see The Prime Pages maintained by Chris Caldwell (University of Tennessee, Martin). See also Frequently Asked Questions About Today's Cryptography on the RSA Laboratories' homepage.

Last January, an item in Science's NetWatch (January 29; 283: 599b) featured 16-year old Sarah Flannery of Blarney, County Cork, Ireland. She had won a Young Scientist contest earlier that month with her project: "Cryptography--A new algorithm versus the RSA." Science goes on to explain: ``The RSA, invented in 1977, is a mathematical technique used widely to encrypt e-mail and credit card transactions. Like RSA, Flannery's code is a public key method--part of the key is public, rather than kept secret by the two people using it--and involves factoring two prime numbers.''

The basic mathematical phenomenon that powers the RSA codes is the fact that multiplications are like omelets:

it is easier to do a multiplication than to undo it.

For example, it is easy to check that 193 and 223 are prime numbers, and to compute their product 43039. It is considerably more difficult, given the number 43039 and no other information, to discover that it factors as 193 times 223. Try to factor 42881.

Need to review?

The goal of this column is to describe exactly what these statements mean, and how this mathematical phenomenon can be implemented into secure, public-key codes.

--Tony Phillips

© copyright 1999, American Mathematical Society.