'
`
`..
`
`F ““5
`
`1‘;
`
`APPLIED
`cavP'roeRA PHv
`
`
`
`Protocols, Algorithms. and Source Code in C
`
`BRUCE SCHNEIER
`
`Petitioner Apple Inc. — Exhibit 1041, p. 1
`
`Petitioner Apple Inc. - Exhibit 1041, p. 1
`
`

`

`Petitioner Apple Inc. — Exhibit 1041, p. 2
`
`Petitioner Apple Inc. - Exhibit 1041, p. 2
`
`

`

`Applied Cryptography
`Protocols, Algorithms,
`and Source Codo
`inC
`
`Petitioner Apple Inc. — Exhibit 1041, p. 3
`
`Petitioner Apple Inc. - Exhibit 1041, p. 3
`
`

`

`
`
`Cryptography
`
`Protocols, Algorithms,
`and Source Code
`
`in C
`
`Bruce Schneier
`
`John Wiley & Sons, Inc.
`NEW YORK . CHICHESTER . BRISBANE . TORONTO .
`
`SINGAPORE
`
`Petitioner Apple Inc. — Exhibit 1041, p. 4
`
`Petitioner Apple Inc. - Exhibit 1041, p. 4
`
`

`

`Associate Publisher: Katherine Schowalter
`Editor: Paul Farrel]
`
`Managing Editor: Beth Austin
`Editorial Prodilction 81. Design: Editorial Services of New England. Inc.
`
`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
`professional services. If legal. acc0unting. medical, psychological, or any other expert assistance is
`required. the services of a competent professional person should be sought. ADAP'I‘ED FROM A
`DECLARATIONS OF PRINCIPLES OF A JOINT COMMITTEE OF THE AMERICAN BAR
`ASSOCIATION AND PUBLISHERS.
`
`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 mom inability to use the protocols and algorithms in this
`book, even if the publisher 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 applicable 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
`necessary export licenses before implementing in software for export any protocol or algorithm in
`this book.
`
`This text is printed on acid-free paper.
`
`Trademarks
`
`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 infon'nation regarding trademarks and registration.
`'
`
`Copyright © 1994 John Wiley & Sons. Inc.
`
`All rights reserved. Published simultaneously in Canada.
`
`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 infon'nation should be addressed to the Permissions Department,
`John Wiley & Sons, Inc.
`
`Library of Congress Cataloging-in-Publication Data
`Schneier. Bruce
`Applied cryptography : protocols. algorithms, and source code in C
`I Bnice Schneier.
`p. cm.
`Includes bibliographical references and index.
`ISBN 0-471-59156-2 (paper)
`1. Computer security. '2. Telecommunication—security measures. 3. Cryptography. 4. Title
`
`QA?6.9.A25835 1993
`005 .8 ’ 2—dc20
`
`Printed in the United States of America
`10 9 8 T 6 5 4 3 2 1
`
`93-2139
`CIP
`
`Petitioner Apple Inc. - Exhibit 1041, p. 5
`
`Petitioner Apple Inc. - Exhibit 1041, p. 5
`
`

`

`Contents
`
`
`
`'xi
`
`XV
`
`I7
`
`l9
`
`FOREWORD by Whitfield Diffie
`
`PREFACE
`
`How to Read This Book
`
`xvi
`
`Acknowledgments
`
`xviii
`
`CHAPTER I
`
`Foundations
`
`1.]
`
`1.2
`
`1.3
`
`]
`Terminology
`Classical Cryptography
`Large Numbers
`15
`
`8
`
`PART ONE
`
`CRYPTOGRAPHIC PROTOCOLS .
`
`CHAPTER 2
`
`Protocol Building Blocks
`2.1
`Introduction to Protocols
`
`19
`
`2.2
`
`2.3
`
`2.4
`
`2.5
`
`2.6
`
`2.7
`
`2.8
`
`Communications Using Symmetric Cryptography
`One-Way Functions
`27
`
`One-Way Hash Functions
`
`28
`
`Communications Using Public-Key Cryptography
`Digital Signatures
`31
`3?
`Digital Signatures with Encryption
`Random and Pseudo-Random Sequence Generation
`
`26
`
`29
`
`39
`
`Petitioner Apple Inc. — Exhibit 1041, p. 6
`
`Petitioner Apple Inc. - Exhibit 1041, p. 6
`
`

`

`vi
`
`CHAPTER 3
`
`Basic Protocols
`
`3.1
`3.2
`
`3.3
`3.4
`3.5
`3.6
`3.7
`3.8
`
`Key Exchange
`Authentication
`
`42
`47
`
`51
`
`Authentication and Key Exchange
`Multiple-Key Public- Key Cryptography
`Secret Splitting
`58
`Secret Sharing
`59
`Cryptographic Protection of Databases
`Timestamping Services
`61
`
`56
`
`61
`
`CHAPTER 4
`
`Intermediate Protocols
`
`4.]
`
`4.2
`4.3
`4.4
`4.5
`4.6
`
`4.7
`4.8
`
`Subliminal Channel
`
`66
`
`Undeniable Digital Signatures
`Fail-Stop Digital Signatures
`Group Signatures
`70
`Computing with Encrypted Data
`Bit Commitment
`71
`
`68
`69
`
`71
`
`Fair Coin Flips
`Mental Poker
`
`74
`78
`
`CHAPTER 5
`
`Advanced Protocols
`
`5.]
`5.2
`5.3
`5.4
`5.5
`
`82
`Fair Cryptosystems
`All-or-Nothing Disclosure of Secrets
`Zero-Knowledge Proofs of Knowledge
`Zero~Knowledge Proofs of Identity
`Blind Signatures
`93
`
`83
`84
`
`91
`
`CHAPTER 6
`
`Esoteric Protocols
`
`6.1
`
`6.2
`6.3
`6.4
`6.5
`
`6.6
`6.7
`6.8
`
`Oblivious Transfer
`
`97
`
`Simultaneous Contract Signing
`Digital Certified Mail
`103
`Simultaneous Exchange of Secrets
`Secure Elections
`105
`
`Secure Multiparty Computation
`Digital Cash
`11'?
`Anonymous Message Broadcast
`
`99
`
`104
`
`114
`
`124
`
`PART Two
`
`CRYPTOGRAPHIC TECHNIQUES
`CHAPTER 7
`
`Keys
`7.1
`7.2
`7.3
`
`Key Length
`139
`Key Management
`Public-Key Key Management
`
`129
`
`152
`
`Petitioner Apple Inc. - Exhibit 1041, p. 7
`
`Contents
`
`42
`
`66
`
`82
`
`97
`
`ll?
`
`. I29
`
`Petitioner Apple Inc. - Exhibit 1041, p. 7
`
`

`

`Contents
`
`CHAPTER 8
`
`154
`165
`
`Using Algorithms
`8.1
`Block Cipher Modes
`8.2
`Multiple Encryption
`168
`8.3
`Stream Ciphers
`176
`8.4
`Stream Ciphers vs. Block Ciphers
`8.5
`Public—Key Cryptography vs. Symmetric Cryptography
`8.6
`Encrypting Communications Networks
`178
`8.7
`Encrypting Data for Storage
`180
`8.8
`Hardware Encryption vs. Software Encryption
`8.9
`File Erasure
`183
`
`181
`
`8.10
`
`Choosing an Algorithm
`
`[83
`
`PART 'I'I-IREE
`
`CRYPTOGRAPHIC ALGORITHMS
`
`CHAPTER 9
`
`Mathematical Background
`9.1
`Information Theory
`9.2
`Complexity Theory
`9.3
`Number Theory
`21 l
`9.4
`Factoring
`9.5
`Prime Number Generation
`
`198
`
`189
`193
`
`213
`
`9.6
`
`Discrete Logarithms in a Finite Field
`
`216
`
`CHAPTER IO
`
`Data Encryption Standard (DES)
`10.1
`Data Encryption Standard (DES)
`10.2
`DES Variants
`241
`
`219
`
`CHAPTER I
`
`1
`
`Other Block Algorithms
`11.1
`Lucifer
`244
`
`177
`
`vii
`
`I54
`
`187
`
`IE?
`
`2|9
`
`244
`
`11.2 Madryga
`11.3
`NewDES
`
`FEAL—N
`
`REDOC
`
`245
`247
`
`249
`
`252
`
`11.4
`
`11.5
`
`11.6
`
`11.7
`
`11.8
`11.9
`
`LOKI
`
`255
`
`Khufu and Khafre
`
`257
`
`RC2 and RC4
`IDEA
`260
`
`259
`
`11.10 MB
`
`11.11
`
`(IA-1. 1
`
`266
`
`268
`
`269
`11.12 Skipjack
`11.13 Using One-Way Hash Functions
`11.14 Other Block Algorithms
`272
`11.15 Which Block Algorithm Is Best?
`
`270
`
`272
`
`Petitioner Apple Inc. — Exhibit 1041, p. 8
`
`Petitioner Apple Inc. - Exhibit 1041, p. 8
`
`

`

`viii
`
`CHAPTER |2
`
`Public-Key Algorithms
`12.1
`Background
`12.2
`Diffie-Hellman
`
`2?.3
`275
`
`12.3
`12.4
`
`12.5
`12.6
`
`1 2.7
`
`Knapsack Algorithms
`RSA
`281
`
`277
`
`Pohlig-Hellman
`Rabin
`289
`
`288
`
`Feige-Fiat-Shamir
`
`291
`
`CHAPTER I3
`More Public-Key Algorithms
`13.1
`GuillousQuisquater
`13.2
`Ong—Schnorr-Shamir
`13.3
`ElGamal
`300
`
`297
`299
`
`13.4
`
`13.5
`13.6
`
`Schnorr
`
`302
`
`Digital Signature Algorithm (DSA)
`ESIGN
`314
`
`304
`
`13.7 McEliece
`
`316
`
`13.8
`
`13.9
`
`Okamoto 92
`
`317
`
`Cellular Automata
`
`31?
`
`31'?
`13.10 Elliptic Curve Cryptosystems
`318
`13.11 Other Public-Key Algorithms
`13.12 Which Public-Key Algorithm Is Best?
`
`320
`
`CHAPTER l4
`
`One-Way Hash Functions
`14.1
`Background
`32 1
`14.2
`Snefru
`
`324
`
`14.3
`
`N-Hash
`
`326
`
`14.4 MD4
`
`14.5 MDS
`
`14.6 MD2
`
`329
`
`329
`
`333
`
`14.7
`14.8
`
`14.9
`
`Secure Hash Algorithm (SI-IA)
`RIPE-MD
`336
`
`333
`
`HAVAL
`
`336
`
`337
`14.10 Other One—Way Hash Functions
`'
`14.11 Using Symmetric Block Algorithms
`344
`14.12 Using Public-Key Algorithms
`14.13 Which One-Way Hash Function Is Best?
`14.14 Key—Dependent One—Way Hash Functions
`
`338
`
`345
`345
`
`CHAPTER I5
`
`Random Sequence Generators and Stream Ciphers
`15.1
`Pseudo-Random Sequence Generators
`347
`15.2
`Stream Ciphers
`356
`
`Contents
`
`273
`
`297
`
`32|
`
`347
`
`Petitioner Apple Inc. - Exhibit 1041, p. 9
`
`Petitioner Apple Inc. - Exhibit 1041, p. 9
`
`

`

`Contents
`
`15.3
`15.4
`15.5
`
`368
`Real Random Sequence Generators
`Generating Numbers and Nonuniforrn Distributions
`Generating Random Permutations
`374
`
`372
`
`CHAPTER l6
`Special Algorithms for Protocols
`16.1
`Key Exchange
`376
`378
`16.2
`Encrypted Key Exchange
`16.3 Multiple-Key Public-Key Cryptography
`16.4
`Secret Broadcasting
`382
`16.5
`Secret Sharing Algorithms
`16.6
`Subliminal Channel
`
`383
`
`387
`
`392
`395
`
`Undeniable Digital Signatures
`16.7
`Computing with Encrypted Data
`16.8
`Fair Coin Flips
`395
`16.9
`398
`16.10 Fair Ciyptosystems
`16.11 All-or-Nothing Disclosure of Secrets
`16.12 Zero-Knowledge Proofs of Knowledge
`16.13 Blind Signatures
`403
`16.14 Oblivious Transfer
`404
`
`16.15 Secure Multiparty Computation
`16.16 Probabilistic Encryption
`406
`16.17 Quantum Cryptography
`408
`
`404
`
`PART FOUR
`
`THE REAL WORLD
`
`381
`
`399
`401
`
`CHAPTER 17
`
`Example Implementations
`17.1
`IBM Secret-Key Management Protocol
`17.2 Mitrenet
`414
`
`413
`
`17.3
`
`17.4
`
`17.5
`17.6
`
`ISBN
`
`415
`
`Kerberos
`
`417
`
`425
`Kryptoknight
`ISO Authentication Framework
`
`Privacy-Enhanced Mail (FEM)
`17.7
`17.8 Message Security Protocol (MSP)
`17.9
`Pretty Good Privacy (PGP)
`17.10 Clipper
`437
`17.11 CAPSTONE
`
`438
`
`436
`
`425
`
`428
`436
`
`ix
`
`376
`
`4| l
`
`4 I 3
`
`CHAPTER l8
`
`Politics
`
`18.1
`18.2
`18.3
`18.4
`
`439
`National Security Agency (NSA)
`440
`National Computer Security Center (NCSC)
`National Institute of Standards and Technology (NIST)
`RSA Data Security, Inc.
`444
`
`439
`
`441
`
`Petitioner Apple Inc. - Exhibit 1041, p. 10
`
`Petitioner Apple Inc. - Exhibit 1041, p. 10
`
`

`

`18.5
`
`18.6
`
`183?r
`
`18.8
`
`18.9
`
`18.10
`
`18.11
`
`18.12.
`
`18.13
`
`PART FIVE .
`
`SOURCE CODE
`
`International Association of Cryptographic Research
`(IACR)
`44S
`
`445
`
`Sci.crypt
`445
`Cypherpunks
`Research and Development in Advanced
`Communication Technologies in Europe (RACE)
`Electronic Frontier Foundation (EFF)
`446
`Computer Professionals for Social Responsibility (CPSR)
`Patents
`447
`
`446
`
`Export Rules
`Legal Issues
`
`448
`454
`
`Contents
`
`446
`
`SOURCE CODE
`
`VIGENERE, BEAUFORD, VARIANT BEAUFORD
`ENIGMA
`460
`DES
`
`467
`
`45?
`
`457
`
`LUCIFER
`NEWDES
`
`FEAL-B
`
`FEAL-NX
`
`REDOC III
`
`LOKI 9
`
`l
`
`485
`49l
`
`495
`
`502
`
`507
`
`5| |
`
`IDEA
`
`5 | 9
`
`N-HAS
`
`H
`
`532
`
`MD5
`
`542
`
`SECUR
`
`E HASH ALGORITHM
`
`549
`
`SECRET SHARING
`
`557
`
`REFERENCES
`
`INDEX
`
`57I
`
`605
`
`Petitioner Apple Inc. - Exhibit 1041, p. 11
`
`Petitioner Apple Inc. - Exhibit 1041, p. 11
`
`

`

`Foreword
`
`
`
`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 20th 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 [355]. 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 [418a],
`the device destined to be a mainstay of military
`cryptography for nearly fifty 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 transition 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 chhnicai Journal
`in 1949 [804]. It was similar to Friedman’s 1918 paper, in that it grew out of
`wartime work of Shannon’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
`different sort of contribution appeared: David Kahn‘s history, The Codebreaker-s
`[462]. 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
`
`Petitioner Apple Inc. - Exhibit 1041, p. 12
`
`xi
`
`Petitioner Apple Inc. - Exhibit 1041, p. 12
`
`

`

`xii
`
`Foreword
`
`the government 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.
`
`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
`deveIOpment of what was to become the US. Data Encryption Standard, and by
`the early I970s several technical reports on this subject by Feistel and his
`colleagues had been made public by IBM [339,837,839].
`This was the situation when I entered the field in late 1972. The cryptographic
`literature 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 integration of cryptography and cryptanalysis. This arises out
`of the fact that in the absence of real communications requirements, it is easy to
`propose a system 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 much harder than designing them in the first place. The
`result is that the competitive process, which is one strong motivation in academic
`research, cannot take hold.
`
`When Martin Hellman and I proposed public key cryptography in 1975 [299].
`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 peeple 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
`expository 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 pOpulate 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
`available 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
`contemporary researcher, yes, but whatabout 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 literature before being able to design the sort of cryptographic utilities
`glibly described in popular articles.
`
`Petitioner Apple Inc. - Exhibit 1041, p. 13
`
`Petitioner Apple Inc. - Exhibit 1041, p. 13
`
`

`

`Foreword
`
`xiii
`
`This is the gap that Bruce Schneier's Applied Cryptography: Protocols, Algorithms, and
`Source Code in C 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 fifteen years of public research.
`The table of contents tells 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.
`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
`International Association for Cryptologic Research to the National Security Agency.
`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 contained an explicit exemption for published material— but gave both
`the public practice of cryptography and the 1977 Information Theory Workshop
`lots of unexpected publicity.
`A more serious attempt occurred in 1980, when 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
`cryptographic papers; researchers were requested to ask the NSA’S opinion on
`whether disclosure 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 substantial influence not only over what was exported, but of
`what was sold in the United States.
`
`As this is written. a newchallenge confronts the public practice of cryptography.
`The government proposes to replace the widely published and available Data
`Encryption 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 proposal 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. It has attracted widespread negative comment,
`especially from independent cryptographers. Some people, however, see more future
`in programming than politicki ng and have redoubled their efforts to provide the world
`with strong cryptography that is accessible to public scrutiny.
`
`Petitioner Apple Inc. - Exhibit 1041, p. 14
`
`Petitioner Apple Inc. - Exhibit 1041, p. 14
`
`

`

`xiv
`
`Foreword
`
`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
`gone away should be evident from statements at a recent 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 gray area”
`with respect to the law. If that is so, it is a gray area on which this book can be
`expected to shed some light.
`The shift in the NSA‘S strategy, from attempting to control cryptographic
`research to tightening its grip on the development and deployment of cryptographic
`products, 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
`might 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
`might.
`
`Whitfield Diffie
`
`Mountain View, CA
`
`Petitioner Apple Inc. - Exhibit 1041, p. 15
`
`Petitioner Apple Inc. - Exhibit 1041, p. 15
`
`

`

`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
`governments from reading your files. This book is about the latter.
`if I take a letter, lock it in a safe, and hide the safe somewhere in New York .
`
`. . and
`
`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
`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
`military. The United States’ National Security Agency, and its counterparts in the
`Soviet Union, England, France, Israel, and elsewhere, have spent billions of
`dollars in the very serious game of securing their own communications while
`trying to break everyone else’s. The private individual, with far less expertise and
`budget, has been powerless to protect his own privacy against these governments.
`During the last twenty years, there has been an explosion of public academic
`research in cryptography. For the first time, state-of-theart computer cryptography is
`being practiced outside the secured walls of the military agencies. It is now possible
`for you and me to employ security practices that can protect against the most powerful
`of adversaries—security that may even protect against the military agencies.
`Does the average person really need this kind of security? I say yes. He may
`be planning a political campaign, discussing his taxes, or having an illicit affair.
`He may be designing a new product, discussing a marketing strategy, or planning
`a hostile business takeover. He may be living in a country that does not respect
`the rights of privacy of its citizens. He may be doing something that he feels
`
`Petitioner Apple Inc. - Exhibit 1041, p. 16
`
`xv
`
`Petitioner Apple Inc. - Exhibit 1041, p. 16
`
`

`

`xvi
`
`Preface
`
`shouldn’t be illegal, but is. Whatever his reasons, his data and communications
`are personal, private, and nobody’s business but his own.
`This book is being published in a tumultuous time. The Clinton Administration
`has just proposed the Clipper chip, which ensures the government the ability to
`conduct electronic surveillance. Clipper is based on the Orwellian assumption that
`the government has the right to listen to private communications. It promotes the
`power of the government over the power of the individual. This is not simply a
`little government proposal in some obscure area; it is a preemptive and unilateral
`attempt to usurp powers that previously belonged to the people.
`Clipper does not protect privacy; it forces individuals to unconditionally trust
`that the government will respect their privacy. It assumes that the government is
`the good guy and private citizens are all bad guys. The same law enforcement
`authorities that illegally tapped Martin Luther King, Jr.’s phones can easily tap a
`phone protected with Clipper. During the past five years, local police authorities
`have been either charged criminally or sued civilly in numerous jurisdictions —-
`including Maryland, Connecticut, Vermont, Georgia, Missouri, and Nevada —for
`conducting illegal wiretaps. It’s a poor idea to deploy technologies that could
`someday facilitate a police state.
`At the time I am writing, it is too early to tell what will happen to the Clipper
`chip. At one extreme, it could become a minor anecdote about a failed attempt
`by the government to invade peoples’ privacy—people reading this five years
`from now will wonder what I am talking about. At the other, it could be the first
`in a series of initiatives designed to outlaw private encryption—five years from
`now most of the techniques described in this book will be illegal. The truth will
`probably lie somewhere in the middle.
`Encryption is too important to be left to the government.
`
`HOW TO READ THIS BOOK
`
`I wrote Applied Cryptography to be a comprehensive reference work for modem
`cryptography. The first chapter introduces cryptography, defines many terms, and
`briefly discusses pre-computer cryptography.
`Part 1 (Chapters 2 through 6) discuss cryptographic protocols. This is what
`you can do with cryptography. The protocols range from the simple (sending
`encrypted messages from one person to another) to the complex (flipping a coin
`over the telephone) to the esoteric (secure and anonymous digital money). Some
`of these protocols are obvious; others are almost amazing. If you are interested,
`read through all of the things cryptography can do that seem impossible. If these
`protocols start getting tedious, skip to the next section.
`Part II discusses cryptographic techniques. Both chapters in this section are
`important for even the most basic uses of cryptography. Chapter 7 is about keys:
`how long should a key be in order to be secure, how do you generate keys, how
`do you store keys, how do you dispose of keys, etc. Key management is the hardest
`part of cryptography, and often the Achilles heel of an otherwise secure system.
`Chapter 8 discusses different ways of using cryptographic algorithms, and how to
`choose algorithms for communication, data storage, etc.
`
`Petitioner Apple Inc. - Exhibit 1041, p. 17
`
`Petitioner Apple Inc. - Exhibit 1041, p. 17
`
`

`

`Preface
`
`xvii
`
`In Part III, the book finally turns to algorithms. Chapter 9 is a mathematical
`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 this chapter. Chapter 10 discusses DES. Chapter 1 1 discusses other symmetric
`algorithms. If you want something more secure than DES, skip to the section on
`IDEA. If you want to read about a bunch of algorithms, some of which may be
`more secure than DES, read the whole chapter. Chapters 12 and 13 discuss
`public-key algorithms; if you just want the basics, read the introduction to Chapter
`12, the section on Diffie—Hellman, the section on RSA, and the section in Chapter
`13 on DSS. Chapter 14 is about one-way hash functions: MDS and SHA are the
`most common, although I discuss many more. Chapter 15 is about random number
`generation and stream ciphers. There is a bias in cryptographic research in the
`world; most of the work on stream ciphers is done in Europe, while in the United
`States stream cipher research takes a back seat to block cipher research. To some
`degree, this book perpetuates the bias. And finally, Chapter 16 discusses algorithms
`specifically designed to implement some of the protocols in Part I. The math can
`get complicated here; wear your seat belt.
`Part IV has two chapters. Chapter 17 discusses some real-World implementations
`of these algorithms and protocols, and chapter 18 touches on some of the
`political issues surrounding cryptography. These are by no means intended to
`be comprehensive.
`Finally, Part V gives source code listings for some of the algorithms'In Part IV.
`I wanted to include much more code than I was able to, but space limitations got
`in the way. There is an associated source code disk that includes these listings, as
`well as all the listings that I didn’t have space for. If you are at all interested in
`implementing or playing with the cryptographic algorithms in this book, get the
`disk.
`
`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 who are interested in formalism, there are copious pointers to references in
`the academic literature.
`
`If there was a criticism of this book, it 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. There is a lot being done in the field; this is the first time so much of it
`has been gathered under one roof. For those who are more interested in a tutorial,
`I apologize. Even so, there are many things that space forced me to leave out. I
`tried to cover topics that I felt were important, topics that I felt were practical, and
`topics that I felt were interesting. If I couldn t cover a topic in depth, I gave
`references to articles and papers that did. If there are aspects of cryptography that
`you wish were coVered in more depth, I apologize.
`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. Any errors I find after publication
`will be corrected on the source code disk. Any new information discovered after
`publication will also be on the disk. If someone finds an error, please tell me. The
`first person to find each error in the book will get a free copy of the source code disk.
`
`Petitioner Apple Inc. - Exhibit 1041, p. 18
`
`Petitioner Apple Inc. - Exhibit 1041, p. 18
`
`

`

`xviii
`
`ACKNOWLEDGMENTS
`
`Preface
`
`The list of people who had a hand in this book seems unending, but all are
`worthy of mention. I would like to thank Don Alvarez, Ross Anderson, Karl
`Barres, Steve'Bellovin, Dan Bernstein, Eli Biham, Joan Boyar, Karen Cooper,
`Whitfield Diffie, Joan Feigenbaum, Phil Kam, Neal Koblitz, Xuija Lai, Torn
`Leranth, Mark Markowitz, Ralph Merkle, Bill Patton, Peter Pearson, Mark
`Riordan, and Marc Schwartz for reading and editing all or parts of the manuscript;
`Lawrie Brown, Leisa Condie, Peter Gutmann, Alan lnsley, Xuija Lai, Peter
`Pearson, Ken Pizzini, Richard Outerbridge, RSA Data Security Inc., Michael
`Wood, and Phil Zimmermann for providing source code; the readers of sci.crypt
`for commenting on ideas and answering questions, Paul Machrland for creating
`the figures; Randy Seuss for providing Internet access; Jeff Duntemann and Jon
`Erickson for helping me find a publisher; Paul Farrell for editing this book;
`assorted random lnsleys for the impetus, encouragement, support, conversations,
`friendship, and dinners; and AT&T Bell Labs for firing me and making this all
`possible. These people helped to create a far better book than I could have done
`alone.
`
`Bruce Schneier
`
`Oak Park, 1]].
`
`Petitioner Apple Inc. - Exhibit 1041, p. 19
`
`Petitioner Apple Inc. - Exhibit 1041, p. 19
`
`

`

`
`
`Foundafions
`
`I . I
`
`TERMINOLOGY
`
`Sender and Receiver
`
`Suppose someone, whom we shall call the sender, wants to send a message to
`someone else, whom we shall call the receiver. Moreover. the sender wants to
`make sure an intermediary cannot affect the message in any way: specifically, the
`receiver cannot intercept and read the message, intercept and modify the message,
`or fabricate a realistic-looking substitute message.
`
`Messages and Encryption
`
`A message is called either plaintext or cleartext. The process of disguising a
`message in such a way as to hide its substance is called encryption. An encrypted
`message is called ciphertext. The process of turning ciphertext back into plaintext
`is called decryption. This is shown in Figure 1.1.
`The art and science of keeping messages secure is called cryptography, and it
`is practiced by cryptographers. Cryptanalysts are practitioners of
`cryptanalysis, the art and science of breaking ciphertext, i.e.. seeing through the
`disguise. The branch of mathematics embodying both cryptography and
`cryptanalysis is called cryptology, and its practitioners are called cryptolo