A Classical Introduction to Cryptography Applications for Communications SecurityPDF电子书下载

1 Prehistory of Cryptography 1

1.1 Foundations of Conventional Cryptography 1

1.1.1 The Origins of Cryptography 1

1.1.2 Key Words 2

1.1.3 Transpositions，Substitutions，and Secret Keys 4

1.1.4 Vernam Cipher 7

1.1.5 Enigma：Toward Industrial Cryptography 8

1.2 Roots of Modern Cryptography 10

1.2.1 Cryptographic Problems：The Fundamental Trilogy 10

1.2.2 Assumptions of Modern Cryptography 11

1.2.3 Adversarial Models 12

1.2.4 Cryptography from Various Perspectives 13

1.2.5 Methodology 15

1.3 The Shannon Theory of Secrecy 15

1.3.1 Secrecy of Communication 15

1.3.2 Entropy 17

1.3.3 Perfect Secrecy 18

1.3.4 Product Ciphers 19

1.4 Exercises 19

2 Conventional Cryptography 21

2.1 The Data Encryption Standard （DES） 22

2.2 DES Modes of Operation 25

2.2.1 Electronic Code Book （ECB） 25

2.2.2 Cipher Block Chaining （CBC） 26

2.2.3 Output Feedback （OFB） 27

2.2.4 Cipher Feedback （CFB） 29

2.2.5 Counter Mode （CTR） 30

2.3 Multiple Encryption 30

2.3.1 Double Mode 30

2.3.2 Triple Mode 31

2.4 An Application of DES：UNIX Passwords 31

2.5 Classical Cipher Skeletons 32

2.5.1 Feistel Schemes 32

2.5.2 Lai-Massey Scheme 33

2.5.3 Substitution-Permutation Network 36

2.6 Other Block Cipher Examples 37

2.6.1 FOX：A Lai-Massey Scheme 37

2.6.2 CS-CIPHER：A Substitution-Permutation Network 40

2.7 The Advanced Encryption Standard （AES） 42

2.8 Stream Ciphers 46

2.8.1 Stream Ciphers versus Block Ciphers 46

2.8.2 RC4 46

2.8.3 A5/1：GSM Encryption 48

2.8.4 E0：Bluetooth Encryption 50

2.9 Brute Force Attacks 51

2.9.1 Exhaustive Search 52

2.9.2 Dictionary Attack 53

2.9.3 Codebook Attack 54

2.9.4 Time-Memory Tradeoffs 54

2.9.5 Meet-in-the-Middle Attack 59

2.10 Exercises 60

3 Dedicated Conventional Cryptographic Primitives 63

3.1 Cryptographic Hashing 63

3.1.1 Usage 63

3.1.2 Threat Models 64

3.1.3 From Compression to Hashing 65

3.1.4 Example of MD5 66

3.1.5 Examples of SHA and SHA-1 67

3.2 The Birthday Paradox 70

3.3 A Dedicated Attack on MD4 74

3.4 Message Authentication Codes 78

3.4.1 Usage 78

3.4.2 Threat Model 79

3.4.3 MAC from Block Ciphers：CBC-MAC 80

3.4.4 Analysis of CBC-MAC 82

3.4.5 MAC from Stream Ciphers 86

3.4.6 MAC from Hash Functions：HMAC 88

3.4.7 An Authenticated Mode of Operation 90

3.5 Cryptographic Pseudorandom Generators 92

3.5.1 Usage and Threat Model 92

3.5.2 Congruential Pseudorandom Generator 92

3.5.3 Practical Examples 93

3.6 Exercises 95

4 Conventional Security Analysis 97

4.1 Differential Cryptanalysis 97

4.2 LinearCryptanalysis 103

4.3 Classical Security Strengthening 111

4.3.1 Nonlinearities 111

4.3.2 Characteristics and Markov Ciphers 112

4.3.3 Theoretical Differential and Linear Cryptanalysis 114

4.3.4 Ad hoc Construction 120

4.4 Modern Security Analysis 123

4.4.1 Distinguishability Security Model 123

4.4.2 The Luby-Rackoff Result 125

4.4.3 Decorrelation 126

4.5 Exercises 132

5 Security Protocols with Conventional Cryptography 135

5.1 Password Access Control 135

5.1.1 UNIX Passwords 136

5.1.2 Basic Access Control in HTTP 136

5.1.3 PAP Access Control in PPP 137

5.2 Challenge-Response Protocols 137

5.2.1 Digest Access Control in HTTP 138

5.2.2 CHAP Access Control in PPP 140

5.3 One-Time Password 140

5.3.1 Lamport Scheme 140

5.3.2 S/Key and OTP 141

5.4 Key Distribution 142

5.4.1 The Needham-Schroeder Authentication Protocol 142

5.4.2 Kerberos 143

5.4.3 Merkle Puzzles 145

5.5 Authentication Chains 145

5.5.1 Merkle Tree 145

5.5.2 Timestamps and Notary 147

5.6 Wireless Communication：Two Case Studies 148

5.6.1 The GSM Network 148

5.6.2 The Bluetooth Network 150

5.7 Exercises 153

6 Algorithmic Algebra 155

6.1 Basic Group Theory 155

6.1.1 Basic Set Theory 155

6.1.2 Groups 157

6.1.3 Generating a Group，Comparing Groups 158

6.1.4 Building New Groups 159

6.1.5 Fundamentals on Groups 159

6.2 The Ring Zn 160

6.2.1 Rings 160

6.2.2 Definition of Zn 161

6.2.3 Additions，Multiplications，Inversion 162

6.2.4 The Multiplicative Group Z*n 166

6.2.5 Exponentiation 167

6.2.6 Zmn：The Chinese Remainder Theorem 167

6.3 The Finite Field Zp 169

6.3.1 Basic Properties of Zp 169

6.3.2 Quadratic Residues 170

6.4 Finite Fields 172

6.5 Elliptic Curves over Finite Fields 173

6.5.1 Characteristic p ＞ 3 173

6.5.2 Characteristic Two 176

6.5.3 General Results 177

6.6 Exercises 178

7 Algorithmic Number Theory 181

7.1 Primality 181

7.1.1 Fermat Test 181

7.1.2 Carmichael Numbers 182

7.1.3 Solovay-Strassen Test 184

7.1.4 Miller-Rabin Test 187

7.1.5 Analysis of the Miller-Rabin Test 189

7.1.6 Prime Number Generation 189

7.2 Factorization 190

7.2.1 Pollard Rho Method 190

7.2.2 Pollard p - 1 Method 192

7.2.3 The Elliptic Curves Method （ECM） 194

7.2.4 Fermat Factorization and Factor Bases 196

7.2.5 The Quadratic Sieve 197

7.2.6 Factorization Nowadays 199

7.2.7 Factorization Tomorrow 199

7.3 Computing Orders in Groups 201

7.3.1 Finding the Group Exponent 201

7.3.2 Computing Element Orders in Groups 202

7.4 Discrete Logarithm 203

7.4.1 Pollard Rho Method 204

7.4.2 Shanks Baby Steps - Giant Steps Algorithm 204

7.4.3 Pohlig-Hellman Algorithm 205

7.4.4 Factor Base and Index Calculus Algorithm 210

7.5 Exercises 211

8 Elements of Complexity Theory 215

8.1 Formal Computation 215

8.1.1 Formal Languages and Regular Expressions 215

8.1.2 Finite Automata 216

8.1.3 Beyond Finite Automata Capabilities 218

8.1.4 Turing Machines 218

8.2 Ability Frontiers 220

8.2.1 Standard Computational Models 220

8.2.2 Beyond Computability 220

8.2.3 Decisional Problems and Decidability 221

8.3 Complexity Reduction 222

8.3.1 Asymptotic Time Complexity 222

8.3.2 Complexity Classes P，NP，co-NP 223

8.3.3 Intractability 224

8.3.4 Oracles and Turing Reduction 225

8.4 Exercises 226

9 Public-Key Cryptography 229

9.1 Diffie-Hellman 229

9.1.1 Public-Key Cryptosystems 230

9.1.2 The Diffie-Hellman Key Agreement Protocol 231

9.2 Experiment with NP-Completeness 234

9.2.1 Knapsack Problem 235

9.2.2 The Merkle-Hellman Cryptosystem 235

9.3 Rivest-Shamir-Adleman （RSA） 236

9.3.1 Plain RSA Cryptosystem 236

9.3.2 RSA Standards 240

9.3.3 Attacks on Broadcast Encryption with Low Exponent 241

9.3.4 Attacks on Low Exponent 241

9.3.5 Side Channel Attacks 241

9.3.6 Bit Security of RSA 243

9.3.7 Back to the Encryption Security Assumptions 244

9.3.8 RSA-OAEP 246

9.4 ElGamal Encryption 248

9.5 Exercises 250

10 Digital Signature 253

10.1 Digital Signature Schemes 253

10.2 RSA Signature 255

10.2.1 From Public-Key Cryptosystem to Digital Signature 255

10.2.2 On the Plain RSA Signature 256

10.2.3 ISO/IEC 9796 257

10.2.4 Attack on the ISO/IEC 9796 Signature Scheme 259

10.2.5 PKCS#1 260

10.3 ElGamal Signature Family 260

10.3.1 ElGamal Signature 260

10.3.2 The Bleichenbacher Attack against the ElGamal Signature 262

10.3.3 Schnorr Signature 263

10.3.4 The Digital Signature Standard （DSS） 264

10.3.5 ECDSA 264

10.3.6 Pointcheval-Vaudenay Signature 266

10.4 Toward Provable Security for Digital Signatures 266

10.4.1 From Interactive Proofs to Signatures 266

10.4.2 Security in the Random Oracle Model 270

10.5 Exercises 274

11 Cryptographic Protocols 277

11.1 Zero-Knowledge 277

11.1.1 Notion of Zero-Knowledge 277

11.1.2 The Basic Fiat-Shamir Protocol 278

11.1.3 The Feige-Fiat-Shamir Protocol 280

11.2 SecretSharing 282

11.2.1 The Shamir Threshold Scheme 283

11.2.2 Perfect Secret Sharing Schemes 284

11.2.3 Access Structure of Perfect Secret Sharing Schemes 285

11.2.4 The Benaloh-Leichter Secret Sharing Scheme 286

11.3 Special Purpose Digital Signatures 287

11.3.1 Undeniable Signature 288

11.3.2 Other Special Purpose Digital Signatures 291

11.4 Other Protocols 292

11.5 Exercises 293

12 From Cryptography to Communication Security 295

12.1 Certificates 296

12.2 SSH：Secure Shell 297

12.2.1 Principles of SSH 298

12.2.2 SSH2 Key Exchange and Authentication 299

12.3 SSL：Secure Socket Layer 300

12.3.1 Handshake 301

12.3.2 Cipher Suites 302

12.3.3 Record Protocol 304

12.3.4 Stream Cipher 304

12.3.5 Block Cipher 304

12.3.6 Master Key Exchange 305

12.3.7 Key Derivation 306

12.4 PGP：Pretty Good Privacy 307

12.4.1 Security for Individuals 308

12.4.2 Public-Key Management 310

12.4.3 Security Weaknesses 310

12.5 Exercises 311

Further Readings 313

Bibliography 315

Index 329