Let's say we have the following:
How would Bob and Alice use PGP or alternative public-key cryptography system to meet their communication needs?
Per the stipulation that Alice and Bob may conduct a private initial exchange in person (or through some other secure channel they have been previously using) Bob simply generates a separate Private-Public key pair for each of them. He can then hand Alice her private key and they can proceed to do normal public key cryptography from then on as if Alice had constructed her own Private-Public key pair.
Merkle's initial scheme for "Secure Communication over Insecure Channels," the first approximation of public key cryptography, could solve exactly this problem without even the need for the initial secure exchange of information.
Here is how Bruce Schneier summarized the scheme in his book "Applied Cryptography":
Merkle's technique was based on “puzzles” that were easier to solve for the sender and receiver than for an eavesdropper. Here's how Alice sends an encrypted message to Bob without first having to exchange a key with him.
- Bob generates 2^20, or about a million, messages of the form: “This is puzzle number x. This is the secret key number y,” where x is a random number and y is a random secret key. Both x and y are different for each message. Using a symmetric algorithm, he encrypts each message with a different 20-bit key and sends them all to Alice.
- Alice chooses one message at random and performs a brute-force attack to recover the plaintext. This is a large, but not impossible, amount of work.
- Alice encrypts her secret message with the key she recovered and some symmetric algorithm, and sends it to Bob along with x.
- Bob knows which secret key y he encrypts in message x, so he can decrypt the message.
