Introduction to Cryptography

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 PseudorandomNumbers.- 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 theExercises.