Pretty Good Privacy, more commonly known as PGP, was developed by Phil Zimmerman in the late 1980s and early 1990s. In contrast to X.509 certificates, PGP is a very decentralized system with no CA. Each user has a certificate, but the trust in this certificate is certified to various degrees by other users. This creates a web of trust.

For example, if Alice knows Bob and can verify directly that his certificate is valid, then she signs his certificate with her public key. Charles trusts Alice and has her public key, and therefore can check that Alice’s signature on Bob’s certificate is valid. Charles then trusts Bob’s certificate. However, this does not mean that Charles trusts certificates that Bob signs – he trusts Bob’s public key. Bob could be gullible and sign every certificate that he encounters. His signature would be valid, but that does not mean that the certificate is.

Alice maintains a file with a keyring containing the trust levels Alice has in various people’s signatures. There are varying levels of trust that she can assign: no information, no trust, partial trust, and complete trust. When a certificate’s validity is being judged, the PGP program accepts certificates that are signed by someone Alice trusts, or a sufficient combination of partial trusts. Otherwise it alerts Alice and she needs to make a choice on whether to proceed.

The primary use of PGP is for authenticating and encrypting email. Suppose Alice receives an email asking for her bank account number so that Charles can transfer millions of dollars into her account. Alice wants to be sure that this email comes from Charles and not from Eve, who wants to use the account number to empty Alice’s account. In the unlikely case that this email actually comes from her trusted friend Charles, Alice sends her account information, but she should encrypt it so that Eve cannot intercept it and empty Alice’s account. Therefore, the first email needs authentication that proves that it comes from Charles, while the second needs encryption. There are also cases where both authentication and encryption are desirable. We’ll show how PGP handles these situations.

To keep the discussion consistent, we’ll always assume that Alice is sending a message to Bob. Alice’s RSA public key is $(n\text{,}e)$ and her private key is $d$.

Authentication.

1. Alice uses a hash function and computes the hash of the message.

2. Alice signs the hash by raising it to her secret decryption exponent $d\text{ mod }n$. The resulting hash code is put at the beginning of the message, which is sent to Bob.

3. Bob raises the hash code to Alice’s public RSA exponent $e$. The result is compared to the hash of the rest of the message.

4. If the result agrees with the hash, and if Bob trusts Alice’s public key, the message is accepted as coming from Alice.

   This authentication is the RSA signature method from Section 13.1. Note the role that trust plays. If Bob does not trust Alice’s public key as belonging to Alice, then he cannot be sure that the message did not come from Eve, with Eve’s signature in place of Alice’s.

Encryption.

1. Alice’s computer generates a random number, usually 128 bits, to be used as the session key for a symmetric private key encryption algorithm such as 3DES, IDEA, or CAST-128 (these last two are block ciphers using 128-bit keys).

2. Alice uses the symmetric algorithm with this session key to encrypt her message.

3. Alice encrypts the session key using Bob’s public key.

4. The encrypted key and the encrypted message are sent to Bob.

5. Bob uses his private RSA key to decrypt the session key. He then uses the session key to decrypt Alice’s message.

   The combination of a public key algorithm and a symmetric algorithm is used because encryption is generally faster with symmetric algorithms than with public key algorithms. Therefore, the public key algorithm RSA is used for the small encryption of the session key, and then the symmetric algorithm is used to encrypt the potentially much larger message.

Authentication and Encryption

1. Alice hashes her message and signs the hash to obtain the hash code, as in step (2) of the authentication procedure described previously. This hash code is put at the beginning of the message.

2. Alice produces a random 128-bit session key and uses a symmetric algorithm with this session key to encrypt the hash code together with the message, as in the encryption procedure described previously.

3. Alice uses Bob’s public key to encrypt the session key.

4. The encrypted session key and the encryption of the hash code and message are sent to Bob.

5. Bob uses his private key to decrypt the session key.

6. Bob uses the session key to obtain the hash code and message.

7. Bob verifies the signature by using Alice’s public key, as in the authentication procedure described previously.

   Of course, this procedure requires that Bob trusts Alice’s public key certificate. Also, the reason the signature is done before the encryption is so that Bob can discard the session key after decrypting and therefore store the plaintext message with its signature.

To set up a PGP certificate, Alice’s computer uses random input obtained from keystrokes, timing, mouse movements, etc. to find primes $p$, $q$ and then produce an RSA modulus $n=pq$ and encryption and decryption exponents $e$ and $d$. The numbers $n$ and $e$ are then Alice’s public key. Alice also chooses a secret passphrase. The secret key $d$ is stored securely in her computer. When the computer needs to use her private key, the computer asks her for her passphrase to be sure that Alice is the correct person. This prevents Eve from using Alice’s computer and pretending to be Alice. The advantage of the passphrase is that Alice is not required to memorize or type in the decryption exponent $d$, which is probably more than one hundred digits long.

In the preceding, we have used RSA for signatures and for encryption of the session keys. Other possibilities are allowed. For example, Diffie-Hellman can be used to establish the session key, and DSA can be used to sign the message.