Computer Security and Cryptography

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