17.6 Pretty Good Privacy
Pretty Good Privacy (PGP) is a security program that was created by Phil Zimmerman [17] and published in 1991 as freeofcharge shareware. It has since become the “de facto” standard for electronic mail (email) and file encryption. PGP, widely used as version 2.6, remained essentially unchanged until PGP version 5.0 (which is compatible with version 2.6) became available. Table 17.9 illustrates the algorithms used in versions 2.6, 5.0, and later.
Table 17.9 PGP 2.6 versus PGP 5.0 and Later
Function 
PGP Version 2.6 Algorithm Used [17] 
PGP Version 5.0 and Later Algorithm Used [18] 

Encryption of message using privatekey algorithm with privatesession key 
IDEA 
TripleDES, CAST, or IDEA 
Encryption of privatesession key with publickey algorithm 
RSA 
RSA or DiffieHellman (the Elgamal variation) 
Digital Signature 
RSA 
RSA and NIST^{1} Digital Signature Standard (DSS)^{2} 
Hash Function used for creating message digest for Digital Signatures 
MD5 
SHA1 
As listed in Table 17.9, PGP uses a variety of encryption algorithms, including both privatekey and publickeybased systems. A privatekey algorithm (with a new session key generated at each session) is used for encryption of the message. The privatekey algorithms offered by PGP are International Data Encryption Algorithm (IDEA), TripleDES (Data Encryption Standard), and CAST (named after the inventors Carlisle Adams and Stafford Tavares [19]). A publickey algorithm is used for the encryption of each session key. The publickey algorithms offered by PGP are the RSA algorithm, described in Section 17.5.3, and the DiffieHellman algorithm.
Publickey algorithms are also used for the creation of digital signatures. PGP version 5.0 uses the Digital Signature Algorithm (DSA) specified in the NIST Digital Signature Standard (DSS). PGP version 2.6 uses the RSA algorithm for its digital signatures. If the available channel is insecure for key exchange, it is safest to use a publickey algorithm. If a secure channel is available, then privatekey encryption is preferred, since it typically offers improved speed over publickey systems.
The technique for message encryption employed by PGP version 2.6 is illustrated in Figure 17.20. The plaintext is compressed with the ZIP algorithm prior to encryption. PGP uses the ZIP routine written by JeanLoup Gailly, Mark Alder, and Richard B. Wales [18]. If the compressed text is shorter than the uncompressed text, the compressed text will be encrypted; otherwise the uncompressed text is encrypted.
Small files (approximately 30 characters for ASCII files) will not benefit from compression. Additionally, PGP recognizes files previously compressed by popular compression routines, such as PKZIP, and will not attempt to compress them. Data compression removes redundant character strings in a file and produces a more uniform distribution of characters. Compression provides a shorter file to encrypt and decrypt (which reduces the time needed to encrypt, decrypt, and transmit a file), but compression is also advantageous because it can hinder some cryptanalytic attacks that exploit redundancy. If compression is performed on a file, it should occur prior to encryption (never afterwards). Why is that a good rule to follow? Because a good encryption algorithm yields ciphertext with a nearly statistically uniform distribution of characters; therefore, if a data compression algorithm came after such encryption, it should result in no compression at all. If any ciphertext can be compressed, then the encryption algorithm that formed that ciphertext was a poor algorithm. A compression algorithm should be unable to find redundant patterns in text that was encrypted by a good encryption algorithm.
As shown in Figure 17.20, PGP Version 2.6 begins file encryption by creating a 128bit session key using a pseudorandom number generator. The compressed plaintext file is then encrypted with the IDEA privatekey algorithm using this random session key. The random session key is then encrypted by the RSA publickey algorithm using the recipient’s public key. The RSAencrypted session key and the IDEAencrypted file are sent to the recipient. When the recipient needs to read the file, the encrypted session key is first decrypted with RSA using the recipient’s private key. The ciphertext file is then decrypted with IDEA using the decrypted session key. After uncompression, the recipient can read the plaintext file.
17.6.1 TripleDES, CAST, and IDEA
As listed in Table 17.9, PGP offers three block ciphers for message encryption, TripleDES, CAST, and IDEA. All three ciphers operate on 64bit blocks of plaintext and ciphertext. TripleDES has a key size of 168bits, while CAST and IDEA use key lengths of 128 bits.
17.6.1.1 Description of TripleDES
The Data Encryption Standard (DES) described in Section 17.3.5 has been used since the late 1970s, but some have worried about its security because of its relatively small key size (56 bits). With TripleDES, the message to be encrypted is run through the DES algorithm 3 times (the second DES operation is run in decrypt mode); each operation is performed with a different 56bit key. As illustrated in Figure 17.21, this gives the effect of a 168bit key length.
17.6.1.2 Description of CAST
CAST is a family of block ciphers developed by Adams and Tavares [19]. PGP version 5.0 uses a version of CAST known as CAST5, or CAST128. This version has a block size of 64bits and a key length of 128bits. The CAST algorithm uses six Sboxes with an 8bit input and a 32bit output. By comparison, DES uses eight Sboxes with a 6bit input and a 4bit output. The Sboxes in Cast128 were designed to provide highly nonlinear transformations, making this algorithm particularly resistant to cryptanalysis [11].
17.6.1.3 Description of IDEA
The International Data Encryption Algorithm (IDEA) is a block cipher designed by Xuejia Lai and James Massey [19]. It is a 64bit iterative block cipher (involving eight iterations or rounds) with a 128bit key. The security of IDEA relies on the use of three types of arithmetic operations on 16bit words. The operations are addition modulo 2^{16}, multiplication modulo 2^{16} + 1, and bitwise exclusiveOR (XOR). The 128bit key is used for the iterated encryption and decryption in a reordered fashion. As shown in Table 17.10, the original key K_{0} is divided into eight 16bit subkeys Z_{x}^{(R)}, where x is the subkey number of the round R. Six of these subkeys are used in round 1, and the remaining two are used in round 2. K_{0} is then rotated 25 bits to the left yielding K_{1}, which is in turn divided into eight subkeys; the first 4 of these subkeys are used in round 2, and the last four in round 3. The process continues, as shown in Table 17.10, yielding a total of 52 subkeys.
Table 17.10 IDEA formation of Subkeys
128bit key (divided into eight 16bit subkeys) 
Bit string from which keys are derived 

Z_{1}^{1} Z_{2}^{1} Z_{3}^{1} Z_{4}^{1} Z_{5}^{1} Z_{6}^{1} Z_{1}^{2} Z_{2}^{2} 
K_{0} = Original 128bit key 
Z_{3}^{2} Z_{4}^{2} Z_{5}^{2} Z_{6}^{2} Z_{1}^{3} Z_{2}^{3} Z_{3}^{3} Z_{4}^{3} 
K_{1} = 25bit rotation of K_{0} 
Z_{5}^{3} Z_{6}^{3} Z_{1}^{4} Z_{2}^{4} Z_{3}^{4} Z_{4}^{4} Z_{5}^{4} Z_{6}^{4} 
K_{2} = 25bit rotation of K_{1} 
Z_{1}^{5} Z_{2}^{5} Z_{3}^{5} Z_{4}^{5} Z_{5}^{5} Z_{6}^{5} Z_{1}^{6} Z_{2}^{6} 
K_{3} = 25bit rotation of K_{2} 
Z_{3}^{6} Z_{4}^{6} Z_{5}^{6} Z_{6}^{6} Z_{1}^{7} Z_{2}^{7} Z_{3}^{7} Z_{4}^{7} 
K_{4} = 25bit rotation of K_{3} 
Z_{5}^{7} Z_{6}^{7} Z_{1}^{8} Z_{2}^{8} Z_{3}^{8} Z_{4}^{8} Z_{5}^{8} Z_{6}^{8} 
K_{5} = 25bit rotation of K 
_{4} Z_{1}^{out} Z_{2}^{out} Z_{3}^{out} Z_{4}^{out} 
First 64 bits of K_{6} where K_{6} = 25bit rotation of K_{5} 
The subkey schedule for each round is listed in Table 17.11 for both encryption and decryption rounds. Decryption is carried out in the same manner as encryption. The decryption subkeys are calculated from the encryption subkeys, as shown in Table 17.11, where it is seen that the decryption subkeys are either the additive or multiplicative inverses of the encryption subkeys.
Table 17.11 IDEA Subkey Schedule
Round 
Set of Encryption Subkeys 
Set of Decryption Subkeys 

1 
Z_{1}^{1} Z_{2}^{1} Z_{3}^{1} Z_{4}^{1} Z_{5}^{1} Z_{6}^{1} 
(Z_{1}^{out})^{ 1}  Z_{2}^{out}  Z_{3}^{out} (Z_{4}^{out}) ^{ 1} Z_{5}^{8} Z_{6}^{8} 
2 
Z_{1}^{2} Z_{2}^{2} Z_{3}^{2} Z_{4}^{2} Z_{5}^{2} Z_{6}^{2} 
(Z_{1}^{8})^{ 1}  Z_{2}^{8}  Z_{3}^{8} (Z_{4}^{8})^{ 1} Z_{5}^{7} Z_{6}^{7} 
3 
Z_{1}^{3} Z_{2}^{3} Z_{3}^{3} Z_{4}^{3} Z_{5}^{3} Z_{6}^{3} 
(Z_{1}^{7})^{ 1}  Z_{2}^{7}  Z_{3}^{7} (Z_{4}^{7})^{ 1} Z_{5}^{6} Z_{6}^{6} 
4 
Z_{1}^{4} Z_{2}^{4} Z_{3}^{4} Z_{4}^{4} Z_{5}^{4} Z_{6}^{4} 
(Z_{1}^{6})^{ 1}  Z_{2}^{6} Z_{3}^{6} (Z_{4}^{6})^{ 1} Z_{5}^{5} Z_{6}^{5} 
5 
Z_{1}^{5} Z_{2}^{5} Z_{3}^{5} Z_{4}^{5} Z_{5}^{5}Z_{6}^{5} 
(Z_{1}^{5})^{ 1}  Z_{2}^{5}  Z_{3}^{5} (Z_{4}^{5})^{ 1} Z_{5}^{4} Z_{6}^{4} 
6 
Z_{1}^{6} Z_{2}^{6} Z_{3}^{6} Z_{4}^{6} Z_{5}^{6} Z_{6}^{6} 
(Z_{1}^{4})^{ 1}  Z_{2}^{4}  Z_{3}^{4} (Z_{4}^{4})^{ 1} Z_{5}^{3} Z_{6}^{3} 
7 
Z_{1}^{7} Z_{2}^{7} Z_{3}^{7} Z_{4}^{7} Z_{5}^{7} Z_{6}^{7} 
(Z_{1}^{3})^{ 1} Z_{2}^{3}  Z_{3}^{3} (Z_{4}^{3})^{ 1} Z_{5}^{2} Z_{6}^{2} 
8 
Z_{1}^{8} Z_{2}^{8} Z_{3}^{8} Z_{4}^{8} Z_{5}^{8} Z_{6}^{8} 
(Z_{1}^{2})^{ 1}  Z_{2}^{2}  Z_{3}^{2} (Z_{4}^{2})^{ 1} Z_{5}^{1} Z_{6}^{1} 
Output 
Z_{1}^{out} Z_{2}^{out} Z_{3}^{out} Z_{4}^{out} 
(Z_{1}^{1})^{ 1}  Z_{2}^{1}  Z_{3}^{1} (Z_{4}^{1})^{ 1} 
Transformation 
The message is divided into 64bit data blocks. These blocks are then divided into four 16bit subblocks: M_{1}, M_{2}, M_{3}, and M_{4}. A sequence of such four subblocks becomes the input to the first round of IDEA algorithm. This data is manipulated for a total of eight rounds. Each round uses a different set of six subkeys as specified in Table 17.11. After a round, the second and third 16bit data subblocks are swapped. After the completion of the eighth round, the four subblocks are manipulated in a final output transformation. For the representation of Z_{x}^{(}R) shown in Tables 17.10 and 17.11, the round number is shown without parentheses for ease of notation.
Each round consists of the steps shown in Table 17.12. The final values from steps 11–14 form the output of the round. The two inner 16bit data subblocks (except for the last round) are swapped, and then these four subblocks are the input to the next round. This technique continues for a total of 8 rounds. After round 8, the final output transformation is as follows:
Table 17.12 IDEA Operational Steps in Each Round

17.6.2 DiffieHellman (Elgamal Variation) and RSA
For encryption of the session key, PGP offers a choice of two publickey encryption algorithms, RSA and the DiffieHellman (Elgamal variation) protocol. PGP allows for key sizes of 1024 to 4096 bits for RSA or DiffieHellman algorithms. The key size of 1024 bits is considered safe for exchanging most information. The security of the RSA algorithm (see Section 17.5.3) is based on the difficulty of factoring large integers.
The DiffieHellman protocol was developed by Whitfield Diffie, Martin E. Hellman, and Ralph C. Merkle in 1976 [19, 20] for publickey exchange over an insecure channel. It is based on the difficulty of the discrete logarithm problem for finite fields [21]. It assumes that it is computationally infeasible to compute g^{ab} knowing only g^{a} and g^{b}. U.S. Patent 4,200,770, which expired in 1997, covers the DiffieHellman protocol and variations such as Elgamal. The Elgamal variation, which was developed by Taher Elgamal, extends the DiffieHellman protocol for message encryption. PGP employs the Elgamal variation of DiffieHellman for the encryption of the sessionkey.
17.6.2.1 Description of DiffieHellman, Elgamal Variant:
The protocol has twosystem parameter n and g that are both public. Parameter n is a large prime number, and parameter g is an integer less than n that has the following property: for every number p between 1 and n  1 inclusive, there is a power k of g such that g^{k} = p mod n. The Elgamal encryption scheme [19, 21] that allows user B to send a message to user A is described below:
User A randomly chooses a large integer, a (this is user A’s private key).
User A’s public key is computed as: y = g^{a} mod n.
User B wishes to send a message M to user A. User B first generates a random number k that is less than n.
User B computes the following:
User B sends the ciphertext (y_{1}, y_{2}) to user A.
Upon receiving ciphertext (y_{1}, y_{2}), user A computes the plaintext message M as follows:
17.6.3 PGP Message Encryption
The privatekey algorithms that PGP uses for message encryption were presented in Section 17.6.1. The publickey algorithms that PGP uses to encrypt the privatesession key were presented in Section 17.6.2. The next example combines the two types of algorithms to illustrate the PGP encryption technique shown in Figure 17.20.
17.6.4 PGP Authentication and Signature
The public key algorithms can be used to authenticate or “sign” a message. As illustrated in Figure 17.18, a sender can encrypt a document with his private key (which no one else has access to) prior to encrypting it with the recipient’s public
Equal? If yes, this verifies that the sender is the owner of the public key used and that the message arrived uncorrupted key. The recipient must first use his private key to decrypt the message, followed by a second decryption using the sender’s public key. This technique encrypts the message for secrecy and also provides authentication of the sender.
Because of the slowness of publickey algorithms, PGP allows for a different method of authenticating a sender. Instead of the timeconsuming process of encrypting the entire plaintext message, the PGP approach encrypts a fixedlength message digest created with a oneway hash function. The encryption of the message digest is performed using a publickey algorithm. This method is known as a digital signature and is shown in Figure 17.22. A digital signature is used to provide authentication of both the sender and the message. Authentication of the message provides a verification that the message was not altered in some way. Using this technique, if a message has been altered in any way (i.e. by a forger), its message digest will be different.
PGP version 2.6 uses the MD5 (Message Digest 5) algorithm to create a 128bit message digest (or hash value) of the plaintext. This hash value is then encrypted with the sender’s private key and sent with the plaintext. When the recipient receives the message, he will first decrypt the message digest with the sender’s public key. The recipient will then apply the hash function to the plaintext and compare the two message digests. If they match, the signature is valid. In Figure 17.22, the message is sent without encryption (as plaintext), but it may be encrypted by the method illustrated in Figure 17.20.
17.6.4.1 MD5 and SHA1
MD5 and SHA1 are hash functions. A hash function H(x) takes an input and returns a fixedsize string h, called the hash value (also known as a message digest). A cryptographic hash function has the following properties:
The output length is fixed.
The hash value is relatively simple to compute.
The function is one way—in other words, it is hard to invert. If given a hash value h, it is computationally infeasible to find the function’s input x.
The function is collision free. A collisionfree hash function is a function for which it is infeasible that two different messages will create the same hash value.
The MD5 algorithm used in PGP version 2.6 creates a 128bit message digest. The MD5 algorithm processes the text in 512bit blocks through four rounds of data manipulation. Each round uses a different nonlinear function that consists of the logical operators AND, OR, NOT or XOR. Each function is performed 16 times in a round. Bit shifts and scalar additions are also performed in each round [19]. Hans Dobbertin [18] has determined that collisions may exist in MD5. Because of this potential weakness, the PGP specification recommends using the Digital Signature Standard (DSS). DSS uses the SHA1 (Secure Hash Algorithm1) algorithm. The SHA1 algorithm takes a message of less than 2^{64} bits in length and produces a 160bit message digest. SHA1 is similar to MD5 in that it uses a different nonlinear function in each of its 4 rounds. In SHA1, each function is performed 20 times per round. SHA1 also uses various scalar additions and bit shifting. The algorithm is slightly slower than MD5 but the larger message digest (160bit versus 128 bit) makes it more secure against bruteforce attacks [19]. A bruteforce attack consists of trying many input combinations in an attempt to match the message digest under attack.
17.6.4.2 Digital Signature Standard and RSA
For digital signatures, PGP version 2.6 uses the RSA algorithm for encryption of the hash value produced by the MD5 function; however, versions 5.0 and later adhere to the NIST Digital Signature Standard (DSS) [22]. The NIST DSS requires the use of the SHA1 hash function. The hash value is then encrypted using the Digital Standard Algorithm (DSA). Like the DiffieHellman protocol, DSA is based on the discrete logarithm problem. (Reference [22] contains a detailed description of DSA.)