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.

PREFACE.PART I: MATHEMATICAL PRELIMINARIES.1. Counting.1.1: The Sum and Product Rules.1.2: Mathematical Induction.1.3: Factorial.1.4: Binomial Coefficients.1.5: Multinomial Coefficients.1.6: Permutations.1.7: Combinations.1.8: The Principle of Inclusion-Exclusion.1.9: Partitions.1.10: Relations.1.11: Inverse Relations.Appendix 1: Summations Involving Binomial Coefficients.2. Recurrence and Generating Functions.2.1: Recursions.2.2: Generating Functions.2.3: Linear Constant Coefficient Recursions.2.4: Solving Homogeneous LCCRs Using Generating Functions.2.5: The Catalan Recursion.2.6: The Umbral Calculus.2.7: Exponential Generating Functions.2.8: Partitions of a Set: The Bell and Stirling Numbers.2.9: Rouché's Theorem and the Lagrange's Inversion Formula.3. Asymptotic Analysis.3.1: Growth Notation for Sequences.3.2: Asymptotic Sequences and Expansions.3.3: Saddle Points.3.4: Laplace's Method.3.5: The Saddle Point Method.3.6: When Will the Saddle Point Method Work?3.7: The Saddle Point Bounds.3.8: Examples of Saddle Point Analysis.4. Discrete Probability Theory.4.1: The Origins of Probability Theory.4.2: Chance Experiments, Sample Points, Spaces, and Events.4.3: Random Variables.4.4: Moments--Expectation and Variance.4.5: The Birthday Paradox.4.6: Conditional Probability and Independence.4.7: The Law of Large Numbers (LLN).4.8: The Central Limit Theorem (CLT).4.9: Random Processes and Markov Chains.5. Number Theory and Modern Algebra.5.1: Prime Numbers.5.2: Modular Arithmetic and the Euclidean Algorithm.5.3: Modular Multiplication.5.4: The Theorems of Fermat and Euler.5.5: Fields and Extension Fields.5.6: Factorization of Integers.5.7: Testing Primality.6. Basic Concepts of Cryptography.6.1: The Lexicon of Cryptography.6.2: Stream Ciphers.6.3: Block Ciphers.6.4: Secrecy Systems and Cryptanalysis.6.5: Symmetric and Two-Key Cryptographic Systems.6.6: The Appearance of Public Key Cryptographic systems.6.7: A Multitude of Keys.6.8: The RSA Cryptosystem.6.9: Does PKC Solve the Problem of Key Distribution?6.10: Elliptic Groups Over the Reals.6.11: Elliptic Groups Over the Field Zm,2 .6.12: Elliptic Group Cryptosystems.6.13: The Menezes-Vanstone Elliptic Curve Cryptosystem.6.14: Super-Singular Elliptic Curves.PART II: HASHING FOR STORAGE: DATA MANAGEMENT.7. Basic Concepts.7.1: Overview of the Records Management Problem.7.2: A Simple Storage Management Protocol: Plain Vanilla Chaining.7.3: Record-Management with Sorted Keys.8. Hash Functions.8.1: The Origin of Hashing.8.2: Hash Tables.8.3: A Statistical Model for Hashing.8.4: The Likelihood of Collisions.9. Hashing Functions: Examples and Evaluation.9.1: Overview: The Tradeoff of Randomization Versus Computational Simplicity.9.2: Some Examples of Hashing Functions.9.3: Performance of Hash Functions: Formulation.9.4: The X²-Test.9.5: Testing a Hash Function.9.6: The McKenzie et al. Results.10. Record Chaining with Hash Tables.10.1: Separate Chaining of Records.10.2: Analysis of Separate Chaining Hashing Sequences and the Chains They Create.10.3: A Combinatorial Analysis of Separate Chaining.10.4: Coalesced Chaining.10.5: The Pittel-Yu Analysis of EICH Coalesced Chaining.10.6: To Separate or to Coalesce; and Which Version? That Is the Question.11. Perfect Hashing.11.1: Overview.11.2: Chichelli's Construction.12. The Uniform Hashing Model.12.1: An Idealized Hashing Model.12.2: The Asymptotics of Uniform Hashing.12.3: Collision-Free Hashing.13. Hashing with Linear Probing.13.1: Formulation and Preliminaries.13.2: Performance Measures for LP Hashing.13.3: All Cells Other than HTn-1 in the Hash-Table of n Cells are Occupied.13.4: m-Keys Hashed into a Hash Table of n Cells Leaving Cell HTn-1 Unoccupied.13.5: The Probability Distribution for the Length of a Search.13.6: Asymptotics.13.7: Hashing with Linear Open Addressing: Coda.13.8: A Possible Improvement to Linear Probing.14. Double Hashing.14.1: Formulation of Double Hashing.14.2: Progressions and Strides.14.3: The Number of Progressions Which Fill a Hash-Table Cell.14.3.1: Progression Graphs.14.4: Dominance.14.5: Insertion-Cost Bounds Relating Uniform and Double Hashing.14.6: UsuallyDoubleHash.14.7: The UDH Chance Experiment and the Cost to Insert the Next Key by Double Hashing.14.8: Proof of Equation (14.12a).14.9: UsuallyDoubleHash.14.10: Proof of Equation (14.12b).15. Optimum Hashing.15.1: The Ullman-Yao Framework.15.1.1: The Ullman-Yao Hashing Functions.15.1.2: Ullman-Yao INSERT(k) and SEARCH(k).15.1.3: The Ullman-Yao Statistical Model.15.2: The Rates at Which a Cell is Probed and Occupied.15.3: Partitions of (i)Scenarios, (i)Subscenarios, and Their Skeletons.15.3.1: (i)Subscenarios.15.3.2: Skeletons.15.4: Randomly Generated m-Scenarios.15.5: Bounds on Random Sums.15.6: Completing the Proof of Theorem 15.1.PART III: SOME NOVEL APPLICATIONS OF HASHING.16. Karp-Rabin String Searching.16.1: Overview.16.2: The Basic Karp-Rabin Hash-Fingerprint Algorithm.16.3: The Plain Vanilla Karp-Rabin Fingerprint Algorithm.16.4: Some Estimates on Prime Numbers.16.5: The Cost of False Matches in the Plain Vanilla Karp-Rabin Fingerprint Algorithm.16.6: Variations on the Plain Vanilla Karp-Rabin Fingerprint Algorithm.16.7: A Nonhashing Karp-Rabin Fingerprint.17. Hashing Rock and Roll.17.1: Overview of Audio Fingerprinting .17.2: The Basics of Fingerprinting Music.17.3: Haar Wavelet Coding.17.4: Min-Hash.17.5: Some Commercial Fingerprinting Products.18. Hashing in E-Commerce.18.1: The Varied Applications of Cryptography.18.2: Authentication.18.3: The Need for Certificates.18.4: Cryptographic Hash Functions.18.5: X.509 Certificates and CCIT Standardization.18.6: The Secure Socket Layer (SSL).18.7: Trust on the Web ... Trust No One Over 40!18.8: MD5.18.9: Criticism of MD5.18.10: The Wang-Yu Collision Attack.18.11: Steven's Improvement to the Wang-Yu Collision Attack.18.12: The Chosen-Prefix Attack on MD5.18.13: The Rogue CA Attack Scenario.18.14: The Secure Hash Algorithms.18.15: Criticism of SHA-1.18.16: SHA-2.18.17: What Now?Appendix 18: Sketch of the Steven's Chosen Prefix Attack.19. Hashing and the Secure Distribution of Digital Media.19.1: Overview.19.2: Intellectual Property (Copyrights and Patents).19.3: Steganography.19.4: Boil, Boil, Toil ... and But First, Carefully Mix.19.5: Software Distribution Systems.19.6: Watermarks.19.7: An Image-Processing Technique for Watermarking.19.8: Using Geometric Hashing to Watermark Images.19.9: Biometrics and Hashing.19.10: The Dongle.Appendix 19: Reed-Solomon and Hadamard Coding.Exercises and Solutions.INDEX.