Hashing in Computer Science - Fifty Years of Slicing and Dicing

Informationen zum Autor Alan G. Konheim, PhD, is Professor Emeritus of Computer Science at the University of Californa, Santa Barbara. Dr. Konheim's early work at IBM led to the Data Encryption Standard (DES), which was evaluated by his Yorktown Probability and Cryptography Group. DES was certified as a national standard in the 1970s. Dr. Konheim continues to consult the government in the area of cryptanalysis. Klappentext Gain the Skills and Knowledge Needed to Understanding Data Security SystemsA file of computer data is composed of records to each of which a key or identifier is associated. The key is used to search for the address of a desired record. When the file is a telephone directory, searching is easy--the key is the subscriber's name and the records are naturally arranged in alphabetic order. For data whose records are not easily alphabetized, a hash function is used to arithmetically derive from the key record's address. Hashing was invented during the design of the IBM 701 machine in the 1950s by Hans Peter Luhn. In the ensuing half century, the hashing concept has found a variety of applications. When combined with cryptography, hashing can be used to authenticate users in e-commerce on the Web.Professor Konheim is an authority on computer security and an early contributor to hashing technology. Based on courses taught by the author, this book unravels the complicated mathematics involved in hashing as it explains in detail the various hashing methods. It describes:* Techniques for audio fingerprinting, the automated recognition of music* The use of hashing in e-commerce to protect against identity theft* How hashing is used to inhibit the unlawful copying and distribution of music, video, software, books, and dataKey points are reinforced in the sample problems and solutions provided; also included are an accompanying instructor's manual and extensive bibliography. Hashing in Computer Science is valuable reading for graduate students and researchers in mathematics, cryptography, and security. It can be used as a textbook in senior and graduate courses on cryptography and others that employ cryptanalysis, computer security, analysis of randomized and combinatorial algorithms, computer networks, compiler design, computational geometry, and theory of computation. Zusammenfassung 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. Inhaltsverzeichnis 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...

List of contents

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.
&

Report

"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)

Product details

• Authors: Konheim, AG Konheim, Alan G Konheim, Alan G. Konheim, Alan G. (Ibm Konheim, Konheim Alan G.
• Publisher: Wiley, John and Sons Ltd
• Languages: English
• Product format: Hardback
• Released: 25.06.2010
• EAN: 9780470344736
• ISBN: 978-0-470-34473-6
• No. of pages: 408
• Subjects: Natural sciences, medicine, IT, technology > Technology > Electronics, electrical engineering, communications engineering; Electrical & Electronics Engineering, Elektrotechnik u. Elektronik, Sicherheit in Kommunikationssystemen, Communication System Security, Hash-Verfahren