" ... the best introduction
`to cryptography I've
`ever seen .... The book
`the National Security
`Agency wanted never
`to be published .... "
`-Wired Magazine
`
`SAMSUNG EX. 1024 - 1/21
`
`

`

`New York
`
`John Wiley & Sons, Inc.
`• Chichester
`• Brisbane
`• Toronto
`
`• Singapore
`
`SAMSUNG EX. 1024 - 2/21
`
`

`

`Publisher: Katherine Schowalter
`Editor: Phil Sutherland
`Assistant Editor: Allison Roarty
`Managing Editor: Robert Aronds
`Text Design & Composition: North Market Street Graphics
`Designations used by companies to distinguish their products are often claimed as trademarks. In all
`instances where John Wiley & Sons, Inc. is aware of a claim, the product names appear in initial capital
`or all capital letters. Readers, however, should contact the appropriate companies for more complete
`information regarding trademarks and registration.
`This text is printed on acid-free paper.
`Copyright© 1996 by Bruce Schneier
`Published by John Wiley & Sons, Inc.
`All rights reserved. Published simultaneously in Canada.
`This publication is designed to provide accurate and authoritative information in regard to the subject
`matter covered. It is sold with the understanding that the publisher is not engaged in rendering legal,
`accounting, or other professional service. If legal advice or other expert assistance is required, the services
`of a competent professional person should be sought.
`In no event will the publisher or author be liable for any consequential, incidental, or indirect damages
`(including damages for loss of business profits, business interruption, loss of business information, and
`the like) arising from the use or inability to use the protocols and algorithms in this book, even if the pub-
`lisher or author has been advised of the possibility of such damages.
`Some of the protocols and algorithms in this book are protected by patents and copyrights. It is the
`responsibility of the reader to obtain all necessary patent and copyright licenses before implementing in
`software any protocol or algorithm in this book. This book does not contain an exhaustive list of all appli-
`cable patents and copyrights.
`Some of the protocols and algorithms in this book are regulated under the United States Department of
`State International Traffic in Arms Regulations. It is the responsibility of the reader to obtain all neces-
`sary export licenses before implementing in software for export any protocol or algorithm in this book.
`Reproduction or translation of any part of this work beyond that permitted by section 107 or 108 of the
`1976 United States Copyright Act without the permission of the copyright owner is unlawful. Requests
`for permission or further information should be addressed to the Permissions Department, John Wiley &
`Sons, Inc.
`
`Library of Congress Cataloging-in-Publication Data:
`Schneier, Bruce
`Applied Cryptography Second Edition: protocols, algorithms, and source code inC
`/ Bruce Schneier.
`p.
`em.
`Includes bibliographical references (p. 675).
`ISBN 0-471-12845-7 (cloth: acid-free paper).- ISBN
`0-471-11709-9 (paper: acid-free paper)
`1. Computer security. 2. Telecommunication-Security measures.
`3. Cryptography.
`I. Title.
`QA76.9.A25S35
`1996
`005.8'2-dc20
`
`95-12398
`CIP
`
`Printed in the United States of America
`10 9 8 7 6
`
`SAMSUNG EX. 1024 - 3/21
`
`

`

`Contents
`
`10.6 COMPRESSION, ENCODING, AND ENCRYPTION 226
`10.7 DETECTING ENCRYPTION 226
`10.8 HIDING CIPHERTEXT IN CIPHERTEXT 227
`10.9 DESTROYING INFORMATION 228
`
`PART Ill CRYPTOGRAPHIC ALGORITHMS
`11 MATHEMATICAL BACKGROUND 233
`11.1
`INFORMATION THEORY 233
`11.2 COMPLEXITY THEORY 23 7
`11.3 NUMBER THEORY 242
`11.4 FACTORING 255
`11.5 PRIME NUMBER GENERATION 258
`11.6 DISCRETE LOGARITHMS IN A FINITE FIELD 261
`12 DATA ENCRYPTION STANDARD (DES) 265
`12.1 BACKGROUND 265
`12.2 DESCRIPTION OF DES 270
`12.3 SECURITY OF DES 278
`12.4 DIFFERENTIAL AND LINEAR CRYPTANALYSIS 285
`12.5 THE REAL DESIGN CRITERIA 293
`12.6 DES VARIANTS 294
`12.7 How SECURE Is DES TODAY? 300
`13 OTHER BLOCK CIPHERS 303
`13.1 LUCIFER 303
`13.2 MADRYGA 304
`13.3 NEwDES 306
`13.4 PEAL 308
`13.5 REDOC 311
`13.6 LOKI 314
`13.7 KHuFU AND KHAFRE 316
`13.8 RC2 318
`13.9 IDEA 319
`13.10 MMB 325
`13.11 CA-1.1 327
`13.12 SKIPJACK 328
`14 STILL OTHER BLOCK CIPHERS 331
`14.1 COST 331
`14.2 CAST 334
`14.3 BLOWFISH 336
`14.4 SAFER 339
`14.5 3-WAY 341
`
`SAMSUNG EX. 1024 - 4/21
`
`

`

`Contents
`
`14.6 CRAB 342
`14.7 SXAL8/MBAL 344
`14.8 RC5 344
`14.9 OTHER BLOCK ALGORITHMS 346
`14.10 THEORY OF BLOCK CIPHER DESIGN 346
`14.11 USING ONE-WAY HASH FUNCTIONS 351
`14.12 CHOOSING A BLOCK ALGORITHM 354
`15 COMBINING BLOCK CIPHERS 357
`15.1 DOUBLE ENCRYPTION 35 7
`15.2 TRIPLE ENCRYPTION 358
`15.3 DOUBLING THE BLOCK LENGTH 363
`15.4 OTHER MULTIPLE ENCRYPTION SCHEMES 363
`15.5 CDMF KEY SHORTENING 366
`15.6 WHITENING 366
`15.7 CASCADING MULTIPLE BLOCK ALGORITHMS 367
`15.8 COMBINING MULTIPLE BLOCK ALGORITHMS 368
`16 PSEUDO-RANDOM-SEQUENCE
`GENERATORS AND STREAM CIPHERS 369
`16.1 LINEAR CONGRUENTIAL GENERATORS 369
`16.2 LINEAR FEEDBACK SHIFT REGISTERS 372
`16.3 DESIGN AND ANALYSIS OF STREAM CIPHERS 379
`16.4 STREAM CIPHERS USING LFSRs 381
`16.5 AS 389
`16.6 HUGHES XPD/KPD 389
`16.7 NANOTEQ 390
`16.8 RAMBUTAN 390
`16.9 ADDITIVE GENERATORS 390
`16.10 GIFFORD 392
`393
`16.11 ALGORITHM M
`16.12 PKZIP 394
`17 OTHER STREAM CIPHERS AND REAL
`RANDOM-SEQUENCE GENERATORS 397
`17.1 RC4 397
`17.2 SEAL 398
`17.3 WAKE 400
`1 7.4 FEEDBACK WITH CARRY SHIFT REGISTERS 402
`17.5 STREAM CIPHERS USING FCSRs 405
`17.6 NONLINEAR-FEEDBACK SHIFT REGISTERS 412
`1 7. 7 OTHER STREAM CIPHERS 413
`17.8 SYSTEM-THEORETIC APPROACH TO STREAM-CIPHER DESIGN 415
`17.9 COMPLEXITY-THEMATIC APPROACH TO STREAM-CIPHER DESIGN 416
`17.10 OTHER APPROACHES TO STREAM-CIPHER DESIGN 418
`
`SAMSUNG EX. 1024 - 5/21
`
`

`

`Contents
`
`17.11 CASCADING MULTIPLE STREAM CIPHERS 419
`17.12 CHOOSING A STREAM CIPHER 420
`17.13 GENERATING MULTIPLE STREAMS FROM A
`SINGLE PSEUDO-RANDOM-SEQUENCE GENERATOR 420
`17.14 REAL RANDOM-SEQUENCE GENERATORS 421
`18 ONE-WAY HASH FUNCTIONS 429
`18.1 BACKGROUND 429
`18.2 SNEFRU 431
`18.3 N-HASH 432
`18.4 MD4 435
`18.5 MD5 436
`18.6 MD2 441
`18.7 SECURE HASH ALGORITHM (SHA) 441
`18.8 RIPE-MD 445
`18.9 HAVAL 445
`18.10 OTHER ONE-WAY HASH FUNCTIONS 446
`18.11 ONE-WAY HASH FUNCTIONS USING SYMMETRIC BLOCK ALGORITHMS 446
`18.12 USING PUBLIC-KEY ALGORITHMS 455
`18.13 CHOOSING A ONE-WAY HASH FUNCTION 455
`18.14 MESSAGE AUTHENTICATION CODES 455
`19 PUBLIC-KEY ALGORITHMS 461
`19.1 BACKGROUND 461
`19.2 KNAPSACK ALGORITHMS 462
`19.3 RSA 466
`19.4 POHLIG-HELLMAN 474
`19.5 RABIN 475
`19.6 ELGAMAL 476
`19.7 McELIECE 479
`19.8 ELLIPTIC CURVE CRYPTOSYSTEMS 480
`19.9 LUC 481
`19.10 FINITE AUTOMATON PUBLIC-KEY CRYPTOSYSTEMS 482
`20 PUBLIC-KEY DIGITAL SIGNATURE ALGORITHMS 483
`20.1 DIGITAL SIGNATURE ALGORITHM (DSA) 483
`20.2 DSA VARIANTS 494
`20.3 GOST DIGITAL SIGNATURE ALGORITHM 495
`20.4 DISCRETE LOGARITHM SIGNATURE SCHEMES 496
`20.5 ONG-SCHNORR-SHAMIR 498
`20.6 ESIGN 499
`20.7 CELLULAR AUTOMATA 500
`20.8 OTHER PUBLIC-KEY ALGORITHMS 500
`21 IDENTIFICATION SCHEMES 503
`21.1 FEIGE-FIAT-SHAMIR 503
`
`SAMSUNG EX. 1024 - 6/21
`
`

`

`Contents
`
`21.2 GUILLOU-QUISQUATER 508
`21.3 SCHNORR 510
`21.4 CONVERTING IDENTIFICATION SCHEMES TO SIGNATURE SCHEMES 512
`22 KEY-EXCHANGE ALGORITHMS 513
`22.1 DIFFIE-HELLMAN 513
`22.2 STATION-TO-STATION PROTOCOL 516
`22.3 SHAMIR'S THREE-PASS PROTOCOL 516
`22.4 COMSET 517
`22.5 ENCRYPTED KEY EXCHANGE 518
`22.6 FORTIFIED KEY NEGOTIATION 522
`22.7 CONFERENCE KEY DISTRIBUTION AND SECRET BROADCASTING 523
`23 SPECIAL ALGORITHMS FOR PROTOCOLS 527
`23.1 MULTIPLE-KEY PUBLIC-KEY CRYPTOGRAPHY 527
`23.2 SECRET-SHARING ALGORITHMS 528
`23.3 SUBLIMINAL CHANNEL 531
`23.4 UNDENIABLE DIGITAL SIGNATURES 536
`23.5 DESIGNATED CONFIRMER SIGNATURES 539
`23.6 COMPUTING WITH ENCRYPTED DATA 540
`23.7 FAIR CoiN FLIPS 541
`23.8 ONE-WAY ACCUMULATORS 543
`23.9 ALL-OR-NOTHING DISCLOSURE OF SECRETS 543
`23.10 FAIR AND FAILSAFE CRYPTOSYSTEMS 546
`23.11 ZERO-KNOWLEDGE PROOFS OF KNOWLEDGE 548
`23.12 BLIND SIGNATURES 549
`23.13 OBLIVIOUS TRANSFER 550
`23.14 SECURE MULTIPARTY COMPUTATION 551
`23.15 PROBABILISTIC ENCRYPTION 552
`23.16 QUANTUM CRYPTOGRAPHY 554
`
`PART IV THE REAL WORLD
`24 EXAMPLE IMPLEMENTATIONS 561
`24.1
`IBM SECRET-KEY MANAGEMENT PROTOCOL 561
`24.2 MITRENET 562
`24.3 ISDN 563
`24.4 STU-III 565
`24.5 KERBEROS 566
`24.6 KRYPTOKN!GHT 571
`24.7 SESAME 5 72
`24.8
`IBM COMMON CRYPTOGRAPHIC ARCHITECTURE 573
`24.9
`ISO AUTHENTICATION FRAMEWORK 574
`24.10 PRIVACY-ENHANCED MAIL (PEM) 577
`24.11 MESSAGE SECURITY PROTOCOL (MSP) 584
`
`SAMSUNG EX. 1024 - 7/21
`
`

`

`CHAPTER 1 Foundations
`
`More recently, people are hiding secret messages in graphic images. Replace the
`least significant bit of each byte of the image with the bits of the message. The
`graphical image won't change appreciably-most graphics standards specify more
`gradations of color than the human eye can notice-and the message can be stripped
`out at the receiving end. You can store a 64-kilobyte message in a 1024 x 1024 grey-
`scale picture this way. Several public-domain programs do this sort of thing.
`Peter Wayner's mimic functions obfuscate messages. These functions modify a
`message so that its statistical profile resembles that of something else: the classi-
`fieds section of The New York Times, a play by Shakespeare, or a newsgroup on the
`Internet [1584, 1585]. This type of steganography won't fool a person, but it might
`fool some big computers scanning the Internet for interesting messages.
`1.3 SUBSTITUTION CIPHERS AND TRANSPOSITION CIPHERS
`Before computers, cryptography consisted of character-based algorithms. Different
`cryptographic algorithms either substituted characters for one another or transposed
`characters with one another. The better algorithms did both, many times each.
`Things are more complex these days, but the philosophy remains the same. The
`primary change is that algorithms work on bits instead of characters. This is actu-
`ally just a change in the alphabet size: from 26 elements to two elements. Most good
`cryptographic algorithms still combine elements of substitution and transposition.
`Substitution Ciphers
`A substitution cipher is one in which each character in the plaintext is substi-
`tuted for another character in the ciphertext. The receiver inverts the substitution
`on the ciphertext to recover the plaintext.
`In classical cryptography, there are four types of substitution ciphers:
`A simple substitution cipher, or monoalphabetic cipher, is one in
`which each character of the plaintext is replaced with a correspond-
`ing character of ciphertext. The cryptograms in newspapers are sim-
`ple substitution ciphers.
`A homophonic substitution cipher is like a simple substitution cryp-
`tosystem, except a single character of plaintext can map to one of sev-
`eral characters of ciphertext. For example, "A" could correspond to
`either 5, 13, 25, or 56, "B" could correspond to either 7, 19, 31, or 42,
`and so on.
`A polygram substitution cipher is one in which blocks of characters
`are encrypted in groups. For example, "ABA" could correspond to
`"RTQ," "ABB" could correspond to "SLL," and so on.
`A polyalphabetic substitution cipher is made up of multiple simple
`substitution ciphers. For example, there might be five different sim-
`ple substitution ciphers used; the particular one used changes with
`the position of each character of the plaintext.
`
`SAMSUNG EX. 1024 - 8/21
`
`

`

`1.3 Substitution Ciphers and Transposition Ciphers
`
`The famous Caesar Cipher, in which each plaintext character is replaced by the
`character three to the right modulo 26 ("A" is replaced by "D," "B" is replaced by
`"E," . .. , "W" is replaced by "Z," "X" is replaced by "A," "Y" is replaced by "B,"
`and "Z" is replaced by "C") is a simple substitution cipher. It's actually even sim-
`pler, because the ciphertext alphabet is a rotation of the plaintext alphabet and not
`an arbitrary permutation.
`ROT13 is a simple encryption program commonly found on UNIX systems; it is
`also a simple substitution cipher. In this cipher, "A" is replaced by "N," "B" is
`replaced by "0," and so on. Every letter is rotated 13 places.
`Encrypting a file twice with ROT13 restores the original file.
`P = ROT13 (ROT13 (P))
`ROT13 is not intended for security; it is often used in Usenet posts to hide poten-
`tially offensive text, to avoid giving away the solution to a puzzle, and so forth.
`Simple substitution ciphers can be easily broken because the cipher does not hide
`the underlying frequencies of the different letters of the plaintext. All it takes is
`about 25 English characters before a good cryptanalyst can reconstruct the plaintext
`[1434]. An algorithm for solving these sorts of ciphers can be found in [578,587,
`1600,78,1475, 1236,880]. A good computer algorithm is [703].
`Homophonic substitution ciphers were used as early as 1401 by the Duchy of Man-
`tua [794]. They are much more complicated to break than simple substitution ciphers,
`but still do not obscure all of the statistical properties of the plaintext language. With
`a known-plaintext attack, the ciphers are trivial to break. A ciphertext-only attack is
`harder, but only takes a few seconds on a computer. Details are in [1261].
`Polygram substitution ciphers are ciphers in which groups of letters are encrypted
`together. The Playfair cipher, invented in 1854, was used by the British during
`World War I [794]. It encrypts pairs of letters together. Its cryptanalysis is discussed
`in [587, 1475,880]. The Hill cipher is another example of a polygram substitution
`cipher [732]. Sometimes you see Huffman coding used as a cipher; this is an insecure
`polygram substitution cipher.
`Polyalphabetic substitution ciphers were invented by Leon Battista in 1568 [794].
`They were used by the Union army during the American Civil War. Despite the fact
`that they can be broken easily [819,577,587, 794] (especially with the help of com-
`puters), many commercial computer security products use ciphers of this form
`[1387, 1390, 1502]. (Details on how to break this encryption scheme, as used in Word-
`Perfect, can be found in [135, 139].) The Vigenere cipher, first published in 1586, and
`the Beaufort cipher are also examples of polyalphabetic substitution ciphers.
`Polyalphabetic substitution ciphers have multiple one-letter keys, each of which
`is used to encrypt one letter of the plaintext. The first key encrypts the first letter of
`the plaintext, the second key encrypts the second letter of the plaintext, and so on.
`After all the keys are used, the keys are recycled. If there were 20 one-letter keys,
`then every twentieth letter would be encrypted with the same key. This is called the
`period of the cipher. In classical cryptography, ciphers with longer periods were sig-
`nificantly harder to break than ciphers with short periods. There are computer tech-
`niques that can easily break substitution ciphers with very long periods.
`
`SAMSUNG EX. 1024 - 9/21
`
`

`

`CHAPTER 2 Protocol Building Blocks
`
`2.2 COMMUNICATIONS USING SYMMETRIC CRYPTOGRAPHY
`How do two parties communicate securely? They encrypt their communications, of
`course. The complete protocol is more complicated than that. Let's look at what
`must happen for Alice to send an encrypted message to Bob.
`( 1) Alice and Bob agree on a cryptosystem.
`(2) Alice and Bob agree on a key.
`(3) Alice takes her plaintext message and encrypts it using the encryption
`algorithm and the key. This creates a ciphertext message.
`(4) Alice sends the ciphertext message to Bob.
`(5) Bob decrypts the ciphertext message with the same algorithm and key and
`reads it.
`What can Eve, sitting between Alice and Bob, learn from listening in on this pro-
`tocol? If all she hears is the transmission in step (4), she must try to cryptanalyze the
`ciphertext. This passive attack is a ciphertext-only attack; we have algorithms that
`are resistant (as far as we know) to whatever computing power Eve could realisti-
`cally bring to bear on the problem.
`Eve isn't stupid, though. She also wants to listen in on steps ( 1) and (2). Then, she
`would know the algorithm and the key-
`just as well as Bob. When the message
`comes across the communications channel in step (4), all she has to do is decrypt it
`herself.
`A good cryptosystem is one in which all the security is inherent in knowledge
`of the key and none is inherent in knowledge of the algorithm. This is why key
`management is so important in cryptography. With a symmetric algorithm, Alice
`and Bob can perform step (1) in public, but they must perform step (2) in secret.
`The key must remain secret before, during, and after the protocol- as long as the
`message must remain secret- otherwise the message will no longer be secure.
`(Public-key cryptography solves this problem another way, and will be discussed
`in Section 2.5.)
`Mallory, an active attacker, could do a few other things. He could attempt to
`break the communications path in step (4), ensuring that Alice could not talk to Bob
`at all. Mallory could also intercept Alice's messages and substitute his own. If he
`knew the key (by intercepting the communication in step (2), or by breaking the
`cryptosystem), he could encrypt his own message and send it to Bob in place of the
`intercepted message. Bob would have no way of knowing that the message had not
`come from Alice. If Mallory didn't know the key, he could only create a replacement
`message that would decrypt to gibberish.•Bob, thinking the message came from
`Alice, might conclude that either the network or Alice had some serious problems.
`What about Alice? What can she do to disrupt the protocol? She can give a copy of
`the key to Eve. Now Eve can read whatever Bob says. She can reprint his words in
`The New York Times. Although serious, this is not a problem with the protocol.
`There is nothing to stop Alice from giving Eve a copy of the plaintext at any point
`
`SAMSUNG EX. 1024 - 10/21
`
`

`

`2.3 One-Way Functions
`
`during the protocol. Of course, Bob could also do anything that Alice could. This
`protocol assumes that Alice and Bob trust each other.
`In summary, symmetric cryptosystems have the following problems:
`Keys must be distributed in secret. They are as valuable as all the
`messages they encrypt, since knowledge of the key gives knowledge
`of all the messages. For encryption systems that span the world, this
`can be a daunting task. Often couriers hand-carry keys to their desti-
`nations.
`If a key is compromised (stolen, guessed, extorted, bribed, etc.), then
`Eve can decrypt all message traffic encrypted with that key. She can
`also pretend to be one of the parties and produce false messages to
`fool the other party.
`Assuming a separate key is used for each pair of users in a network,
`the total number of keys increases rapidly as the number of users
`increases. A network of n users requires n(n - 1)/2 keys. For example,
`10 users require 45 different keys to talk with one another and 100
`users require 4950 keys. This problem can be minimized by keeping
`the number of users small, but that is not always possible.
`2.3 ONE-WAY FUNCTIONS
`The notion of a one-way function is central to public-key cryptography. While not
`protocols in themselves, one-way functions are a fundamental building block for
`most of the protocols discussed in this book.
`One-way functions are relatively easy to compute, but significantly harder to
`reverse. That is, given x it is easy to compute f(x), but given f(x) it is hard to compute
`x. In this context, "hard" is defined as something like: It would take millions of
`years to compute x from f(x), even if all the computers in the world were assigned to
`the problem.
`Breaking a plate is a good example of a one-way function. It is easy to smash a
`plate into a thousand tiny pieces. However, it's not easy to put all of those tiny
`pieces back together into a plate.
`This sounds good, but it's a lot of smoke and mirrors. If we are being strictly math-
`ematical, we have no proof that one-way functions exist, nor any real evidence that
`they can be constructed [230,530,600,661]. Even so, many functions look and smell
`one-way: We can compute them efficiently and, as of yet, know of no easy way to
`reverse them. For example, in a finite field x2 is easy to compute, but x1/2 is much
`arder. For the rest of this section, I'm going to pretend that there are one-way func-
`:i.ons. I'll talk more about this in Section 11.2.
`So, what good are one-way functions? We can't use them for encryption as is. A
`:::tessage encrypted with the one-way function isn't useful; no one could decrypt it.
`Exercise: Write a message on a plate, smash the plate into tiny bits, and then give
`-- e bits to a friend. Ask your friend to read the message. Observe how impressed
`
`SAMSUNG EX. 1024 - 11/21
`
`

`

`CHAPTER 2 Protocol Building Blocks
`
`he is with the one-way function.) For public-key cryptography, we need something
`else (although there are cryptographic applications for one-way functions-see
`Section 3.2).
`A trapdoor one-way function is a special type of one-way function, one with a
`secret trapdoor. It is easy to compute in one direction and hard to compute in the
`other direction. But, if you know the secret, you can easily compute the function in
`the other direction. That is, it is easy to compute f(x) given x, and hard to compute
`x given f(x). However, there is some secret information, y, such that given f(x) andy
`it is easy to compute x.
`Taking a watch apart is a good example of a trap-door one-way function. It is easy
`to disassemble a watch into hundreds of minuscule pieces. It is very difficult to put
`those tiny pieces back together into a working watch. However, with the secret
`information-the assembly instructions of the watch- it is much easier to put the
`watch back together.
`2.4 ONE-WAY HASH fUNCTIONS
`A one-way hash function has many names: compression function, contraction func-
`tion, message digest, fingerprint, cryptographic checksum, message integrity check
`(MIC), and manipulation detection code (MDC). Whatever you call it, it is central to
`modern cryptography. One-way hash functions are another building block for many
`protocols.
`Hash functions have been used in computer science for a long time. A hash func-
`tion is a function, mathematical or otherwise, that takes a variable-length input
`string (called a pre-image) and converts it to a fixed-length (generally smaller) output
`string (called a hash value). A simple hash function would be a function that takes
`pre-image and returns a byte consisting of the XOR of all the input bytes.
`The point here is to fingerprint the pre-image: to produce a value that indicates
`whether a candidate pre-image is likely to be the same as the real pre-image.
`Because hash functions are typically many-to-one, we cannot use them to deter-
`mine with certainty that the two strings are equal, but we can use them to get a rea-
`sonable assurance of accuracy.
`A one-way hash function is a hash function that works in one direction: It is easy
`to compute a hash value from pre-image, but it is hard to generate a pre-image that
`hashes to a particular value. The hash function previously mentioned is not one-
`way: Given a particular byte value, it is trivial to generate a string of bytes whose
`XOR is that value. You can't do that with a one-way hash function. A good one-way
`hash function is also collision-free: It is hard to generate two pre-images with the
`same hash value.
`The hash function is publici there's no secrecy to the process. The security of a
`one-way hash function is its one-wayness. The output is not dependent on the input
`in any discernible way. A single bit change in the pre-image changes, on the average,
`half of the bits in the hash value. Given a hash value, it is computationally unfeasi-
`ble to find a pre-image that hashes to that value.
`
`0
`p
`n
`0
`tl
`
`SAMSUNG EX. 1024 - 12/21
`
`

`

`I
`
`I
`
`2.5 Communications Using Public-Key Cryptography
`
`Think of it as a way of fingerprinting files. If you want to verify that someone has
`a particular file (that you also have), but you don't want him to send it to you, then
`ask him for the hash value. If he sends you the correct hash value, then it is almost
`certain that he has that file. This is particularly useful in financial transactions,
`where you don't want a withdrawal of $100 to turn into a withdrawal of $1000
`somewhere in the network. Normally, you would use a one-way hash function
`without a key, so tliat anyone can verify the hash. If you want only the recipient to
`be able to verify the hash, then read the next section.
`Message Authentication Codes
`A message authentication code (MAC), also known as a data authentication code
`DAC), is a one-way hash function with the addition of a secret key (see Section
`18.14). The hash value is a function of both the pre-image and the key. The theory
`is exactly the same as hash functions, except only someone with the key can verify
`the hash value. You can create a MAC out of a hash function or a block encryption
`algorithm; there are also dedicated MACs.
`2.5 COMMUNICATIONS USING Pusuc-KEY CRYPTOGRAPHY
`Think of a symmetric algorithm as a safe. The key is the combination. Someone
`with the combination can open the safe, put a document inside, and close it again.
`omeone else with the combination can open the safe and take the document out.
`Anyone without the combination is forced to learn safecracking.
`In 1976, Whitfield Diffie and Martin Hellman changed that paradigm of cryptog-
`raphy forever [496]. (The NSA has claimed knowledge of the concept as early as
`.966, but has offered no proof.) They described public-key cryptography. They used
`:.vo different keys-one public and the other private. It is computationally hard to
`educe the private key from the public key. Anyone with the public key can encrypt
`a message but not decrypt it. Only the person with the private key can decrypt the
`:nessage. It is as if someone turned the cryptographic safe into a mailbox. Putting
`mail in the mailbox is analogous to encrypting with the public key; anyone can do
`it. Just open the slot and drop it in. Getting mail out of a mailbox is analogous to
`ecrypting with the private key. Generally it's hard; you need welding torches.
`However, if you have the secret (the physical key to the mailbox), it's easy to get
`mail out of a mailbox.
`Mathematically, the process is based on the trap-door one-way functions previ-
`ously discussed. Encryption is the easy direction. Instructions for encryption are the
`public key; anyone can encrypt a message. Decryption is the hard direction. It's
`made hard enough that people with Cray computers and thousands (even millions)
`of years couldn't decrypt the message without the secret. The secret, or trapdoor, is
`the private key. With that secret, decryption is as easy as encryption.
`This is how Alice can send a message to Bob using public-key cryptography:
`(1) Alice and Bob agree on a public-key cryptosystem.
`
`1
`
`{
`t
`t
`
`k
`D
`'I
`
`t
`t
`s
`s
`._
`l-
`
`'I
`t
`e
`'I
`e
`a
`Lt
`i-
`
`SAMSUNG EX. 1024 - 13/21
`
`

`

`_______ C_HAP ___ T_E_R_2 __ P_r_o_t_o_co_l_B_u_l_.ld_l_·n_g_B_l_o_ck_s ____________________
`
`(2) Bob sends Alice his public key.
`(3) Alice encrypts her message using Bob's public key and sends it to Bob.
`(4) Bob decrypts Alice's message using his private key.
`Notice how public-key cryptography solves the key-management problem with
`symmetric cryptosystems. Before, Alice and Bob had to agree on a key in secret.
`Alice could choose one at random, but she still had to get it to Bob. She could hand
`it to him sometime beforehand, but that requires foresight. She could send it to him
`by secure courier, but that takes time. Public-key cryptography makes it easy. With
`no prior arrangements, Alice can send a secure message to Bob. Eve, listening in on
`the entire exchange, has Bob's public key and a message encrypted in that key, but
`cannot recover either Bob's private key or the message.
`More commonly, a network of users agrees on a public-key cryptosystem. Every
`user has his or her own public key and private key, and the public keys are all pub-
`lished in a database somewhere. Now the protocol is even easier:
`( 1) Alice gets Bob's public key from the database.
`(2) Alice encrypts her message using Bob's public key and sends it to Bob.
`(3) Bob then decrypts Alice's message using his private key.
`In the first protocol, Bob had to send Alice his public key before she could send
`him a message. The second protocol is more like traditional mail. Bob is not
`involved in the protocol until he wants to read his message.
`Hybrid Cryptosystems
`The first public-key algorithms became public at the same time that DES was
`being discussed as a proposed standard. This resulted in some partisan politics in the
`cryptographic community. As Diffie described it [494]:
`The excitement public key cryptosystems provoked in the popular and scientific
`press was not matched by corresponding acceptance in the cryptographic estab-
`lishment, however. In the same year that public key cryptography was discovered,
`the National Security Agency (NSA), proposed a conventional cryptographic sys-
`tem, designed by International Business Machines (IBM), as a federal Data
`Encryption Standard (DES). Marty Hellman and I criticized the proposal on the
`ground that its key was too small, but manufacturers were
`up to support
`the proposed standard and our criticism was seen by many as an attempt to dis-
`rupt the standards-making process to the advantage of our own work. Public key
`cryptography in its turn was attacked, in sales literature [1125] and technical
`papers [849, 1159] alike, more as though it were a competing product than a recent
`research discovery. This, however, did not deter the NSA from claiming its share
`of the credit. Its director, in the words of the Encyclopedia Britannica [1461],
`pointed out that "two-key cryptography had been discovered at the agency a
`decade earlier," although no evidence for this claim was ever offered publicly.
`
`SAMSUNG EX. 1024 - 14/21
`
`

`

`, __ /"
`
`2.5 Communications Using Public-Key Cryptography
`
`In the real world, public-key algorithms are not a substitute for symmetric algo-
`rithms. They are not used to encrypt messages; they are used to encrypt keys. There
`are two reasons for this:
`
`1. Public-key algorithms are slow. Symmetric algorithms are generally at
`least 1000 times faster than public-key algorithms. Yes, computers are get-
`ting faster and faster, and in 15 years computers will be able to do public-
`key cryptography at speeds comparable to symmetric cryptography today.
`But bandwidth requirements are also increasing, and there will always be
`the need to encrypt data faster than public-key cryptography can manage.
`2. Public-key cryptosystems are vulnerable to chosen-plaintext attacks. If C
`= E(P), when P is one plaintext out of a set of n possible plaintexts, then a
`cryptanalyst only has to encrypt all n possible plaintexts and compare the
`results with C (remember, the encryption key is public). He won't be able
`to recover the decryption key this way, but he will be able to determine P.
`A chosen-plaintext attack can be particularly effective if there are relatively few
`possible encrypted messages. For example, if P were a dollar amount less than
`$1,000,000, this attack would work; the cryptanalyst tries all million possible dollar
`amounts. (Probabilistic encryption solves the problem; see Section 23.15.) Even if P
`is not as well-defined, this attack can be very effective. Simply knowing that a
`ciphertext does not correspond to a particular plaintext can be useful information.
`Symmetric cryptosystems are not vulnerable to this attack because a cryptanalyst
`cannot perform trial encryptions with an unknown key.
`In most practical implementations public-key cryptography is used to secure and
`distribute session keys; those session keys are used with symmetric algorithms to
`secure message traffic [879]. This is sometimes called a hybrid cryptosystem.
`( 1) Bob sends Alice his public key.
`(2) Alice generates a random session key, K, encrypts it using Bob's public key,
`and sends it to Bob.
`EB(K)
`(3) Bob decrypts Alice's message using his private key to recover the session
`key.
`
`DB(EB(K)) = K
`(4) Both of them encrypt their communications using the same session key.
`Using public-key cryptography for key distribution solves a very important key-
`management problem. With symmetric cryptography, the data encryption key sits
`around until it is used. If Eve ever gets her hands on it, she can decrypt messages
`encrypted with it. With the previous protoco