You are previewing Modern Cryptanalysis: Techniques for Advanced Code Breaking.
O'Reilly logo
Modern Cryptanalysis: Techniques for Advanced Code Breaking

Book Description

As an instructor at the University of Tulsa, Christopher Swenson could find no relevant text for teaching modern cryptanalysis-so he wrote his own. This is the first book that brings the study of cryptanalysis into the 21st century. Swenson provides a foundation in traditional cryptanalysis, examines ciphers based on number theory, explores block ciphers, and teaches the basis of all modern cryptanalysis: linear and differential cryptanalysis. This time-honored weapon of warfare has become a key piece of artillery in the battle for information security.

Table of Contents

  1. Copyright
  2. About the Author
  3. Credits
  4. Acknowledgments
  5. Introduction
    1. Concepts of Security
    2. Cryptology
    3. History of Cryptology
    4. Principles of Good Cryptography
    5. Conventions Used in This Book
    6. Book Contents
  6. 1. Simple Ciphers
    1. 1.1. Monoalphabetic Ciphers
    2. 1.2. Keying
      1. 1.2.1. Keyed Alphabets
      2. 1.2.2. ROT13
      3. 1.2.3. Klingon
    3. 1.3. Polyalphabetic Ciphers
      1. 1.3.1. Vigenère Tableau
    4. 1.4. Transposition Ciphers
      1. 1.4.1. Columnar Transpositions
      2. 1.4.2. Double Columnar Transpositions
    5. 1.5. Cryptanalysis
      1. 1.5.1. Breaking Monoalphabetic Ciphers
        1. 1.5.1.1. Frequency Analysis
        2. 1.5.1.2. Index of Coincidence
        3. 1.5.1.3. Other Issues
      2. 1.5.2. Breaking Polyalphabetic Ciphers
      3. 1.5.3. Breaking Columnar Transposition Ciphers
      4. 1.5.4. Breaking Double Columnar Transposition Ciphers
    6. 1.6. Summary
    7. 1.7. Exercises
  7. 2. Number Theoretical Ciphers
    1. 2.1. Probability
      1. 2.1.1. Permutations and Choices
      2. 2.1.2. Dependence
        1. 2.1.2.1. Fun with Poker
      3. 2.1.3. The Birthday Paradox
      4. 2.1.4. Cryptographic Hashes
    2. 2.2. Number Theory Refresher Course
      1. 2.2.1. Divisibility and Prime Numbers
      2. 2.2.2. Congruences
    3. 2.3. Algebra Refresher Course
      1. 2.3.1. Definitions
      2. 2.3.2. Finite Field Inverses
    4. 2.4. Factoring-Based Cryptography
      1. 2.4.1. The RSA Algorithm
    5. 2.5. Discrete Logarithm-Based Cryptography
      1. 2.5.1. The Diffie-Hellman Algorithm
    6. 2.6. Elliptic Curves
      1. 2.6.1. Addition of Points
      2. 2.6.2. Elliptic Curve Cryptography
      3. 2.6.3. Elliptic Curve Diffie-Hellman
    7. 2.7. Summary
    8. 2.8. Exercises
  8. 3. Factoring and Discrete Logarithms
    1. 3.1. Factorization
    2. 3.2. Algorithm Theory
      1. 3.2.1. Notation
      2. 3.2.2. A Crash Course in Python
    3. 3.3. Exponential Factoring Methods
      1. 3.3.1. Brute-Force
        1. 3.3.1.1. Analysis
      2. 3.3.2. Fermat's Difference of Squares
        1. 3.3.2.1. Analysis of Fermat's Difference of Squares
      3. 3.3.3. Pollard's ρ
        1. 3.3.3.1. Analysis of Pollard's ρ
      4. 3.3.4. Pollard's p – 1
        1. 3.3.4.1. Analysis of Pollard's p – 1
      5. 3.3.5. Square Forms Factorization
        1. 3.3.5.1. Analysis of SQUFOF
      6. 3.3.6. Elliptic Curve Factorization Method
        1. 3.3.6.1. Analysis of ECM
    4. 3.4. Subexponential Factoring Methods
      1. 3.4.1. Continued Fraction Factorization
        1. 3.4.1.1. Analysis of CFRAC
      2. 3.4.2. Sieving Methods
    5. 3.5. Discrete Logarithms
      1. 3.5.1. Brute-Force Methods
      2. 3.5.2. Baby-Step Giant-Step Method
        1. 3.5.2.1. Baby-Step Giant-Step Analysis
      3. 3.5.3. Pollard's ρ for Discrete Logarithms
        1. 3.5.3.1. Analysis of Pollard's ρ for Discrete Logarithms
      4. 3.5.4. Pollard's λ for Discrete Logarithms
        1. 3.5.4.1. Analysis of Pollard's λ
      5. 3.5.5. Index Calculus Method
    6. 3.6. Summary
    7. 3.7. Exercises
  9. 4. Block Ciphers
    1. 4.1. Operations on Bits, Bytes, Words
      1. 4.1.1. Operations
      2. 4.1.2. Code
    2. 4.2. Product Ciphers
    3. 4.3. Substitutions and Permutations
      1. 4.3.1. S-Box
      2. 4.3.2. P-Box
      3. 4.3.3. Shift Registers
    4. 4.4. Substitution–Permutation Network
      1. 4.4.1. EASY1 Cipher
        1. 4.4.1.1. Python Implementation
    5. 4.5. Feistel Structures
    6. 4.6. DES
      1. 4.6.1. DES Key Schedule
      2. 4.6.2. DES Round Function
      3. 4.6.3. Triple DES
      4. 4.6.4. DESX
    7. 4.7. FEAL
      1. 4.7.1. S-function
      2. 4.7.2. Key-Generating Function: fK
      3. 4.7.3. Round Function: f
      4. 4.7.4. Key Scheduling
    8. 4.8. Blowfish
      1. 4.8.1. Blowfish Key Schedule
      2. 4.8.2. Blowfish Algorithm
      3. 4.8.3. Blowfish Round Function
      4. 4.8.4. Notes on Blowfish
    9. 4.9. AES/Rijndael
      1. 4.9.1. Rijndael Encryption Algorithm
        1. 4.9.1.1. SubBytes
        2. 4.9.1.2. ShiftRows
        3. 4.9.1.3. MixColumns
        4. 4.9.1.4. AddRoundKey
      2. 4.9.2. Rijndael Decryption Algorithm
      3. 4.9.3. Key Expansion
      4. 4.9.4. Notes on Rijndael
    10. 4.10. Block Cipher Modes
      1. 4.10.1. Electronic Code Book
      2. 4.10.2. Cipher Block Chaining
      3. 4.10.3. Cipher Feedback
      4. 4.10.4. Output Feedback
      5. 4.10.5. Counter Mode
    11. 4.11. Skipjack
      1. 4.11.1. Skipjack Encryption Algorithm
      2. 4.11.2. Skipjack Decryption Algorithm
      3. 4.11.3. Permutations
    12. 4.12. Message Digests and Hashes
      1. 4.12.1. Checksums
      2. 4.12.2. Cyclic Redundancy Checks
      3. 4.12.3. MD5
      4. 4.12.4. SHA-1
    13. 4.13. Random Number Generators
      1. 4.13.1. Bias
      2. 4.13.2. Linear Congruential Random Number Generator
    14. 4.14. One-Time Pad
    15. 4.15. Summary
    16. 4.16. Exercises
  10. 5. General Cryptanalytic Methods
    1. 5.1. Brute-Force
    2. 5.2. Time–Space Trade-offs
      1. 5.2.1. Meet-in-the-Middle Attack
      2. 5.2.2. Hellman Time–Space Trade-off
      3. 5.2.3. Time–Space Trade-off Success
      4. 5.2.4. Flaws
      5. 5.2.5. Multi-Table Trade-off
      6. 5.2.6. Rivest's Distinguished Endpoints
    3. 5.3. Rainbow Tables
      1. 5.3.1. Advantages of Rainbow Tables
      2. 5.3.2. Microsoft LAN Manager Password Hash
    4. 5.4. Slide Attacks
      1. 5.4.1. Slide Attacks on Feistel Ciphers
      2. 5.4.2. Advanced Slide Attacks
    5. 5.5. Cryptanalysis of Hash Functions
    6. 5.6. Cryptanalysis of Random Number Generators
    7. 5.7. Summary
    8. 5.8. Exercises
  11. 6. Linear Cryptanalysis
    1. 6.1. Overview
    2. 6.2. Matsui's Algorithms
    3. 6.3. Linear Expressions for S-Boxes
    4. 6.4. Matsui's Piling-up Lemma
    5. 6.5. EASY1 Cipher
    6. 6.6. Linear Expressions and Key Recovery
    7. 6.7. Linear Cryptanalysis of DES
    8. 6.8. Multiple Linear Approximations
    9. 6.9. Finding Linear Expressions
    10. 6.10. Linear Cryptanalysis Code
    11. 6.11. Summary
    12. 6.12. Exercises
  12. 7. Differential Cryptanalysis
    1. 7.1. Overview
    2. 7.2. Notation
    3. 7.3. S-Box Differentials
    4. 7.4. Combining S-Box Characteristics
    5. 7.5. Key Derivation
    6. 7.6. Differential Cryptanalysis Code
    7. 7.7. Differential Cryptanalysis of Feistel Ciphers
      1. 7.7.1. Differential Cryptanalysis of FEAL
      2. 7.7.2. Differential Cryptanalysis of DES
    8. 7.8. Analysis
    9. 7.9. Differential-Linear Cryptanalysis
    10. 7.10. Conditional Characteristics
    11. 7.11. Higher-Order Differentials
    12. 7.12. Truncated Differentials
    13. 7.13. Impossible Differentials
    14. 7.14. Boomerang Attack
    15. 7.15. Interpolation Attack
    16. 7.16. Related-Key Attack
      1. 7.16.1. Related-Key Attack on GOST
      2. 7.16.2. Related-Key Attack on 3DES
    17. 7.17. Summary
    18. 7.18. Exercises