Public Key Cryptography

Introduction

The concept of Public Key Cryptography (PKC) is that you should be able to tell everyone and anyone how to scramble a message to be sent to you, while neverthess, you are the only one who can undo the scrambling to recover the message. How is this possible? In principle, it isn't: eavesdroppers could "simply" apply your scrambling method to every possible message until they find the one that produces the same scrambled results.

However, one of the important aspects of computer science is the idea that just because a computation is possible, doesn't mean it's practical. One of the main projects of computer science is to show that given a certain speed of computer, and a certain set of possible problems, it is simply not possible to program the computer to find the answer in less than a certain amount of time in every case, or even most cases. If it would take a supercomputer a million years to find the answer (assuming no hints are given), then you can feel somewhat safe in the assumption that the answer -- if you happen to have worked backwards to rig up the problem -- will remain yours alone.

The embarrassing part of this story is that despite several decades of effort, computer scientists have still not definitively shown that the most important classes of problems which are believed to be computationally difficult, really are computationally difficult. The problem on which we will base PKC -- factoring integers into primes -- is in this sad category of problems believed, but not absolutely known, to be difficult to solve. Since the entire structure of electronic commerce will depend on the security provided by PKC, the lack of an absolutely rigorous mathematical proof suddenly becomes remarkably relevant!

The Woodrow Wilson Leadership Program in Mathematics lpt@www.woodrow.org
The Woodrow Wilson National Fellowship Foundation webmaster@woodrow.org
CN 5281, Princeton NJ 08543-5281 Tel:(609)452-7007 Fax:(609)452-0066