The Mathematics of Encryption. An Elementary Introduction (True PDF, low-resolution figures)

How quickly can you compute the remainder when dividing $109837^{97}$ by 120143? Why would you even want to compute this? And what does this have to do with cryptography? Modern cryptography lies at the intersection of mathematics and computer sciences, involving number theory, algebra, computational complexity, fast algorithms, and even quantum mechanics. Many people think of codes in terms of spies, but in the information age, highly mathematical codes are used every day by almost everyone, whether at the bank ATM, at the grocery checkout, or at the keyboard when you access your email or purchase products online. This book provides a historical and mathematical tour of cryptography, from classical ciphers to quantum cryptography. The authors introduce just enough mathematics to explore modern encryption methods, with nothing more than basic algebra and some elementary number theory being necessary. Complete expositions are given of the classical ciphers and the attacks on them, along with a detailed description of the famous Enigma system. The public-key system RSA is described, including a complete mathematical proof that it works. Numerous related topics are covered, such as efficiencies of algorithms, detecting and correcting errors, primality testing and digital signatures. The topics and exposition are carefully chosen to highlight mathematical thinking and problem solving. Each chapter ends with a collection of problems, ranging from straightforward applications to more challenging problems that introduce advanced topics. Unlike many books in the field, this book is aimed at a general liberal arts student, but without losing mathematical completeness. Contents Preface Acknowledgments Chapter 1. Historical Introduction 1.1. Ancient Times 1.2. Cryptography During the Two World Wars 1.3. Postwar Cryptography, Computers, and Security 1.4. Summary 1.5. Problems Chapter 2. Classical Cryptology: Methods 2.1. Ancient Cryptography 2.2. Substitution Alphabet Ciphers 2.3. The Caesar Cipher 2.4. Modular Arithmetic 2.5. Number Theory Notation 2.6. The Affine Cipher 2.7. The Vigen`ere Cipher 2.8. The Permutation Cipher 2.9. The Hill Cipher 2.10. Summary 2.11. Problems Chapter 3. Enigma and Ultra 3.1. Setting the Stage 3.2. Some Counting 3.3. Enigma’s Security 3.4. Cracking the Enigma 3.5. Codes in World War II 3.6. Summary 3.7. Appendix: Proofs by Induction 3.8. Problems Chapter 4. Classical Cryptography: Attacks I 4.1. Breaking the Caesar Cipher 4.2. Function Preliminaries 4.3. Modular Arithmetic and the Affine Cipher 4.4. Breaking the Affine Cipher 4.5. The Substitution Alphabet Cipher 4.6. Frequency Analysis and the Vigen`ere Cipher 4.7. The Kasiski Test 4.8. Summary 4.9. Problems Chapter 5. Classical Cryptography: Attacks II 5.1. Breaking the Permutation Cipher 5.2. Breaking the Hill Cipher 5.3. Running Key Ciphers 5.4. One-Time Pads 5.5. Summary 5.6. Problems Chapter 6. Modern Symmetric Encryption 6.1. Binary Numbers and Message Streams 6.2. Linear Feedback Shift Registers 6.3. Known-Plaintext Attack on LFSR Stream Ciphers 6.4. LFSRsum 6.5. BabyCSS 6.6. Breaking BabyCSS 6.7. BabyBlock 6.8. Security of BabyBlock 6.9. Meet-in-the-Middle Attacks 6.10. Summary 6.11. Problems Chapter 7. Introduction to Public-Channel Cryptography 7.1. The Perfect Code Cryptography System 7.2. KidRSA 7.3. The Euclidean Algorithm 7.4. Binary Expansion and Fast Modular Exponentiation 7.5. Prime Numbers 7.6. Fermat’s little Theorem 7.7. Summary 7.8. Problems Chapter 8. Public-Channel Cryptography 8.1. RSA 8.2. RSA and Symmetric Encryption 8.3. Digital Signatures 8.4. Hash Functions 8.5. Diffie–Hellman Key Exchange 8.6. Why RSA Works 8.7. Summary 8.8. Problems Chapter 9. Error Detecting and Correcting Codes 9.1. Introduction 9.2. Error Detection and Correction Riddles 9.3. Definitions and Setup 9.4. Examples of Error Detecting Codes 9.5. Error Correcting Codes 9.6. More on the Hamming 9.7. From Parity to UPC Symbols 9.8. Summary and Further Topics 9.9. Problems Chapter 10. Modern Cryptography 10.1. Steganography—Messages You Don’t Know Exist 10.2. Steganography in the Computer Age 10.3. Quantum Cryptography 10.4. Cryptography and Terrorists at Home and Abroad 10.5. Summary 10.6. Problems Chapter 11. Primality Testing and Factorization 11.1. Introduction 11.2. Brute Force Factoring 11.3. Fermat’s Factoring Method 11.4. Monte Carlo Algorithms and F T Primality Test 11.5. Miller–Rabin Test 11.6. Agrawal–Kayal–Saxena Primality Test 11.7. Problems Chapter 12. Solutions to Selected Problems 12.1. Chapter 1: Historical Introduction 12.2. Chapter 2: Classical Cryptography: Methods 12.3. Chapter 3: Enigma and Ultra 12.4. Chapter 4: Classical Cryptography: Attacks I 12.5. Chapter 5: Classical Cryptography: Attacks II 12.6. Chapter 6: Modern Symmetric Encryption 12.7. Chapter 7: Introduction to Public-Channel Cryptography 12.8. Chapter 8: Public-Channel Cryptography 12.9. Chapter 9: Error Detecting and Correcting Codes 12.10. Chapter 10: Modern Cryptography 12.11. Chapter 11: Primality Testing and Factorization Bibliography Index How Quickly Can You Compute The Remainder When Dividing 10983797 By 120143? Why Would You Even Want To Compute This? And What Does This Have To Do With Cryptography? Modern Cryptography Lies At The Intersection Of Mathematics And Computer Sciences, Involving Number Theory, Algebra, Computational Complexity, Fast Algorithms, And Even Quantum Mechanics. Many People Think Of Codes In Terms Of Spies, But In The Information Age, Highly Mathematical Codes Are Used Every Day By Almost Everyone, Whether At The Bank Atm, At The Grocery Checkout, Or At The Keyboard When You Access Your Email Or Purchase Products Online. This Book Provides A Historical And Mathematical Tour Of Cryptography, From Classical Ciphers To Quantum Cryptography. The Authors Introduce Just Enough Mathematics To Explore Modern Encryption Methods, With Nothing More Than Basic Algebra And Some Elementary Number Theory Being Necessary. Complete Expositions Are Given Of The Classical Ciphers And The Attacks On Them, Along With A Detailed Description Of The Famous Enigma System. The Public-key System Rsa Is Described, Including A Complete Mathematical Proof That It Works. Numerous Related Topics Are Covered, Such As Efficiencies Of Algorithms, Detecting And Correcting Errors, Primality Testing And Digital Signatures. The Topics And Exposition Are Carefully Chosen To Highlight Mathematical Thinking And Problem Solving. Each Chapter Ends With A Collection Of Problems, Ranging From Straightforward Applications To More Challenging Problems That Introduce Advanced Topics. Unlike Many Books In The Field, This Book Is Aimed At A General Liberal Arts Student, But Without Losing Mathematical Completeness.--book Cover. Historical Introduction -- Classical Cryptology : Methods -- Enigma And Ultra -- Classical Cryptography : Attacks I -- Classical Cryptography : Attacks Ii -- Modern Symmetric Encryption -- Introduction To Public-channel Cryptography -- Public-channel Cryptography -- Error Detecting And Correcting Codes -- Modern Cryptography -- Primality Testing And Factorization -- Solutions To Selected Problems. Margaret Cozzens, Steven J. Miller. Includes Bibliographical References And Index.