" ... the best introduction
`to cryptography I've
`ever seen .... The book
`the National Security
`Agency wanted never
`to be published .... "
`-Wired Magazine
`
`CELLSPIN
`EX. 2013, Page 1
`
`

`

`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 r~served. 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(cid:173)
`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(cid:173)
`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(cid:173)
`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 in C
`/ Bruce Schneier.
`p.
`cm.
`Includes bibliographical references (p. 675).
`ISBN 0-471-12845-7 (cloth : acid-free paper). -
`0-471-11709-9 (paper : acid-free paper)
`1. Computer security. 2. Telecommunication-Security measures.
`I. Title.
`3. Cryptography.
`QA76.9.A25S35
`1996
`005 .8'2-dc20
`
`ISBN
`
`95-12398
`CIP
`
`Printed in the United States of America
`10 9 8 7 6
`
`CELLSPIN
`EX. 2013, Page 2
`
`

`

`CHAPTER
`
`1
`
`Foundations
`
`1.1 TERMINOLOGY
`Sender and Receiver
`Suppose a sender wants to send a message to a receiver. Moreover, this sender
`wants to send the message securely: She wants to make sure an eavesdropper can(cid:173)
`not read the message.
`
`Messages and Encryption
`A message is plaintext (sometimes called cleartext). The process of disguising a
`message in such a way as to hide its substance is encryption. An encrypted message
`is ciphertext. The process of turning ciphertext back into plaintext is decryption.
`This is all shown in Figure 1.1.
`(If you want to follow the ISO 7 498-2 standard, use the terms "encipher" and
`"decipher." It seems that some cultures find the terms "encrypt" and "decrypt"
`offensive, as they refer to dead bodies.)
`The art and science of keeping messages secure is cryptography, and it is practiced
`by cryptographers. Cryptanalysts are practitioners of cryptanalysis, the art and sci(cid:173)
`ence of breaking ciphertext; that is, seeing through the disguise. The branch of
`mathematics encompassing both cryptography and cryptanalysis is cryptology and
`its practitioners are cryptologists. Modern cryptologists are generally trained in the(cid:173)
`oretical mathematics-they have to be.
`
`Original
`I Ciphertext I
`:
`Plaintext I
`Plaintext
`., _ Decryption I
`------. .. -_ Encryption _
`
`.,
`
`Figure 1.1 Encryption and Decryption.
`
`CELLSPIN
`EX. 2013, Page 3
`
`

`

`CHAPTER 1 Foundations
`
`Plaintext is denoted by M, for message, or P, for plaintext. It can be a stream of
`bits, a text file, a bitmap, a stream of digitized voice, a digital video image ... what(cid:173)
`ever. As far as a computer is concerned, Mis simply binary data. (After this chapter,
`this book concerns itself with binary data and computer cryptography.) The plain(cid:173)
`text can be intended for either transmission or storage. In any case, Mis the message
`to be encrypted.
`Ciphertext is denoted by C. It is also binary data: sometimes the same size as M,
`sometimes larger. (By combining encryption with compression, C may be smaller
`than M. However, encryption does not accomplish this. J The encryption function E,
`operates on M to produce C. Or, in mathematical notation:
`
`E(MJ=C
`In the reverse process, the decryption function D operates on C to produce M:
`
`D(CJ=M
`Since the whole point of encrypting and then decrypting a message is to recover
`the original plaintext, the following identity must hold true:
`
`D(E(MJJ=M
`
`Authentication, Integrity, and Nonrepudiation
`In addition to providing confidentiality, cryptography is often asked to do other
`jobs:
`
`Authentication. It should be possible for the receiver of a message to
`ascertain its origin; an intruder should not be able to masquerade as
`someone else.
`Integrity. It should be possible for the receiver of a message to verify
`that it has not been modified in transit; an intruder should not be able
`to substitute a false message for a legitimate one.
`Nonrepudiation. A sender should not be able to falsely deny later that
`he sent a message.
`
`These are vital requirements for social interaction on computers, and are analo(cid:173)
`gous to face-to-face interactions. That someone is who he says he is ... that some(cid:173)
`one's credentials-whether a driver's license, a medical degree, or a passport-are
`valid . .. that a document purporting to come from a person actually came from that
`person .... These are the things that authentication, integrity, and nonrepudiation
`provide.
`
`Algorithms and Keys
`A cryptographic algorithm, also called a cipher, is the mathematical function used
`for encryption and decryption. (Generally, there are two related functions: one for
`encryption and the other for decryption. J
`
`CELLSPIN
`EX. 2013, Page 4
`
`