Cryptography has been employed in war and diplomacy from the time of Julius Caesar. In our Internet age, cryptography's most widespread application may be for commerce, from protecting the security of electronic transfers to guarding communication from industrial espionage. This accessible introduction for undergraduates explains the cryptographic protocols for achieving privacy of communication and the use of digital signatures for certifying the validity, integrity, and origin of a message, document, or program. Rather than offering a how-to on configuring web browsers and e-mail programs, the author provides a guide to the principles and elementary mathematics underlying modern cryptography, giving readers a look under the hood for security techniques and the reasons they are thought to be secure.

Preface page ix

Acknowledgments xiii

1 Introduction 1

1.1 Encryption and decryption

1.2 Channels, secure and insecure 2

1.3 Security through obscurity 5

1.4 The alternative: The Kerckhoffs Doctrine 6

1.5 A taxonomy of cryptography 7

1.6 Attacks on cryptosystems 9

1.7 Problems 11

2 Modular Arithmetic 12

2.1 The Caesar cypher 12

2.2 The number circle 13

2.3 Modular arithmetic in daily life 13

2.4 Congruences 14

2.5 Another example: Congruences modulo 10 15

2.6 Substituting using congruences 16

2.7 Representatives and remainder 20

2.8 Problems 23

3 The Addition Cypher, an Insecure Block Cypher 26

3.1 The addition cypher 27

3.2 Block cyphers 27

3.3 Attacks on the addition cypher 29

3.4 Attacks on any block cypher that uses ECB mode 31

3.5 Problems 31

4 Functions 32

4.1 η1e basics 32

4.2 lnvertibility 34

4.3 Functions from modular arithmetic 37

4.4 Function notation 40

4.5 Uses of functions 41

4.6 A two-input function: The encryption function for the generalized Caesar cypher 42

4.7 Specialization：Turning a two-input function into a one-input function 43

4.8 Problems 44

5 Probability Theory 49

5.1 Outcomes of an experiment 49

5.2 Probabilities of outcomes 49

5.3 Plotting a probability distribution 50

5.4 Probabilities of sets of outcomes 51

5.5 Summary so far 51

5.6 Uniform distributions 52

5.7 Random variables 53

5.8 Problems 56

6 Perfect Secrecy and Perfectly Secure Cryptosystems 62

6.1 What does an eavesdropper learn from seeing a cyphertext? 62

6.2 Evaluation of cryptosystems 65

6.3 Perfect secrecy versus unique decryptability 70

6.4 A brief history of perfect secrecy 70

6.5 The drawback of perfectly secret cryptosystems 73

6.6 Problems 74

7 Number Theory 82

7.1 Divisibility 82

7.2 Relative primality 82

7.3 Prime numbers 83

7.4 Prime factorization 83

7.5 Euler's phi function cp(x) 84

7.6 Exponentiation 85

7.7 Euler's Theorem 86

7.8 Problems 86

8 Euclid'S Algorithm 89

8.1 The measuring puzzle 89

8.2 Finding a modular multipl icative inverse by solving a measuring puzzle 91

8.3 Euclid 's algorithm 93

8.4 The backward part of Euclid's algorithm 96

8.5 The EuclidCards 98

8.6 What Euclid's algorithm teaches us 103

8.7 Problems 104

9 Some Uses of Perfect Secrecy 106

9.1 Secret-sharing and perfect secrecy 106

9.2 Threshold secret-sharing 107

9.3 Message authent ication codes 111

9.4 Problems 112

10 Computational Problems, Easy and Hard 118

10.1 Computational problems 118

10.2 Algorithms 119

10.3 Predicting how many computer steps are needed by an algorithm 121

10.4 Fast algorithms and slow algorith ms, easy problems and hard problems 122

10.5 Problem s 123

11 Modular Exponentiation , Modular Logarithm, and One-Way Functions 129

11.1 Modular logarithms 129

11.2 Application of one-way functions to password security 133

11.3 Application of one-way functions to logging in: s/key 135

11.4 (Mis) application of one-way functions to commitment 137

11.5 Problems 140

12 Diffie and Hellman 's Exponential-Key-Agreement Protocol 143

12.1 Motivation 143

12.2 Background 143

12.3 The protocol 144

12.4 Security 145

12.5 Eve in the middle 145

12.6 Problems 146

13 Computationally Secure Single-Key Cryptosystems 147

13.1 Secure block cyphers in the real world 147

13.2 Cypher block chaining 148

13.3 The exponentiation cypher 150

13.4 How to find a big prime 152

13.5 Problems 153

14 Public-Key Cryptosystems and Digital Signatures 157

14.1 Public-key cryptosystems 157

14.2 El Gamal 'scryptosystem 158

14.3 More remarks about the El Gamal cryptosystem 159

14.4 Public-key cryptography in practice 160

14.5 Signatures 161

14.6 Trapdoor one-way functions and their use in public-key encryption and digital signatures 162

14.7 The RSA trapdoor one-way function 163

14.8 The RSA public-key cryptosystem 163

14.9 The RSA digital signature scheme 163

14.10 Message digest functions 164

14.11 Use of message digest functions in commitment 165

14.12 Problems 165

Further Reading 171

Index 173

中科院文献情报中心