Algebraic aspects of cryptography 论文

摘要

1. Cryptography.- 1. Early History.- 2. The Idea of Public Key Cryptography.- 3. The RSA Cryptosystem.- 4. Diffie-Hellman and the Digital Signature Algorithm.- 5. Secret Sharing, Coin Flipping, and Time Spent on Homework.- 6. Passwords, Signatures, and Ciphers.- 7. Practical Cryptosystems and Useful Impractical Ones.- Exercises.- 2. Complexity of Computations.- 1. The Big-O Notation.- Exercises.- 2. Length of Numbers.- Exercises.- 3. Time Estimates.- Exercises.- 4. P, NP, and NP-Completeness.- Exercises.- 5. Promise Problems.- 6. Randomized Algorithms and Complexity Classes.- Exercises.- 7. Some Other Complexity Classes.- Exercises.- 3. Algebra.- 1. Fields.- Exercises.- 2. Finite Fields.- Exercises.- 3. The Euclidean Algorithm for Polynomials.- Exercises.- 4. Polynomial Rings.- Exercises.- 5. Grobner Bases.- Exercises.- 4. Hidden Monomial Cryptosystems.- 1. The Imai-Matsumoto System.- Exercises.- 2. Patarin's Little Dragon.- Exercises.- 3. Systems That Might Be More Secure.- Exercises.- 5. Combinatorial-Algebraic Cryptosystems.- 1. History.- 2. Irrelevance of Brassard's Theorem.- Exercises.- 3. Concrete Combinatorial-Algebraic Systems.- Exercises.- 4. The Basic Computational Algebra Problem.- Exercises.- 5. Cryptographic Version of Ideal Membership.- 6. Linear Algebra Attacks.- 7. Designing a Secure System.- 6. Elliptic and Hyperelliptic Cryptosystems.- 1. Elliptic Curves.- Exercises.- 2. Elliptic Curve Cryptosystems.- Exercises.- 3. Elliptic Curve Analogues of Classical Number Theory Problems.- Exercises.- 4. Cultural Background: Conjectures on Elliptic Curves and Surprising Relations with Other Problems.- 5. Hyperelliptic Curves.- Exercises.- 6. Hyperelliptic Cryptosystems.- Exercises.- 1. Basic Definitions and Properties.- 2. Polynomial and Rational Functions.- 3. Zeros and Poles.- 4. Divisors.- 5. Representing Semi-Reduced Divisors.- 6. Reduced Divisors.- 7. Adding Reduced Divisors.- Exercises.- Answers to Exercises.