Applied Cryptography

Bruce Schneier is an internationally renowned security technologist, called a "security guru" by The Economist. He is the author of twelve books—including his seminal work, Applied Cryptography: Protocols, Algorithms, and Source Code in C, and Secrets & Lies: Digital Security in a Networked World as well as hundreds of articles, essays, and academic papers. His influential newsletter "Crypto-Gram" and blog "Schneier on Security" are read by over 250,000 people. Schneier is a fellow at the Berkman Center for Internet and Society at Harvard Law School, a program fellow at the New America Foundation's Open Technology Institute, a board member of the Electronic Frontier Foundation, and an Advisory Board member of the Electronic Privacy Information Center. He is also the Chief Technology Officer of Resilient Systems, Inc. You can read his blog, essays, andacademic papers at www.schneier.com. He tweets at @schneierblog.

CONTENTS INTRODUCTION XIII FOREWORD BY WHITFIELD DIFFIE XVII PREFACE XXI HOW TO READ THIS BOOK XXII ACKNOWLEDGMENTS XXIV ABOUT THE AUTHOR XXV 1 FOUNDATIONS 7 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 27 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 47 2.8 RANDOM AND PSEUDO-RANDOM SEQUENCE GENERATION 44 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 226 5.6 OBLIVIOUS SIGNATURES 227 5.7 SIMULTANEOUS CONTRACT SIGNING 228 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 234 6.3 ANONYMOUS MESSAGE BROADCAST 237 6.4 DIGITAL CASH 239 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 EMETOR 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 181 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 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 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 255 11.5 PRIME NUMBER GENERATION 258 11.6 DISCRETE LOGARITHMS IN A FINITE FIELD 262 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