Version 1.5

The comp.security.pgp FAQ

Appendix I - The functionality behind PGP

This part is largely based on a post made by J. Kelly Cunningham <[email protected]>.

Background
Encryption
Decryption
Signing
Authentication
Encryption & Signing
Decryption & Authentication

0) Background

PGP uses three cryptographic components: RSA, IDEA, and md5.

RSA is a public key cipher. That is, there is not one key, but two components, which are used for specific purposes. In this text, P0() is your public key and S0() is your private key. Anything encrypted by one can be decrypted by the other, and it is considered impossible to determine S0() from P0().

Suppose X is a message. P0(X) is meaningless gibberish, however S0(P0(X)) = X. Similarly, S0(X) is gibberish, but P0(S0(X)) = X.

IDEA is a symmetric key cipher. This is "normal" cryptography: the same key encrypts and decrypts the message. IDEA uses a 128 bit key to transform a message into meaningless gibberish. The same key, when applied to the meaningless gibberish, will produce the original message.

Suppose X is a message and k is a key. Then IDEA(X,k) is meaningless gibberish, but IDEA(IDEA(X,k),k) = X.

MD5 will produce an essentially unique 128 bit one way hash of any input. It is considered impossible to determine the input when given the hash, and the chance of two different inputs having the same hash is extremely small. Think of a hash as a very good checksum.

md5(X) is a 128 bit representation of X.

1) Encryption

You wish to encrypt the message X to a recipient whose public key is P1(). PGP randomly generates a 128 bit key k. IDEA( ,k) is applied to X to produce meaningless gibberish IDEA(X,k). P1() is applied to k to produce meaningless gibberish P1(k). (IDEA(X,k), P1(k)) is sent to recipient. Since k is random X will never be encrypted the same way twice.

In the case that you want to encrypt the message to two recipients, the random key k is encrypted with the public keys of each recipient, but the actual message is only encrypted once. Now (IDEA(X,k), P1(k), P2(k), ...) is sent to each recipient, who has to pick out the bit which is encrypted with his public key himself.

2) Decryption

You have received (IDEA(X,k), P0(k)). PGP applies S0() to P0(k) to retrieve k = S0(P0(k)). Now that you have k, PGP applies IDEA( ,k) to IDEA(X,k) to obtain X = (IDEA(X,k),k).

3) Signing

You wish to sign a message X. MD5 is applied to X to obtain MD5(X). S0() is applied to MD5(X) to obtain the 'signature' S0(MD5(X)). (X,S0(MD5(X))) is sent to recipient.

Normally, the signature is put before the actual message you are sending, but if you use the "clearsign" option, the signature will be put below the message. Additionally, when you "clearsign" a message, spaces and tabs after a line are stripped off first, and newlines are converted to carriage return/newline pairs. This ensures that mail and news transport programs will not mangle the message in such a way that the signature becomes invalid.

4) Authentication

Recipient, who has your public key, wishes to verify that a signed message, (X,S0(MD5(X))), came from you. PGP applies P0() to S0(MD5(X)) to retrieve MD5(X) = P0(S0(MD5(X)). Next, MD5() is applied to X to obtain MD5(X) directly from X. If the two match, then the message is the one you sent.

Of course, you have to be sure that the public key you use to check the signature really belongs to the person it claims to be from.

5) Encryption & Signing

You wish to encrypt a signed message to a recipient whose public key is P1(). PGP forms (X,S0(MD5(X))) as in 3). PGP then forms (IDEA((X,S0(MD5(X))),k), P1(k)) as in 1). This is sent to the recipient.

6) Decryption & Authentication

You receive (IDEA((X,S1(MD5(X))),k), P0(k)) formed as in 5). PGP retrieves IDEA((X,S1(MD5(X))) as in 2). IDEA((X,S1(MD5(X))) is authenticated as in 4).

[ Table of Contents | About this FAQ | Glossary ]