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:
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.