O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

A Course in Mathematical Cryptography

Book Description

Cryptography has become essential as bank transactions, credit card infor-mation, contracts, and sensitive medical information are sent through inse-cure channels. This book is concerned with the mathematical, especially algebraic, aspects of cryptography. It grew out of many courses presented by the authors over the past twenty years at various universities and covers a wide range of topics in mathematical cryptography. It is primarily geared towards graduate students and advanced undergraduates in mathematics and computer science, but may also be of interest to researchers in the area.

Besides the classical methods of symmetric and private key encryption, the book treats the mathematics of cryptographic protocols and several unique topics such as

  • Group-Based Cryptography
  • Gröbner Basis Methods in Cryptography
  • Lattice-Based Cryptography

Table of Contents

  1. Cover
  2. Title
  3. Copyright Page
  4. Preface
  5. Table of content
  6. 1  Basic Ideas of Cryptography
    1. 1.1   Mathematical Cryptography
    2. 1.2   Cryptography, Cryptanalysis and Cryptosystems
    3. 1.3   A Very Brief History of Cryptography
    4. 1.4   Encryption and Number Theory
    5. 1.5   Public Key Cryptography
    6. 1.6   Cryptosystems and the Key Space
    7. 1.7   Cryptographic Protocols
    8. 1.8   Exercises
  7. 2  Symmetric Key Cryptosystems
    1. 2.1   Mixed Encryption
    2. 2.2   Block Ciphers
    3. 2.3   Stream Ciphers
    4. 2.4   Feistel Networks, DES and AES
    5. 2.5   One-Way Functions and Trapdoors
    6. 2.6   Exercises
  8. 3  Cryptanalysis and Complexity
    1. 3.1   Cryptanalysis and Cryptanalytic Attacks
    2. 3.2   Statistical Methods
    3. 3.3   Cryptographic Security
    4. 3.3.1     Security Proofs
    5. 3.4   Perfect Security and the One-Time Pad
      1. 3.4.1     Vigenere Encryption and Polyalphabetic Ciphers
      2. 3.4.2     Breaking a Protocol
    6. 3.5   Complexity of Algorithms
    7. 3.6   Exercises
  9. 4  Cryptographic Protocols
    1. 4.1   Cryptographic Protocols
    2. 4.2   Cryptographic Hash Functions
    3. 4.3   Authentication Protocols
    4. 4.4   Digital Signatures
    5. 4.5   Secret Sharing Schemes
      1. 4.5.1     The Shamir Secret Sharing Scheme
      2. 4.5.2     Alternatives for Secret Sharing Protocols
      3. 4.5.3     Verifying Secret Sharing Protocols (VSS)
    6. 4.6   Zero-Knowledge Proofs
    7. 4.7   Exercises
  10. 5  Elementary Number Theoretic Techniques
    1. 5.1   Cryptography and Number Theory
    2. 5.2   Modular Arithmetic
    3. 5.3   Units and the Multiplicative Group Z*
    4. 5.4   The Field Zp and Finite Fields
    5. 5.5   Finite Abelian Groups
    6. 5.6   Cyclic Groups and Primitive Elements
    7. 5.7   The Chinese Remainder Theorem
    8. 5.8   Exercises
  11. 6  Some Number Theoretic Algorithms
    1. 6.1   Algorithms for Public Key Cryptography
    2. 6.2   Quadratic Residues and Square Roots
    3. 6.3   Modular Square Roots
    4. 6.4   Products of Two Primes
    5. 6.5   The Discrete Log Problem
      1. 6.5.1     Shank’s Baby Step Giant Step Algorithm (BSGS)
      2. 6.5.2     Pollard’s p-Algorithm
      3. 6.5.3     The Index Calculus Method
    6. 6.6   Primality Testing
      1. 6.6.1     Sieving Methods
      2. 6.6.2     Fermat’s Primality Testing
      3. 6.6.3     Pseudoprimes and Probabilistic Primality Testing
      4. 6.6.4     Miller-Rabin Primality Testing
      5. 6.6.5     Mersenne Primes and the Lucas-Lehmer Test
    7. 6.7   Exercises
  12. 7  Public Key Cryptography
    1. 7.1   Public Key Cryptography
    2. 7.2   Standard Model for Public Key Encryption
    3. 7.3   The Diffie-Hellman Key Exchange and Protocol
    4. 7.4   ElGamal Encryption
      1. 7.4.1     Generalizations of ElGamal
    5. 7.5   The RSA Algorithm and Protocol
      1. 7.5.1     The RSA Cryptosystem
      2. 7.5.2     RSA as a Block Cipher
      3. 7.5.3     Practical Implementation of RSA
      4. 7.5.4     Feasibility of the RSA Algorithm
      5. 7.5.5     Security of RSA
      6. 7.5.6     Cryptanalysis of RSA
    6. 7.6   Rabin Encryption
      1. 7.6.1     Quadratic residues and Rabin Encryption
      2. 7.6.2     The Rabin Cryptosystem
      3. 7.6.3     Security Equivalence of the Rabin Cryptosystem
    7. 7.7   Session Keys and Mixed Encryption
    8. 7.8   The RSA Signature Method
    9. 7.9   Exercises
  13. 8  Elliptic Curve Cryptography
    1. 8.1   The ElGamal and Elliptic Curve Encryption System
    2. 8.2   Elliptic Curves
      1. 8.2.1     Fields and Field Extensions
      2. 8.2.2     Elliptic Curves
      3. 8.2.3     Elliptic Curve Groups
      4. 8.2.4     The Order of an Elliptic Curve Group
      5. 8.2.5     Calculating Points in Elliptic Curve Groups
    3. 8.3   Elliptic Curve Cryptography
    4. 8.4   Cryptoanalysis of Elliptic Curve Cryptosystems
    5. 8.5   The MOV-Algorithm
    6. 8.6   The Elliptic Curve Digital Signature
    7. 8.7   Exercises
  14. 9  Basic Concepts from Group Theory
    1. 9.1   Groups and Group Theory
    2. 9.2   Cosets and Normal Subgroups
    3. 9.3   Examples of Groups
    4. 9.4   Generators and Group Presentations
    5. 9.5   Free Groups and Group Presentations
    6. 9.6   Group Presentations
      1. 9.6.1     The Modular Group
    7. 9.7   Presentations of Subgroups
    8. 9.8   Group Decision Problems
    9. 9.9   Group Amalgams
    10. 9.10      Exercises
  15. 10  Group Based Cryptography
    1. 10.1      Group Based Methods
    2. 10.2      The Magnus Method
      1. 10.2.1   The Wagner-Magyarik Method
    3. 10.3      Free Group Cryptosystems
      1. 10.3.1   An Implementation Within the Classical Modular Group
      2. 10.3.2   A Variation Using the Magnus Representation
    4. 10.4    Cryptographic Protocols Using Groups
    5. 10.5    Non-Abelian Digital Signatures
    6. 10.6    Password Security
      1. 10.6.1   The Strong Generic Free Group Property
      2. 10.6.2   Security Analysis of the Group Randomizer Protocols
      3. 10.6.3   Actual Implementation of a Group Randomizer System Protocol
    7. 10.7    A Secret Sharing Scheme
    8. 10.8    Exercises
  16. 11  Braid Group Cryptography
    1. 11.1    Cryptographic Platforms and Platform Groups
    2. 11.2    The Ko-Lee and AAG Protocols
      1. 11.2.1   The Ko-Lee Protocol
      2. 11.2.2   The Anshel-Anshel-Goldfeld Protocol
    3. 11.3    Some Other Group Based Cryptosystems
    4. 11.4    The Shamir Three-Pass
    5. 11.5    Hard Group Theoretic Properties
    6. 11.6    Braid Group Cryptography
    7. 11.7    The Braid Groups
      1. 11.7.1   The Artin Presentation
      2. 11.7.2   Normal Forms Within Bn
      3. 11.7.3   The Pure Braid Group for Bn
      4. 11.7.4   Linear Representations of Bn
    8. 11.8    Cryptanalysis of Braid Group Cryptosystems
      1. 11.8.1   Attacks on the Conjugacy Search Problem
      2. 11.8.2   Length Based Attacks
      3. 11.8.3   Representation Theoretic Attacks
      4. 11.8.4   Braid Group Security Summary
    9. 11.9    Some Other Braid Group Based Protocols
    10. 11.10    Exercises
  17. 12  Further Applications
    1. 12.1    Finitely Presented Groups and Cryptography
    2. 12.2    Group Theory for Access Control
    3. 12.3    Public Key Control Groups
    4. 12.4    Diophantine Control Security groups
    5. 12.5    The Social Security Control Groups
    6. 12.6    Further Extensions of Diffie-Hellman and RSA
    7. 12.7    Exercises
  18. 13  Commutative Grobner Basis Methods
    1. 13.1    Commutative Grobner Bases
    2. 13.2    Commutative Grobner Basis Cryptosystems
    3. 13.3    Algebraic Attacks Using Grobner Bases
      1. 13.3.1   The Grobner Basis Attack
      2. 13.3.2   The Integer Programming Attack
      3. 13.3.3   The SAT Attack
    4. 13.4    Exercises
  19. 14  Non-Commutative Grobner Basis Methods
    1. 14.1    Non-Commutative Grobner Bases
    2. 14.2    Elimination and its Applications
    3. 14.3    Grobner Bases of Modules
    4. 14.4    Non-Commutative GB Cryptosystems
    5. 14.5    Exercises
  20. 15  Lattice-Based Cryptography
    1. 15.1    Lattice-Based Cryptography
    2. 15.2    General Cryptoprimitives
    3. 15.3    Lattices and Their Properties
      1. 15.3.1   The Geometry of Numbers
    4. 15.4    Hard Lattice Problems
    5. 15.5    Lattice Reduction and Babai’s Algorithm
    6. 15.6    Main Lattice Based Cryptosystems
      1. 15.6.1   Ajtai’s Hash Function and Cryptosystem
      2. 15.6.2   The Ajtai-Dwork Cryptosystem
      3. 15.6.3   The GGH Cryptosystem
      4. 15.6.4   NTRU Cryptosystem
    7. 15.7    Security Proofs
    8. 15.8    Exercises
  21. Bibliography
  22. Index