APPLIE;p CRYPTOG~PHY,
`SECOND EDITION
`PROTOCOLS, A.t,G~;,~SOJ:[RCE CODE IN C
`
`BRUCE SCHNEIER
`
`New York
`
`John Wiley & Sons, Inc.
`• Chichester
`• Brisbane
`• Toronto
`
`• Singapore
`
`~ ............................ .
`
`CSCO-1032
`Page 1 of 4
`
`

`

`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(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). -ISBN
`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
`
`95-12398
`CIP
`
`Printed in the United States of America
`10 9 8 7 6 5
`
`Page 2 of 4
`
`

`

`~~-s;;,,--~~~-C~HA~PT_E_R_2~_P_r_o_to_c_o_l_B_u_i_ld_1_·n_g_B_l_o_ck~s~~~~~~~~~~~~
`
`I, i
`
`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) and y
`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(cid:173)
`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(cid:173)
`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(cid:173)
`mine with certainty that the two strings are equal, but we can use them to get area(cid:173)
`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(cid:173)
`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 public; 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(cid:173)
`ble to find a pre-image that hashes to that value.
`
`Page 3 of 4
`
`

`

`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 that 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 PuBLIC-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.
`Someone 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(cid:173)
`raphy forever [496]. (The NSA has claimed knowledge of the concept as early as
`1966, but has offered no proof.) They described public-key cryptography. They used
`two different keys-one public and the other private. It is computationally hard to
`deduce 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
`message. 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
`decrypting 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(cid:173)
`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.
`
`Page 4 of 4
`
`