An Introduction to Mathematical Cryptography

Höfundar: Jeffrey Hoffstein; Jill Pipher; Joseph H. Silverman (Útgáfa: 2)
An Introduction to Mathematical Cryptography

Kaup valmöguleikar

This self-contained introduction to modern cryptography emphasizes the mathematics behind the theory of public key cryptosystems and digital signature schemes. The book focuses on these key topics while developing the mathematical tools needed for the construction and security analysis of diverse cryptosystems. Only basic linear algebra is required of the reader; techniques from algebra, number theory, and probability are introduced and developed as required.

This text provides an ideal introduction for mathematics and computer science students to the mathematical foundations of modern cryptography. The book includes an extensive bibliography and index; supplementary materials are available online. The book covers a variety of topics that are considered central to mathematical cryptography. Key topics include: classical cryptographic constructions, such as Diffie–Hellmann key exchange, discrete logarithm-based cryptosystems, the RSA cryptosystem, anddigital signatures; fundamental mathematical tools for cryptography, including primality testing, factorization algorithms, probability theory, information theory, and collision algorithms; an in-depth treatment of important cryptographic innovations, such as elliptic curves, elliptic curve and pairing-based cryptography, lattices, lattice-based cryptography, and the NTRU cryptosystem.

The second edition of An Introduction to Mathematical Cryptography includes a significant revision of the material on digital signatures, including an earlier introduction to RSA, Elgamal, and DSA signatures, and new material on lattice-based signatures and rejection sampling. Many sections have been rewritten or expanded for clarity, especially in the chapters on information theory, elliptic curves, and lattices, and the chapter of additional topics has been expanded to include sections on digital cash and homomorphic encryption.

Nánar um bókina

Útgefandi
Springer Nature
ISBN
9781493917112
Print ISBN
9781493917105
Format
ePub
Útgáfa
2
Höfundar
Jeffrey Hoffstein; Jill Pipher; Joseph H. Silverman
Tungumál
English
Útgefið
2014-09-11
Prent takmörkun á líftíma
100
Prent takmörkun
2
Afritunar takmörkun
2

Kaflar

  • Undergraduate Texts in Mathematics
  • An Introduction to Mathematical Cryptography
  • Preface
  • Contents
  • 1. An Introduction to Cryptography
  • 1.1 Simple Substitution Ciphers
  • 1.1.1 Cryptanalysis of Simple Substitution Ciphers
  • 1.2 Divisibility and Greatest Common Divisors
  • 1.3 Modular Arithmetic
  • 1.3.1 Modular Arithmetic and Shift Ciphers
  • 1.3.2 The Fast Powering Algorithm
  • 1.4 Prime Numbers, Unique Factorization, and Finite Fields
  • 1.5 Powers and Primitive Roots in Finite Fields
  • 1.6 Cryptography Before the Computer Age
  • 1.7 Symmetric and Asymmetric Ciphers
  • 1.7.1 Symmetric Ciphers
  • 1.7.2 Encoding Schemes
  • 1.7.3 Symmetric Encryption of Encoded Blocks
  • 1.7.4 Examples of Symmetric Ciphers
  • 1.7.5 Random Bit Sequences and Symmetric Ciphers
  • 1.7.6 Asymmetric Ciphers Make a First Appearance
  • Exercises
  • 2. Discrete Logarithms and Diffie–Hellman
  • 2.1 The Birth of Public Key Cryptography
  • 2.2 The Discrete Logarithm Problem
  • 2.3 Diffie–Hellman Key Exchange
  • 2.4 The Elgamal Public Key Cryptosystem
  • 2.5 An Overview of the Theory of Groups
  • 2.6 How Hard Is the Discrete Logarithm Problem?
  • 2.7 A Collision Algorithm for the DLP
  • 2.8 The Chinese Remainder Theorem
  • 2.8.1 Solving Congruences with Composite Moduli
  • 2.9 The Pohlig–Hellman Algorithm
  • 2.10 Rings, Quotient Rings, Polynomial Rings, and Finite Fields
  • 2.10.1 An Overview of the Theory of Rings
  • 2.10.2 Divisibility and Quotient Rings
  • 2.10.3 Polynomial Rings and the Euclidean Algorithm
  • 2.10.4 Quotients of Polynomial Rings and Finite Fields of Prime Power Order
  • Exercises
  • 3. Integer Factorization and RSA
  • 3.1 Euler’s Formula and Roots Modulo pq
  • 3.2 The RSA Public Key Cryptosystem
  • 3.3 Implementation and Security Issues
  • 3.4 Primality Testing
  • 3.4.1 The Distribution of the Set of Primes
  • 3.4.2 Primality Proofs Versus Probabilistic Tests
  • 3.5 Pollard’s p − 1 Factorization Algorithm
  • 3.6 Factorization via Difference of Squares
  • 3.7 Smooth Numbers, Sieves, and Building Relations for Factorization
  • 3.7.1 Smooth Numbers
  • 3.7.2 The Quadratic Sieve
  • 3.7.3 The Number Field Sieve
  • 3.8 The Index Calculus Method for Computing Discrete Logarithms in
  • 3.9 Quadratic Residues and Quadratic Reciprocity
  • 3.10 Probabilistic Encryption and the Goldwasser–Micali Cryptosystem
  • 4. Digital Signatures
  • 4.1 What Is a Digital Signature?
  • 4.2 RSA Digital Signatures
  • 4.3 Elgamal Digital Signatures and DSA
  • Exercises
  • 5. Combinatorics, Probability, and Information Theory
  • 5.1 Basic Principles of Counting
  • 5.1.1 Permutations
  • 5.1.2 Combinations
  • 5.1.3 The Binomial Theorem
  • 5.2 The Vigenère Cipher
  • 5.2.1 Cryptanalysis of the Vigenère Cipher: Theory
  • 5.2.2 Cryptanalysis of the Vigenère Cipher: Practice
  • 5.3 Probability Theory
  • 5.3.1 Basic Concepts of Probability Theory
  • 5.3.2 Bayes’s Formula
  • 5.3.3 Monte Carlo Algorithms
  • 5.3.4 Random Variables
  • 5.3.5 Expected Value
  • 5.4 Collision Algorithms and Meet-in-the-Middle Attacks
  • 5.4.1 The Birthday Paradox
  • 5.4.2 A Collision Theorem
  • 5.4.3 A Discrete Logarithm Collision Algorithm
  • 5.5 Pollard’s Method
  • 5.5.1 Abstract Formulation of Pollard’s Method
  • 5.5.2 Discrete Logarithms via Pollard’s Method
  • 5.6 Information Theory
  • 5.6.1 Perfect Secrecy
  • 5.6.2 Entropy
  • 5.6.3 Redundancy and the Entropy of Natural Language
  • 5.6.4 The Algebra of Secrecy Systems
  • 5.7 Complexity Theory and Versus
  • 6. Elliptic Curves and Cryptography
  • 6.1 Elliptic Curves
  • 6.2 Elliptic Curves over Finite Fields
  • 6.3 The Elliptic Curve Discrete Logarithm Problem (ECDLP)
  • 6.3.1 The Double-and-Add Algorithm
  • 6.3.2 How Hard Is the ECDLP?
  • 6.4 Elliptic Curve Cryptography
  • 6.4.1 Elliptic Diffie–Hellman Key Exchange
  • 6.4.2 Elliptic Elgamal Public Key Cryptosystem
  • 6.4.3 Elliptic Curve Signatures
  • 6.5 The Evolution of Public Key Cryptography
  • 6.6 Lenstra’s Elliptic Curve Factorization Algorithm
  • 6.7 Elliptic Curves over and over
  • 6.8 Bilinear Pairings on Elliptic Curves
  • 6.8.1 Points of Finite Order on Elliptic Curves
  • 6.8.2 Rational Functions and Divisors on Elliptic Curves
  • 6.8.3 The Weil Pairing
  • 6.8.4 An Efficient Algorithm to Compute the Weil Pairing
  • 6.8.5 The Tate Pairing
  • 6.9 The Weil Pairing over Fields of Prime Power Order
  • 6.9.1 Embedding Degree and the MOV Algorithm
  • 6.9.2 Distortion Maps and a Modified Weil Pairing
  • 6.9.3 A Distortion Map on
  • 6.10 Applications of the Weil Pairing
  • 6.10.1 Tripartite Diffie–Hellman Key Exchange
  • 6.10.2 ID-Based Public Key Cryptosystems
  • Exercises
  • 7. Lattices and Cryptography
  • 7.1 A Congruential Public Key Cryptosystem
  • 7.2 Subset-Sum Problems and Knapsack Cryptosystems
  • 7.3 A Brief Review of Vector Spaces
  • 7.4 Lattices: Basic Definitions and Properties
  • 7.5 Short Vectors in Lattices
  • 7.5.1 The Shortest Vector Problem and the Closest Vector Problem
  • 7.5.2 Hermite’s Theorem and Minkowski’s Theorem
  • 7.5.3 The Gaussian Heuristic
  • 7.6 Babai’s Algorithm and Using a “Good” Basis to Solve apprCVP
  • 7.7 Cryptosystems Based on Hard Lattice Problems
  • 7.8 The GGH Public Key Cryptosystem
  • 7.9 Convolution Polynomial Rings
  • 7.10 The NTRU Public Key Cryptosystem
  • 7.10.1 NTRUEncrypt
  • 7.10.2 Mathematical Problems for NTRUEncrypt
  • 7.11 NTRUEncrypt as a Lattice Cryptosystem
  • 7.11.1 The NTRU Lattice
  • 7.11.2 Quantifying the Security of an NTRU Lattice
  • 7.12 Lattice-Based Digital Signature Schemes
  • 7.12.1 The GGH Digital Signature Scheme
  • 7.12.2 Transcript Analysis
  • 7.12.3 Rejection Sampling
  • 7.12.4 Rejection Sampling Applied to an Abstract Signature Scheme
  • 7.12.5 The NTRU Modular Lattice Signature Scheme
  • 7.13 Lattice Reduction Algorithms
  • 7.13.1 Gaussian Lattice Reduction in Dimension 2
  • 7.13.2 The LLL Lattice Reduction Algorithm
  • 7.13.3 Using LLL to Solve apprCVP
  • 7.13.4 Generalizations of LLL
  • 7.14 Applications of LLL to Cryptanalysis
  • 7.14.1 Congruential Cryptosystems
  • 7.14.2 Applying LLL to Knapsacks
  • 7.14.3 Applying LLL to GGH
  • 7.14.4 Applying LLL to NTRU
  • Exercises
  • 8. Additional Topics in Cryptography
  • 8.1 Hash Functions
  • 8.2 Random Numbers and Pseudorandom Number Generators
  • 8.3 Zero-Knowledge Proofs
  • 8.4 Secret Sharing Schemes
  • 8.5 Identification Schemes
  • 8.6 Padding Schemes, the Random Oracle Model, and Provable Security
  • 8.7 Building Protocols from Cryptographic Primitives
  • 8.8 Blind Digital Signatures, Digital Cash, and Bitcoin
  • 8.9 Homomorphic Encryption
  • 8.10 Hyperelliptic Curve Cryptography
  • 8.11 Quantum Computing
  • 8.12 Modern Symmetric Cryptosystems: DES and AES
  • List of Notation
  • References
  • Index