At what points do each of the four keys from the two key pairs get used?
Let Alice have a key pair (PubKeyA, PrivKeyA), where the first is public, the second private, and similarly for Bob (PubKeyB, PrivKeyB). Alice and Bob know each other's public keys in a reliable way (from a key server, or because they received them in person etc.) If we use RSA keys, e.g., then they could use just one pair, so I'll assume this first.
When Alice sends Bob a signed message (signing is optional in PGP, but good practice), the following happens, simplified:
- Alice generates a key K for some symmetric cipher algorithm, say AES (i.e. the program does, using a good random number generator, etc.)
- Alice encrypts the message M using K, to get AES-Enc(M,K).
- Alice encrypts K using PubkeyB, to get RSA-Enc(K, PubKeyB).
- The 2 parts RSA-Enc(K, PubKeyB) and AES-Enc(M) are combined in an unambiguous way (so they can be split later) into an encrypted message M' = Enc(M, K, PubKeyB).
- Alice uses her PrivKeyA to cryptographically sign M' (which mostly means hashing M' and "encrypting" the result with that private key, in the case of RSA), which gives us Sign(M',PrivKeyA)
- Enc(M, K, PubKeyB) and Sign(M',PrivKeyA) are combined in an unambiguous way into the message that Alice sends.
Note that we need a secure mode of operation to AES to encrypt M using K, a secure way to encrypt the key K using PubKeyB (using a secure padding scheme, like OAEP), a secure hash function and way to sign (also using a padding scheme) and a good file format to unambiguously pack all the data in. Read up on the standards involving them...
Bob does the following (simplified) when he receives the message:
- Split the message into M' = Enc(M, K, PubKeyB) and Sign(M', PrivKeyA).
- Check, using PubKeyA, that Sign(M', PrivKeyA) is a valid signature for M'. Stop if that fails. If it succeeds Bob is confident that M' is intact and indeed sent by Alice.
- Then split M' into RSA-Enc(K, PubKeyB) and AES-Enc(M).
- Using his PrivKeyB, decrypt K from RSA-Enc(K, PubKeyB) and PrivKeyB.
- Using K, decrypt M from AES-Enc(M) and K.
Now Bob has M too, and is confident it is the actual message Alice wanted to send, and was not tempered with in transit.
Like I said, the devil is in the details, but this is the essence of it.
Now, in practice, PGP creates 2 pairs per user, an encryption pair and a signing pair. Also the programs sends key-identifiers with the message to indicate which ones are used (in general, a user could have more public keys etc.)
Here's a mnemonic and metaphor for you.
Someone's public key is like their phone number. You have to have their phone number to call them and you use their phone number to call them. Other people use your number to call you.
From a crypto aspect, you encrypt to a public key and then decrypt with the private key.