Hoffstein J., Pipher J., Silverman J.H. An Introduction to Mathematical Cryptography

Springer, 2008. — 532 p. — (Undergraduate Texts in Mathematics). — ISBN: 978-0-387-77993-5. e-ISBN: 978-0-387-77994-2.The creation of public key cryptography by Diffie and Hellman in 1976 and the subsequent invention of the RSA public key cryptosystem by Rivest, Shamir, and Adleman in 1978 are watershed events in the long history of secret communications. It is hard to overestimate the importance of public key cryptosystems and their associated digital signature schemes in the modern world of computers and the Internet. This book provides an introduction to the theory of public key cryptography and to the mathematical ideas underlying that theory.Public key cryptography draws on many areas of mathematics, including number theory, abstract algebra, probability, and information theory. Each of these topics is introduced and developed in sufficient detail so that this book provides a self-contained course for the beginning student. The only prerequisite is a first course in linear algebra. On the other hand, students with stronger mathematical backgrounds can move directly to cryptographic applications and still have time for advanced topics such as elliptic curve pairings and lattice-reduction algorithms.
Among the many facets of modern cryptography, this book chooses to concentrate primarily on public key cryptosystems and digital signature schemes. This allows for an in-depth development of the necessary mathematics required for both the construction of these schemes and an analysis of their security. The reader who masters the material in this book will not only be well prepared for further study in cryptography, but will have acquired a real understanding of the underlying mathematical principles on which modern cryptography is based.
Topics covered in this book include Diffie-Hellman key exchange, discrete logarithm based cryptosystems, the RSA cryptosystem, primality testing, factorization algorithms, probability theory, information theory, collision algorithms, elliptic curves, elliptic curve cryptography, pairing-based cryptography, lattices, lattice-based cryptography, the NTRU cryptosystem, and digital signatures. A final chapter very briefly describes some of the many other aspects of modern cryptography (hash functions, pseudorandom number generators, zero-knowledge proofs, digital cash, AES, …) and serves to point the reader toward areas for further study.An Introduction to Cryptography
Simple substitution ciphers
Divisibility and greatest common divisors
Modular arithmetic
Prime numbers, unique factorization, and finite fields
Powers and primitive roots in finite fields
Cryptography before the computer age
Symmetric and asymmetric ciphers
ExercisesDiscrete Logarithms and Diffie–Hellman
The birth of public key cryptography
The discrete logarithm problem
Diffie–Hellman key exchange
The ElGamal public key cryptosystem
An overview of the theory of groups
How hard is the discrete logarithm problem?
A collision algorithm for the DLP
The Chinese remainder theorem
The Pohlig–Hellman algorithm
Rings, quotients, polynomials, and finite fields
ExercisesInteger Factorization and RSA
Euler’s formula and roots modulo pq
The RSA public key cryptosystem
Implementation and security issues
Primality testing
Pollard’s p - 1 factorization algorithm
ExercisesInteger Factorization and RSA
Euler’s formula and roots modulo pq
The RSA public key cryptosystem
Implementation and security issues
Primality testing
Pollard’s p - 1 factorization algorithm
Factorization via difference of squares
Smooth numbers and sieves
The index calculus and discrete logarithms
Quadratic residues and quadratic reciprocity
Probabilistic encryption
ExercisesCombinatorics, Probability, and Information Theory
Basic principles of counting
The Vigen`ere cipher
Probability theory
Collision algorithms and meet-in-the-middle attacks
Pollard’s - method
Information theory
Complexity Theory and P versus NP
ExercisesElliptic Curves and Cryptography
Elliptic curves
Elliptic curves over finite fields
The elliptic curve discrete logarithm problem
Elliptic curve cryptography
The evolution of public key cryptography
Lenstra’s elliptic curve factorization algorithm
Elliptic curves over F 2 and over F 2k
Bilinear pairings on elliptic curves
TheWeil pairing over fields of prime power order
Applications of the Weil pairing
ExercisesLattices and Cryptography
A congruential public key cryptosystem
Subset-sum problems and knapsack cryptosystems
A brief review of vector spaces
Lattices: Basic definitions and properties
Short vectors in lattices
Babai’s algorithm
Cryptosystems based on hard lattice problems
The GGH public key cryptosystem
Convolution polynomial rings
The NTRU public key cryptosystem
NTRU as a lattice cryptosystem
Lattice reduction algorithms
Applications of LLL to cryptanalysis
ExercisesDigital Signatures
What is a digital signature?
RSA digital signatures
ElGamal digital signatures and DSA
GGH lattice-based digital signatures
NTRU digital signatures
ExercisesAdditional Topics in Cryptography
Hash functions
Random numbers and pseudorandom number generators
Zero-knowledge proofs
Secret sharing schemes
Identification schemes
Padding schemes and the random Oracle model
Building protocols from cryptographic primitives
Hyperelliptic curve cryptography
Quantum computing
Modern symmetric cryptosystems: DES and AESList of Notation

Index