How PGP Works

J. Kelly Cunninghamgif ( deviate@lipschitz.sfasu.edu) - R. Kaszeta

11 September 1996

1 Introduction

This document is meant as a brief overview of the methods that PGP uses for encryption, decryption, and authentication. This document does not cover how to use PGP. For information on using PGP you should read either the documentation included with PGP or PGP: Pretty Good Privacy by Simson Garfinkel, available from O'reilly and Associates.

2 The Basics

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

RSA consists of the components tex2html_wrap_inline168 and tex2html_wrap_inline170 . tex2html_wrap_inline168 is your public key and tex2html_wrap_inline170 is your private key. Anything encrypted by one can be decrypted by the other, and it is considered impossible to determine tex2html_wrap_inline170 from tex2html_wrap_inline168 .

Suppose X is a message. tex2html_wrap_inline182 is meaningless gibberish, however tex2html_wrap_inline184 . Similarly, tex2html_wrap_inline186 is gibberish, but tex2html_wrap_inline188 .

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 tex2html_wrap_inline194 is meaningless gibberish, but tex2html_wrap_inline196 .

md5 will produce an essentially unique 128 bit one way hash of any input.

md5(X) is an essentially unique 128 bit representation of X.

3 Conventional Encryption

tex2html_wrap_inline202 is the conventional encryption of X with passphrase tex2html_wrap_inline206 . Your private key is protected with conventional encryption.

4 Public Key Encryption

 

You wish to encrypt the message X to a recipient whose public key is tex2html_wrap_inline210 . PGP randomly generates a 128 bit key k. tex2html_wrap_inline214 is applied to X to produce meaningless gibberish tex2html_wrap_inline194 . tex2html_wrap_inline210 is applied to k to produce meaningless gibberish tex2html_wrap_inline224 . tex2html_wrap_inline226 is sent to recipient. Since k is random X will never be encrypted the same way twice.

5 Decryption

 

You have received tex2html_wrap_inline234 . PGP applies tex2html_wrap_inline170 to tex2html_wrap_inline238 to retrieve tex2html_wrap_inline240 . Now that you have k, PGP applies tex2html_wrap_inline214 to tex2html_wrap_inline194 to obtain

displaymath232

6 Digital Signatures

 

You wish to sign a message X. md5 is applied to X to obtain md5(X). tex2html_wrap_inline170 is applied to md5(X) to obtain the ``signature'' tex2html_wrap_inline258 . tex2html_wrap_inline260 is sent to recipient.

7 Authentication of a Digital Signature

 

Recipient, who has your public key, wishes to verify that a signed message, tex2html_wrap_inline260 , came from you. PGP applies tex2html_wrap_inline168 to tex2html_wrap_inline258 to retrieve tex2html_wrap_inline268 . 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.

8 Public Key Encryption and Digital Signatures

 

You wish to encrypt a signed the message X to a recipient whose public key is tex2html_wrap_inline210 . PGP forms tex2html_wrap_inline260 as in section 6. PGP then forms tex2html_wrap_inline284 as in section 4.

9 Decryption and Authentication

You receive tex2html_wrap_inline288 formed as in section 8. PGP retrieves

displaymath286

as in section 5. tex2html_wrap_inline290 is authenticated as in section 7.

10 Encrypting to Multiple Recipients

 

You wish to encrypt a message X to a list of recipients whose public keys are tex2html_wrap_inline210 , tex2html_wrap_inline298 , tex2html_wrap_inline300 . Form the message as in section 4, but also attach tex2html_wrap_inline302 , tex2html_wrap_inline304 to get tex2html_wrap_inline306 . If you wish to sign the message, form

displaymath292

as in section 8, but with several RSA encrypted IDEA keys.

11 Signatures on Public Keys

tex2html_wrap_inline168 is just data, and, as such, can be fed to tex2html_wrap_inline312 to obtain a signature. When you sign your public key you are forming tex2html_wrap_inline314 as in section 6. tex2html_wrap_inline168 can now be authenticated as in section 7.

Other signatures can be attached to attest to the authenticity of tex2html_wrap_inline168 . If the owners of tex2html_wrap_inline320 , tex2html_wrap_inline322 , and tex2html_wrap_inline324 are convinced that tex2html_wrap_inline168 belongs to you, then each can attach a signature to tex2html_wrap_inline168 , forming

displaymath308

Someone in possession of tex2html_wrap_inline298 , who trusts its owner, can authenticate tex2html_wrap_inline168 as in section 7.

About this document ...

How PGP Works

This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 -show_section_numbers pgp.tex.

The translation was initiated by Curtis L. Olson on Fri Sep 13 10:30:17 CDT 1996

...Cunningham
This is derived from a post to alt.security.pgp by J. Kelly Cunningham on 9 September 1996 
 


 



Curtis L. Olson 

Fri Sep 13 10:30:17 CDT 1996