PGP Cryptography Instruction Manual

An Introduction to Cryptography

Copyright © 1990-1998 Network Associates, Inc. and its Affiliated Companies. All Rights
Reserved.

PGP*, Version 6.0.2
11-98. Printed in the United States of A merica.
PGP, Pretty Good, and Pretty Good Privacy are registered trademarks of Network Associates,

Inc. and/or its Aff iliated Companies in the US and other countries. All other registered and
unregistered trademarks in this document are the so le property of their respective owners.

Portions of this softw ar e may use public key alg orithms described in U.S. Patent numbers
4,200,770, 4,218,582, 4,405,829, and 4,424,414, licensed exclusively by Public Key Partners; the
IDEA(tm) cryptographic cipher described in U.S. patent number 5,214,703, licensed from
Ascom Tech AG; and the Northern Telecom Ltd., CAST Encryption Algorithm,licensed from
Northern Telecom, Ltd. IDEA is a trademark of Ascom Tech AG. Network Associates Inc. may
have patents and/or pending patent applications covering subject matter in this s oftware o r its
documentation; thefurnishing of thissoftwareor documentationdoesnot give you any license
to these patents. The com pression code in PGP is by Mark Adler and Jean- Loup Gailly, used
with permission from the free Info-ZIP implementation. LDAP software provided courtesy
University of Michigan at Ann Arbor, Copyright © 1992-1996 Regents of the U niversity of
Michigan. All rights reserved. This product includes software developed by the Apache Group
for use in the Apache HTTPserverproject (http://www.apache.org/). Copyright © 1995-1997
The Apache Group. All rights reserved. See text files included with the software or the PGP
web site for further information. Thissoftwareis based in part on the work of the Independent
JPEG Group. Soft TEMPEST font courtesy of Ross Anderson and M arcus Kuhn.

The software provided w ith this documentation is licensed to you for your individualuse
under the terms of the End User License Agreement and Limited Warranty provided with the
software. The information in this document is subject to change without notice. Network
Associates Inc. does not warrant that the i nformation meets your requirements or that the
information is free of errors. The information may include technical inaccuracies or
typographical errors. Changes may be made to the i nformation and incorporated in new
editions of this document, if and when made available by Network As so ciates Inc.

Export of this software and documentation may be subject to compliance with the rules and
regulations promulgated from time to time by the Bureau of Export Administration,United
States Department of Commerce, which restrict the export and re-export of certain products
and technical data.

Network Associates, Inc. [phone] main
3965 Freedom Circle
Santa Clara, CA 95054
http://www.nai.com

[e-mail]
* is sometimes used instead of the ® for registered trademarks to protect marks registered

LIMITED WARRANTY

Limited Warranty. Network Associates warrants that for sixty (60) days from the date of
original purchase the media (for example diskettes) on which the Software is contained will be
free from defects in materials and workmanship.

Customer Remedies. Network Associates' and its suppliers ' entire liability and your exclusive
remedy shall be, at Network Associates' option, either (i) return of the purchase price paid for
the license, if any, or (ii) replacement of the defective media in which the Software is contained
with a copy on nondefective media. You must return the defective media to Network
Associates at your expense with a copy of your receipt. This limited warranty is void if the
defect has resulted from accident, abuse, o r misapplication. Any replacement media will be
warranted for the remainder of the original wa rranty period. Outside the United States, this
remedyisnotavailableto theextentNetwork Associatesissubject to restrictions under United
States export control laws and regulations.

Warranty Disclaimer. To the maximum extent permitted by applicable law, and except for the
limited warranty set forth herein, THE SOFTWARE IS PROV IDED ON AN "AS IS" BASIS
WITHOUT W ARRANTY OF AN Y KIND, EXPRESS OR IMPLIED. WITHOUT LIMITING THE
FOREGOING PROVISIONS, YOU ASSUME RESPONSIBILITY F OR SELECTING THE
SOFTWARE TO ACHIEVE YOUR INTENDED RESULTS, AND FOR THE INSTALLATION
OF, USE OF, AND RESULTS OBTAINED FROM THE SOFTWARE. WITHOUT LIMITING
THE FOREGOING PROVISIONS, NETWORK ASSOCIATES MAKES NO W ARRANTY
THATTHESOFTWAREWILLBEERROR-FREEORFREEFROMINTERRUPTIONSOR
OTHER FAILURES OR THAT THE SOFTWARE WILL MEET YOUR REQUIREMENTS. TO
THE MAXIMUM EXTENT PERMITTED BY APPLICABLELAW, NETWORK ASSOCIATES
DISCLAIMS ALL WARRANTIES, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT
LIMITED TO IMPLIED WARRANTIES OF MERCHANTABILITY,FITNESS FOR A
PARTICULAR PURPOSE, AND NONINFRINGEMENT WITH RESPECT TO THE
SOFTWARE AND THE ACCOMPANYING DOCUMENTATION. SOME STATES AND
JURISDICTIONS DO NOT ALLOW LIMITATIONS ON IMPLIED WARRANTIES, SO THE
ABOVE LIMIT ATION MAY NOT APPLY TO Y OU. The foregoing provisions shall be
enforceable to the maximum extent permitted by applicable law.

Preface

Cryptography is the stuff of spy novelsandactioncomics. Kids once savedup
Ovaltine
Almost everyone h as seen a television show or movie involving a nondescript
suit-clad gent leman with a briefcase handcuffed to his wrist. The word
“espionage” conjures images of James Bond, car chases, and flying bul lets.

And here you are, sittinginyouroffice,faced with the rather mundane task of
sending a sales report to a coworker in such a way that no one else can read it.
You just w ant to be sure that your colleague was the actual and only recipient
of the emailandyouwant him or her to know that you were unmistakablythe
sender.It’s notnationalsecurityatstake, but ifyourcompany’s competitorgot
a hold of it, it could cost you. How can you accomplish this?

You can use cryptography. You may find it lacks some of the drama of code
phrases whispered in dar k alleys, but the result is the same: information
revealed only to those for whom it was intended.

TM

labels and sent away for Captain Midnight’s Secret Decoder Ring.

Who should read this guide

This guide is useful to anyone who is interested in knowing the basics of
cryptography, and explains the terminology and technology you will
encounter as you use PGP products. You will find it useful to read before you
begin working with cryptography.

How to use this guide

This guide describes how to use PGP to securely manage your organization’s
messages and data storage.

Chapter 1, “The Basics of Cryptography,” provides an overview of the

terminology and concepts you will encounter as you use PGP products.

Chapter 2, “Phil Zimmermann on PGP,” written by PGP’s creator,contains

discussions of security, privacy, and the vulnerabilities inherent in any
security system,even PGP.

An Introduction to Cryptography v

Preface

For more information

There are several ways to find out more about Network Associates and its
products.

Customer service

To order products or obtain product information, contact the Network
Associates Customer Care department.

You can contact C ustomer Care at one of the following numbers Monday
through Friday between 6:00

Phone [phone]

Or write to:

Network Associates, Inc.
3965 Freedom Circle
Santa Clara, CA 95054
U.S.A.

Technical support

A.M. and 6:00 P.M. Pacific time.

Network Associates is famous for its dedication to customer satisfaction. We
have continued this tradition by making our site on the Wor ld Wide Web a
valuable resource for answers to technical support issues. We encourage you
to make this your first stop for answers to frequently asked questions, for
updatesto NetworkAssociatessoftware,and foraccessto NetworkAssociates
news and encryptioninformation

World Wide Web http://www.nai.com

Technical Support for your PGP product is also available through these
channels:

Phone
Email [e-mail]

To provide the answers you need quickly and efficiently, the Network
Associates technical support staff needs some information about your
computer an d your software. Please have this information ready before you
call:

•PGPproductname

• PGP product version

vi An Introduction to Cryptography

.

[phone]

• Computer platform and CPU type

• Amount of available memory(RAM)

• Operating system and version and type of network

• Content of any status or error message displayed on screen, or appearing
in a log file (not all products produce log files)

• Email application and version (if the problem involves using PGP with an
email pr oduct, for example, the Eudora plug-in)

Relate d re ad i ng

Here are some documents that you may find helpful in understanding
cryptography:

Non-Technica l and beginning technical books

•“Cryptography for the Internet,” by Philip R. Zimmermann. Scientific
American, October 1998. This article,written by PGP’s creator, is a tutorial
onvariouscryptographicprotocols and algorithms,manyofwhichhappen
to be us ed by PGP.

•“Privacy on the Li ne,” by Whitfield Diffie and Susan Eva Landau. MIT Press;
ISBN: 0262041677. This book is a d iscussion of the history and policy
surrounding cryptogra phy and communications security. It is a n excellent
read, even for beginners and no n-technical people, and contains
information that e ven a lot of experts don't know.

Preface

•“The Codebreakers,” by David Kahn. Scribner; ISBN: 0684831309. This book
is a history of codes and code breakers from the time of the Egyptians to the
end of WWII. Kah n first wrote it in the sixties, and published a revised
edition in 1996. This book won't teach you anything about how
cryptography is accomplished, but it has been the inspirationof the whole
modern generation of cryptographers.

• “Network Security: Private Communi cation in a Public World,” by Charlie
Kaufman, Radia Perlman, and Mike Spencer. Prentice Hall; ISBN:
0-13-061466-1. This is a good description of network security systems and
protocols, including descriptions of what works, what doesn't work, and
why. Published in 1995, it doesn't have many of t he latest technological
advances, but is still a good book. It also contains one of the most clear
descriptions of how DES works of any book written.

An Introduction to Cryptography vii

Preface

Intermediatebooks

• “Applied Cryptography:Protocols, Algorithms,andSourceCodeinC,”byBruce
Schneier,JohnWiley&Sons;ISBN:0-471-12845-7. This is a good beginning
technical book on how a lot of cryptography works. If you want to become
an expert, this is the place to start.

•“Handbook of Applied Cryptography,”byAlfredJ.Menezes,PaulC.van
Oorschot, and Scott Vanstone. CRC Press; ISBN: 0-8493-8523-7. This is the
technicalbook you should read after Schneier’s book. T here is a lot of
heavy-dutymath in this book, but it is nonethelessusable for those who do
not understand the math.

•“Internet Cryptography,” by Richard E. Smith. Addison-Wesley Pub Co;
ISBN: 0201924803. This book describes how many I nternet security
protocols work. Most importantly, it describes h ow systems that are
designed well nonetheless end up with flaws through careless op eration.
This book is lig ht on math, and heavy on practical information.

•“Firewalls and Internet Security: Repelling the Wily Hacker ,” by William R.
Cheswickand Steven M. Bellovin. Addison-Wesley Pub Co; ISBN:

0201633574. This book is written by two senior researchers at AT&T Bell
Labs and is about their e xperiences maintaining and redesigning AT&T's
Internet connection. V ery readable.

Advanced books

•“A Course in Number Theory and Cryptography,” by Neal Koblitz.
Springer-Verlag; ISBN: 0-387-94293-9. An excellent graduate-level
mathematics textbook on number theory and cryptography.

•“DifferentialCryptanalysis of theDataEncryptionStandard,”by Eli Biham and
Adi Shamir. Springer-Verlag; ISBN: 0-387-97930-1. This book describes the
technique of differential cryptanalysis as applied to DES. It is an excellent
book for learning a bo ut this technique.

viii An Introduction to Cryptography

Table of Contents

Preface......................................................v

Whoshouldreadthisguide ..............................................v

Howtousethisguide ...................................................v

Formoreinformation...................................................vi

Customerservice .............................................vi

Technicalsupport ............................................vi

Relatedreading ....................................................... vii

Chapter1. TheBasicsofCryptography .........................11

Encryptionanddecryption ..............................................11

Whatiscryptography?..................................................11

Strongcryptography...............................................12

Howdoescryptographywork? .....................................12

Conventionalcryptography .............................................13

Caesar’sCipher ...................................................13

Keymanagementandconventionalencryption.......................14

Publickeycryptography ................................................14

HowPGPworks .......................................................16

Keys ..................................................................17

Digitalsignatures ......................................................18

Hashfunctions....................................................19

Digitalcertificates......................................................21

Validityandtrust ......................................................23

Checkingvalidity .................................................23

Establishingtrust .................................................24

Metaandtrustedintroducers ..................................24

Trustmodels .....................................................24

DirectTrust..................................................25

HierarchicalTrust ............................................25

WebofTrust.................................................26

LevelsoftrustinPGP.........................................26

An Introduction to Cryptography ix

Table of Contents

Whatisapassphrase? ..................................................27

Key splitting ..........................................................28

Technicaldetails .......................................................28

Chapter2. PhilZimmermannonPGP ...........................29

WhyIwrotePGP ......................................................29

ThePGPsymmetricalgorithms..........................................33

AboutPGPdatacompressionroutines...............................35

Abouttherandomnumbersusedassessionkeys .....................35

Aboutthemessagedigest ..........................................36

Howtoprotectpublickeysfromtampering ..........................37

HowdoesPGPkeeptrackofwhichkeysarevalid? ...................40

Howtoprotectprivatekeysfromdisclosure..........................42

Whatifyouloseyourprivatekey? .............................43

Bewareofsnakeoil ....................................................43

Vulnerabilities . . ......................................................48

Compromisedpassphraseandprivatekey ...........................48

Publickeytampering ..............................................49

NotQuiteDeletedFiles ............................................49

VirusesandTrojanhorses..........................................50

Swapfilesorvirtualmemory ..................................51

Physicalsecuritybreach............................................52

Tempestattacks ...................................................52

Protectingagainstbogustimestamps ................................52

Exposureonmulti-usersystems.....................................53

Trafficanalysis ...................................................54

Cryptanalysis .....................................................54

Glossary . ...................................................57

Index.......................................................77

x An Introduction to Cryptography

1The Basics of Cryptography

When Julius Caesar sent messages to his generals, he didn't trust his
messengers. So he replaced every A i n his mes sages with a D, every B with an
E, and so on through the alphabet. Only someone who knew the “shift by 3”
rule could deciph er his messages.

And so we begi n.

Encryption and decryption

Data that can be read and understood without any special measures is called
plaintext or cleartext. The method of disguising plaintext in such a way as to
hide its substance is called encryption. Encrypting plaintext results in
unreadable gibberish called ciphertext. You use encryption to ensure that
information is hidden from anyone for whom it is not intended, even those
who can see the encrypted data. The process of reverting ciphertext to its
original plaintext i s called decryption.

Figure 1-1 illustrates this process.

1

decryptionencryption

plaintext ciphertext plaintext

Figure 1-1. Encryption and decryption

What is cryptography?

Cryptographyis the science of using mathematics to encrypt and decrypt data.
Cryptography enables you to store sensitive information or transmit it across
insecurenetworks (liketheInternet) sothatitcannot be read byanyoneexcept
the intended recipient.

An Introduction to Cryptography 11

The Basics of Cryptography

While cryptography is the science of securing data, cryptanalysis is the science
of analyzing and breaking secure communication. Classical cryptanalysis
involves an interesting combin ation of analytical reasoning, applicatio n of
mathematicaltools, pattern finding, patience, d etermination, and luck.
Cryptanalysts are also called attackers.

Cryptology embraces both cryptography and cryptanalysis.

Strong cryptography

“There are two kinds of cryptography in this world: cryptography that will stop your
kid sister from reading your files, and cryptograp hy that will stop major governments
from reading your files. This book is about the latter.”

--Bruce Schneier,Applied Cryptography: Protocols, Algorithms, and Source
Code in C.

PGPisalsoaboutthelattersortofcryptography.
Cryptography can be strong or weak, as explained above. Cryptographic

strengthismeasured in the time and resourcesitwouldrequire to recover the
plaintext. The result of strong cryptography is ciphertext that is very difficult to
decipherwithoutpossession of the appropriatedecoding tool.How difficult?
Given all of today’s computing power and available time—even a billion
computers doing a billion checks a second—it is not possible to decipher the
result of strong cryptography before the end of the universe.

One would think, then, that strong cryptographywould hold up rather well
against even an extremely determined cryptanalyst. W ho’s really to say? No
one has proven that the strongest encryptionobtainable today will hold up
under tomorrow’s computing power. However, the strong cryptography
employedbyPGP is the best available today. Vigilance and conservatism will
protect you better, however, than claims of impenetrability.

How does cryptogr aphy work?

A cryptographic algorithm,orcipher, is a mathematical function used in the
encryption and decryption process. A cryptographic algorithm works in
combination with a key—a word, number,or phrase—toencrypt the plaintext.
The same plaintext encrypts to different ciphertext with different keys. The
security of encrypted data is entirely dependent on two t hings: t he strength of
the cryptographic algorithm and the secrecy of the key.

A cryptographic algorithm, plus all possiblekeys and all the protocols that
make it work comprise a cryptosystem. PGP is a cryptosystem.

12 An Introduction to Cryptography

The Basicsof Cryptography

Conventional cryptography

In conventional cryptography, also called secret-key or symmetric-key
encryption, one key is used both for encryption and decryption. The Data
Encryption Standard (DES) is an example of a conventional cryptosystemthat
is widely employed by the Federal Government. Figure 1-2 is an illustration of
the conventional encryption process.

decryptionencryption

plaintext ciphertext plaintext

Figure 1-2. Conventional encry ption

Caesar’s Cipher

An extremely simple example of conventional cryptography is a substitution
cipher. A substitution cipher substitutes one piece of information for another.
This is most frequently done by offsetting letters of the alphabet. Two examples
areCaptainMidnight’s SecretDecoderRing,which you may have owned when
you were a kid, and Julius Caesar’s cipher. In both cases, t he algorithm is to
offset the alphabet and the key is the number of characters to offset it.

For example, if we encode the word “SECRET” using Caesar’s key value of 3,
we offset the alphabet so that the 3rd letter down (D) begins the a lphabet.

So starting with
ABCDEFGHIJKLMNOPQRSTUVWXYZ
and sliding ev erything up by 3, you get
DEFGHIJKLMNOPQRSTUVWXYZABC
where D=A, E=B, F=C, and so on.

An Introduction to Cryptography 13

The Basics of Cryptography

Using this scheme, the plaintext, “SE CRET” encrypts as “VHFUHW.” To
allow s omeone else to read the ciphertext, you tell them that the key is 3.

Obviously, this is exceedingly weak cryptography by today’s standards, but
hey, it worked for Caesar, and it also i llustrates how conventional
cryptography works.

Key management and conventional encryption

Conventional encryption has benefits. It is very fast. It i s especially useful for
encrypting data that is not going anywhere. However, conventional
encryptionalone as a means for transmitting secure data can be quite
expensive sim ply due to the difficulty of secure key distribution.

Recall a character from your favoritespy movie: the person w ith a locked
briefcasehandcuffedto his or her wrist. What is in the briefcase, anyway? It’s
probably not the m issile launch code/biotoxin formula/invasion plan itself.
It’s the key that will decrypt the secret data.

For a sender and recip ient to communica te securely using conven tional
encryption, they must agree upon a key and keep it secret between
themselves. Iftheyare in different physicallocations,theymust trustacourier,
the Bat Phone, or some other secure communication medium to prevent the
disclosure of the secret key during transmission. Anyone who overhears or
intercepts the key in transit can later read, modify, and forge all information
encrypted or authenticated with that key. From DES to Captain Midnight’s
Secret Decod er Ring, the persistent pr oblem with conventional encryption is
key distribution: how do you get the key to the recipient without someone
intercepting it?

Public key cryptography

The problems of key distribution are solved by public k ey cryptography,the
concept of which was introduced by Whitf ie ld Diffie and Martin Hellman in

1975. (There is now evidence that the British S ecret Service invented it a few
years before Diffie and He llman, but kept it a military secret—an d did nothing
with it.)

Public key cryptography is an asymmetric scheme that uses a pair of keys for
encryption: a public key, which encrypts data, and a corresponding private, or
secret key fordecryption.Youpublishyourpublickeytotheworldwhile
keeping your private keysecret. Anyone with a copyof your public key can then
encryptinformation that only you can read. Even people you have never met.

1. J H Ellis, The Possibility of Secure Non-Secret Digital Encryption, CESG Report, January 1970.

14 An Introduction to Cryptography

1

[CESG is the UK’s National Authority for the official use of cryptography.]

The Basicsof Cryptography

It is computatio nally infeasible to deduce the private key from t he public key.
Anyonewhohasapublickeycanencryptinformationbutcannotdecryptit.
Only the person who has the corresponding private key can decrypt the
information.

public key private key

decryptionencryption

plaintext ciphertext plaintext

Figure 1-3. Public key encryption

The primary ben efit of public key cryptography is that it allows people who
have no preexisting security arrangement to exchange messages securely. The
need for sender and receiver to share secret keys via some secure channel is
eliminated; all communications involve o nly public keys, and no private key
is ever transmitted or shared. So me examples of public-key cryptosystems are
Elgamal (named for its inventor, Taher Elgamal), RSA (named for its
inventors, Ron Rivest, Adi Shamir, and Leonard Adleman), Diffie-Hellman
(named, you guessed it, for its inventors), and D SA, the Digital Signature
Algorithm (invented by David Kravitz).

Because conventional cryptography was once the only available means for
relayingsecret information, the expense of secure channels and key
distribution relegated its use only to those who could afford it, such as
governments an d large banks (or small children with secret decoder rings).
Public key encryption is the technological revolution that provides strong
cryptography to the adult masses. Remember the courier with the locked
briefcase handcuffed to h is wrist? Public-key encryption puts him out of
business (probably to his relief).

An Introduction to Cryptography 15

The Basics of Cryptography

How PGP works

PGP combines some of t he best features of both conventional and public key
cryptography. PGP is a hybrid cryptosystem.

When a us e r encrypt s plaintext wi th PGP, PGP first compresses the plaintext.
Data compression saves modem transmission time and disk space and, more
importantly, strengthens cryptogr aphic security. Most cryptanalysis
techniques exploit patterns found in the plaintext t o crack the cipher.
Compression reduces these patterns in the plaintext, thereby greatly
enhancing resistance to cryptanalysis. (Files t hat are too short to compres s or
which don’t compress well aren’t compressed.)

PGP then creates a session key, which is a one-time-only secret key. This key is
a random numbergeneratedfrom the randommovements of your mouse and
the keystrokes you type. This session key works with a very secure, fast
conventional encryption algorithm to encrypt the plaintext; the result is
ciphertext. Once the data is encrypted,thesession key is then encryptedtothe
recipient’s public key. This public key-encrypted session key is t ransmitted
along with the ciphertext to the recipient.

plaintext is encrypted
with session key

Figure 1-4. How PGP encryption works

16 An Introduction to Cryptography

session key is encrypted
with public key

ciphertext +

encrypted sessi on key

The Basicsof Cryptography

Decryption works in the reverse. The recipient’s copy of PGP uses his or her
private key to recover the temporary session key, which PGP then uses to
decrypt the conventionally-encrypted ciphertext.

encrypted message

Figure 1-5. How PGP decryption works

The combination of the two encryption methodscombines the convenience of
public key encryption with the speed of conventional encryption.
Conventionalencryption is about 1,000 times faster than public key
encryption. Publickey encryption in turn provides a solution to key
distribution and data transmission issues.Used together, performance and
key distribution are improved without any sacrifice in security.

encrypted
session key

ciphertext

recipient’s private key used
to decrypt session key

session key used
to decrypt ciphertext

original
plaintext

Keys

A key is a value that works with a cryp tographic algorithm to produce a
specific ciphertext. Keys are basically really, really, rea lly big numbers. Key
size is measured in bits; the number representing a 1024-bit key is darn huge.
In public key cryptography, the bigger the key,the more secure the ciphertext.

However, public key size and conventional cryptography’s secret key size are
totally unrelated. A conventional 80-bit key has the equivalent strength of a
1024-bit public key. A conventional 128-bit key is equivalent to a 3000-bit
public key. Again, the bigger the key, the more secure,but the algorithms used
for each type of cryptography are very different and thus comparison is like
that of apples to oranges.

An Introduction to Cryptography 17

The Basics of Cryptography

While the public and private keys are related, it’s v ery difficult to derive the
private key given only the public key; however, deriving the private key is
always possible given enough time and computing power. This makes it very
importanttopickkeysoftherightsize;largeenoughtobesecure,butsmall
enough to be applied fairly quickly. Additio nally, you need to consi der who
might be trying to read your files, how determined they are, how much time
they have, and what their resources might be.

Larger keys will be cryptographically secure for a longer period of time. If
what you want to encrypt needs to be hidden for many years, you might want
to use a very large key. Of course, who knows how long it will take to
determine your key using tomorrow’s faster, more efficient computers? There
was a time wh en a 56-bit symmetric key was considered extremely safe.

Keys are s tored in encrypted form. PGP stores the keys in two files on you r
hard disk; one for public keys and one for private keys. These files are calle d
keyrings. As yo u use PGP, you will typically add the public keys of your
recipients to your public keyring. Yo ur private keys are stored on y our private
keyring. If you lose your private keyring, you will be unable to d e crypt any
information encrypted to keys on that ring.

Digital signatures

Amajorbenefitofpublickeycryptographyisthatitprovidesamethodfor
employing digital signatures. Digital signatures enable the recipient of
information to verify the authenticity of the information’s origin, and also
verify that the information is intact. Thus, public key digital signatures
provide authentication and data integrity. A digital signature also provides
non-repudiation, w hich means that it prevents the sender from claiming that he
or she did not actually send the information. These features are every bit as
fundamental to cryptography as privacy, if not more.

A digital signature serves the same p urpose as a handwrit ten signature.
However,ahandwritten signatureiseasy to counterfeit. A digital signatureis
superior to a handwritten signature in that it is nearly impossible to
counterfeit, plus it attests to the contents of the information as well as to the
identity of the signer.

Some people t end to use signatures more than t hey use encryption. For
example, you may not care if anyone knows that you just deposited $1000 in
your account, but you do want to be darn sureit was the bank teller you were
dealing with.

18 An Introduction to Cryptography

The Basicsof Cryptography

The basic manner in which digital signatures are created is illustrated in Figur e

1-6. Instead of encrypting information using someone else’s public key, you

encryptit withyourprivatekey.If the information canbedecryptedwithyour
public key, then it must have originated with you.

private key public key

signing

original text signed text verified text

Figure 1-6. Simple digital signatures

Hash functions

The systemdescribed above has some problems. It is slow, and it produces an
enormous vo lume of data—at least double the size of the original information.
An improvement on the above scheme is the addition of a one-way hash
function in the process. A one-way hash function takes variable-length
input—in this case, a message of any length, eve n thousands or millions of
bits—and produces a fixed-length output; say, 160-bits. The hash function
ensures that, if the information is changed in any way—even by just one
bit—an entirely different output value is produced.

PGP uses a cryptographically strong hash function on the plaintext the user is
signing. This generates a fixed-length data item known as a message digest.
(Again, any change to the information results in a totally different digest.)

verifying

An Introduction to Cryptography 19

The Basics of Cryptography

Then PGP uses the digest and the private key to create the “signature.” PGP
transmitsthe signature and the plaintext together. Upon receipt of the
message, the recipient uses PGP to recompute the digest, thus verifying the
signature. PGP can encryp t the p laintext or not; signing plaintext is useful if
some of the recipients are not interested in or capable of verifying the
signature.

As long as a secure hash function is used, there is no way to take someone's
signature from one document and attach it to another, or to alter a signed
message in any way. The slightest change in a signed document will ca use the
digital signature verification process to fail.

plaintext

hash function

digest signed
with private key

message digest

plaintext

+

signature

private key
used for signing

Figure 1-7. Secure digital signatures

Digital sig natures play a major role in authenticating and validatingotherPGP
users’ keys.

20 An Introduction to Cryptography

Digital certificates

One issue with public key cryptosystems is that users must be constantly
vigilant to ensure that they are enc rypting to the correct per son’s key. In an
environment wher e it is safe to freely exchange keys via public servers,
man-in-the-middle attacksare a potential threat. In this typeof attack, someone
posts a phony key with the name and user ID of the user’s intended recipient.
Data encrypted to— and intercepted by—the true owner of this bogus key is
now in the wro ng hands.

In a public key environment, it is vital that you are assured that the public key
to which you are enc rypting data is in fact the public key of the intended
recipientandnotaforgery.Yo u cou ld simply encrypt only to those keys which
have been physically hand ed to you. But suppose you need to exchange
information with people you have never met; how can you tell that you have
the correct key?

Digital certificates, or certs, simplify the task of establishing whether a key truly
belongstothepurportedowner.

Webster’s dictionary defines certificate as “a document containing a certified
statement, especially as to the truth of something.” A certificate is a form of
credential. Examples might be your passport, your social security card, or
yourbirthcertificate.Eachof thesehassomei nformationonitidentifying you
andsomeauthorizationstatingthatsomeone elsehasconfirmedyouridentity.
Some certificates, such as your driver’s license, are important enough
confirmation of your identity that you would not want to lose them, lest
someone use them to impersonateyou.

The Basicsof Cryptography

A digital certificate is da ta that functions much like a physical certificate. A
digital certificate is information included with a person’s public key that helps
others verifythat a key is genuine or valid. Digital certificates are u sed to
thwart attempts to substitute one person’s key for another.

A digital certificate consists of three things:

• A public key.

• Certificate information. (“Identity” information about the user, such as
name, user ID, and so on.)

• One or more d igital signatures.

The purpose of the digital signature on a certificate is to state that the
certificate information has been attested to by some other person or entity. The
digital signature does not attest to the authenticity of the certificate as a whole;
it vouches only that the signed identity informa tion goes along with, or is
bound to, the public key.

An Introduction to Cryptography 21

The Basics of Cryptography

While some security experts believe it is not a good practice to mix
professional and personal identity information on one key, but rather have
separate keys for each, you will come across cert ificates containing a public
key with several associated identities (for example, the user’s name and
corporate email account, the user’s nickname and home email account, the
user’s maiden name and college email account—all in one certificate). The list
of signaturesof eachof those identitiesmay differ;signatures usually attestto
the authenticity of one of the identities, not that all three are authentic.

For example, suppose your coworker, Alice, asks you to sign he r certificate.
You look it up on the server and see that A lice has two pieces of identity
information associated with the certifica te. The first one reads “Alice Petucci,
[e-mail].”The secondreads“Cleopatra,[e-mail].”
Depending on how well you kno w Alice, you might want to choose to sign
only the one that relates to t he Alice you know at wo rk.

key

userid userid

Figure 1-8. Anatomy of a certificate

22 An Introduction to Cryptography

certification

certificate

signaturesignature signature

Validity and trust

Every user in a public key system is vulnerable to mistaking a phony key
(certificate) for a real one. Validity is confidence that a public key certificate
belongs to its purported owner. Validity is essential in a public key
environment where you must constantlyestablish whether or not a particular
certificate is authentic.

When you’ve assured yourself that a certificate belonging to someone else is
valid, you can sign the copy on your keyring to attest to the fact that you’ve
checkedthecertificateandthatit’s a good one.Ifyouwantothers to knowthat
you gave the certificate your stamp of approval, you can export t he signature
to a certificate server so that others can see it.

Some companies designate one or more Certification Authorities (CA),whose
jobitistogoaroundandcheckthevalidityofallthecertificatesinthe
organization and then sign the good ones. The CA is the Grand Pooh-bah of
validation in an organization, whom everyone trusts, and in some public key
environments, no certificate is considered valid unless it has been attested to
by a CA.

Checking validity

The Basicsof Cryptography

Oneway to establishvalidity is to go through some manual process.Thereare
severalways to accomplishthis. You could require your intended recipientto
physically hand you a c opy of his or her public key. But this is often
inconvenient and inefficient.

Another way is to m anually check the certificate’s fingerprint.Justasevery
human’s fingerprints are unique, every PGP certificate’s finge rprint is unique.
The fingerprint is a hash o f the user’s certificate and appears as one of the
certificate’s properties. You can check that a certificate is v alid by calling the
key’s owner (so that you orig inate the transaction) and asking the owner to
read his or her key’s fingerprint to you and verifying that fingerprint against
the one you believe to be the real one. This works if you know the owner’s
voice, but, how do you manually verify the identity of someone you don’t
know? Some people put the fingerprintof their key on their business cards for
this very reason.

Another wa y to establish validity of someone’s certificate is to trust that a third
individual has gone through the process of validating it.

A CA, for example, is respon sible for ensuring that prior to assigning validity
toacertificate,heorshecarefullychecksittobesureitbelongstothe
purported owner. Anyone who trusts the CA will automatically consider any
certificates validated by the CA to be valid.

An Introduction to Cryptography 23

The Basics of Cryptography

Establ is hin g trust

You validate keys. You trust people. Mor e specifically, you trust people to
validate other peo ple’ keys. Typically, unless the owner hands you the
certificate, you have to go by someone else’s word that it is valid.

Meta and trus ted introducers

In most situations, people completely trust the CA to establish certificates’
validity. This means that everyone else relies upon the CA t o go through the
whole manual validation process for them. This is fine up to a certain number
of users or number of work sites, and then it may not be possiblefor the CA to
maintain the same level of quality validation. In that case, adding other
validators to the system is necessary.

ACAcanalsobeameta-introducer. A meta-introducer bestows not only
validityon keys,butbestowsthe ability to trustkeysupon others. Similar tothe
kingwhohandshissealtohistrustedadvisorssotheycanactonhisauthority,
the m eta-introducer enables others t o act as trusted introducers. These trusted
introducers can validate keys to the same effect as that of the meta-introducer.
They cannot, however, create new trusted introducers.

Trust models

Inrelativelyclosedsystems,suchaswithin a company,it is easy to traceapath
of trust back to the root CA. However, in the real world, users must often
communicate with people outside of their corporate env ironment, including
some whom they have never met, such as vendors,customers, clients,
associates, and so on. Establishing a line of trust to those who have not been
explicitly trusted by a CA is difficult.

Companiesfollow one or another trust model, which dictates how users will go
about establishing key validity. There are three different models:

•DirectTrust

• Hierarchical Trust

•AWebofTrust

24 An Introduction to Cryptography