throbber
·~ .. 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

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket