An Introduction to Cryptography - 2nd Edition - 2007下载

RICHARD A. MOLLIN 1 Mathematical Basics 1 1.1 Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Primes, Primality Testing, and Induction . . . . . . . . . . 6 1.3 An Introduction to Congruences . . . . . . . . . . . . . . . . 17 1.4 Euler, Fermat, and Wilson . . . . . . . . . . . . . . . . . . . 35 1.5 Primitive Roots . . . . . . . . . . . . . . . . . . . . . . . . . . 44 1.6 The Index Calculus and Power Residues . . . . . . . . . . 51 1.7 Legendre, Jacobi, & Quadratic Reciprocity . . . . . . . . . 58 1.8 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 2 Cryptographic Basics 79 2.1 Definitions and Illustrations . . . . . . . . . . . . . . . . . . 79 2.2 Classic Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 2.3 Stream Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . 109 2.4 LFSRs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 2.5 Modes of Operation . . . . . . . . . . . . . . . . . . . . . . . . 122 2.6 Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 3 DES and AES 131 3.1 S-DES and DES . . . . . . . . . . . . . . . . . . . . . . . . . . 131 3.2 AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 4 Public-Key Cryptography 157 4.1 The Ideas Behind PKC . . . . . . . . . . . . . . . . . . . . . 157 4.2 Digital Envelopes and PKCs . . . . . . . . . . . . . . . . . . 165 4.3 RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 4.4 ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 4.5 DSA — The DSS . . . . . . . . . . . . . . . . . . . . . . . . . 187 5 Primality Testing 189 5.1 True Primality Tests . . . . . . . . . . . . . . . . . . . . . . . 189 5.2 Probabilistic Primality Tests . . . . . . . . . . . . . . . . . . 198 vii © 2007 by Taylor & Francis Group, LLC viii 5.3 Recognizing Primes . . . . . . . . . . . . . . . . . . . . . . . . 204 6 Factoring 207 6.1 Classical Factorization Methods . . . . . . . . . . . . . . . . 207 6.2 The Continued Fraction Algorithm . . . . . . . . . . . . . . 211 6.3 Pollard’s Algorithms . . . . . . . . . . . . . . . . . . . . . . . 214 6.4 The Quadratic Sieve . . . . . . . . . . . . . . . . . . . . . . . 217 6.5 The Elliptic Curve Method (ECM) . . . . . . . . . . . . . . 220 7 Electronic Mail and Internet Security 223 7.1 History of the Internet and the WWW . . . . . . . . . . . 223 7.2 Pretty Good Privacy (PGP) . . . . . . . . . . . . . . . . . . 227 7.3 Protocol Layers and SSL . . . . . . . . . . . . . . . . . . . . . 241 7.4 Internetworking and Security — Firewalls . . . . . . . . . 250 7.5 Client–Server Model and Cookies . . . . . . . . . . . . . . . 259 8 Leading-Edge Applications 263 8.1 Login and Network Security . . . . . . . . . . . . . . . . . . 263 8.2 Viruses and Other Infections . . . . . . . . . . . . . . . . . . 273 8.3 Smart Cards . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 8.4 Biometrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 Appendix A: Fundamental Facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 Appendix B: Computer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . 325 Appendix C: The Rijndael S-Box . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 Appendix D: Knapsack Ciphers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .337 Appendix E: Silver-Pohlig-Hellman Algorithm . . . . . . . . . . . . . . 344 Appendix F: SHA-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .346 Appendix G: Radix-64 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 Appendix H: Quantum Cryptography. . . . . . . . . . . . . . . . . . . . . . . .352 Solutions to Odd-Numbered Exercises . . . . . . . . . . . . . . . . . . . . . . . 358 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377 About the Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413