Enough advertising; now we describe a public-key cryptosystem. The system we describe is a slight variant of one proposed by Tahir El Gamal. This was not the first such cryptosystem proposed--the RSA cryptosystem was first--but it is easy to understand once you have understood exponential key agreement, which we now review.
Let m be a system-wide modulus. In the key agreement protocol,
Alice chooses a secret random number A, and sends 
to
Bob. Bob similarly chooses a secret random number B, and sends 
to Alice. Then they are both able to calculate a key
. Alice calculates this key by taking the number
sent to her by Bob, 
, and raising it to the power of A. Bob
calculates the same key by taking the number sent to him by Alice,
, and raising it to the power of B.
The essential idea of El Gamal's scheme is to take a piece of the key
agreement protocol and make it instead part of the set-up. In
particular, during the set-up Bob chooses a number BobSecret to
be used as his secret key. He calculates 
and publicizes this number, which we shall call
BobPublic. Now when Alice wants to send an encrypted message to
Bob, she first looks up Bob's public key, and finds that it is the number
BobPublic. Next she essentially follows the key agreement protocol
but instead of waiting for Bob to send his BobPart, she uses
BobPublic as BobPart. That is, Alice chooses a random
number A, then calculates 
. Then
she calculates the key by raising BobPublic to the power A
(in modular arithmetic). She encrypts her cleartext using that key
in the manner of a one-time pad, by adding the cleartext to the key
modulo m. Finally, she sends Bob a two-part message. The first
part is AlicePart, and the second part is the cyphertext.
Bob can determine the key, essentially as he does in the exponential key agreement protocol, by raising AlicePart to the power of BobSecret. He then uses this key to decrypt the cyphertext, obtaining the cleartext.
The above description may be confusing because there are so many numbers that might be described as keys. There is BobSecret, which is Bob's secret key. There is BobPublic, which is Bob's public key. All well and good; we knew that public-key cryptography involved two keys, one public and one secret. But there is also the key finally used by Alice to encrypt her cleartext; the same key is used by Bob to decrypt. What is this third key doing in our cryptosystem? It is sort of a ``disposable'' key, used just once to encrypt just one message. While essential to the functioning of the El Gamal cryptosystem, it does not appear in other public-key cryptosystems and does not play a role in the concept of a public-key cryptosystem.
Think of public-key cryptosystems as automobiles. There is essentially one way to drive an automobile, regardless of whether it runs on gasoline or on electricity. In a gas-driven auto, the carburetor is an essential part, but it has nothing to do with the concept of an auto. Similarly, every public-key cryptosystem has a public key and a secret key, and from a high-level view these are used in the same way in every public-key cryptosystem, but the details differ. The disposable key is in this sense like the carburetor.
The most famous (and the first) public-key cryptosystem proposed, the RSA cryptosystem, doesn't involve a disposable key. Indeed, RSA is conceptually simpler than El Gamal, but is based on slightly more sophisticated mathematics. We describe the RSA cryptosystem in a subsequent handout.
It is interesting that Diffie and Hellman, who discovered both exponential key agreement and the concept of a public-key cryptosystem, failed to discover the El Gamal system, which is so similar to key agreement. The reason may be that Diffie and Hellman thought about public-key cryptography in terms of a mathematical notion called a trap-door one-way function, and were looking for a cryptosystem that was based on that notion. El Gamal's system is not based on that idea. For this reason, perhaps, it was not in Diffie and Hellman's line of sight. We explain the notion of a trap-door one-way function in the handout on RSA.