Handbook of Applied Cryptography

This book is intended as a reference for professional cryptographers, presenting thetechniques and algorithms of greatest interest to the current practitioner, along with the supporting motivation and background material. It also provides a comprehensive source from which to learn cryptography, serving both students and instructors. In addition, the rigorous treatment, breadth, and extensive bibliographic material should make it an important reference for research professionals.The goal was to assimilate the existing cryptographic knowledge of industrial interest into one consistent, self-contained volume accessible to engineers in practice, to computer scientists and mathematicians in academia, and to motivated non-specialists with a strong desire to learn cryptography. Such a task is beyond the scope of each of the following: research papers, which by nature focus on narrow topics using very specialized (and often non-standard) terminology; survey papers, which typically address, at most, a small number of major topics at a high level; and (regretably also) most books, due to the fact that many book authors lack either practical experience or familiarity with the research literature or both. Our intent was to provide a detailed presentation of those areas of cryptography which we have found to be of greatest practical utility in our own industrial experience, while maintaining a sufficiently formal approach to be suitable both as a trustworthy reference for those whose primary interest is further research, and to provide a solid foundation for students and others first learning the subject. Title......Page 1 forward......Page 2 preface......Page 4 Contents......Page 10 1.1 Introduction......Page 19 1.2 Information Security......Page 20 1.3 Functions......Page 24 1.4 Terminology......Page 29 1.5 Symmetric-key Encryption......Page 33 1.6 Digital Signatures......Page 40 1.7 Authentication......Page 42 1.8 Public-key cryptography......Page 43 1.10 Protocols......Page 51 1.11 Key Management......Page 53 1.12 Random Numbers......Page 57 1.13 Security Attacks......Page 59 1.14 References......Page 63 2. Math Background......Page 67 2.1 Probability Theory......Page 68 2.2 Information Theory......Page 74 2.3 Complexity Theory......Page 75 2.4 Number Theory......Page 81 2.5 Abstract Algebra......Page 93 2.6 Finite Fields......Page 98 2.7 References......Page 103 3.1 Introduction......Page 105 3.2 Integer Factorization......Page 107 3.3 RSA Problem......Page 116 3.5 Square Roots......Page 117 3.6 Discrete Logs......Page 121 3.7 Diffie-Hellman......Page 131 3.9 Computing Bits......Page 132 3.10 Subset Sum......Page 135 3.11 Factoring Polynomials......Page 140 3.12 References......Page 143 4.1 Introduction......Page 151 4.2 Primality Tests......Page 153 4.3 Proving Primality......Page 160 4.4 Generating Primes......Page 163 4.5 Irreducible Polynomials......Page 172 4.6 Generators......Page 178 4.7 References......Page 183 5. Random Numbers......Page 187 6. Stream Ciphers......Page 209 7. Block Ciphers......Page 241 8. Public-Key Encryption......Page 301 9. Hash Functions......Page 338 10. Authentication......Page 401 11. Digital Signatures......Page 441 12. Key Protocols......Page 505 13. Key Management......Page 558 14. Efficient Algorithms......Page 606 15. Patents & Standards......Page 650 A.1 Asiacrypt Proceedings......Page 677 A.2 Crypto Proceedings......Page 681 A.3 Eurocrypt Proceedings......Page 698 A.4 Fast Encryption Proceedings......Page 712 A.5 Journal of Cryptology......Page 714 References......Page 717 Index......Page 769 Title 1 forward 2 preface 4 Contents 10 1. Overview 19 1.1 Introduction 19 1.2 Information Security 20 1.3 Functions 24 1.4 Terminology 29 1.5 Symmetric-key Encryption 33 1.6 Digital Signatures 40 1.7 Authentication 42 1.8 Public-key cryptography 43 1.9 Hash Functions 51 1.10 Protocols 51 1.11 Key Management 53 1.12 Random Numbers 57 1.13 Security Attacks 59 1.14 References 63 2. Math Background 67 2.1 Probability Theory 68 2.2 Information Theory 74 2.3 Complexity Theory 75 2.4 Number Theory 81 2.5 Abstract Algebra 93 2.6 Finite Fields 98 2.7 References 103 3. Number-Theory Problems 105 3.1 Introduction 105 3.2 Integer Factorization 107 3.3 RSA Problem 116 3.4 Quadratic Residuosity 117 3.5 Square Roots 117 3.6 Discrete Logs 121 3.7 Diffie-Hellman 131 3.8 Composite Moduli 132 3.9 Computing Bits 132 3.10 Subset Sum 135 3.11 Factoring Polynomials 140 3.12 References 143 4. Prime Number Issues 151 4.1 Introduction 151 4.2 Primality Tests 153 4.3 Proving Primality 160 4.4 Generating Primes 163 4.5 Irreducible Polynomials 172 4.6 Generators 178 4.7 References 183 5. Random Numbers 187 6. Stream Ciphers 209 7. Block Ciphers 241 8. Public-Key Encryption 301 9. Hash Functions 338 10. Authentication 401 11. Digital Signatures 441 12. Key Protocols 505 13. Key Management 558 14. Efficient Algorithms 606 15. Patents & Standards 650 Bibliography 677 A.1 Asiacrypt Proceedings 677 A.2 Crypto Proceedings 681 A.3 Eurocrypt Proceedings 698 A.4 Fast Encryption Proceedings 712 A.5 Journal of Cryptology 714 References 717 Index 769