Home > Articles

  • Print
  • + Share This
This chapter is from the book

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 free-of-charge shareware. It has since become the “de facto” standard for electronic mail (e-mail) 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 private-key algorithm with private-session key

IDEA

Triple-DES, CAST, or IDEA

Encryption of private-session key with public-key algorithm

RSA

RSA or Diffie-Hellman (the Elgamal variation)

Digital Signature

RSA

RSA and NIST1 Digital Signature Standard (DSS)2

Hash Function used for creating message digest for Digital Signatures

MD5

SHA-1

As listed in Table 17.9, PGP uses a variety of encryption algorithms, including both private-key- and public-key-based systems. A private-key algorithm (with a new session key generated at each session) is used for encryption of the message. The private-key algorithms offered by PGP are International Data Encryption Algorithm (IDEA), Triple-DES (Data Encryption Standard), and CAST (named after the inventors Carlisle Adams and Stafford Tavares [19]). A public-key algorithm is used for the encryption of each session key. The public-key algorithms offered by PGP are the RSA algorithm, described in Section 17.5.3, and the Diffie-Hellman algorithm.

Public-key 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 public-key algorithm. If a secure channel is available, then private-key encryption is preferred, since it typically offers improved speed over public-key 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 Jean-Loup 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 128-bit session key using a pseudo-random number generator. The compressed plaintext file is then encrypted with the IDEA private-key algorithm using this random session key. The random session key is then encrypted by the RSA public-key algorithm using the recipient’s public key. The RSA-encrypted session key and the IDEA-encrypted 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 Triple-DES, CAST, and IDEA

As listed in Table 17.9, PGP offers three block ciphers for message encryption, Triple-DES, CAST, and IDEA. All three ciphers operate on 64-bit blocks of plaintext and ciphertext. Triple-DES has a key size of 168-bits, while CAST and IDEA use key lengths of 128 bits.

17.6.1.1 Description of Triple-DES

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 Triple-DES, 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 56-bit key. As illustrated in Figure 17.21, this gives the effect of a 168-bit 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 CAST-128. This version has a block size of 64-bits and a key length of 128-bits. The CAST algorithm uses six S-boxes with an 8-bit input and a 32-bit output. By comparison, DES uses eight S-boxes with a 6-bit input and a 4-bit output. The S-boxes in Cast-128 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 64-bit iterative block cipher (involving eight iterations or rounds) with a 128-bit key. The security of IDEA relies on the use of three types of arithmetic operations on 16-bit words. The operations are addition modulo 216, multiplication modulo 216 + 1, and bit-wise exclusive-OR (XOR). The 128-bit key is used for the iterated encryption and decryption in a reordered fashion. As shown in Table 17.10, the original key K0 is divided into eight 16-bit subkeys Zx(R), where x is the subkey number of the round R. Six of these sub-keys are used in round 1, and the remaining two are used in round 2. K0 is then rotated 25 bits to the left yielding K1, 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

128-bit key (divided into eight 16-bit subkeys)

Bit string from which keys are derived

Z11 Z21 Z31 Z41 Z51 Z61 Z12 Z22

K0 = Original 128-bit key

Z32 Z42 Z52 Z62 Z13 Z23 Z33 Z43

K1 = 25-bit rotation of K0

Z53 Z63 Z14 Z24 Z34 Z44 Z54 Z64

K2 = 25-bit rotation of K1

Z15 Z25 Z35 Z45 Z55 Z65 Z16 Z26

K3 = 25-bit rotation of K2

Z36 Z46 Z56 Z66 Z17 Z27 Z37 Z47

K4 = 25-bit rotation of K3

Z57 Z67 Z18 Z28 Z38 Z48 Z58 Z68

K5 = 25-bit rotation of K

4 Z1out Z2out Z3out Z4out

First 64 bits of K6 where K6 = 25-bit rotation of K5

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

Z11 Z21 Z31 Z41 Z51 Z61

(Z1out)- 1 - Z2out - Z3out (Z4out) - 1 Z58 Z68

2

Z12 Z22 Z32 Z42 Z52 Z62

(Z18)- 1 - Z28 - Z38 (Z48)- 1 Z57 Z67

3

Z13 Z23 Z33 Z43 Z53 Z63

(Z17)- 1 - Z27 - Z37 (Z47)- 1 Z56 Z66

4

Z14 Z24 Z34 Z44 Z54 Z64

(Z16)- 1 - Z26 -Z36 (Z46)- 1 Z55 Z65

5

Z15 Z25 Z35 Z45 Z55Z65

(Z15)- 1 - Z25 - Z35 (Z45)- 1 Z54 Z64

6

Z16 Z26 Z36 Z46 Z56 Z66

(Z14)- 1 - Z24 - Z34 (Z44)- 1 Z53 Z63

7

Z17 Z27 Z37 Z47 Z57 Z67

(Z13)- 1 Z23 - Z33 (Z43)- 1 Z52 Z62

8

Z18 Z28 Z38 Z48 Z58 Z68

(Z12)- 1 - Z22 - Z32 (Z42)- 1 Z51 Z61

Output

Z1out Z2out Z3out Z4out

(Z11)- 1 - Z21 - Z31 (Z41)- 1

Transformation

The message is divided into 64-bit data blocks. These blocks are then divided into four 16-bit subblocks: M1, M2, M3, and M4. 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 16-bit 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 Zx(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 16-bit 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

  1. M1 × Z1(R)

  2. M2 + Z2(R)

  3. M3 + Z3(R)

  4. M4 × Z4(R)

  5. XOR3 the results from steps 1 and 3.

  6. XOR the results from steps 2 and 4.

  7. Results from step 5 and Z5(R) are multiplied.

  8. Results from step 6 and 7 are added.

  9. Results from step 8 and Z6(R) are multiplied.

  10. Results from steps 7 and 9 are added.

  11. XOR the results from steps 1 and 9.

  12. XOR the results from steps 3 and 9.

  13. XOR the results from steps 2 and 10.

  14. XOR the results from steps 4 and 10.

17.6.2 Diffie-Hellman (Elgamal Variation) and RSA

For encryption of the session key, PGP offers a choice of two public-key encryption algorithms, RSA and the Diffie-Hellman (Elgamal variation) protocol. PGP allows for key sizes of 1024 to 4096 bits for RSA or Diffie-Hellman 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 Diffie-Hellman protocol was developed by Whitfield Diffie, Martin E. Hellman, and Ralph C. Merkle in 1976 [19, 20] for public-key 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 gab knowing only ga and gb. U.S. Patent 4,200,770, which expired in 1997, covers the Diffie-Hellman protocol and variations such as Elgamal. The Elgamal variation, which was developed by Taher Elgamal, extends the Diffie-Hellman protocol for message encryption. PGP employs the Elgamal variation of Diffie-Hellman for the encryption of the session-key.

17.6.2.1 Description of Diffie-Hellman, Elgamal Variant:

The protocol has two-system 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 gk = 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 = ga 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:

    Image

  • User B sends the ciphertext (y1, y2) to user A.

  • Upon receiving ciphertext (y1, y2), user A computes the plaintext message M as follows:

    Image

17.6.3 PGP Message Encryption

The private-key algorithms that PGP uses for message encryption were presented in Section 17.6.1. The public-key algorithms that PGP uses to encrypt the private-session 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 public-key algorithms, PGP allows for a different method of authenticating a sender. Instead of the time-consuming process of encrypting the entire plaintext message, the PGP approach encrypts a fixed-length message digest created with a one-way hash function. The encryption of the message digest is performed using a public-key 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 128-bit 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 SHA-1

MD5 and SHA-1 are hash functions. A hash function H(x) takes an input and returns a fixed-size string h, called the hash value (also known as a message digest). A cryptographic hash function has the following properties:

  1. The output length is fixed.

  2. The hash value is relatively simple to compute.

  3. 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.

  4. The function is collision free. A collision-free 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 128-bit message digest. The MD5 algorithm processes the text in 512-bit 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 SHA-1 (Secure Hash Algorithm-1) algorithm. The SHA-1 algorithm takes a message of less than 264 bits in length and produces a 160-bit message digest. SHA-1 is similar to MD5 in that it uses a different nonlinear function in each of its 4 rounds. In SHA-1, each function is performed 20 times per round. SHA-1 also uses various scalar additions and bit shifting. The algorithm is slightly slower than MD5 but the larger message digest (160-bit versus 128 bit) makes it more secure against brute-force attacks [19]. A brute-force 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 SHA-1 hash function. The hash value is then encrypted using the Digital Standard Algorithm (DSA). Like the Diffie-Hellman protocol, DSA is based on the discrete logarithm problem. (Reference [22] contains a detailed description of DSA.)

  • + Share This
  • 🔖 Save To Your Account

InformIT Promotional Mailings & Special Offers

I would like to receive exclusive offers and hear about products from InformIT and its family of brands. I can unsubscribe at any time.

Overview


Pearson Education, Inc., 221 River Street, Hoboken, New Jersey 07030, (Pearson) presents this site to provide information about products and services that can be purchased through this site.

This privacy notice provides an overview of our commitment to privacy and describes how we collect, protect, use and share personal information collected through this site. Please note that other Pearson websites and online products and services have their own separate privacy policies.

Collection and Use of Information


To conduct business and deliver products and services, Pearson collects and uses personal information in several ways in connection with this site, including:

Questions and Inquiries

For inquiries and questions, we collect the inquiry or question, together with name, contact details (email address, phone number and mailing address) and any other additional information voluntarily submitted to us through a Contact Us form or an email. We use this information to address the inquiry and respond to the question.

Online Store

For orders and purchases placed through our online store on this site, we collect order details, name, institution name and address (if applicable), email address, phone number, shipping and billing addresses, credit/debit card information, shipping options and any instructions. We use this information to complete transactions, fulfill orders, communicate with individuals placing orders or visiting the online store, and for related purposes.

Surveys

Pearson may offer opportunities to provide feedback or participate in surveys, including surveys evaluating Pearson products, services or sites. Participation is voluntary. Pearson collects information requested in the survey questions and uses the information to evaluate, support, maintain and improve products, services or sites, develop new products and services, conduct educational research and for other purposes specified in the survey.

Contests and Drawings

Occasionally, we may sponsor a contest or drawing. Participation is optional. Pearson collects name, contact information and other information specified on the entry form for the contest or drawing to conduct the contest or drawing. Pearson may collect additional personal information from the winners of a contest or drawing in order to award the prize and for tax reporting purposes, as required by law.

Newsletters

If you have elected to receive email newsletters or promotional mailings and special offers but want to unsubscribe, simply email information@informit.com.

Service Announcements

On rare occasions it is necessary to send out a strictly service related announcement. For instance, if our service is temporarily suspended for maintenance we might send users an email. Generally, users may not opt-out of these communications, though they can deactivate their account information. However, these communications are not promotional in nature.

Customer Service

We communicate with users on a regular basis to provide requested services and in regard to issues relating to their account we reply via email or phone in accordance with the users' wishes when a user submits their information through our Contact Us form.

Other Collection and Use of Information


Application and System Logs

Pearson automatically collects log data to help ensure the delivery, availability and security of this site. Log data may include technical information about how a user or visitor connected to this site, such as browser type, type of computer/device, operating system, internet service provider and IP address. We use this information for support purposes and to monitor the health of the site, identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents and appropriately scale computing resources.

Web Analytics

Pearson may use third party web trend analytical services, including Google Analytics, to collect visitor information, such as IP addresses, browser types, referring pages, pages visited and time spent on a particular site. While these analytical services collect and report information on an anonymous basis, they may use cookies to gather web trend information. The information gathered may enable Pearson (but not the third party web trend services) to link information with application and system log data. Pearson uses this information for system administration and to identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents, appropriately scale computing resources and otherwise support and deliver this site and its services.

Cookies and Related Technologies

This site uses cookies and similar technologies to personalize content, measure traffic patterns, control security, track use and access of information on this site, and provide interest-based messages and advertising. Users can manage and block the use of cookies through their browser. Disabling or blocking certain cookies may limit the functionality of this site.

Do Not Track

This site currently does not respond to Do Not Track signals.

Security


Pearson uses appropriate physical, administrative and technical security measures to protect personal information from unauthorized access, use and disclosure.

Children


This site is not directed to children under the age of 13.

Marketing


Pearson may send or direct marketing communications to users, provided that

  • Pearson will not use personal information collected or processed as a K-12 school service provider for the purpose of directed or targeted advertising.
  • Such marketing is consistent with applicable law and Pearson's legal obligations.
  • Pearson will not knowingly direct or send marketing communications to an individual who has expressed a preference not to receive marketing.
  • Where required by applicable law, express or implied consent to marketing exists and has not been withdrawn.

Pearson may provide personal information to a third party service provider on a restricted basis to provide marketing solely on behalf of Pearson or an affiliate or customer for whom Pearson is a service provider. Marketing preferences may be changed at any time.

Correcting/Updating Personal Information


If a user's personally identifiable information changes (such as your postal address or email address), we provide a way to correct or update that user's personal data provided to us. This can be done on the Account page. If a user no longer desires our service and desires to delete his or her account, please contact us at customer-service@informit.com and we will process the deletion of a user's account.

Choice/Opt-out


Users can always make an informed choice as to whether they should proceed with certain services offered by InformIT. If you choose to remove yourself from our mailing list(s) simply visit the following page and uncheck any communication you no longer want to receive: www.informit.com/u.aspx.

Sale of Personal Information


Pearson does not rent or sell personal information in exchange for any payment of money.

While Pearson does not sell personal information, as defined in Nevada law, Nevada residents may email a request for no sale of their personal information to NevadaDesignatedRequest@pearson.com.

Supplemental Privacy Statement for California Residents


California residents should read our Supplemental privacy statement for California residents in conjunction with this Privacy Notice. The Supplemental privacy statement for California residents explains Pearson's commitment to comply with California law and applies to personal information of California residents collected in connection with this site and the Services.

Sharing and Disclosure


Pearson may disclose personal information, as follows:

  • As required by law.
  • With the consent of the individual (or their parent, if the individual is a minor)
  • In response to a subpoena, court order or legal process, to the extent permitted or required by law
  • To protect the security and safety of individuals, data, assets and systems, consistent with applicable law
  • In connection the sale, joint venture or other transfer of some or all of its company or assets, subject to the provisions of this Privacy Notice
  • To investigate or address actual or suspected fraud or other illegal activities
  • To exercise its legal rights, including enforcement of the Terms of Use for this site or another contract
  • To affiliated Pearson companies and other companies and organizations who perform work for Pearson and are obligated to protect the privacy of personal information consistent with this Privacy Notice
  • To a school, organization, company or government agency, where Pearson collects or processes the personal information in a school setting or on behalf of such organization, company or government agency.

Links


This web site contains links to other sites. Please be aware that we are not responsible for the privacy practices of such other sites. We encourage our users to be aware when they leave our site and to read the privacy statements of each and every web site that collects Personal Information. This privacy statement applies solely to information collected by this web site.

Requests and Contact


Please contact us about this Privacy Notice or if you have any requests or questions relating to the privacy of your personal information.

Changes to this Privacy Notice


We may revise this Privacy Notice through an updated posting. We will identify the effective date of the revision in the posting. Often, updates are made to provide greater clarity or to comply with changes in regulatory requirements. If the updates involve material changes to the collection, protection, use or disclosure of Personal Information, Pearson will provide notice of the change through a conspicuous notice on this site or other appropriate way. Continued use of the site after the effective date of a posted revision evidences acceptance. Please contact us if you have questions or concerns about the Privacy Notice or any objection to any revisions.

Last Update: November 17, 2020