Computer Security and Cryptography

Gain the skills and knowledge needed to create effective data security systems This book updates readers with all the tools, techniques, and concepts needed to understand and implement data security systems. It presents a wide range of topics for a thorough understanding of the factors that affect the efficiency of secrecy, authentication, and digital signature schema. Most importantly, readers gain hands-on experience in cryptanalysis and learn how to create effective cryptographic systems. The author contributed to the design and analysis of the Data Encryption Standard (DES), a widely used symmetric-key encryption algorithm. His recommendations are based on firsthand experience of what does and does not work. Thorough in its coverage, the book starts with a discussion of the history of cryptography, including a description of the basic encryption systems and many of the cipher systems used in the twentieth century. The author then discusses the theory of symmetric- and public-key cryptography. Readers not only discover what cryptography can do to protect sensitive data, but also learn the practical limitations of the technology. The book ends with two chapters that explore a wide range of cryptography applications. Three basic types of chapters are featured to facilitate learning: Chapters that develop technical skills Chapters that describe a cryptosystem and present a method of analysis Chapters that describe a cryptosystem, present a method of analysis, and provide problems to test your grasp of the material and your ability to implement practical solutions With consumers becoming increasingly wary of identity theft and companies struggling to develop safe, secure systems, this book is essential reading for professionals in e-commerce and information technology. Written by a professor who teaches cryptography, it is also ideal for students. COVER......Page 1 CONTENTS......Page 8 FOREWORD......Page 12 WHY STUDY CRYPTOGRAPHY?......Page 14 MY PRIOR ART......Page 15 ORGANIZATION OF THE BOOK......Page 17 ACKNOWLEDGMENTS......Page 18 ABOUT THE AUTHOR......Page 20 1.1 THE LEXICON OF CRYPTOGRAPHY......Page 22 1.3 CRYPTANALYSIS......Page 25 1.5 THOMAS JEFFERSON AND THE M-94......Page 27 1.6 CRYPTOGRAPHY AND HISTORY......Page 28 1.7 CRYPTOGRAPHY AND COMPUTERS......Page 29 1.8 THE NATIONAL SECURITY AGENCY......Page 30 1.9 THE GIANTS......Page 31 1.10 NO SEX, MONEY, CRIME OR . . . LOVE......Page 33 1.11 AN EXAMPLE OF THE INFERENCE PROCESS IN CRYPTANALYSIS......Page 34 1.12 WARNING!......Page 36 REFERENCES......Page 38 2.2 THE RULES OF COLUMNAR TRANSPOSITION ENCIPHERMENT......Page 39 2.3 CRIBBING......Page 42 2.4 EXAMPLES OF CRIBBING......Page 46 2.5 PLAINTEXT LANGUAGE MODELS......Page 51 2.6 COUNTING k-GRAMS......Page 54 2.8 MARKOV SCORING......Page 55 2.9 THE ADFGVX TRANSPOSITION SYSTEM......Page 68 2.10 CODA......Page 70 PROBLEMS......Page 71 APPENDIX: MARKOV PARAMETERS......Page 76 REFERENCES......Page 83 3.1 MONOALPHABETIC SUBSTITUTION......Page 84 3.2 CAESAR’S CIPHER......Page 86 3.3 CRIBBING USING ISOMORPHS......Page 87 3.4 THE χ2-TEST OF A HYPOTHESIS......Page 88 3.5 PRUNING FROM THE TABLE OF ISOMORPHS......Page 89 3.6 PARTIAL MAXIMUM LIKELIHOOD ESTIMATION OF A MONOALPHABETIC SUBSTITUTION......Page 94 3.7 THE HIDDEN MARKOV MODEL (HMM)......Page 99 3.8 HILL ENCIPHERMENT OF ASCII N-GRAMS......Page 111 3.9 GAUSSIAN ELIMINATION......Page 123 3.10 MONOALPHABETIC SUBSTITUTION PROBLEMS......Page 132 REFERENCES......Page 135 4.1 RUNNING KEYS......Page 137 4.3 GILBERT S. VERNAM......Page 138 4.4 THE ONE-TIME PAD......Page 140 4.5 FINDING THE KEY OF VERNAM–VIGENÈRE CIPHERTEXT WITH KNOWN PERIOD BY CORRELATION......Page 141 4.6 COINCIDENCE......Page 145 4.7 VENONA......Page 148 PROBLEMS......Page 153 REFERENCES......Page 156 5.2 THE KOLMOGOROV–SMIRNOV TEST......Page 157 5.3 NIST’S PROPOSED STATISTICAL TESTS......Page 159 5.4 DIAGNOSIS......Page 160 PROBLEMS......Page 164 REFERENCES......Page 170 6.1 THE ROTOR......Page 171 6.2 ROTOR SYSTEMS......Page 173 6.3 ROTOR PATENTS......Page 174 6.4 A CHARACTERISTIC PROPERTY OF CONJUGACY......Page 176 6.5 ANALYSIS OF A 1-ROTOR SYSTEM: CIPHERTEXT ONLY......Page 177 6.6 THE DISPLACEMENT SEQUENCE OF A PERMUTATION......Page 179 6.7 ARTHUR SCHERBIUS......Page 181 6.8 ENIGMA KEY DISTRIBUTION PROTOCOL......Page 184 6.9 CRYPTANALYSIS OF THE ENIGMA......Page 187 6.10 CRIBBING ENIGMA CIPHERTEXT......Page 188 6.11 THE LORENZ SCHLÜSSELZUSATZ......Page 191 6.12 THE SZ40 PIN WHEELS......Page 192 6.13 SZ40 CRYPTANALYSIS PROBLEMS......Page 196 6.14 CRIBBING SZ40 CIPHERTEXT......Page 197 REFERENCES......Page 211 7.2 HALF-ROTORS......Page 212 7.3 COMPONENTS OF THE RED MACHINE......Page 214 7.4 CRIBBING RED CIPHERTEXT......Page 221 7.5 GENERALIZED VOWELS AND CONSONANTS......Page 230 7.6 “CLIMB MOUNT ITAKA” – WAR!......Page 231 7.7 COMPONENTS OF THE PURPLE MACHINE......Page 232 7.8 THE PURPLE KEYS......Page 238 7.9 CRIBBING PURPLE: FINDING THE V-STEPPER......Page 240 7.10 CRIBBING PURPLE: FINDING THE C-STEPPERS......Page 259 REFERENCES......Page 264 8.2 FEEDBACK SHIFT REGISTERS......Page 265 8.3 THE ALGEBRA OF POLYNOMIALS OVER ZZ2......Page 268 8.4 THE CHARACTERISTIC POLYNOMIAL OF A LINEAR FEEDBACK SHIFT REGISTER......Page 272 8.5 PROPERTIES OF MAXIMAL LENGTH LFSR SEQUENCES......Page 275 8.6 LINEAR EQUIVALENCE......Page 279 8.7 COMBINING MULTIPLE LINEAR FEEDBACK SHIFT REGISTERS......Page 280 8.8 MATRIX REPRESENTATION OF THE LFSR......Page 281 8.9 CRIBBING OF STREAM ENCIPHERED ASCII PLAINTEXT......Page 282 8.10 NONLINEAR FEEDBACK SHIFT REGISTERS......Page 292 8.11 NONLINEAR KEY STREAM GENERATION......Page 294 8.12 IRREGULAR CLOCKING......Page 296 8.13 RC4......Page 299 REFERENCES......Page 302 9.1 LUCIFER......Page 304 9.2 DES......Page 309 9.3 THE DES S-BOXES, P-BOX, AND INITIAL PERMUTATION (IP)......Page 310 9.4 DES KEY SCHEDULE......Page 313 9.5 SAMPLE DES ENCIPHERMENT......Page 315 9.6 CHAINING......Page 316 9.7 IS DES A RANDOM MAPPING?......Page 318 9.8 DES IN THE OUTPUT-FEEDBACK MODE (OFB)......Page 320 9.9 CRYPTANALYSIS OF DES......Page 321 9.10 DIFFERENTIAL CRYPTANALYSIS......Page 323 9.11 THE EFS DES-CRACKER......Page 329 9.12 WHAT NOW?......Page 332 9.14 AND THE WINNER IS!......Page 333 9.15 THE RIJNDAEL OPERATIONS......Page 335 9.17 RIJNDAEL’S STRENGTH: PROPAGATION OF PATTERNS......Page 344 9.18 WHEN IS A PRODUCT BLOCK-CIPHER SECURE?......Page 347 9.19 GENERATING THE SYMMETRIC GROUP......Page 348 9.20 A CLASS OF BLOCK CIPHERS......Page 350 REFERENCES......Page 353 10.1 IN THE BEGINNING. . .......Page 355 10.2 KEY DISTRIBUTION......Page 356 10.3 E-COMMERCE......Page 357 10.4 PUBLIC-KEY CRYPTOSYSTEMS: EASY AND HARD COMPUTATIONAL PROBLEMS......Page 358 10.5 DO PKCS SOLVE THE PROBLEM OF KEY DISTRIBUTION?......Page 362 REFERENCES......Page 363 11.1 SUBSET SUM AND KNAPSACK PROBLEMS......Page 365 11.2 MODULAR ARITHMETIC AND THE EUCLIDEAN ALGORITHM......Page 367 11.4 TRAP-DOOR KNAPSACKS......Page 371 11.5 KNAPSACK ENCIPHERMENT AND DECIPHERMENT OF ASCII-PLAINTEXT......Page 376 11.6 CRYPTANALYSIS OF THE MERKLE–HELLMAN KNAPSACK SYSTEM (MODULAR MAPPING) [SHAMIR, 1982]......Page 379 11.7 DIOPHANTINE APPROXIMATION......Page 385 11.8 SHORT VECTORS IN A LATTICE......Page 389 PROBLEMS......Page 392 REFERENCES......Page 396 12.1 A SHORT NUMBER-THEORETIC DIGRESSION [KOBLITZ, 1987]......Page 397 12.2 RSA [RIVEST ET AL., 1978]......Page 399 12.3 THE RSA ENCIPHERMENT AND DECIPHERMENT OF ASCII-PLAINTEXT......Page 400 12.4 ATTACK ON RSA [SIMMONS, 1983; DELAURENTIS, 1984]......Page 403 12.5 WILLIAMS VARIATION OF RSA......Page 404 12.6 MULTIPRECISION MODULAR ARITHMETIC......Page 408 REFERENCES......Page 410 13.2 PRIME NUMBERS AND THE SIEVE OF ERATOSTHENES......Page 411 13.3 POLLARD’S p-1 METHOD [POLLARD, 1974]......Page 412 13.4 POLLARD’S ρ-ALGORITHM [POLLARD, 1978]......Page 415 13.5 QUADRATIC RESIDUES......Page 417 13.6 RANDOM FACTORIZATION......Page 422 13.7 THE QUADRATIC SIEVE (QS)......Page 424 13.8 TESTING IF AN INTEGER IS A PRIME......Page 426 13.9 THE RSA CHALLENGE......Page 428 13.10 PERFECT NUMBERS AND THE MERSENNE PRIMES......Page 429 13.11 MULTIPRECISION ARITHMETIC......Page 430 13.12 PRIME NUMBER TESTING AND FACTORIZATION PROBLEMS......Page 431 REFERENCES......Page 434 14.1 THE DISCRETE LOGARITHM PROBLEM MODULO p......Page 435 14.2 SOLUTION OF THE DLP MODULO p GIVEN A FACTORIZATION OF p-1......Page 436 14.3 ADELMAN’S SUBEXPONENTIAL ALGORITHM FOR THE DISCRETE LOGARITHM PROBLEM [ADELMAN, 1979]......Page 440 14.5 THE INDEX-CALCULUS METHOD......Page 441 14.6 POLLARD’S ALGORITHM [POLLARD, 1978]......Page 445 14.7 EXTENSION FIELDS......Page 447 REFERENCES......Page 449 15.1 ELLIPTIC CURVES......Page 450 15.2 THE ELLIPTIC GROUP OVER THE REALS......Page 452 15.3 LENSTRA’S FACTORIZATION ALGORITHM [LENSTRA, 1986]......Page 453 15.4 THE ELLIPTIC GROUP OVER Zp ( p > 3)......Page 455 15.5 ELLIPTIC GROUPS OVER THE FIELD Zm,2......Page 457 15.6 COMPUTATIONS IN THE ELLIPTIC GROUP εzm2(a,b)......Page 459 15.7 SUPERSINGULAR ELLIPTIC CURVES......Page 462 15.8 DIFFIE–HELLMAN KEY EXCHANGE USING AN ELLIPTIC CURVE......Page 463 15.9 THE MENEZES–VANSTONE ELLIPTIC CURVE CRYPTOSYSTEM......Page 464 15.10 THE ELLIPTIC CURVE DIGITAL SIGNATURE ALGORITHM......Page 465 15.12 NSA AND ELLIPTIC CURVE CRYPTOGRAPHY......Page 466 REFERENCES......Page 467 16.1 KEY DISTRIBUTION IN A NETWORK......Page 468 16.3 SPOOFING......Page 469 16.4 EL GAMAL’S EXTENSION OF DIFFIE–HELLMAN......Page 471 16.5 SHAMIR’S AUTONOMOUS KEY EXCHANGE......Page 472 16.6 X9.17 KEY EXCHANGE ARCHITECTURE [ANSI, 1985]......Page 474 16.7 THE NEEDHAM–SCHROEDER KEY DISTRIBUTION PROTOCOL [NEEDHAM AND SCHROEDER, 1998]......Page 477 REFERENCES......Page 484 17.1 THE NEED FOR SIGNATURES......Page 485 17.3 SECRECY, DIGITAL SIGNATURES, AND AUTHENTICATION......Page 486 17.4 THE DESIDERATA OF A DIGITAL SIGNATURE......Page 487 17.5 PUBLIC-KEY CRYPTOGRAPHY AND SIGNATURE SYSTEMS......Page 488 17.6 RABIN’S QUADRATIC RESIDUE SIGNATURE PROTOCOL......Page 489 17.7 HASH FUNCTIONS......Page 491 17.8 MD5......Page 492 17.9 THE SECURE HASH ALGORITHM......Page 494 17.10 NIST’S DIGITAL SIGNATURE ALGORITHM [NIST, 1991, 1994]......Page 495 17.11 EL GAMAL’S SIGNATURE PROTOCOL [EL GAMAL, 1985a, b]......Page 496 17.12 THE FIAT–SHAMIR IDENTIFICATION AND SIGNATURE SCHEMA [FIAT AND SHAMIR, 1986]......Page 497 REFERENCES......Page 499 18.1 UNIX PASSWORD ENCIPHERMENT......Page 501 18.2 MAGNETIC STRIPE TECHNOLOGY......Page 503 18.3 PROTECTING ATM TRANSACTIONS......Page 505 18.5 SMART CARDS......Page 512 18.7 X.509 CERTIFICATES......Page 516 18.8 THE SECURE SOCKET LAYER (SSL)......Page 518 18.9 MAKING A SECURE CREDIT CARD PAYMENT ON THE WEB......Page 523 REFERENCES......Page 526 19.1 WHAT IS A PATENT?......Page 527 19.3 THE FORMAT OF A PATENT......Page 528 19.4 PATENTABLE VERSUS NONPATENTABLE SUBJECTS......Page 529 19.7 U.S. PATENT 3,543,904 [CONSTABLE, 1970]......Page 530 19.8 U.S. PATENT 4,200,770 [HELLMAN ET AL., 1977]......Page 532 19.10 U.S. PATENT 4,405,829 [RIVERST ET AL., 1977]......Page 533 19.12 LEON STAMBLER......Page 535 REFERENCES......Page 536 INDEX......Page 537