Making, Breaking Codes
Introduction to Cryptology
Published on 11. October 2000
Book
Hardback
544 pages
978-0-13-030369-1 (ISBN)
Description
For courses in Cryptography, Cryptology, and Applications of Number Theory and Abstract Algebra.
This is the only undergraduate text to explain fundamental ideas of classical and modern cryptography, and provide the essential background in number theory, abstract algebra, and probability-with surveys of relevant parts of complexity theory. A level of linear algebra sophistication is assumed in the reader. A user-friendly, down-to-earth tone gives students concretely motivated introductions to all topics.
This is the only undergraduate text to explain fundamental ideas of classical and modern cryptography, and provide the essential background in number theory, abstract algebra, and probability-with surveys of relevant parts of complexity theory. A level of linear algebra sophistication is assumed in the reader. A user-friendly, down-to-earth tone gives students concretely motivated introductions to all topics.
More details
Other editions
New editions
Book
10/2011
2nd Edition
Pearson
€53.22
Article exhausted; check for reprint
Previous edition
Book
10/2011
2nd Edition
Pearson
€53.22
Article exhausted; check for reprint
Content
Introduction.
1. Simple Ciphers.
The Shift Cipher. Reduction/Division Algorithm. The One-Time Pad. The Affine Cipher.
2. Probability.
Counting. Basic Ideas. Statistics of English. Attack on the Affine Cipher.
3. Permutations.
Cryptograms: Substitutions. Anagrams: Transpositions. Permutations. Shuffles. Block Interleavers.
4. A Serious Cipher.
The Vigenere Cipher. LCMs and GCDs. Kasiski Attack. Expected Values. Friedman Attack.
5. More Probability.
Generating Functions. Variance, Standard Deviation. Chebycheff's Inequality. Law of Large Numbers.
6. Modern Symmetric Ciphers.
Design Goals. Data Encryption Standard. Advanced Encryption Standard.
7. The Integers.
Divisibility. Unique Factorization. Euclidean Algorithm. Multiplicative Inverses. Computing Inverses. Equivalence Relations. The Integers mod m. Primitive Roots, Discrete Logs.
8. The Hill Cipher.
Hill Cipher Operation. Hill Cipher Attacks.
9. Complexity.
Big-Oh/Little-Oh Notation. Bit Operations. Probabilistic Algorithms. Comlexity. Subexponential Algorithms. Kolmogorov Complexity. Linear Complexity. Worst-Case versus Expected.
10. Public-Key Ciphers.
Trapdoors. The RSA Cipher. Diffie-Hellman Key Exchange. ElGamal Cipher. Knapsack Ciphers. NTRU Cipher. Arithmetica Key Exchange. Quantum Cryptography. U.S. Export Regulations.
11. Prime Numbers.
Euclid's Theorem. Prime Number Theorem. Primes in Sequences. Chebycheff's Theorem. Sharpest Asymptotics. Riemann Hypothesis.
12. Roots Mod p .
Fermat's Little Theorem. Factoring Special Expressions. Mersenne Numbers. More Examples. Exponentiation Algorithm. Square Roots mod p. Higher Roots mod p.
13. Roots Mod Composites.
Sun Ze's Theorem. Special Systems. Composite Moduli. Hensel's Lemma. Square-Root Oracles. Euler's Theorem. Facts about Primitive Roots. Euler's Criterion.
14. Weakly Multiplicativity.
Weak Multiplicativity. Arithmetic Convolutions. Moebius Inversion.
15. Quadratic Reciprocity.
Square Roots. Quadratic Symbols. Multiplicative Property. Quadratic Reciprocity. Fast Computation.
16. Pseudoprimes.
Fermat Pseudoprimes. Non-Prime Pseudoprimes. Euler Pseudoprimes. Solovay-Strassen Test. Strong Pseudoprimes. Miller-Rabin Test.
17. Groups.
Groups. Subgroups. Langrange's Theorem. Index of a Subgroup. Laws of Exponents. Cyclic Subgroups. Euler's Theorem. Exponents of Groups.
18. Sketches of Protocols.
Basic Public-Key Protocol. Diffie-Hellman Key Exchange. Secret Sharing. Oblivious Transfer. Zero-Knowledge Proofs. Authentication. e-Money, e-Commerce.
19. Rings, Fields, Polynomials.
Rings, Fields. Divisibility. Polynomial Rings. Euclidean Algorithm. Euclidean Rings.
20. Cyclotomic Polynomials.
Characteristics. Multiple Factors. Cyclotomic Polynomials. Primitive Roots. Primitive Roots mod p. Prime Powers. Counting Primitive Roots. Non-Existence. Search Algorithm.
21. Random Number Generators.
Fake One-Time Pads. Period of a pRNG. Congruential Generators. Feedback Shift Generators. Blum-Blum-Shub Generator. Naor-Reingold Generator. Periods of LCGs. Primitive Polynomials. Periods of LFSRs. Examples of Primitives. Testing for Primitivity.
22. More on Groups.
Group Homomorphisms. Finite Cyclic Groups. Infinite Cyclic Groups. Roots and Powers in Groups. Square Root Algorithm.
23. Pseudoprimality Proofs.
Lambda Function. Carmichael Numbers. Euler Witnesses. Strong Witnesses.
24. Factorization Attacks.
Pollard's Rho Method. Pollard's p-1 Method. Pocklington-Lehmer Criterion. Strong Primes. Primality Certificates.
25. Modern Factorization Attacks.
Gaussian Elimination. Random Squares Factoring. Dixon's Algorithm. Non-Sieving Quadratic Sieve. The Quadratic Sieve. Other Improvements.
26. Finite Fields.
Making Finite Fields. Examples of Field Extensions. Addition mod P. Multiplication mod P. Multiplicative Inverses mod P.
27. Discrete Logs.
Baby-Step Giant-Step. Pollard's Rho Method. The Index Calculus.
28. Elliptic Curves.
Abstract Discrete Logarithms. Discrete Log Ciphers. Elliptic Curves. Points at Infinity. Projective Elliptic Curves.
29. More on Finite Fields.
Ideals in Commutative Rings. Ring Homomorphisms. Quotient Rings. Maximal Ideals and Fields. More on Field Extensions. Frobenius Automorphism. Counting Irreducibles. Counting Primitives.
Appendices.
Sets and Functions. Searching, Sorting. Vectors. Matrices. Stirling's Formula.
Tables.
Factorizations under 600. Primes below 10,000. Primitive Roots under 100.
Bibliography.
Answers to Selected Exercises.
Index.
1. Simple Ciphers.
The Shift Cipher. Reduction/Division Algorithm. The One-Time Pad. The Affine Cipher.
2. Probability.
Counting. Basic Ideas. Statistics of English. Attack on the Affine Cipher.
3. Permutations.
Cryptograms: Substitutions. Anagrams: Transpositions. Permutations. Shuffles. Block Interleavers.
4. A Serious Cipher.
The Vigenere Cipher. LCMs and GCDs. Kasiski Attack. Expected Values. Friedman Attack.
5. More Probability.
Generating Functions. Variance, Standard Deviation. Chebycheff's Inequality. Law of Large Numbers.
6. Modern Symmetric Ciphers.
Design Goals. Data Encryption Standard. Advanced Encryption Standard.
7. The Integers.
Divisibility. Unique Factorization. Euclidean Algorithm. Multiplicative Inverses. Computing Inverses. Equivalence Relations. The Integers mod m. Primitive Roots, Discrete Logs.
8. The Hill Cipher.
Hill Cipher Operation. Hill Cipher Attacks.
9. Complexity.
Big-Oh/Little-Oh Notation. Bit Operations. Probabilistic Algorithms. Comlexity. Subexponential Algorithms. Kolmogorov Complexity. Linear Complexity. Worst-Case versus Expected.
10. Public-Key Ciphers.
Trapdoors. The RSA Cipher. Diffie-Hellman Key Exchange. ElGamal Cipher. Knapsack Ciphers. NTRU Cipher. Arithmetica Key Exchange. Quantum Cryptography. U.S. Export Regulations.
11. Prime Numbers.
Euclid's Theorem. Prime Number Theorem. Primes in Sequences. Chebycheff's Theorem. Sharpest Asymptotics. Riemann Hypothesis.
12. Roots Mod p .
Fermat's Little Theorem. Factoring Special Expressions. Mersenne Numbers. More Examples. Exponentiation Algorithm. Square Roots mod p. Higher Roots mod p.
13. Roots Mod Composites.
Sun Ze's Theorem. Special Systems. Composite Moduli. Hensel's Lemma. Square-Root Oracles. Euler's Theorem. Facts about Primitive Roots. Euler's Criterion.
14. Weakly Multiplicativity.
Weak Multiplicativity. Arithmetic Convolutions. Moebius Inversion.
15. Quadratic Reciprocity.
Square Roots. Quadratic Symbols. Multiplicative Property. Quadratic Reciprocity. Fast Computation.
16. Pseudoprimes.
Fermat Pseudoprimes. Non-Prime Pseudoprimes. Euler Pseudoprimes. Solovay-Strassen Test. Strong Pseudoprimes. Miller-Rabin Test.
17. Groups.
Groups. Subgroups. Langrange's Theorem. Index of a Subgroup. Laws of Exponents. Cyclic Subgroups. Euler's Theorem. Exponents of Groups.
18. Sketches of Protocols.
Basic Public-Key Protocol. Diffie-Hellman Key Exchange. Secret Sharing. Oblivious Transfer. Zero-Knowledge Proofs. Authentication. e-Money, e-Commerce.
19. Rings, Fields, Polynomials.
Rings, Fields. Divisibility. Polynomial Rings. Euclidean Algorithm. Euclidean Rings.
20. Cyclotomic Polynomials.
Characteristics. Multiple Factors. Cyclotomic Polynomials. Primitive Roots. Primitive Roots mod p. Prime Powers. Counting Primitive Roots. Non-Existence. Search Algorithm.
21. Random Number Generators.
Fake One-Time Pads. Period of a pRNG. Congruential Generators. Feedback Shift Generators. Blum-Blum-Shub Generator. Naor-Reingold Generator. Periods of LCGs. Primitive Polynomials. Periods of LFSRs. Examples of Primitives. Testing for Primitivity.
22. More on Groups.
Group Homomorphisms. Finite Cyclic Groups. Infinite Cyclic Groups. Roots and Powers in Groups. Square Root Algorithm.
23. Pseudoprimality Proofs.
Lambda Function. Carmichael Numbers. Euler Witnesses. Strong Witnesses.
24. Factorization Attacks.
Pollard's Rho Method. Pollard's p-1 Method. Pocklington-Lehmer Criterion. Strong Primes. Primality Certificates.
25. Modern Factorization Attacks.
Gaussian Elimination. Random Squares Factoring. Dixon's Algorithm. Non-Sieving Quadratic Sieve. The Quadratic Sieve. Other Improvements.
26. Finite Fields.
Making Finite Fields. Examples of Field Extensions. Addition mod P. Multiplication mod P. Multiplicative Inverses mod P.
27. Discrete Logs.
Baby-Step Giant-Step. Pollard's Rho Method. The Index Calculus.
28. Elliptic Curves.
Abstract Discrete Logarithms. Discrete Log Ciphers. Elliptic Curves. Points at Infinity. Projective Elliptic Curves.
29. More on Finite Fields.
Ideals in Commutative Rings. Ring Homomorphisms. Quotient Rings. Maximal Ideals and Fields. More on Field Extensions. Frobenius Automorphism. Counting Irreducibles. Counting Primitives.
Appendices.
Sets and Functions. Searching, Sorting. Vectors. Matrices. Stirling's Formula.
Tables.
Factorizations under 600. Primes below 10,000. Primitive Roots under 100.
Bibliography.
Answers to Selected Exercises.
Index.