Introduction to Cryptography/ Johannes A. Buchmann.

1 Integers -- 1.1 Basics -- 1.2 Divisibility -- 1.3 Representation of Integers -- 1.4 O- and ?-Notation -- 1.5 Cost of Addition, Multiplication, and Division with Remainder -- 1.6 Polynomial Time -- 1.7 Greatest Common Divisor -- 1.8 Euclidean Algorithm -- 1.9 Extended Euclidean Algorithm -- 1.10 Analysis of the Extended Euclidean Algorithm -- 1.11 Factoring into Primes -- 1.12 Exercises -- 2 Congruences and Residue Class Rings -- 2.1 Congruences -- 2.2 Semigroups -- 2.3 Groups -- 2.4 Residue Class Rings -- 2.5 Fields -- 2.6 Division in the Residue Class Ring -- 2.7 Analysis of Operations in the Residue Class Ring -- 2.8 Multiplicative Group of Residues -- 2.9 Order of Group Elements -- 2.10 Subgroups -- 2.11 Fermat's Little Theorem -- 2.12 Fast Exponentiation -- 2.13 Fast Evaluation of Power Products -- 2.14 Computation of Element Orders -- 2.15 The Chinese Remainder Theorem -- 2.16 Decomposition of the Residue Class Ring -- 2.17 A Formula for the Euler ?-Function -- 2.18 Polynomials -- 2.19 Polynomials over Fields -- 2.20 Structure of the Unit Group of Finite Fields -- 2.21 Structure of the Multiplicative Group of Residues mod a Prime Number -- 2.22 Exercises -- 3 Encryption -- 3.1 Encryption Schemes -- 3.2 Symmetric and Asymmetric Cryptosystems -- 3.3 Cryptanalysis -- 3.4 Alphabets and Words -- 3.5 Permutations -- 3.6 Block Ciphers -- 3.7 Multiple Encryption -- 3.8 Use of Block Ciphers -- 3.9 Stream Ciphers -- 3.10 Affine Cipher -- 3.11 Matrices and Linear Maps -- 3.12 Affine Linear Block Ciphers -- 3.13 Vigenère, Hill, and Permutation Ciphers -- 3.14 Cryptanalysis of Affine Linear Block Ciphers -- 3.15 Exercises -- 4 Probability and Perfect Secrecy -- 4.1 Probability -- 4.2 Conditional Probability -- 4.3 Birthday Paradox -- 4.4 Perfect Secrecy -- 4.5 Vernam One-Time Pad -- 4.6 Random Numbers -- 4.7 Pseudorandom Numbers -- 4.8 Exercises -- 5 DES -- 5.1 Feistel Ciphers -- 5.2 DES Algorithm -- 5.3 An Example -- 5.4 Security of DES -- 5.5 Exercises -- 6 Prime Number Generation -- 6.1 Trial Division -- 6.2 Fermat Test -- 6.3 Carmichael Numbers -- 6.4 Miller-Rabin Test -- 6.5 Random Primes -- 6.6 Exercises -- 7 Public-Key Encryption -- 7.1 Idea -- 7.2 RSA Cryptosystem -- 7.3 Rabin Encryption -- 7.4 Diffie-Hellman Key Exchange -- 7.5 ElGamal Encryption -- 7.6 Exercises -- 8 Factoring -- 8.1 Trial Division -- 8.2 p - 1 Method -- 8.3 Quadratic Sieve -- 8.4 Analysis of the Quadratic Sieve -- 8.5 Efficiency of Other Factoring Algorithms -- 8.6 Exercises -- 9 Discrete Logarithms -- 9.1 DL Problem -- 9.2 Enumeration -- 9.3 Shanks Baby-Step Giant-Step Algorithm -- 9.4 Pollard ?-Algorithm -- 9.5 Pohlig-Hellman Algorithm -- 9.6 Index Calculus -- 9.7 Other Algorithms -- 9.8 Generalization of the Index Calculus Algorithm -- 9.9 Exercises -- 10 Cryptographic Hash Functions -- 10.1 Hash Functions and Compression Functions -- 10.2 Birthday Attack -- 10.3 Compression Functions from Encryption Functions -- 10.4 Hash Functions from Compression Functions -- 10.5 Efficient Hash Functions -- 10.6 An Arithmetic Compression Function -- 10.7 Message Authentication Codes -- 10.8 Exercises -- 11 Digital Signatures -- 11.1 Idea -- 11.2 RSA Signatures -- 11.3 Signatures from Public-Key Systems -- 11.4 ElGamal Signature -- 11.5 Digital Signature Algorithm (DSA) -- 11.6 Exercises -- 12 Other Groups -- 12.1 Finite Fields -- 12.2 Elliptic Curves -- 12.3 Quadratic Forms -- 12.4 Exercises -- 13 Identification -- 13.1 Passwords -- 13.2 One-Time Passwords -- 13.3 Challenge-Response Identification -- 13.4 Exercises -- 14 Public-Key Infrastructures -- 14.1 Personal Security Environments -- 14.2 Certification Authorities -- 14.3 Certificate Chains -- References -- Solutions to the Exercises.