How PGP Works

PGP uses three cryptographic components: RSA, IDEA, and md5. You can find a

detailed discussion of each at http://www.ph.tn.tudelft.nl/~visser/faq.txt.

RSA consists of the components P0() and S0(). 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.

On the other hand, IDEA is a symmetric key cipher. 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.

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

0) Conventional Encryption

IDEA(X, md5(PP)) is the conventional encryption of X with passphrase PP. Your

private key is protected with conventional encryption.

1) Public Key Encryption

You wish to encrypt the message X to a recipient whose public key is P1().

PGP generates a random 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 almost never be encrypted the same way twice.

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(IDEA(X,k),k).

3) Digital Signatures

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.

4) Authentication of a Digital Signature

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.

5) Public Key Encryption & Digital Signatures

You wish to encrypt a signed message X 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)

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

7) Encrypting to Multiple Recipients

You wish to encrypt a message X to a list of recipients whose public keys are

P1(), P2(), P3(). Form the message as in 1), but also attach P2(k), P3(k) to

get [IDEA(X,k), {P1(k), P2(k), P3(k)}]. If you wish to sign the message, form

[IDEA([X,S0(md5(X))],k), {P1(k), P2(k), P3(k)}] as in 5), but with several

RSA encrypted IDEA keys.

8) Signatures on Public Keys

P0() is just data, and, as such, can be fed to S0(md5()) to obtain a signature.

When you sign your public key you are forming [P0(), S0(md5(P0()))] as in 3).

P0() can now be authenticated as in 4).

Other signatures can be attached to attest to the authenticity of P0(). If the

owners of S1(), S2(), and S3() are convinced that P0() belongs to you,

then each can attach a signature to P0(), forming

[P0(), {S0(md5(P0())), S1(md5(P0())),S2(md5(P0())),S3(md5(P0()))}]

Someone in possession of P2(), who trusts its owner, can authenticate P0() as

in 4).

--

-- kc

Furbling, v.:

Having to wander through a maze of ropes at an airport or bank