Computer security and cryptography

Foreword

Preface

About the Author

Chapter 1. Aperitifs

1.1. The Lexicon of Cryptography

1.2. Cryptographic Systems

1.3. Cryptanalysis

1.4. Side Information

1.5. Thomas Jefferson and the M-94

1.6. Cryptography and History

1.7. Cryptography and Computers

1.8. The National Security Agency

1.9. The Giants

1.10. No Sex, Money, Crime or...Love

1.11. An Example of the Inference Process in Cryptanalysis

1.12. Warning!

Chapter 2. Columnar Transposition

2.1. Shannon's Classification of Secrecy Transformations

2.2. The Rules of Columnar Transposition Encipherment

2.3. Cribbing

2.4. Examples of Cribbing

2.5. Plaintext Language Models

2.6. Counting k-Grams

2.7. Deriving the Parameters of a Markov Model from Sliding Window Counts

2.8. Markov Scoring

2.9. The ADFGVX Transposition System

2.10. Coda

2.11. Columnar Transposition Problems

Chapter 3. Monoalphabetic Substitution

3.1. Monoalphabetic Substitution

3.2. Caesar's Cipher

3.3. Cribbing Using Isomorphs

3.4. The x[superscript 2]-Test of a Hypothesis

3.5. Pruning from the Table of Isomorphs

3.6. Partial Maximum Likelihood Estimation of a Monoalphabetic Substitution

3.7. The Hidden Markov Model (HMM)

3.8. Hill Encipherment of ASCII N-Grams

3.9. Gaussian Elimination

3.10. Monoalphabetic Substitution Problems

Chapter 4. Polyalphabetic Substitution

4.1. Running Keys

4.2. Blaise de Vigenere

4.3. Gilbert S. Vernam

4.4. The One-Time Pad

4.5. Finding the Key of Vernam-Vigenere Ciphertext with Known Period by Correlation

4.6. Coincidence

4.7. Venona

4.8. Polyalphabetic Substitution Problems

Chapter 5. Statistical Tests

5.1. Weaknesses in a Cryptosystem

5.2. The Kolmogorov-Smirnov Test

5.3. NIST's Proposed Statistical Tests

5.4. Diagnosis

5.5. Statistical Tests Problems

Chapter 6. The Emergence of Cipher Machines

6.1. The Rotor

6.2. Rotor Systems

6.3. Rotor Patents

6.4. A Characteristic Property of Conjugacy

6.5. Analysis of a 1-Rotor System: Ciphertext Only

6.6. The Displacement Sequence of a Permutation

6.7. Arthur Scherbius

6.8. Enigma Key Distribution Protocol

6.9. Cryptanalysis of the Enigma

6.10. Cribbing Enigma Ciphertext

6.11. The Lorenz Schlusselzusatz

6.12. The SZ40 Pin Wheels

6.13. SZ40 Cryptanalysis Problems

6.14. Cribbing SZ40 Ciphertext

Chapter 7. The Japanese Cipher Machines

7.1. Japanese Signaling Conventions

7.2. Half-Rotors

7.3. Components of the RED Machine

7.4. Cribbing RED Ciphertext

7.5. Generalized Vowels and Consonants

7.6. "Climb Mount Itaka" - War!

7.7. Components of the Purple Machine

7.8. The Purple Keys

7.9. Cribbing Purple Finding the V-Stepper

7.10. Cribbing purple Finding the C-Steppers

Chapter 8. Stream Ciphers

8.1. Stream Ciphers

8.2. Feedback Shift Registers

8.3. The Algebra of Polynomials over Z[subscript 2]

8.4. The Characteristic Polynomial of a Linear Feedback Shift Register

8.5. Properties of Maximal Length LFSR Sequences

8.6. Linear Equivalence

8.7. Combining Multiple Linear Feedback Shift Registers

8.8. Matrix Representation of the LFSR

8.9. Cribbing of Stream Enciphered ASCII Plaintext

8.10. Nonlinear Feedback Shift Registers

8.11. Nonlinear Key Stream Generation

8.12. Irregular Clocking

8.13. RC4

8.14. Stream Encipherment Problems

Chapter 9. Block-Ciphers Lucifer, Des, and Aes

9.1. Lucifer

9.2. DES

9.3. The DES S-Boxes, P-Box, and Initial Permutation (IP)

9.4. DES Key Schedule

9.5. Sample DES Encipherment

9.6. Chaining

9.7. Is DES a Random Mapping?

9.8. DES in the Output-Feedback Mode (OFB)

9.9. Cryptanalysis of DES

9.10. Differential Cryptanalysis

9.11. The EFS DES-Cracker

9.12. What Now?

9.13. The Future Advanced Data Encryption Standard

9.14. And the Winner Is!

9.15. The Rijndael Operations

9.16. The Rijndael Cipher

9.17. Rijndael's Strength Propagation of Patterns

9.18. When is a Product Block-Cipher Secure?

9.19. Generating the Symmetric Group

9.20. A Class of Block Ciphers

9.21. The IDEA Block Cipher

Chapter 10. The Paradigm of Public key Cryptography

10.1. In the Beginning...

10.2. Key Distribution

10.3. E-Commerce

10.4. Public-Key Cryptosystems: Easy and Hard Computational Problems

10.5. Do PKCs Solve the Problem of Key Distribution?

10.6. P.S.

Chapter 11. The Knapsack Cryptosystem

11.1. Subset Sum and Knapsack Problems

11.2. Modular Arithmetic and the Euclidean Algorithm

11.3. A Modular Arithmetic Knapsack Problem

11.4. Trap-Door Knapsacks

11.5. Knapsack Encipherment and Decipherment of ASCII-Plaintext

11.6. Cryptanalysis of the Merkle-Hellman Knapsack System (Modular Mapping)

11.7. Diophantine Approximation

11.8. Short Vectors in a Lattice

11.9. Knapsack-Like Cryptosystems

11.10. Knapsack Cryptosystem Problems

Chapter 12. The RSA Cryptosystem

12.1. A Short Number-Theoretic Digression

12.2. RSA

12.3. The RSA Encipherment and Decipherment of ASCII-Plaintext

12.4. Attack on RSA

12.5. Williams Variation of RSA

12.6. Multiprecision Modular Arithmetic

Chapter 13. Prime Numbers and Factorization

13.1. Number Theory and Cryptography

13.2. Prime Numbers and the Sieve of Eratosthenes

13.3. Pollard's p - 1 Method

13.4. Pollard's [rho]-Algorithm

13.5. Quadratic Residues

13.6. Random Factorization

13.7. The Quadratic Sieve (QS)

13.8. Testing if an Integer is a Prime

13.9. The RSA Challenge

13.10. Perfect Numbers and the Mersenne Primes

13.11. Multiprecision Arithmetic

13.12. Prime Number Testing and Factorization Problems

Chapter 14. The Discrete Logarithm Problem

14.1. The Discrete Logarithm Problem Modulo p

14.2. Solution of the DLP Modulo p Given a Factorization of p - 1

14.3. Adelman's Subexponential Algorithm for the Discrete Logarithm Problem

14.4. The Baby-Step, Giant-Step Algorithm

14.5. The Index-Calculus Method

14.6. Pollard's [rho]-Algorithm

14.7. Extension Fields

14.8. The Current State of Discrete Logarithm Research

Chapter 15. Elliptic Curve Cryptography

15.1. Elliptic Curves

15.2. The Elliptic Group over the Reals

15.3. Lenstra's Factorization Algorithm

15.4. The Elliptic Group over Z[subscript p] (p > 3)

15.5. Elliptic Groups over the Field Z[subscript m,2]

15.6. Computations in the Elliptic Group [epsilon][subscript Zm,2](a, b)

15.7. Supersingular Elliptic Curves

15.8. Diffie-Hellman Key Exchange Using an Elliptic Curve

15.9. The Menezes-Vanstone Elliptic Curve Cryptosystem

15.10. The Elliptic Curve Digital Signature Algorithm

15.11. The Certicom Challenge

15.12. NSA and Elliptic Curve Cryptography

Chapter 16. Key Exchange in a Network

16.1. Key Distribution in a Network

16.2. U.S. Patent '770

16.3. Spoofing

16.4. El Gamal's Extension of Diffie-Hellman

16.5. Shamir's Autonomous Key Exchange

16.6. X9.17 Key Exchange Architecture

16.7. The Needham-Schroeder Key Distribution Protocol

Chapter 17. Digital Signatures and Authentication

17.1. The Need for Signatures

17.2. Threats to Network Transactions

17.3. Secrecy, Digital Signatures, and Authentication

17.4. The Desiderata of a Digital Signature

17.5. Public-Key Cryptography and Signature Systems

17.6. Rabin's Quadratic Residue Signature Protocol

17.7. Hash Functions

17.8. MD5

17.9. The Secure Hash Algorithm

17.10. NIST's Digital Signature Algorithm

17.11. El Gamal's Signature Protocol

17.12. The Fiat-Shamir Identification and Signature Schema

17.13. The Oblivious Transfer

Chapter 18. Applications of cryptography

18.1. UNIX Password Encipherment

18.2. Magnetic Stripe Technology

18.3. Protecting ATM Transactions

18.4. Keyed-Access Cards

18.5. Smart Cards

18.6. Who Can You Trust?: Kohnfelder's Certificates

18.7. X.509 Certificates

18.8. The Secure Socket Layer (SSL)

18.9. Making a Secure Credit Card Payment on the Web

Chapter 19. Cryptographic Patents

19.1. What is a Patent?

19.2. Patentability of Ideas

19.3. The Format of a Patent

19.4. Patentable versus Nonpatentable Subjects

19.5. Infringement

19.6. The Role of Patents in Cryptography

19.7. U.S. Patent 3,543,904

19.8. U.S. Patent 4,200,770

19.9. U.S. Patent 4,218,582

19.10. U.S. Patent 4,405,829

19.11. PKS/RSADSI Litigation

19.12. Leon Stambler

Index