Категории

Handbook of Applied Cryptography

Сумата се прибавя директно в кошницата

38.00лв

Описание

Table of Contents

List of Tables xv

List of Figures xix

Foreword by R.L. Rivest xxi

Preface xxiii

1 Overview of Cryptography 1

1.1 Introduction 1

1.2 Information security and cryptography 2

1.3 Background on functions 6

1.3.1 Functions (1-1, one-way, trapdoor one-way) 6

1.3.2 Permutations 10

1.3.3 Involutions 10

1.4 Basic terminology and concepts 11

1.5 Symmetric-key encryption 15

1.5.1 Overview of block ciphers and stream ciphers 15

1.5.2 Substitution ciphers and transposition ciphers 17

1.5.3 Composition of ciphers 19

1.5.4 Stream ciphers 20

1.5.5 The key space 21

1.6 Digital signatures 22

1.7 Authentication and identification 24

1.7.1 Identification 24

1.7.2 Data origin authentication 25

1.8 Public-key cryptography 25

1.8.1 Public-key encryption 25

1.8.2 The necessity of authentication in public-key systems 27

1.8.3 Digital signatures from reversible public-key encryption 28

1.8.4 Symmetric-key vs. public-key cryptography 31

1.9 Hash functions 33

1.10 Protocols and mechanisms 33

1.11 Key establishment, management, and certification 35

1.11.1 Key management through symmetric-key techniques 36

1.11.2 Key management through public-key techniques 37

1.11.3 Trusted third parties and public-key certificates 39

1.12 Pseudorandom numbers and sequences 39

1.13 Classes of attacks and security models 41

1.13.1 Attacks on encryption schemes 41

1.13.2 Attacks on protocols 42

1.13.3 Models for evaluating security 42

1.13.4 Perspective for computational security 44

1.14 Notes and further references 45

2 Mathematical Background 49

2.1 Probability theory 50

2.1.1 Basic definitions 50

2.1.2 Conditional probability 51

2.1.3 Random variables 51

2.1.4 Binomial distribution 52

2.1.5 Birthday attacks 53

2.1.6 Random mappings 54

2.2 Information theory 56

2.2.1 Entropy 56

2.2.2 Mutual information 57

2.3 Complexity theory 57

2.3.1 Basic definitions 57

2.3.2 Asymptotic notation 58

2.3.3 Complexity classes 59

2.3.4 Randomized algorithms 62

2.4 Number theory 63

2.4.1 The integers 63

2.4.2 Algorithms in Ъ 66

2.4.3 The integers modulo n 67

2.4.4 Algorithms in 7Ln 71

2.4.5 The Legendre and Jacobi symbols 72

2.4.6 Blum integers 74

2.5 Abstract algebra 75

2.5.1 Groups 75

2.5.2 Rings 76

2.5.3 Fields 77

2.5.4 Polynomial rings 78

2.5.5 Vector spaces 79

2.6 Finite fields 80

2.6.1 Basic properties 80

2.6.2 The Euclidean algorithm for polynomials 81

2.6.3 Arithmetic of polynomials 83

2.7 Notes and further references 85 3

3 Number-Theoretic Reference Problems 87

3.1 Introduction and overview 87

3.2 The integer factorization problem 89

3.2.1 Trial division 90

3.2.2 Pollard’s rho factoring algorithm 91

3.2.3 Pollard’s p — 1 factoring algorithm 92

3.2.4 Elliptic curve factoring 94

3.2.5 Random square factoring methods 94

3.2.6 Quadratic sieve factoring 95

3.2.7 Number field sieve factoring 98

3.3 The RSA problem 98

3.4 The quadratic residuosity problem 99

3.5 Computing square roots in 7Ln 99

3.5.1 Case (i): n prime 100

3.5.2 Case (ii): n composite 101

3.6 The discrete logarithm problem 103

3.6.1 Exhaustive search 104

3.6.2 Baby-step giant-step algorithm 104

3.6.3 Pollard’s rho algorithm for logarithms 106

3.6.4 Pohlig-Hellmanalgorithm 107

3.6.5 Index-calculus algorithm 109

3.6.6 Discrete logarithm problem in subgroups of 7L* 113

3.7 The Diffie-Hellmanproblem 113

3.8 Composite moduli 114

3.9 Computing individual bits 114

3.9.1 The discrete logarithm problem in Z* — individual bits 116

3.9.2 The RSA problem — individual bits 116

3.9.3 The Rabin problem — individual bits 117

3.10 The subset sum problem 117

3.10.1 The T3-lattice basis reduction algorithm 118

3.10.2 Solving subset sum problems of low density 120

3.10.3 Simultaneous diophantine approximation 121

3.11 Factoring polynomials over finite fields 122

3.11.1 Square-free factorization 123

3.11.2 Berlekamp’ sQ -matrix algorithm 124

3.12 Notes and further references 125

4 Public-Key Parameters 133

4.1 Introduction 133

4.1.1 Generating large prime numbers naively 134

4.1.2 Distribution of prime numbers 134

4.2 Probabilistic primality tests 135

4.2.1 Fermat’s test 136

4.2.2 Solovay-Strassen test 137

4.2.3 Miller-Rabin test 138

4.2.4 Comparison: Fermat, Solovay-Strassen, and Miller-Rabin 140

4.3 (True) Primality tests 142

4.3.1 TestingMersenne numbers 142

4.3.2 Primality testing using the factorization of n — 1 143

4.3.3 Jacobi sum test 144

4.3.4 Tests using elliptic curves 145

4.4 Prime number generation 145

4.4.1 Random search for probable primes 145

4.4.2 Strong primes 149

4.4.3 NIST method for generating DSA primes 150

4.4.4 Constructive techniques for provable primes 152

4.5 Irreducible polynomials over 7LV 154

4.5.1 Irreducible polynomials 154

4.5.2 Irreducible trinomials 157

4.5.3 Primitive polynomials 157

4.6 Generators and elements of high order 160

4.6.1 Selecting a prime p and generator of Z* 164

4.7 Notes and further references 165

5 Pseudorandom Bits and Sequences 169

5.1 Introduction 169

5.1.1 Background and Classification 170

5.2 Random bit generation 171

5.3 Pseudorandom bit generation 173

5.3.1 ANSI X9.17 generator 173

5.3.2 FIPS 186 generator 174

5.4 Statistical tests 175

5.4.1 The normal and chi-square distributions 176

5.4.2 Hypothesis testing 179

5.4.3 Golomb’s randomness postulates 180

5.4.4 Five basic tests 181

5.4.5 Maurer’s universal statistical test 183

5.5 Cryptographically secure pseudorandom bit generation 185

5.5.1 RSA pseudorandom bit generator 185

5.5.2 Blum-Blum-Shub pseudorandom bit generator 186

5.6 Notes and further references 187

6 Stream Ciphers 191

6.1 Introduction 191

6.1.1 Classification 192

6.2 Feedback shift registers 195

6.2.1 Linear feedback shift registers 195

6.2.2 Linear complexity 198

6.2.3 Berlekamp-Massey algorithm 200

6.2.4 Nonlinear feedback shift registers 202

6.3 Stream ciphers based on LFSRs 203

6.3.1 Nonlinear combination generators 205

6.3.2 Nonlinear filter generators 208

6.3.3 Clock-controlled generators 209

6.4 Other stream ciphers 212

6.4.1 SEAL 213

6.5 Notes and further references 216 7

7 Block Ciphers 223

7.1 Introduction and overview 223

7.2 Background and general concepts 224

7.2.1 Introduction to block ciphers 224

7.2.2 Modes of operation 228

7.2.3 Exhaustive key search and multiple encryption 233

7.3 Classical ciphers and historical development 237

7.3.1 Transposition ciphers (background) 238

7.3.2 Substitution ciphers (background) 238

7.3.3 Polyalphabetic substitutions and Vigenere ciphers (historical) . . . 241

7.3.4 Polyalphabetic cipher machines and rotors (historical) 242

7.3.5 Cryptanalysis of classical ciphers (historical) 245

7.4 DES 250

7.4.1 Product ciphers and Feistel ciphers 250

7.4.2 DES algorithm 252

7.4.3 DES properties and strength 256

7.5 FEAL 259

7.6 IDEA 263

7.7 SAFER, RC5, and other block ciphers 266

7.7.1 SAFER 266

7.7.2 RC5 269

7.7.3 Other block ciphers 270

7.8 Notes and further references 271

8 Public-Key Encryption 283

8.1 Introduction 283

8.1.1 Basic principles 284

8.2 RSA public-key encryption 285

8.2.1 Description 286

8.2.2 Security of RSA 287

8.2.3 RSA encryption in practice 290

8.3 Rabin public-key encryption 292

8.4 ElGamal public-key encryption 294

8.4.1 Basic ElGamal encryption 294

8.4.2 Generalized ElGamal encryption 297

8.5 McEliece public-key encryption 298

8.6 Knapsack public-key encryption 300

8.6.1 Merkle-Hellman knapsack encryption 300

8.6.2 Chor-Rivest knapsack encryption 302

8.7 Probabilistic public-key encryption 306

8.7.1 Goldwasser-Micali probabilistic encryption 307

8.7.2 Blum-Goldwasser probabilistic encryption 308

8.7.3 Plaintext-aware encryption 311

8.8 Notes and further references 312

9 Hash Functions and Data Integrity 321

9.1 Introduction 321

9.2 Classification and framework 322

9.2.1 General classification 322

9.2.2 Basic properties and definitions 323

9.2.3 Hash properties required for specific applications 327

9.2.4 One-way functions and compression functions 327

9.2.5 Relationships between properties 329

9.2.6 Other hash function properties and applications 330

9.3 Basic constructions and general results 332

9.3.1 General model for iterated hash functions 332

9.3.2 General constructions and extensions 333

9.3.3 Formatting and initialization details 334

9.3.4 Security objectives and basic attacks 335

9.3.5 Bitsizes required for practical security 337

9.4 Unkeyed hash functions (MDCs) 338

9.4.1 Hash functions based on block ciphers 338

9.4.2 Customized hash functions based on MD4 343

9.4.3 Hash functions based on modular arithmetic 351

9.5 Keyed hash functions (MACs) 352

9.5.1 MACs based on block ciphers 353