·~ .. the best introduction
`to cryptography I've
`ever seen .... The book
`the National Security
`Agency wanted never
`to be published ... :•
`
`Page 1 of 174
`
`GOOGLE EXHIBIT 1009
`
`

`

` ‘4APPLIED
`
`a_|CRYPTOGRAPHY
`
`Page 2 of 174
`
`Page 2 of 174
`
`

`

`from reviews of the first edition of
`APPLIED CRYPTOGRAPHY
`Protocols, Algorithms, and Source Code inC
`
`11
`
`• •• the definitive text on the subject .... 11
`-Software Development Magazine
`
`" ... good reading for anyone interested in cryptography."
`-BYTE
`
`"This book should be on the shelf of any computer professional
`involved in the use or implementation of cryptography."
`-IEEE Software
`
`" ... dazzling ... fascinating .... This book absolutely must be on your
`bookshelf ... "
`
`-PC Techniques
`
`" ... comprehensive ... an encyclopedic work ... "
`-The Cryptogram
`
`" ... a fantastic book on cryptography today. It belongs in the library of
`anyone interested in cryptography or anyone who deals with informa(cid:173)
`tion security and cryptographic systems."
`-Computers eiJ Security
`
`"An encyclopedic survey ... could well have been subtitled 'The Joy of
`Encrypting' ... a useful addition to the library of any active or would-be
`security practitioner."
`
`-Cryptologia
`
`" ... encyclopedic ... readable ... well-informed ... picks up where
`Dorothy Denning's classic Cryptography and Data Security left off a
`dozen years ago .... This book would be a bargain at twice the price."
`-;login:
`
`"This is a marvelous resource-the best book on cryptography and its
`application available today."
`
`-Dorothy Denning
`Georgetown University
`
`" ... Schneier's book is an indispensable reference and resource .... I
`recommend it highly."
`
`-Martin Hellman
`Stanford University
`
`Page 3 of 174
`
`

`

`Errata
`
`A list of the errors found in this book along with corresponding
`corrections is updated periodically. For the most recent electronic
`version, send email to:
`
`schneier@counterpane.com
`
`For the most recent printed version, send a stamped, self-addressed
`envelope to:
`
`AC Corrections
`Counterpane Systems
`101 E. Minnekaka Parkway
`Minneapolis, MN 55419
`
`Readers are encouraged to distribute electronic or printed versions
`of this list to other readers of this book.
`
`Page 4 of 174
`
`

`

`New York
`
`John Wiley & Sons, Inc.
`• Chichester
`• Brisbane
`• Toronto
`
`• Singapore
`
`Page 5 of 174
`
`

`

`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 p~inted 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 bee'l 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 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
`20
`
`Page 6 of 174
`
`

`

`Contents in Brief
`
`Foreword by Whitfield Diffie
`Preface
`About the Author
`1 Foundations
`
`Part I Cryptographic Protocols
`2 Protocol Building Blocks
`3 Basic Protocols
`4 Intermediate Protocols
`5 Advanced Protocols
`6 Esoteric Protocols
`
`Part II Cryptographic Techniques
`7 Key Length
`8 Key Management
`9 Algorithm Types and Modes
`10 Using Algorithms
`
`Part III Cryptographic Algorithms
`11 Mathematical Background
`12 Data Encryption Standard (DES)
`13 Other Block Ciphers
`14 Still Other Block Ciphers
`15 Combining Block Ciphers
`16 Pseudo-Random-Sequence Generators and Stream Ciphers
`17 Other Stream Ciphers and Real Random-Sequence Generators
`18 One-Way Hash Functions
`19 Public-Key Algorithms
`20 Public-Key Digital Signature Algorithms
`21
`Identification Schemes
`22 Key-Exchange Algorithms
`23 Special Algorithms for Protocols
`
`Part IV The Real World
`24 Example Implementations
`25 Politics
`Afterword by Matt Blaze
`
`Part V Source Code
`References
`
`Page 7 of 174
`
`

`

`Contents
`
`Foreword by Whitfield Diffie xv
`Preface xix
`How To READ THIS BooK xx
`ACKNOWLEDGMENTS xxii
`About the Author xxiii
`
`1 FOUNDATIONS 1
`1.1 TERMINOLOGY 1
`1.2 STEGANOGRAPHY 9
`1.3 SUBSTITUTION CIPHERS AND TRANSPOSITION CIPHERS 10
`1.4 SIMPLE XOR 13
`1.5 ONE-TIME PADS 15
`1.6 COMPUTER ALGORITHMS 17
`1.7 LARGE NUMBERS 17
`
`PART I CRYPTOGRAPHIC PROTOCOLS
`
`2 PROTOCOL BUILDING BLOCKS 21
`2.1
`INTRODUCTION TO PROTOCOLS 21
`2.2 COMMUNICATIONS USING SYMMETRIC CRYPTOGRAPHY 28
`2.3 ONE-WAY FUNCTIONS 29
`2.4 ONE-WAY HASH FUNCTIONS 30
`2.5 COMMUNICATIONS USING PUBLIC-KEY CRYPTOGRAPHY 31
`2.6 DIGITAL SIGNATURES 34
`2. 7 DIGITAL SIGNATURES WITH ENCRYPTION 41
`2.8 RANDOM AND PSEUDO-RANDOM-SEQUENCE GENERATION 44
`
`Page 8 of 174
`
`

`

`Contents
`
`3 BASIC PROTOCOLS 47
`3.1 KEY EXCHANGE 47
`3.2 AUTHENTICATION 52
`3.3 AUTHENTICATION AND KEY EXCHANGE 56
`3.4 FORMAL ANALYSIS OF AUTHENTICATION AND KEY-EXCHANGE PROTOCOLS 65
`3.5 MULTIPLE-KEY PUBLIC-KEY CRYPTOGRAPHY 68
`3.6 SECRET SPLITTING 70
`3.7 SECRET SHARING 71
`3.8 CRYPTOGRAPHIC PROTECTION OF DATABASES 73
`
`4 INTERMEDIATE PROTOCOLS 75
`4.1 TIMESTAMPING SERVICES 75
`4.2 SUBLIMINAL CHANNEL 79
`4.3 UNDENIABLE DIGITAL SIGNATURES 81
`4.4 DESIGNATED CONFIRMER SIGNATURES 82
`4.5 PROXY SIGNATURES 83
`4.6 GROUP SIGNATURES 84
`4. 7 FAIL-STOP DIGITAL SIGNATURES 85
`4.8 COMPUTING WITH ENCRYPTED DATA 85
`4.9 BIT CoMMITMENT 86
`4.10 FAIR COIN FLIPS 89
`4.11 MENTAL POKER 92
`4.12 ONE-WAY ACCUMULATORS 95
`4.13 ALL-OR-NOTHING DISCLOSURE OF SECRETS 96
`4.14 KEY EsCROW 97
`
`5 ADVANCED PROTOCOLS 101
`5.1 ZERO-KNOWLEDGE PROOFS 101
`5.2 ZERO-KNOWLEDGE PROOFS OF IDENTITY 109
`5.3 BLIND SIGNATURES 112
`5.4
`IDENTITY-BASED PUBLIC-KEY CRYPTOGRAPHY 115
`5.5 OBLIVIOUS TRANSFER 116
`5.6 0BLMOUS SIGNATURES 117
`5. 7 SIMULTANEOUS CONTRACT SIGNING 118
`5.8 DIGITAL CERTIFIED MAIL 122
`5.9 SIMULTANEOUS EXCHANGE OF SECRETS 123
`
`6 ESOTERIC PROTOCOLS 125
`6.1 SECURE ELECTIONS 125
`6.2 SECURE MULTIPARTY COMPUTATION 134
`6.3 ANONYMOUS MESSAGE BROADCAST 137
`6.4 DIGITAL CASH 139
`
`Page 9 of 174
`
`

`

`Contents
`
`PART II CRYPTOGRAPHIC TECHNIQUES
`
`7 KEY LENGTH 151
`7.1 SYMMETRIC KEY LENGTH 151
`7.2 PUBLIC-KEY KEY LENGTH 158
`7.3 COMPARING SYMMETRIC AND PUBLIC-KEY KEY LENGTH 165
`7.4 BIRTHDAY ATTACKS AGAINST ONE-WAY HASH FUNCTIONS 165
`7.5 How LONG SHOULD A KEY BE? 166
`7.6 CAVEAT EMPTOR 168
`
`8 KEY MANAGEMENT 169
`8.1 GENERATING KEYS 170
`8.2 NONLINEAR KEYSPACES 175
`8.3 TRANSFERRING KEYS 176
`8.4 VERIFYING KEYS 178
`8.5 USING KEYS 179
`8.6 UPDATING KEYS 180
`8.7 STORING KEYS 180
`8.8 BACKUP KEYS 181
`8.9 COMPROMISED KEYS 182
`8.10 LIFETIME OF KEYS 183
`8.11 DESTROYING KEYS 184
`8.12 PUBLIC-KEY KEY MANAGEMENT 185
`
`9 ALGORITHM TYPES AND MODES 189
`9.1 ELECTRONIC CODEBOOK MODE 189
`9.2 BLOCK REPLAY 191
`9.3 CIPHER BLOCK CHAINING MODE 193
`9.4 STREAM CIPHERS 197
`9.5 SELF-SYNCHRONIZING STREAM CIPHERS 198
`9.6 CIPHER-FEEDBACK MODE 200
`9. 7 SYNCHRONOUS STREAM CIPHERS 202
`9.8 OUTPUT-FEEDBACK MODE 203
`9.9 COUNTER MODE 205
`9.10 OTHER BLOCK-CIPHER MODES 206
`9.11 CHOOSING A CIPHER MODE 208
`9.12
`INTERLEAVING 210
`9.13 BLOCK CIPHERS VERSUS STREAM CIPHERS 210
`
`10 USING ALGORITHMS 213
`10.1 CHOOSING AN ALGORITHM 214
`10.2 PUBLIC-KEY CRYPTOGRAPHY VERSUS SYMMETRIC CRYPTOGRAPHY 216
`10.3 ENCRYPTING COMMUNICATIONS CHANNELS 216
`10.4 ENCRYPTING DATA FOR STORAGE 220
`10.5 HARDWARE ENCRYPTION VERSUS SOFTWARE ENCRYPTION 223
`
`Page 10 of 174
`
`

`

`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
`INFORMATION THEORY 233
`11.1
`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 FEAL 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 GOST 331
`14.2 CAST 334
`14.3 BLOWFISH 336
`14.4 SAFER 339
`14.5 3-WAY 341
`
`Page 11 of 174
`
`

`

`Contents
`
`14.6 CRAB 342
`14.7 SXAL8/MBAL 344
`14.8 RCS 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 357
`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
`16.11 ALGORITHM M
`16.12 PKZIP 394
`
`393
`
`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
`
`Page 12 of 174
`
`

`

`Contents
`
`17.11 CASCADING MULTIPLE STREAM CIPHERS 419
`1 7.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 42§)
`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 COST 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
`
`Page 13 of 174
`
`

`

`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 S2.CURE 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 KRYPTOKNIGHT 571
`24.7 SESAME 572
`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
`
`Page 14 of 174
`
`

`

`Contents
`
`24.12 PRETTY GooD PRIVACY (PGP) 584
`24.13 SMART CARDS 587
`24.14 PUBLIC-KEY CRYPTOGRAPHY STANDARDS (PKCS) 588
`24.15 UNIVERSAL ELECTRONIC PAYMENT SYSTEM (UEPS) 589
`24.16 CLIPPER 591
`24.17 CAPSTONE 593
`24.18 AT&T MODEL 3600 TELEPHONE SECURITY DEVICE (TSD) 594
`
`25 POLITICS 597
`25.1 NATIONAL SECURITY AGENCY (NSA) 597
`25.2 NATIONAL COMPUTER SECURITY CENTER (NCSC) 599
`25.3 NATIONAL INSTITUTE OF STANDARDS AND TECHNOLOGY (NIST) 600
`25.4 RSA DATA SECURITY, INC. 603
`25.5 PUBLIC KEY PARTNERS 604
`25.6
`INTERNATIONAL ASSOCIATION FOR CRYPTOGRAPHIC RESEARCH (IACR) 605
`25.7 RACE INTEGRITY PRIMITIVES EVALUATION (RIPE) 605
`25.8 CONDITIONAL ACCESS FOR EUROPE (CAFE) 606
`ISO/IEC 9979 607
`25.9
`25.10 PROFESSIONAL, CiVIL LIBERTIES, AND INDUSTRY GROUPS 608
`25.11 SCI. CRYPT 608
`25.12 CYPHERPUNKS 609
`25.13 PATENTS 609
`25.14 U.S. EXPORT RULES 610
`25.15 FOREIGN IMPORT AND EXPORT OF CRYPTOGRAPHY 617
`25.16 LEGAL ISSUES 618
`
`Afterword by Matt Blaze 619
`
`PART V SOURCE CODE
`
`Source Code 623
`
`References 675
`
`Page 15 of 174
`
`

`

`Foreword
`By Whitfield Diffie
`
`The literature of cryptography has a curious history. Secrecy, of course, has always
`played a central role, but until the First World War, important developments appeared
`in print in a more or less timely fashion and the field moved forward in much the
`same way as other specialized disciplines. As late as 1918, one of the most influential
`cryptanalytic papers of the twentieth century, William F. Friedman's monograph The
`Index of Coincidence and Its Applications in Cryptography, appeared as a research
`report of the private Riverbank Laboratories [577]. And this, despite the fact that the
`work had been done as part of the war effort. In the same year Edward H. Hebern of
`Oakland, California filed the first patent for a rotor machine [710], the device destined
`to be a mainstay of military cryptography for nearly 50 years.
`After the First World War, however, things began to change. U.S. Army and Navy
`organizations, working entirely in secret, began to make fundamental advances in
`cryptography. During the thirties and forties a few basic papers did appear in the
`open literature and several treatises on the subject were published, but the latter
`were farther and farther behind the state of the art. By the end of the war the transi(cid:173)
`tion was complete. With one notable exception, the public literature had died. That
`exception was Claude Shannon's paper "The Communication Theory of Secrecy
`Systems," which appeared in the Bell System Technical Journal in 1949 [1432]. It
`was similar to Friedman's 1918 paper, in that it grew out of wartime work of Shan(cid:173)
`non's. After the Second World War ended it was declassified, possibly by mistake.
`From 1949 until 1967 the cryptographic literature was barren. In that year a dif(cid:173)
`ferent sort of contribution appeared: David Kahn's history, The Codebreakers [794].
`It didn't contain any new technical ideas, but it did contain a remarkably complete
`history of what had gone before, including mention of some things that the govern(cid:173)
`ment still considered secret. The significance of The Codebreakers lay not just in its
`remarkable scope, but also in the fact that it enjoyed good sales and made tens of
`thousands of people, who had never given the matter a moment's thought, aware of
`cryptography. A trickle of new cryptographic papers began to be written.
`
`Page 16 of 174
`
`

`

`Foreword by Whitfield Diffie
`
`At about the same time, Horst Feistel, who had earlier worked on identification
`friend or foe devices for the Air Force, took his lifelong passion for cryptography to
`the IBM Watson Laboratory in Yorktown Heights, New York. There, he began devel(cid:173)
`opment of what was to become the U.S. Data Encryption Standard; by the early
`1970s several technical reports on this subject by Feistel and his colleagues had been
`made public by IBM [1482,1484,552].
`This was the situation when I entered the field in late 1972. The cryptographic lit(cid:173)
`erature wasn't abundant, but what there was included some very shiny nuggets.
`Cryptology presents a difficulty not found in normal academic disciplines: the need
`for the proper interaction of cryptography and cryptanalysis. This arises out of the fact
`that in the absence of real communications requirements, it is easy to propose a sys(cid:173)
`tem that appears unbreakable. Many academic designs are so complex that the would(cid:173)
`be cryptanalyst doesn't know where to start; exposing flaws in these designs is far
`harder than designing them in the first place. The result is that the competitive pro(cid:173)
`cess, which is one strong motivation in academic research, cannot take hold.
`When Martin Hellman and I proposed public-key cryptography in 1975 [496], one
`of the indirect aspects of our contribution was to introduce a problem that does not
`even appear easy to solve. Now an aspiring cryptosystem designer could produce
`something that would be recognized as clever-something that did more than just
`turn meaningful text into nonsense. The result has been a spectacular increase in
`the number of people working in cryptography, the number of meetings held, and
`the number of books and papers published.
`In my acceptance speech for the Donald E. Fink award-given for the best expos(cid:173)
`itory paper to appear in an IEEE journal-which I received jointly with Hellman in
`1980, I told the audience that in writing "Privacy and Authentication," I had an
`experience that I suspected was rare even among the prominent scholars who popu(cid:173)
`late the IEEE awards ceremony: I had written the paper I had wanted to study, but
`could not find, when I first became seriously interested in cryptography. Had I been
`able to go to the Stanford bookstore and pick up a modern cryptography text, I
`would probably have learned about the field years earlier. But the only things avail(cid:173)
`able in the fall of 1972 were a few clelssic papers and some obscure technical reports.
`The contemporary researcher has no such problem. The problem now is choosing
`where to start among the thousands of papers and dozens of books. The contempo(cid:173)
`rary researcher, yes, but what about the contemporary programmer or engineer who
`merely wants to use cryptography? Where does that person turn? Until now, it has
`been necessary to spend long hours hunting out and then studying the research lit(cid:173)
`erature before being able to design the sort of cryptographic utilities glibly described
`in popular articles.
`This is the gap that Bruce Schneier's Applied Cryptography has come to fill.
`Beginning with the objectives of communication security and elementary examples
`of programs used to achieve these objectives, Schneier gives us a panoramic view of
`the fruits of 20 years of public research. The title says it all; from the mundane
`objective of having a secure conversation the very first time you call someone to the
`possibilities of digital money and cryptographically secure elections, this is where
`you'll find it.
`
`Page 17 of 174
`
`

`

`Foreword by Whitfield Diffie
`
`Not satisfied that the book was about the real world merely because it went all
`the way down to the code, Schneier has included an account of the world in which
`cryptography is developed and applied, and discusses entities ranging from the Inter(cid:173)
`national Association for Cryptologic Research to the NSA.
`When public interest in cryptography was just emerging in the late seventies and
`early eighties, the National Security Agency (NSA), America's official cryptographic
`organ, made several attempts to quash it. The first was a letter from a long-time
`NSA employee allegedly, avowedly, and apparently acting on his own. The letter
`was sent to the IEEE and warned that the publication of cryptographic material was
`a violation of the International Traffic in Arms Regulations (ITAR). This viewpoint
`turned out not even to be supported by the regulations themselves-which con(cid:173)
`tained an explicit exemption for published material-but gave both the public prac(cid:173)
`tice of cryptography and the 1977 Information Theory Workshop lots of unexpected
`publicity.
`A more serious attempt occurred in 1980, when the NSA funded the American
`Council on Education to examine the issue with a view to persuading Congress to
`give it legal control of publications in the field of cryptography. The results fell far
`short of NSA's ambitions and resulted in a program of voluntary review of crypto(cid:173)
`graphic papersi researchers were requested to ask the NSA's opinion on whether dis(cid:173)
`closure of results would adversely affect the national interest before publication.
`As the eighties progressed, pressure focused more on the practice than the study
`of cryptography. Existing laws gave the NSA the power, through the Department of
`State, to regulate the export of cryptographic equipment. As business became more
`and more international and the American fraction of the world. market declined, the
`pressure to have a single product in both domestic and offshore markets increased.
`Such single products were subject to export control and thus the NSA acquired sub(cid:173)
`stantial influence not only over what was exported, but also over what was sold in
`the United States.
`As this is written, a new challenge confronts the public practice of cryptography.
`The government has augmented the widely published and available Data Encryp(cid:173)
`tion Standard, with a secret algorithm implemented in tamper-resistant chips.
`These chips will incorporate a codified mechanism of government monitoring. The
`negative aspects of this "key-escrow" program range from a potentially disastrous
`impact on personal privacy to the high cost of having to add hardware to products
`that had previously encrypted in software. So far key escrow products are enjoying
`less than stellar sales and the scheme has attracted widespread negative comment,
`especially from the independent cryptographers. Some people, however, see more
`future in programming than politicking and have redoubled their efforts to provide
`the world with strong cryptography that is accessible to public scrutiny.
`A sharp step back from the notion that export control law could supersede the
`First Amendment seemed to have been taken in 1980 when the Federal Register
`announcement of a revision to ITAR included the statement: " ... provision has
`been added to make it clear that the regulation of the export of technical data does
`not purport to interfere with the First Amendment rights of individuals." But the
`fact that tension between the First Amendment and the export control laws has not
`
`Page 18 of 174
`
`

`

`Foreword By Whitfield Diffie
`
`gone away should be evident from statements at a conference held by RSA Data
`Security. NSA's representative from the export control office expressed the opinion
`that people who published cryptographic programs were "in a grey area" with
`respect to the law. If that is so, it is a grey area on which the first edition of this book
`has shed some light. Export applications for the book itself have been granted, with
`acknowledgement that published material lay beyond the authority of the Muni(cid:173)
`tions Control Board. Applications to export the enclosed programs on disk, how(cid:173)
`ever, have been denied.
`The shift in the NSA's strategy, from attempting to control cryptographic research
`to tightening its grip on the development and deployment of cryptographic prod(cid:173)
`ucts, is presumably due to its realization that all the great cryptographic papers in
`the world do not protect a single bit of traffic. Sitting on the shelf, this volume may
`be able to do no better than the books and papers that preceded it, but sitting next
`to a workstation, where a programmer is writing cryptographic code, it just may.
`
`Whitfield Diffie
`Mountain View, CA
`
`Page 19 of 174
`
`

`

`Preface
`
`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 govern(cid:173)
`ments from reading your files. This book is about the latter.
`If I take a letter, lock it in a safe, hide the safe somewhere in New York, then tell
`you to read the letter, that's not security. That's obscurity. On the other hand, if I
`take a letter and lock it in a safe, and then give you the safe along with the design
`specifications of the safe and a hundred identical safes with their combinations so
`that you and the world's best safecrackers can study the locking mechanism-and
`you still can't open the safe and read the letter-that's security.
`For many years, this sort of cryptography was the exclusive domain of the mili(cid:173)
`tary. The United States' National Security Agency (NSA), and its counterparts in
`the former Soviet Union, England, France, Israel, and elsewhere, have spent billions
`of dollars in the very serious game of securing their own communications while try(cid:173)
`ing to break everyone else's. Private individuals, with far less expertise and budget,
`have been powerless to protect their own privacy against these governments.
`During the last 20 years, public academic research in cryptography has exploded.
`While classical cryptography has been long used by ordinary citizens, computer
`cryptography was the exclusive domain of the world's militaries since World War II.
`Today, state-of-the-art computer cryptography is practiced outside the secured walls
`of the military agencies. The layperson can now employ security practices that can
`protect against the most powerful of adversaries-security that may protect against
`military agencies for years to come.
`Do average people really need this kind of security? Yes. They may be planning a
`political campaign, discussing taxes, or having an illicit affair. They may be design(cid:173)
`ing a new product, discussing a marketing strategy, or planning a hostile business
`.~eover. Or they may be living in a country that does not respect the rights of pri(cid:173)
`;Vacy of its citizens. They may be doing something that they feel shouldn't be illegal,
`
`~ d,>
`
`Page 20 of 174
`
`

`

`Preface
`
`but is. For whatever reason, the data and communications are personal, private, and
`no one else's business.
`This book is being published in a tumultuous time. In 1994, the Clinton admin(cid:173)
`istration approved the Escrowed Encryption Standard (including the Clipper chip
`and Fortezza card) and signed the Digital Telephony bill into law. Both of these ini(cid:173)
`tiatives try to ensure the government's ability to conduct electronic surveillance.
`Some dangerously Orwellian assumptions are at work here: that the government
`has the right to listen to private communications, and that there is something
`wrong with a private citizen trying to keep a secret from the government. Law
`enforcement has always been able to conduct court-authorized surveillance if pos(cid:173)
`sible, but this is the first time that the people have been forced to take active mea(cid:173)
`sures to make themselves available for surveillance. These initiatives are not
`simply government proposals in some obscure area; they are preemptive and unilat(cid:173)
`eral attempts to usurp powers that previously belonged to the people.
`Clipper and Digital Telephony do not protect privacy; they force individuals to
`unconditionally trust that the government will respect their privacy. The same law
`enforcement authorities who illegally tapped Martin Luther King Jr.'s phones can
`easily tap a phone protected with Clipper. In the recent past, local police authorities
`have either been charged criminally or sued civilly in numerous jurisdictions(cid:173)
`Maryland, Connecticut, Vermont, Georgia, Missouri, and Nevada-for conducting
`illegal wiretaps. It's a poor idea to deploy a technology that could some day facilitate
`a police state.
`The lesson here is that it is insufficient to protect ourselves with laws; we need to
`protect ourselves with mathematics. Encryption is too important to be left solely to
`governments.
`This book gives you the tools you need to protect your own privacy; cryptography
`products may be declared illegal, but the information will never be.
`
`How To READ THIS BooK
`
`I wrote Applied Cryptography to be both a lively introduction to the field of cryp(cid:173)
`tography and a comprehensive reference. I have tried to keep the text readable with(cid:173)
`out sacrificing accuracy. This book is not intended to be a mathematical text.
`Although I have not deliberately given any false information, I do play fast and loose
`with theory. For those interested in formalism, there are copious references to the
`academic literature.
`Chapter 1 introduces cryptography, defines many terms, and briefly discusses pre(cid:173)
`computer cryptography.
`Chapters 2 through 6 (Part I) describe cryptographic protocols: what people can do
`with cryptography. The protocols range from the simple (sending encrypted mes(cid:173)
`sages from one person to another) to the complex (flipping a coin over the telephone)
`to the esoteric (secure and anonymous digital money exchange). Some of these pro(cid:173)
`tocols are obvious; others are almost amazing. Cryptography can solve a lot of prob(cid:173)
`lems that most people never realized it could.
`
`Page 21 of 174
`
`

`

`Preface
`
`Chapters 7 through 10 (Part ll) discuss cryptographic techniques. All four chapters in
`this section are important for even the most basic uses of cryptography. Chapters 7 and
`8 are about keys: how long a key should be in order to be secure, how to generate keys,
`how to store keys, how to disp