How PGP Works

How PGP Works

Post by J. Kelly Cunningh » Sun, 16 Feb 1997 04:00:00

                                 How PGP Works

PGP uses three cryptographic components: RSA, IDEA, and md5.  You can find a
detailed discussion of each at

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