`
`An Introduction to
`
`Cryptography
`
`Apple 1024
`Apple 1024
`Apple v. USR
`Apple v. USR
`IPR2018-00810
`|PR2018-00810
`
`

`

`Copyright © 1990—1999 Network Associates, Inc. and its Affiliated Companies. All Rights
`Reserved.
`
`PGP*, Version 65.2
`
`10—99. Printed in the United States of America.
`
`PGP, Pretty Good, and Pretty Good Privacy are registered trademarks of Network Associates,
`Inc. and/or its Affiliated Companies in the US and other countries. All other registered and
`unregistered trademarks in this document are the sole property of their respective owners.
`
`Portions of this software may use public key algorithms described in US. 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 US. 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 software or its
`documentation; the furnishing ofthis software or documentation does not give you any license
`to these patents. The compression 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 University of
`Michigan. All rights reserved. This product includes software developed by the Apache Group
`for use in the Apache HTTP server project (http://www.apache.org/). Copyright © 1995—1999
`The Apache Group. All rights reserved. See text files included with the software or the PGP
`web site for further information. This software is based in part on the work of the Independent
`JPEG Group. Soft TEMPEST font courtesy of Ross Anderson and Marcus Kuhn.
`
`The software provided with this documentation is licensed to you for your individual use
`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 information 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 information and incorporated in new
`editions of this document, if and when made available by Network Associates 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.
`
`(408) 988—3832 main
`
`Network Associates, Inc.
`3965 Freedom Circle
`
`Santa Clara, CA 95054
`
`http://wwwnaicom
`
`info@nai.com
`
`* 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 ofthe 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, or misapplication. Any replacement media will be
`warranted for the remainder of the original warranty period. Outside the United States, this
`remedy is not available to the extent Network Associates is subject 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 PROVIDED ON AN “AS IS” BASIS
`WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED. WITHOUT LIMITING THE
`FOREGOING PROVISIONS, YOU ASSUME RESPONSIBILITY FOR 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 WARRANTY
`THAT THE SOFTWARE WILL BE ERROR—FREE OR FREE FROM INTERRUPTIONS OR
`
`OTHER FAILURES OR THAT THE SOFTWARE WILL MEET YOUR REQUIREMENTS. TO
`THE MAXIMUM EXTENT PERMITTED BY APPLICABLE LAW, 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 LIMITATION MAY NOT APPLY TO YOU. The foregoing provisions shall be
`enforceable to the maximum extent permitted by applicable law.
`
`

`

`

`

`Table of Contents
`
`Preface ..................................................... vii
`
`Who should read this guide ........................................ vii
`
`How to use this guide ............................................. vii
`
`For more information ............................................ viii
`
`Related reading ................................................. viii
`
`Chapter 1. The Basics of Cryptography ......................... 11
`
`Encryption and decryption ........................................ 11
`
`What is cryptography? ............................................ 11
`
`Strong cryptography ......................................... 12
`
`How does cryptography work? ................................. 12
`
`Conventional cryptography ........................................ 13
`
`Caesar’s Cipher ............................................. 13
`
`Key management and conventional encryption ................... 14
`
`Public key cryptography .......................................... 14
`How PGP works ................................................. 16
`
`Keys ........................................................... 17
`
`Digital signatures ................................................ 18
`Hash functions .............................................. 19
`
`Digital certificates ................................................ 21
`Certificate distribution ........................................ 22
`
`Certificate formats ........................................... 23
`
`PGP certificate format .................................... 23
`
`X.509 certificate format ................................... 25
`
`Validity and trust ................................................. 28
`
`Checking validity ............................................ 28
`
`Establishing trust ............................................ 29
`
`Meta and trusted introducers .............................. 29
`
`Trust models ................................................ 30
`
`Direct Trust ............................................. 30
`
`Hierarchical Trust ....................................... 31
`
`An Introduction to Cryptography
`
`v
`
`

`

`Table of Contents
`
`Web of Trust ............................................ 31
`
`Levels of trust in PGP .................................... 32
`
`Certificate Revocation ............................................ 33
`
`Communicating that a certificate has been revoked ............... 34
`
`What is a passphrase? ............................................ 35
`
`Key splitting .................................................... 35
`Technical details ................................................. 36
`
`Chapter 2. Phil Zimmermann on PGP ........................... 37
`
`Why I wrote PGP ................................................. 37
`
`The PGP symmetric algorithms ..................................... 41
`
`About PGP data compression routines .......................... 43
`
`About the random numbers used as session keys ................ 43
`
`About the message digest ..................................... 44
`
`How to protect public keys from tampering ...................... 45
`
`How does PGP keep track of which keys are valid? ................ 48
`
`How to protect private keys from disclosure ..................... 50
`
`What if you lose your private key? ......................... 51
`Beware of snake oil .............................................. 51
`
`Vulnerabilities ................................................... 56
`
`Com promised passphrase and private key ....................... 56
`
`Public key tampering ......................................... 57
`Not Quite Deleted Files ....................................... 57
`
`Viruses and Trojan horses .................................... 58
`
`Swap files or virtual memory .............................. 59
`
`Physical security breach ...................................... 60
`
`Tempest attacks ............................................. 60
`
`Protecting against bogus timestamps ........................... 60
`
`Exposure on multi-user systems ............................... 61
`
`Traffic analysis .............................................. 62
`
`Cryptanalysis ............................................... 62
`
`Glossary .................................................... 65
`
`Index ....................................................... 85
`
`vi
`
`An Introduction to Cryptography
`
`

`

`Preface
`
`Cryptography is the stuff of spy novels and action comics. Kids once saved up
`OvaltineTM labels and sent away for Captain Midnight’s Secret Decoder Ring.
`Almost everyone has seen a television show or movie involving a nondescript
`suit—clad gentleman with a briefcase handcuffed to his wrist. The word
`“ espionage” conjures images of James Bond, car chases, and flying bullets.
`
`And here you are, sitting in your office, 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 want to be sure that your colleague was the actual and only recipient
`ofthe email and you want him or her to know that you were unmistakably the
`sender. It’s not national security at stake, but ifyour company’s competitor got
`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 dark alleys, but the result is the same: information
`revealed only to those for whom it was intended.
`
`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
`
`vii
`
`

`

`Preface
`
`For more information
`
`For information on technical support and answers to other product related
`questions you might have, please see the What’s New file accompanying this
`product.
`
`Related reading
`
`Here are some documents that you may find helpful in understanding
`cryptography:
`
`Non-Technical 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
`on various cryptographic protocols and algorithms, many ofwhich happen
`to be used by PGP.
`
`"Privacy on the Line, ” by Whitfield Diffie and Susan Eva Landau. MIT Press;
`ISBN: 0262041677. This book is a discussion of the history and policy
`surrounding cryptography and communications security. It is an excellent
`read, even for beginners and non—technical people, and contains
`information that even a lot of experts don‘t know.
`
`“ 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. Kahn 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 inspiration of the whole
`modern generation of cryptographers.
`
`“Network Security: Private Communication 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 the 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.
`
`Intermediate books
`
`“Applied Cryptography: Protocols, Algorithms, and Source Code in C, " by Bruce
`Schneier, John Wiley & Sons; ISBN: 04171-128453]. 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.
`
`viii
`
`An Introduction to Cryptography
`
`

`

`Preface
`
`“ Handbook oprplied Cryptography,” by Alfred]. Menezes, Paul C. van
`Oorschot, and Scott Vanstone. CRC Press; ISBN: 0—8493-8523—7. This is the
`
`technical book you should read after Schneier’s book. There is a lot of
`heavy-duty math in this book, but it is nonetheless usable 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 Internet security
`protocols work. Most importantly, it describes how systems that are
`designed well nonetheless end up with flaws through careless operation.
`This book is light on math, and heavy on practical information.
`
`" Firewalls and Internet Security: Repelling the Wily Hacker, ” by William R.
`Cheswick and 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 experiences maintaining and redesigning AT&T's
`Internet connection. Very 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.
`
`" Differential Cryptanalysis of the Data Encryption Standard, " by Eli Biham and
`Adi Shamir. Springer—Verlag; ISBN: 0—387197930— 1. This book describes the
`technique of differential cryptanalysis as applied to DES. It is an excellent
`book for learning about this technique.
`
`An Introduction to Cryptography
`
`ix
`
`

`

`Preface
`
`x
`
`An Introduction to Cryptography
`
`

`

`The Basics of Cryptography
`
`When Julius Caesar sent messages to his generals, he didn't trust his
`messengers. So he replaced every A in his messages with a D, every B with an
`E, and so on through the alphabet. Only someone who knew the “shift by 3”
`rule could decipher his messages.
`
`And so we begin.
`
`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 is called decryption.
`
`Figure [.1 illustrates this process.
`
`
`
`.0
`.rrr
`
`plaintext
`
`ciphertext
`
`plaintext
`
`Figure 1-1. Encryption and decryption
`
`What is cryptography?
`
`Cryptography is the science of using mathematics to encrypt and decrypt data.
`Cryptography enables you to store sensitive information or transmit it across
`insecure networks (like the Internet) so that it cannot be read by anyone except
`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 combination of analytical reasoning, application of
`mathematical tools, pattern finding, patience, determination, 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 cryptography 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.
`
`PGP is also about the latter sort of cryptography.
`
`Cryptography can be strong or weak, as explained above. Cryptographic
`strength is measured in the time and resources it would require to recover the
`plaintext. The result of strong cryptography is ciphertext that is very difficult to
`decipher without possession of the appropriate decoding 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 cryptography would hold up rather well
`against even an extremely determined cryptanalyst. Who’s really to say? No
`one has proven that the strongest encryption obtainable today will hold up
`under tomorrow’s computing power. However, the strong cryptography
`employed by PGP is the best available today. Vigilance and conservatism will
`protect you better, however, than claims of impenetrability.
`
`How does cryptography work?
`
`A cryptographic algorithm, or cipher, 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—to encrypt the plaintext.
`The same plaintext encrypts to different ciphertext with different keys. The
`security of encrypted data is entirely dependent on two things: the strength of
`the cryptographic algorithm and the secrecy of the key.
`
`A cryptographic algorithm, plus all possible keys and all the protocols that
`make it work comprise a cryptosystem. PGP is a cryptosystem.
`
`12
`
`An Introduction to Cryptography
`
`

`

`The Basics of Cryptography
`
`Conventional cryptography
`
`In conventional cryptography, also called secret—key or symmetriekey
`encryption, one key is used both for encryption and decryption. The Data
`Encryption Standard (DES) is an example ofa conventional cryptosystem that
`is widely employed by the Federal Government. Figure 172 is an illustration of
`the conventional encryption process.
`
`
`
`decryption
`
`encryption
`
`plaintext
`
`ciphertext
`
`plaintext
`
`Figure 1-2. Conventional encryption
`
`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 ofthe alphabet. Two examples
`are Captain Midnight’s Secret Decoder Ring, which you may have owned when
`you were a kid, and Julius Caesar’s cipher. In both cases, the 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 alphabet.
`
`So starting with
`
`ABCDEFGI—IIJKLMNOPQRSTUVWXYZ
`
`and sliding everything up by 3, you get
`
`DEFGHIJKLMNOPQRSTUVWXYZABC
`
`where DzA, E=B, F:C, and so on.
`
`An Introduction to Cryptography
`
`13
`
`

`

`The Basics of Cryptography
`
`Using this scheme, the plaintext, “SECRET” encrypts as “VHFUHW.” To
`allow someone 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 illustrates how conventional cryptography
`works.
`
`Key management and conventional encryption
`
`Conventional encryption has benefits It is very fast. It is especially useful for
`encrypting data that is not going anywhere. However, conventional
`encryption alone as a means for transmitting secure data can be quite
`expensive simply due to the difficulty of secure key distribution.
`
`Recall a character from your favorite spy movie: the person with a locked
`briefcase handcuffed to his or her wrist. What is in the briefcase, anyway? It’s
`probably not the missile launch code/biotoxin formula/invasion plan itself.
`It’s the keythat will decrypt the secret data.
`
`For a sender and recipient to communicate securely using conventional
`encryption, they must agree upon a key and keep it secret between
`themselves. If they are in different physical locations, they must trust a courier,
`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 Decoder Ring, the persistent problem 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 key cryptography, the
`concept of which was introduced by Whitfield Diffie and Martin Hellman in
`1975. (There is now evidence that the British Secret Service invented it a few
`years before Diffie and Hellman, but kept it a military secret—and 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 for decryption. You publish your public key to the world while
`keeping your private key secret. Anyone with a copy ofyour public key can then
`encrypt information that only you can read. Even people you have never met.
`
`1.] H Ellis, The Possibility ofSecure NorrSecret Digital Encryption. CESG Re ort, January 1970.
`[CESG is the UK‘s National Authority for t] 1e official use of cryptographyf
`
`14
`
`An Introduction to Cryptography
`
`

`

`The Basics of Cryptography
`
`It is computationally infeasible to deduce the private key from the public key.
`Anyone who has a public key can encrypt information but cannot decrypt it.
`Only the person who has the corresponding private key can decrypt the
`information.
`
`public key
`
`a1-
`
`0699
`
`e?)
`
`349+
`
`encryption
`
`plaintext
`
`
`
`ciphertext
`
`Figure 1-3. Public key encryption
`
`private key
`
`(:3
`
`a???
`I
`
`l
`
`decryption
`
`plaintext
`
`The primary benefit 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 only public keys, and no private key
`is ever transmitted or shared. Some 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-l-Iellman
`(named, you guessed it, for its inventors), and DSA, the Digital Signature
`Algorithm (invented by David Kravitzl
`
`Because conventional cryptography was once the only available means for
`relaying secret information, the expense of secure channels and key
`distribution relegated its use only to those who could afford it, such as
`governments and 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 his 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 the best features of both conventional and public key
`cryptography. PGP is a hybrid cryptasystem.
`
`When a user encrypts plaintext with PCP, PGP first compresses the plaintext.
`Data compression saves modem transmission time and disk space and. more
`importantly, strengthens cryptographic security. Most cryptanalysis
`techniques exploit patterns found in the plaintext to crack the cipher.
`Compression reduces these patterns in the plaintext, thereby greatly
`enhancing resistance to cryptanalysis. (Files that are too short to compress 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 number generated from the random movements 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, the session key is then encrypted to the
`recipient’s public key. This public key—encrypted session key is transmitted
`along with the ciphertext to the recipient.
`
`{EM
`plaintext is encrypted
`with session key
`
`4%» r...
`
`
`
`
`session key is encrypted
`with public key
`
`ciphertext +
`encrypted session key
`
`Figure 1-4. How PGP encryption works
`
`16
`
`An Introduction to Cryptography
`
`

`

`The Basics of 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
`
`encrypted
`session key
`
`recipient’s private key used
`to decrypt session key
`
`ciphertext
`
`
`session key used
`to decrypt ciphertext
`
`original
`piaintext
`
`Keys
`
`Figure 1-5. How PGP decryption works
`
`The combination of the two encryption methods combines the convenience of
`public key encryption with the speed of conventional encryption.
`Conventional encryption is about 1,000 times faster than public key
`encryption. Public key 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.
`
`A key is a value that works with a cryptographic algorithm to produce a
`specific ciphertext. Keys are basically really, really, really 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 mathematically related, it’s very 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 important to pick keys of the right size; large enough to be
`secure, but small enough to be applied fairly quickly. Additionally, you need
`to consider 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 when a 56—bit symmetric key was considered extremely safe.
`
`Keys are stored in encrypted form. PGP stores the keys in two files on your
`hard disk; one for public keys and one for private keys. These files are called
`keyrings. As you use PGP, you will typically add the public keys of your
`recipients to your public keyring. Your private keys are stored on your private
`keyring. If you lose your private keyring, you will be unable to decrypt any
`information encrypted to keys on that ring.
`
`Digital signatures
`
`A major benefit of public key cryptography is that it provides a method for
`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, which 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 purpose as a handwritten signature.
`However, a handwritten signature is easy to counterfeit. A digital signature is
`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 tend to use signatures more than they 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 sure it was the bank teller you were
`dealing with.
`
`18
`
`An Introduction to Cryptography
`
`

`

`The Basics of Cryptography
`
`The basic manner in which digital signatures are created is illustrated in Figure
`1754 Instead of encrypting information using someone else’s public key, you
`encrypt it with your private key. lfthe information can be decrypted with your
`public key, then it must have originated with you.
`
`private key
`
`public key
`
`0.6:)
`
`
`l
`
`his
`l
`
`is
`
`Sit—(iris
`
`original text
`
`signed text
`
`verified text
`
`verifying
`
`Figure 1-6. Simple digital signatures
`
`Hash functions
`
`The system described above has some problems. It is slow, and it produces an
`enormous volume of data—at least double the size ofthe 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, even thousands or millions of
`bits—and produces a fixed—length output; say, lGO-bits. The hash function
`ensures that, if the information is changed in any wayfieven 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)
`
`An Introduction to Cryptography
`
`19
`
`

`

`The Basics of Cryptography
`
`Then PGP uses the digest and the private key to create the ”signature.” PGP
`transmits the signature and the plaintext together. Upon receipt of the
`message, the recipient uses PGP to recompute the digest, thus verifying the
`signature. PGP can encrypt the plaintext 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 cause the
`digital signature verification process to fail.
`
`plaintext
`
`
`
`
`
`digest signed
`with private key
`4-5.7
`
`
`
`plaintext
`+
`
`signature
`
`flaw—t
`
`message digest
`
` private key
`
`used for signing
`
`Figure 1-7. Secure digital signatures
`
`Digital signatures play a major role in authenticating and validating other PGP
`users’ keys.
`
`20
`
`An Introduction to Cryptography
`
`

`

`The Basics of Cryptography
`
`Digital certificates
`
`One issue with public key cryptosystems is that users must be constantly
`vigilant to ensure that they are encrypting to the correct person’s key. In an
`environment where it is safe to freely exchange keys via public servers,
`man—in—the—middle attacks are a potential threat. In this type of 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 wrong hands.
`
`In a public key envi