Page 1
Next Chapter
Home Next Page
Prev. Page




APPLIED CRYPTOGRAPHY ............................... 2
Errata ................................................................ 3
Contents in Brief ................................................ 6
Contents ............................................................ 7
PART V SOURCE CODE ................................. 14
Foreword ........................................................... 15
Preface .............................................................. 19
How TO READ THIS BOOK ............................. 20
Acknowledgments ............................................. 22
About the Author ............................................... 23
Home
Prev. Page Next Page
Next page Next Chapter




from reviews of the first edition of
APPLIED CRYPTOGRAPHY
Protocols, Algorithms, and Source Code in C
the definitive text on the subject. . . .”
". . .

-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-
tion security and cryptographic systems.”
-Computers eS 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 2
Home
Prev. Page Next Page Next Chapter




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 3
Home
Prev. Page
Next page Next Page Next Chapter



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 in C
/ Bruce Schneier.

Includes bibliographical references (p. 675).
ISBN O-471-12845-7 (cloth : acid-free paper). - ISBN
0-471-1 1709-9 (paper : acid-free paper)
1. Computer security. 2. Telecommunication-Security measures.
3. Cryptography. I. Title.
QA76.9.A25S35 1996
95-12398
005.8™2-dc20
CIP
Printed in the United States of America
1098765




Page 5
Home
Prev. Page Next Page
Next page Next Chapter




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




Page 6
Home
Prev. Page Previous Page
Next Page
Next page Next Chapter




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 10
SUBSTITUTION CIPHERS AND TRANSPOSITION CIPHERS
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 7
Home
Prev. Page Previous Page
Next Page
Next page Next Chapter
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
TIMESTAMPING SERVICES 75
4.1
SUBLIMINAL CHANNEL 79
4.2
UNDENIABLE DIGITAL SIGNATURES 81
4.3
4.4 DESIGNATED CONFIRMER SIGNATURES 82
4.5 PROXY SIGNATURES 83
4.6 GROUP SIGNATURES 84
FAIL-STOP DIGITAL SIGNATURES 85
4.7
4.8 COMPUTING WITH ENCRYPTED DATA 85
BIT COMMITMENT 86
4.9
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
BLIND SIGNATURES 112
5.3
5.4 IDENTITY-BASED PUBLIC-KEY CRYPTOGRAPHY 115
5.5 OBLIVIOUS TRANSFER 116
5.6 OBLIVIOUS SIGNATURES 117
SIMULTANEOUS CONTRACT SIGNING 118
5.7
DIGITAL CERTIFIED MAIL 122
5.8
SIMULTANEOUS EXCHANGE OF SECRETS 123
5.9

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 8
Home
Prev. Page Previous Page
Next Page
Next page Next Chapter
Contents


PART II CRYPTOGRAPHIC TECHNlQUES

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 FUNC˜ONS 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 T˜NSFERRING KEYS 176
VERIF˜NG KEYS 178
8.4
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
PUBLIC-KEY KEY MANAGEMENT 185
8.12

9 ALGORITHM TYPES AND MODES 189
9.1 ELECTRONIC CODEBOOK MODE 189
9.2 BLOCK REPLAY 191
9.3 CIPHER BLOCK CHAINING MODE 293
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 2 1 0
9.13 BLOCK CIPHERS VERSUS STREAM CIPHERS 210

10 USING ALGORITHMS 213
CHOOSING AN ALGORITHM 214
10.1
10.2 216
PUBLIC-KEY CRYPTOGRAPHY VERSUS SYMMETRIC CRYPTOGRAPHY
10.3 ENCRYPTING COMMUNICATIONS CHANNELS 216
ENCRYP˜NG DATA FOR STORAGE 220
10.4
HARDWARE ENCRYPTION VERSUS SOF˜VARE ENCRYP˜ON 223
10.5




Page 9
Home
Prev. Page Previous Page
Next Page
Next page Next Chapter
Contents


10.6 226
COMPRESSION, ENCODING, AND ENCRYP˜ON
10.7 DETECTING ENCRYPTION 226
10.8 HIDING CIPHERTEXT IN CIPHERTEXT 227
10.9 DESTROYING INFORMATION 228


PART III CRYPTOGRAPHIC ALGORITHMS

11 MATHEMATICAL BACKGROUND 233
11.1 INFORMATION THEORY 233
11.2 COMPLEXITY THEORY 237
11.3 NUMBER THEORY 242
11.4 FACTORING 2 5 5
11.5 POE NUMBER GENERATION 258
11.6 DISCRETE LOGARITHMS IN A FINITE FIELD 261

12 DATA ENCRYPTION STANDARD (DES) 265
12.1 BACKGROUND 265
12.2 DESCRIP˜ON 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 3 0 6
13.4 FEAL 308
13.5 REDOC 311
13.6 LOKI 314
13.7 KI-KJFUAND KHAFRE 316
13.8 RC2 318
13.9 IDEA 319
13.10 MMB 325
13.11 CA-l.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 10
Home
Prev. Page Previous Page
Next Page
Next page Next Chapter
Contents


14.6 CRAB 342
14.7 SXAL8/MBAL 344
14.8 RC5 344
14.9 OTHER BLOCK ALGORITHMS 346
THEORY OF BLOCK CIPHER DESIGN 346
14.10
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 36 7
15.8 COMBINING MULTIPLE BLOCK ALGORITHMS 368

16 PSEUDO-RANDOM-SEQUENCE
GENERATORS AND STREAM CIPHERS 369
16.1 LINEAR CONGRUENTIAL GENERATORS 369
LINEAR FEEDBACK SHIFT REGISTERS 3 72
16.2
DESIGN AND ANALYSIS OF STREAM CIPHERS 3 79
16.3
STREAM CIPHERS USING LFSRs 381
16.4
16.5 A5 389
16.6 HUGHES XPD/KPD 389
16.7 NANOTEQ 390
16.8 RAME%UTAN 3 9 0
16.9 ADDITIVE GENERATORS 390
16.10 GIFFORD 392
16.11 ALGORITHM M 393
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
FEEDBACK WITH CARRY SHIFT REGISTERS 402
17.4
STREAM CIPHERS USING FCSRs 405
17.5
17.6 NONLINEAR-FEEDBACK SHIFT REGISTERS 412
17.7 OTHER STREAM CIPHERS 413
SYSTEM-THEORETIC APPROACH TO STREAM-CIPHER DESIGN 415
17.8
COMPLEXITY-THEMATIC APPROACH TO STREAM-CIPHER DESIGN 416
17.9
OTHER APPROACHES TO STREAM-CIPHER DESIGN 418
17.10




Page 11
Home
Prev. Page Previous Page
Next Page
Next page Next Chapter

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
MD5 436
18.5
MD2 441
18.6
SECURE HASH ALGORITHM (SHA) 441
18.7
18.8 RIPE-MD 445
HAVAL 445
18.9
18.10 OTHER ONE-WAY HASH FUNCTIONS 446
18.11 446
ONE-WAY HASH FUNCTIONS USING SYMMETRIC BLOCK ALGORITHMS
USING PUBLIC-KEY ALGORITHMS 455
18.12
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 4 74
19.5 RABIN 475
19.6 ELGAMAL 4 76
19.7 MCELIECE 4 79
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
DISCRETE LOGARITHM SIGNATURE SCHEMES 496
20.4
ONG-SCHNORR-SHAMIR 498
20.5
20.6 ESIGN 499
20.7 CELLULAR AUTOMATA 500
OTHER PUBLIC-KEY ALGORITHMS 500
20.8

21 IDENTIFICATION SCHEMES 503
21.1 FEIGE-FIAT-SHAMIR 503




Page 12
Home
Prev. Page Previous Page
Next Page
Next page Next Chapter
Contents


21.2 GLJILLOU-QUISQUATER 5 0 8
21.3 SCHNORR 510
21.4 CONVERTING IDENTIFICATION SCHEMES 512
SIGNATURE SCHEMES
TO


22 KEY-EXCHANGE ALGORITHMS 513
22.1 DIFFIE-HELLMAN 5 13
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
ALL-OR-NOTHING DISCLOSURE OF SECRETS 543
23.9
23.10 FAIR AND FAILSAFE CRYPTOSYSTEMS 546
23.11 ZERO-KNOWLEDGE PROOFS OF KNOWLEDGE 548
23.12 BLIND SIGNATURES 549
23.13 OBLMOUS 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 56 1
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 5 73
24.9 IS0 AUTHENTICATION FRAMEWORK 5 74
24.10 P˜ACY-ENHANCED MAIL (PEM) 5 77
24.11 MESSAGE SECURITY PROTOCOL (MSP) 584




Page 13
Home
Prev. Page Previous Page
Next Page
Next page Next Chapter
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 5 93
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
NATIONAL INSTITUTE OF STANDARDS AND TECHNOLOGY (NIST) 600
25.3
25.4 RSA DATA SECURITY, INC. 603
25.5 PUBLIC KEY PARTNERS 604
25.6 INTERNATIONAL ASSOCIATION FOR CRYPTOGRAPHIC RESEARCH (IACR) 605
RACE INTEGRITY PRIMITIVES EVALUATION (RIPE) 605
25.7
25.8 CONDITIONAL ACCESS FOR EUROPE (CAFE) 606
25.9 ISO/IEC 9979 607
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 620
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 14
Home
Prev. Page Previous Page
Next Page
Next page Next Chapter




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-
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-
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-
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-
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 15
Home
Prev. Page Previous Page
Next Page
Next page Next Chapter
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-
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-
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-
tem that appears unbreakable. Many academic designs are so complex that the would-
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-
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-
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-
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-
able in the fall of 1972 were a few classic 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-
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-
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 16
Home
Prev. Page Previous Page
Next Page
Next page Next Chapter




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-
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-
tained an explicit exemption for published material-but gave both the public prac-
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-
graphic papers; researchers were requested to ask the NSA™s opinion on whether dis-
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-
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-
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 17
Home
Prev. Page Previous Page
Next Page
Next page Next Chapter

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-
tions Control Board. Applications to export the enclosed programs on disk, how-
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-
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 18
Home
Prev. Page Previous Page
Next Page
Next page Next Chapter




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-
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-
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-
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-
ing a new product, discussing a marketing strategy, or planning a hostile business
takeover. Or they may be living in a country that does not respect the rights of pri-
vacy of its citizens. They may be doing something that they feel shouldn™t be illegal,




Page 19
Home
Prev. Page Previous Page
Next Page
Next page Next Chapter

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-
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-
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-
sible, but this is the first time that the people have been forced to take active mea-
sures to make themselves available for surveillance. These initiatives are not
simply government proposals in some obscure area; they are preemptive and unilat-
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-
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 READ THIS BOOK
TO

I wrote Applied Cryptography to be both a lively introduction to the field of cryp-
tography and a comprehensive reference. I have tried to keep the text readable with-
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-
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-
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-
tocols are obvious; others are almost amazing. Cryptography can solve a lot of prob-
lems that most people never realized it could.




Page 20
Home
Prev. Page Previous Page
Next Page
Next page Next Chapter




Chapters 7 through 10 (Part II) 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 dispose of keys, and so on. Key management is the hardest
part of cryptography and often the Achilles™ heel of an otherwise secure system. Chap-
ter 9 discusses different ways of using cryptographic algorithms, and Chapter 10 gives
the odds and ends of algorithms: how to choose, implement, and use algorithms.
Chapters 11 through 23 (Part III) list algorithms. Chapter 11 provides the mathe-
matical background. This chapter is only required if you are interested in public-key
algorithms. If you just want to implement DES (or something similar), you can skip
ahead. Chapter 12 discusses DES: the algorithm, its history, its security, and some
variants. Chapters 13, 14, and 15 discuss other block algorithms; if you want some-
thing more secure than DES, skip to the section on IDEA and triple-DES. If you want
to read about a bunch of algorithms, some of which may be more secure than DES,
read the whole chapter. Chapters 16 and 17 discuss stream algorithms. Chapter 18
focuses on one-way hash functions; MD5 and SHA are the most common, although
I discuss many more. Chapter 19 discusses public-key encryption algorithms, Chap-
ter 20 discusses public-key digital signature algorithms, Chapter 21 discusses public-
key identification algorithms, and Chapter 22 discusses public-key key exchange
algorithms. The important algorithms are RSA, DSA, Fiat-Shamir, and Diffie-
Hellman, respectively. Chapter 23 has more esoteric public-key algorithms and pro-
tocols; the math in this chapter is quite complicated, so wear your seat belt.
Chapters 24 and 25 (Part IV) turn to the real world of cryptography. Chapter 24
discusses some of the current implementations of these algorithms and protocols,
while Chapter 25 touches on some of the political issues surrounding cryptography.
These chapters are by no means intended to be comprehensive.
Also included are source code listings for 10 algorithms discussed in Part III. I was
unable to include all the code I wanted to due to space limitations, and crypto-
graphic source code cannot otherwise be exported. (Amazingly enough, the State
Department allowed export of the first edition of this book with source code, but
denied export for a computer disk with the exact same source code on it. Go figure.)
An associated source code disk set includes much more source code than I could fit
in this book; it is probably the largest collection of cryptographic source code out-
side a military institution. I can only send source code disks to U.S. and Canadian
citizens living in the U.S. and Canada, but hopefully that will change someday. If
you are interested in implementing or playing with the cryptographic algorithms in
this book, get the disk. See the last page of the book for details.
One criticism of this book is that its encyclopedic nature takes away from its
readability. This is true, but I wanted to provide a single reference for those who
might come across an algorithm in the academic literature or in a product. For those
who are more interested in a tutorial, I apologize. A lot is being done in the field;
this is the first time so much of it has been gathered between two covers. Even so,
space considerations forced me to leave many things out. I covered topics that I felt
were important, practical, or interesting. If I couldn™t cover a topic in depth, I gave
references to articles and papers that did.




Page 21
Home
Prev. Page Previous Page
Next Page
Next page Next Chapter
Preface



I have done my best to hunt down and eradicate all errors in this book, but many
have assured me that it is an impossible task. Certainly, the second edition has far
fewer errors than the first. An errata listing is available from me and will be period-
ically posted to the Usenet newsgroup sci.crypt. If any reader finds an error, please
let me know. I™ll send the first person to find each error in the book a free copy of the
source code disk.
Acknowledgments
The list of people who had a hand in this book may seem unending, but all are
worthy of mention. I would like to thank Don Alvarez, Ross Anderson, Dave Balen-
son, Karl Barrus, Steve Bellovin, Dan Bernstein, Eli Biham, Joan Boyar, Karen
Cooper, Whit Diffie, Joan Feigenbaum, Phil Karn, Neal Koblitz, Xuejia Lai, Tom
Leranth, Mike Markowitz, Ralph Merkle, Bill Patton, Peter Pearson, Charles
Pfleeger, Ken Pizzini, Bart Preneel, Mark Riordan, Joachim Schurman, and Marc
Schwartz for reading and editing all or parts of the first edition; Marc Vauclair for
translating the first edition into French; Abe Abraham, Ross Anderson, Dave
Banisar, Steve Bellovin, Eli Biham, Matt Bishop, Matt Blaze, Gary Carter, Jan
Camenisch, Claude Crepeau, Joan Daemen, Jorge Davila, Ed Dawson, Whit Diffie,
Carl Ellison, Joan Feigenbaum, Niels Ferguson, Matt Franklin, Rosario Gennaro,
Dieter Gollmann, Mark Goresky, Richard Graveman, Stuart Haber, Jingman He,
Bob Hogue, Kenneth Iversen, Markus Jakobsson, Burt Kaliski, Phil Karn, John
Kelsey, John Kennedy, Lars Knudsen, Paul Kocher, John Ladwig, Xuejia Lai, Arjen
Lenstra, Paul Leyland, Mike Markowitz, Jim Massey, Bruce McNair, William Hugh
Murray, Roger Needham, Clif Neuman, Kaisa Nyberg, Luke O™Connor, Peter Pear-
son, Rene Peralta, Bart Preneel, Yisrael Radai, Matt Robshaw, Michael Roe, Phil
Rogaway, Avi Rubin, Paul Rubin, Selwyn Russell, Kazue Sako, Mahmoud Salma-
sizadeh, Markus Stadler, Dmitry Titov, Jimmy Upton, Marc Vauclair, Serge Vaude-
nay, Gideon Yuval, Glen Zorn, and several anonymous government employees for
reading and editing all or parts of the second edition; Lawrie Brown, Leisa Condie,
Joan Daemen, Peter Gutmann, Alan Insley, Chris Johnston, John Kelsey, Xuejia Lai,
Bill Leininger, Mike Markowitz, Richard Outerbridge, Peter Pearson, Ken Pizzini,
Colin Plumb, RSA Data Security, Inc., Michael Roe, Michael Wood, and Phil Zim-
mermann for providing source code; Paul MacNerland for creating the figures for
the first edition; Karen Cooper for copyediting the second edition; Beth Friedman for
proofreading the second edition; Carol Kennedy for indexing the second edition; the
readers of sci.crypt and the Cypherpunks mailing list for commenting on ideas,
answering questions, and finding errors in the first edition; Randy Seuss for provid-
ing Internet access; Jeff Duntemann and Jon Erickson for helping me get started;
assorted random Insleys for the impetus, encouragement, support, conversations,
friendship, and dinners; and AT&T Bell Labs for firing me and making this all pos-
sible. All these people helped to create a far better book than I could have created
alone.

Bruce Schneier
Oak Park, Ill.
schneier@counterpane.com




Page 22
Home
Prev. Page Previous Page
Next Page
Next page Next Chapter




About the Author


BRUCE SCHNEIER is president of Counterpane Systems, an Oak Park, Illinois con-
sulting firm specializing in cryptography and computer security. Bruce is also the
author of E-Mail Security (John Wiley & Sons, 1995) and Protect Your Macintosh
(Peachpit Press, 1994); and has written dozens of articles on cryptography for major
magazines. He is a contributing editor to Dr. Dobb™s Joournal, where he edits the
“Algorithms Alley” column, and a contributing editor to Computer and Communi-
cations Security Reviews. Bruce serves on the board of directors of the International
Association for Cryptologic Research, is a member of the Advisory Board for the
Electronic Privacy Information Center, and is on the program committee for the
New Security Paradigms Workshop. In addition, he finds time to give frequent lec-
tures on cryptography, computer security, and privacy.




Page 23