An Introduction To Cryptography - Virginia Tech

PrefaceCryptography is the stuff of spy novels and action comics. Kids once saved upOvaltineTM labels and sent away for Captain Midnight’s Secret Decoder Ring.Almost everyone has seen a television show or movie involving a nondescriptsuit-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 ofsending 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 recipientof the email and you want him or her to know that you were unmistakably thesender. It’s not national security at stake, but if your company’s competitor gota 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 codephrases whispered in dark alleys, but the result is the same: informationrevealed only to those for whom it was intended.Who should read this guideThis guide is useful to anyone who is interested in knowing the basics ofcryptography, and explains the terminology and technology you willencounter as you use PGP products. You will find it useful to read before youbegin working with cryptography.How to use this guideThis guide describes how to use PGP to securely manage your organization’smessages and data storage.Chapter 1, “The Basics of Cryptography,” provides an overview of theterminology and concepts you will encounter as you use PGP products.Chapter 2, “Phil Zimmermann on PGP,” written by PGP’s creator, containsdiscussions of security, privacy, and the vulnerabilities inherent in anysecurity system, even PGP.An Introduction to Cryptographyvii

PrefaceFor more informationFor information on technical support and answers to other product relatedquestions you might have, please see the What’s New file accompanying thisproduct.Related readingHere are some documents that you may find helpful in understandingcryptography:Non-Technical and beginning technical books “Cryptography for the Internet,” by Philip R. Zimmermann. ScientificAmerican, October 1998. This article, written by PGP’s creator, is a tutorialon various cryptographic protocols and algorithms, many of which happento 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 policysurrounding cryptography and communications security. It is an excellentread, even for beginners and non-technical people, and containsinformation that even a lot of experts don't know. “The Codebreakers,” by David Kahn. Scribner; ISBN: 0684831309. This bookis a history of codes and code breakers from the time of the Egyptians to theend of WWII. Kahn first wrote it in the sixties, and published a revisededition in 1996. This book won't teach you anything about howcryptography is accomplished, but it has been the inspiration of the wholemodern generation of cryptographers. “Network Security: Private Communication in a Public World,” by CharlieKaufman, Radia Perlman, and Mike Spencer. Prentice Hall; ISBN:0-13-061466-1. This is a good description of network security systems andprotocols, including descriptions of what works, what doesn't work, andwhy. Published in 1995, it doesn't have many of the latest technologicaladvances, but is still a good book. It also contains one of the most cleardescriptions of how DES works of any book written.Intermediate books “Applied Cryptography: Protocols, Algorithms, and Source Code in C,” by BruceSchneier, John Wiley & Sons; ISBN: 0-471-12845-7. This is a good beginningtechnical book on how a lot of cryptography works. If you want to becomean expert, this is the place to start.viiiAn Introduction to Cryptography

Preface “Handbook of Applied Cryptography,” by Alfred J. Menezes, Paul C. vanOorschot, and Scott Vanstone. CRC Press; ISBN: 0-8493-8523-7. This is thetechnical book you should read after Schneier’s book. There is a lot ofheavy-duty math in this book, but it is nonetheless usable for those who donot understand the math. “Internet Cryptography,” by Richard E. Smith. Addison-Wesley Pub Co;ISBN: 0201924803. This book describes how many Internet securityprotocols work. Most importantly, it describes how systems that aredesigned 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 BellLabs and is about their experiences maintaining and redesigning AT&T'sInternet 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-levelmathematics textbook on number theory and cryptography. “Differential Cryptanalysis of the Data Encryption Standard,” by Eli Biham andAdi Shamir. Springer-Verlag; ISBN: 0-387-97930-1. This book describes thetechnique of differential cryptanalysis as applied to DES. It is an excellentbook for learning about this technique.An Introduction to Cryptographyix

PrefacexAn Introduction to Cryptography

The Basics of Cryptography11When Julius Caesar sent messages to his generals, he didn't trust hismessengers. So he replaced every A in his messages with a D, every B with anE, 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 decryptionData that can be read and understood without any special measures is calledplaintext or cleartext. The method of disguising plaintext in such a way as tohide its substance is called encryption. Encrypting plaintext results inunreadable gibberish called ciphertext. You use encryption to ensure thatinformation is hidden from anyone for whom it is not intended, even thosewho can see the encrypted data. The process of reverting ciphertext to itsoriginal plaintext is called decryption.Figure 1-1 illustrates this intextFigure 1-1. Encryption and decryptionWhat is cryptography?Cryptography is the science of using mathematics to encrypt and decrypt data.Cryptography enables you to store sensitive information or transmit it acrossinsecure networks (like the Internet) so that it cannot be read by anyone exceptthe intended recipient.An Introduction to Cryptography11

The Basics of CryptographyWhile cryptography is the science of securing data, cryptanalysis is the scienceof analyzing and breaking secure communication. Classical cryptanalysisinvolves an interesting combination of analytical reasoning, application ofmathematical 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 yourkid sister from reading your files, and cryptography that will stop major governmentsfrom reading your files. This book is about the latter.”--Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and SourceCode in C.PGP is also about the latter sort of cryptography.Cryptography can be strong or weak, as explained above. Cryptographicstrength is measured in the time and resources it would require to recover theplaintext. The result of strong cryptography is ciphertext that is very difficult todecipher without possession of the appropriate decoding tool. How difficult?Given all of today’s computing power and available time—even a billioncomputers doing a billion checks a second—it is not possible to decipher theresult of strong cryptography before the end of the universe.One would think, then, that strong cryptography would hold up rather wellagainst even an extremely determined cryptanalyst. Who’s really to say? Noone has proven that the strongest encryption obtainable today will hold upunder tomorrow’s computing power. However, the strong cryptographyemployed by PGP is the best available today. Vigilance and conservatism willprotect you better, however, than claims of impenetrability.How does cryptography work?A cryptographic algorithm, or cipher, is a mathematical function used in theencryption and decryption process. A cryptographic algorithm works incombination with a key—a word, number, or phrase—to encrypt the plaintext.The same plaintext encrypts to different ciphertext with different keys. Thesecurity of encrypted data is entirely dependent on two things: the strength ofthe cryptographic algorithm and the secrecy of the key.A cryptographic algorithm, plus all possible keys and all the protocols thatmake it work comprise a cryptosystem. PGP is a cryptosystem.12An Introduction to Cryptography

The Basics of CryptographyConventional cryptographyIn conventional cryptography, also called secret-key or symmetric-keyencryption, one key is used both for encryption and decryption. The DataEncryption Standard (DES) is an example of a conventional cryptosystem thatis widely employed by the Federal Government. Figure 1-2 is an illustration ofthe conventional encryption intextFigure 1-2. Conventional encryptionCaesar’s CipherAn extremely simple example of conventional cryptography is a substitutioncipher. A substitution cipher substitutes one piece of information for another.This is most frequently done by offsetting letters of the alphabet. Two examplesare Captain Midnight’s Secret Decoder Ring, which you may have owned whenyou were a kid, and Julius Caesar’s cipher. In both cases, the algorithm is tooffset 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 withABCDEFGHIJKLMNOPQRSTUVWXYZand sliding everything up by 3, you getDEFGHIJKLMNOPQRSTUVWXYZABCwhere D A, E B, F C, and so on.An Introduction to Cryptography13

The Basics of CryptographyUsing this scheme, the plaintext, “SECRET” encrypts as “VHFUHW.” Toallow someone else to read the ciphertext, you tell them that the key is 3.Obviously, this is exceedingly weak cryptography by today’s standards, buthey, it worked for Caesar, and it illustrates how conventional cryptographyworks.Key management and conventional encryptionConventional encryption has benefits. It is very fast. It is especially useful forencrypting data that is not going anywhere. However, conventionalencryption alone as a means for transmitting secure data can be quiteexpensive simply due to the difficulty of secure key distribution.Recall a character from your favorite spy movie: the person with a lockedbriefcase handcuffed to his or her wrist. What is in the briefcase, anyway? It’sprobably not the missile launch code/biotoxin formula/invasion plan itself.It’s the key that will decrypt the secret data.For a sender and recipient to communicate securely using conventionalencryption, they must agree upon a key and keep it secret betweenthemselves. If they are in different physical locations, they must trust a courier,the Bat Phone, or some other secure communication medium to prevent thedisclosure of the secret key during transmission. Anyone who overhears orintercepts the key in transit can later read, modify, and forge all informationencrypted or authenticated with that key. From DES to Captain Midnight’sSecret Decoder Ring, the persistent problem with conventional encryption iskey distribution: how do you get the key to the recipient without someoneintercepting it?Public key cryptographyThe problems of key distribution are solved by public key cryptography, theconcept of which was introduced by Whitfield Diffie and Martin Hellman in1975. (There is now evidence that the British Secret Service invented it a fewyears before Diffie and Hellman, but kept it a military secret—and did nothingwith it.)1Public key cryptography is an asymmetric scheme that uses a pair of keys forencryption: a public key, which encrypts data, and a corresponding private, orsecret key for decryption. You publish your public key to the world whilekeeping your private key secret. Anyone with a copy of your public key can thenencrypt information 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.[CESG is the UK’s National Authority for the official use of cryptography.]14An Introduction to Cryptography

The Basics of CryptographyIt 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 theinformation.public keyprivate tFigure 1-3. Public key encryptionThe primary benefit of public key cryptography is that it allows people whohave no preexisting security arrangement to exchange messages securely. Theneed for sender and receiver to share secret keys via some secure channel iseliminated; all communications involve only public keys, and no private keyis ever transmitted or shared. Some examples of public-key cryptosystems areElgamal (named for its inventor, Taher Elgamal), RSA (named for itsinventors, Ron Rivest, Adi Shamir, and Leonard Adleman), Diffie-Hellman(named, you guessed it, for its inventors), and DSA, the Digital SignatureAlgorithm (invented by David Kravitz).Because conventional cryptography was once the only available means forrelaying secret information, the expense of secure channels and keydistribution relegated its use only to those who could afford it, such asgovernments and large banks (or small children with secret decoder rings).Public key encryption is the technological revolution that provides strongcryptography to the adult masses. Remember the courier with the lockedbriefcase handcuffed to his wrist? Public-key encryption puts him out ofbusiness (probably to his relief).An Introduction to Cryptography15

The Basics of CryptographyHow PGP worksPGP combines some of the best features of both conventional and public keycryptography. PGP is a hybrid cryptosystem.When a user encrypts plaintext with PGP, PGP first compresses the plaintext.Data compression saves modem transmission time and disk space and, moreimportantly, strengthens cryptographic security. Most cryptanalysistechniques exploit patterns found in the plaintext to crack the cipher.Compression reduces these patterns in the plaintext, thereby greatlyenhancing resistance to cryptanalysis. (Files that are too short to compress orwhich don’t compress well aren’t compressed.)PGP then creates a session key, which is a one-time-only secret key. This key isa random number generated from the random movements of your mouse andthe keystrokes you type. This session key works with a very secure, fastconventional encryption algorithm to encrypt the plaintext; the result isciphertext. Once the data is encrypted, the session key is then encrypted to therecipient’s public key. This public key-encrypted session key is transmittedalong with the ciphertext to the recipient.plaintext is encryptedwith session keysession key is encryptedwith public keyciphertext encrypted session keyFigure 1-4. How PGP encryption works16An Introduction to Cryptography

The Basics of CryptographyDecryption works in the reverse. The recipient’s copy of PGP uses his or herprivate key to recover the temporary session key, which PGP then uses todecrypt the conventionally-encrypted ciphertext.encrypted messageencryptedsession keyrecipient’s private key usedto decrypt session keyciphertextsession key usedto decrypt ciphertextoriginalplaintextFigure 1-5. How PGP decryption worksThe combination of the two encryption methods combines the convenience ofpublic key encryption with the speed of conventional encryption.Conventional encryption is about 1,000 times faster than public keyencryption. Public key encryption in turn provides a solution to keydistribution and data transmission issues. Used together, performance andkey distribution are improved without any sacrifice in security.KeysA key is a value that works with a cryptographic algorithm to produce aspecific ciphertext. Keys are basically really, really, really big numbers. Keysize 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 aretotally unrelated. A conventional 80-bit key has the equivalent strength of a1024-bit public key. A conventional 128-bit key is equivalent to a 3000-bitpublic key. Again, the bigger the key, the more secure, but the algorithms usedfor each type of cryptography are very different and thus comparison is likethat of apples to oranges.An Introduction to Cryptography17

The Basics of CryptographyWhile the public and private keys are mathematically related, it’s very difficultto derive the private key given only the public key; however, deriving theprivate key is always possible given enough time and computing power. Thismakes it very important to pick keys of the right size; large enough to besecure, but small enough to be applied fairly quickly. Additionally, you needto 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. Ifwhat you want to encrypt needs to be hidden for many years, you might wantto use a very large key. Of course, who knows how long it will take todetermine your key using tomorrow’s faster, more efficient computers? Therewas 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 yourhard disk; one for public keys and one for private keys. These files are calledkeyrings. As you use PGP, you will typically add the public keys of yourrecipients to your public keyring. Your privat

The Basics of Cryptography 12 An Introduction to Cryptography While cryptography is the science of securing data, cryptanalysisis the science of analyzing and breaking secure communication. Classical cryptanalysis involves an intere