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
