Want a NOOK? Explore Now
Written by one of the developers of the technology, Hashing is both a historical document on the development of hashing and an analysis of the applications of hashing in a society increasingly concerned with security. The material in this book is based on courses taught by the author, and key points are reinforced in sample problems and an accompanying instructor s manual. Graduate students and researchers in mathematics, cryptography, and security will benefit from this overview of hashing and the complicated mathematics that it requires.
"Graduate students and researchers in mathematics, cryptography, and security will benefit from this overview of hashing and the complicated mathematics that it requires." (Forums Digital Media Net, 27 October 2010)
Preface
PART I MATHEMATICAL PRELIMINARIES 1
1 Counting 3
1.1 The Sum and Product Rules 4
1.2 Mathematical Induction 5
1.3 Factorial 6
1.4 Binomial Coefficients 8
1.5 Multinomial Coefficients 10
1.6 Permutations 10
1.7 Combinations 14
1.8 The Principle of Inclusion-Exclusion 17
1.9 Partitions 18
1.10 Relations 19
1.11 Inverse Relations 20
Appendix 1 Summations Involving Binomial Coefficients 21
2 Recurrence and Generating Functions 23
2.1 Recursions 23
2.2 Generating Functions 24
2.3 Linear Constant Coefficient Recursions 25
2.4 Solving Homogeneous LCCRs Using Generating Functions 26
2.5 The Catalan Recursion 30
2.6 The Umbral Calculus 31
2.7 Exponential Generating Functions 32
2.8 Partitions of a Set: The Bell and Stirling Numbers 33
2.9 Rouche's Theorem and the Lagrange's Inversion Formula 37
3 Asymptotic Analysis 40
3.1 Growth Notation for Sequences 40
3.2 Asymptotic Sequences and Expansions 42
3.3 Saddle Points 45
3.4 Laplace's Method 47
3.5 The Saddle Point Method 48
3.6 When Will the Saddle Point Method Work? 51
3.7 The Saddle Point Bounds 52
3.8 Examples of Saddle Point Analysis 54
4 Discrete Probability Theory 64
4.1 The Origins of Probability Theory 64
4.2 Chance Experiments, Sample Points, Spaces, and Events 64
4.3 Random Variables 66
4.4 Moments---Expectation and Variance 67
4.5 The Birthday Paradox 68
4.6 Conditional Probability and Independence 69
4.7 The Law of Large Numbers (LLN) 71
4.8 The Central Limit Theorem (CLT) 73
4.9 Random Processes and Markov Chains 73
5 Number Theory and Modern Algebra 77
5.1 Prime Numbers 77
5.2 Modular Arithmetic and the Euclidean Algorithm 78
5.3 Modular Multiplication 80
5.4 The Theorems of Fermat and Euler 81
5.5 Fields and Extension Fields 82
5.6 Factorization of Integers 86
5.7 Testing Primality 88
6 Basic Concepts of Cryptography 94
6.1 The Lexicon of Cryptography 94
6.2 Stream Ciphers 95
6.3 Block Ciphers 95
6.4 Secrecy Systems and Cryptanalysis 95
6.5 Symmetric and Two-Key Cryptographic Systems 97
6.6 The Appearance of Public Key Cryptographic systems 98
6.7 A Multitude of Keys 102
6.8 The RSA Cryptosystem 102
6.9 Does PKC Solve the Problem of Key Distribution? 105
6.10 Elliptic Groups Over the Reals 106
6.11 Elliptic Groups Over the Field Zm, 2 108
6.12 Elliptic Group Cryptosystems 110
6.13 The Menezes-Vanstone Elliptic Curve Cryptosystem 111
6.14 Super-Singular Elliptic Curves 112
PART II HASHING FOR STORAGE: DATA MANAGEMENT 117
7 Basic Concepts 119
7.1 Overview of the Records Management Problem 119
7.2 A Simple Storage Management Protocol: Plain Vanilla Chaining 120
7.3 Record-Management with Sorted Keys 122
8 Hash Functions 124
8.1 The Origin of Hashing 124
8.2 Hash Tables 126
8.3 A Statistical Model for Hashing 129
8.4 The Likelihood of Collisions 130
9 Hashing Functions: Examples and Evaluation 132
9.1 Overview: The Tradeoff of Randomization Versus Computational Simplicity 132
9.2 Some Examples of Hashing Functions 132
9.3 Performance of Hash Functions: Formulation 135
9.4 The Χ2-Test 137
9.5 Testing a Hash Function 138
9.6 The McKenzie et al. Results 139
10 Record Chaining with Hash Tables 141
10.1 Separate Chaining of Records 141
10.2 Analysis of Separate Chaining Hashing Sequences and the Chains they Create 143
10.3 A Combinatorial Analysis of Separate Chaining 148
10.4 Coalesced Chaining 152
10.5 The Pittel-Yu Analysis of EICH Coalesced Chaining 155
10.6 To Separate or to Coalesce; and Which Version? That is the Question 161
11 Perfect Hashing 164
11.1 Overview 164
11.2 Chichelli's Construction 164
12 The Uniform Hashing Model 167
12.1 An Idealized Hashing Model 167
12.2 The Asymptotics of Uniform Hashing 171
12.3 Collision-Free Hashing 172
13 Hashing with Linear Probing 174
13.1 Formulation and Preliminaries 174
13.2 Performance Measures for LP Hashing 176
13.3 All Cells Other than HTn-1 in the Hash-Table of n Cells are Occupied 178
13.4 m-Keys Hashed into a Hash Table of n Cells Leaving Cell HTn-1 Unoccupied 180
13.5 The Probability Distribution for the Length of a Search 182
13.6 Asymptotics 184
13.7 Hashing with Linear Open Addressing: Coda 189
13.8 A Possible Improvement to Linear Probing 189
14 Double Hashing 205
14.1 Formulation of Double Hashing 205
14.2 Progressions and Strides 207
14.3 The Number of Progressions Which Fill a Hash-Table Cell 208
14.3.1 Progression Graphs 209
14.4 Dominance 215
14.5 Insertion-Cost Bounds Relating Uniform and Double Hashing 216
14.6 UsuallyDoubleHash 218
14.7 The UDH Chance Experiment and the Cost to Insert the Next Key by Double Hashing 219
14.8 Proof of Equation (14.12a) 221
14.9 UsuallyDoubleHash 224
14.10 Proof of Equation (14.12b) 225
15 Optimum Hashing 227
15.1 The Ullman-Yao Framework 227
15.1.1 The Ullman-Yao Hashing Functions 227
15.1.2 Ullman-Yao Insert (k) and Search (k) 228
15.1.3 The Ullman-Yao Statistical Model 228
15.2 The Rates at Which a Cell is Probed and Occupied 230
15.3 Partitions of (i)Scenarios, (i)Subscenarios, and Their Skeletons 232
15.3.1 (i)Subscenarios 234
15.3.2 Skeletons 234
15.4 Randomly Generated m-Scenarios 234
15.5 Bounds on Random Sums 240
15.6 Completing the Proof of Theorem 15.1 244
PART III SOME NOVEL APPLICATIONS OF HASHING 247
16 Karp-Rabin String Searching 249
16.1 Overview 249
16.2 The Basic Karp-Rabin Hash-Fingerprint Algorithm 250
16.3 The Plain Vanilla Karp-Rabin Fingerprint Algorithm 251
16.4 Some Estimates on Prime Numbers 253
16.5 The Cost of False Matches in the Plain Vanilla Karp-Rabin Fingerprint Algorithm 253
16.6 Variations on the Plain Vanilla Karp-Rabin Fingerprint Algorithm 255
16.7 A Nonhashing Karp-Rabin Fingerprint 255
17 Hashing Rock and Roll 259
17.1 Overview of Audio Fingerprinting 259
17.2 The Basics of Fingerprinting Music 260
17.3 Haar Wavelet Coding 262
17.4 Min-Hash 266
17.5 Some Commercial Fingerprinting Products 273
18 Hashing in E-Commerce 275
18.1 The Varied Applications of Cryptography 275
18.2 Authentication 276
18.3 The Need for Certificates 277
18.4 Cryptographic Hash Functions 278
18.5 X.509 Certificates and CCIT Standardization 280
18.6 The Secure Socket Layer (SSL) 281
18.7 Trust on the Web...Trust No One Over 40! 282
18.8 MD5 284
18.9 Criticism of MD5 289
18.10 The Wang-Yu Collision Attack 291
18.11 Steven's Improvement to the Wang-Yu Collision Attack 291
18.12 The Chosen-Prefix Attack on MD5 292
18.13 The Rogue CA Attack Scenario 293
18.14 The Secure Hash Algorithms 294
18.15 Criticism of SHA-1 296
18.16 SHA-2 296
18.17 What Now? 298
Appendix 18 Sketch of the Steven's Chosen Prefix Attack 301
19 Hashing and the Secure Distribution of Digital Media 307
19.1 Overview 307
19.2 Intellectual Property (Copyrights and Patents) 308
19.3 Steganography 313
19.4 Boil, Boil, Toil...and But First, Carefully Mix 314
19.5 Software Distribution Systems 314
19.6 Watermarks 315
19.7 An Image-Processing Technique for Watermarking 317
19.8 Using Geometric Hashing to Watermark Images 320
19.9 Biometrics and Hashing 323
19.10 The Dongle 329
Appendix 19 Reed-Solomon and Hadamard Coding 332
Exercises and Solutions 343
Index 382
Overview
Written by one of the developers of the technology, Hashing is both a historical document on the development of hashing and an analysis of the applications of hashing in a society increasingly concerned with security. The material in this book is based on courses taught by the author, and key points are reinforced in sample problems and an accompanying instructor s manual. Graduate students and researchers in mathematics, cryptography, and security will benefit from this overview of hashing and the complicated ...