Hashing in Computer Science E-Book

Alan G. Konheim

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 610

Veröffentlichungsjahr: 2010

Beschreibung

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.

Leseprobe

Table of Contents

Cover

Table of Contents

Half title page

Title page

Copyright page

Dedication

PREFACE

Part I: MATHEMATICAL PRELIMINARIES

CHAPTER 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

CHAPTER 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 CALCULUS4

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

CHAPTER 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 SADDLE POINT BOUNDS

3.8 EXAMPLES OF SADDLE POINT ANALYSIS

CHAPTER 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 PARADOX1

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

CHAPTER 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 FERMAT2 AND EULER

5.5 FIELDS AND EXTENSION FIELDS

5.6 FACTORIZATION OF INTEGERS

5.7 TESTING PRIMALITY

CHAPTER 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 GROUPS CRYPTOSYSTEMS

6.13 THE MENEZES-VANSTONE ELLIPTIC CURVE CRYPTOSYSTEM

6.14 SUPER SINGULAR ELLIPTIC CURVES

Part II: HASHING FOR STORAGE: DATA MANAGEMENT

CHAPTER 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

CHAPTER 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

CHAPTER 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 HASHING FUNCTIONS: FORMULATION

9.4 THE χ2-TEST

9.5 TESTING A HASH FUNCTION

9.6 THE MCKENZIE ET AL. RESULTS

CHAPTER 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

CHAPTER 11 Perfect Hashing

11.1 OVERVIEW

11.2 CICHELLI’S CONSTRUCTION

CHAPTER 12 The Uniform Hashing Model

12.1 AN IDEALIZED HASHING MODEL

12.2 THE ASYMPTOTICS OF UNIFORM HASHING

12.3 COLLISION-FREE HASHING

CHAPTER 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

CHAPTER 14 Double Hashing

14.1 FORMULATION OF DOUBLE HASHING1

14.2 PROGRESSIONS AND STRIDES

14.3 THE NUMBER OF PROGRESSIONS WHICH FILL A HASH-TABLE CELL

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)

CHAPTER 15 Optimum Hashing

15.1 THE ULLMAN–YAO FRAMEWORK1

15.2 THE RATES AT WHICH A CELL IS PROBED AND OCCUPIED

15.3 PARTITIONS OF (i)SCENARIOS, (i)SUBSCENARIOS, AND THEIR 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

CHAPTER 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

CHAPTER 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

CHAPTER 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

A18.1 BIRTHDAYING1 [SCHNEIER 1996, PP. 165–166], [OORSCHOT AND WIENER 1999]

A18.2 THE BINARY SIGNED DIGIT REPRESENTATION (BSDR)

A18.3 DIFFERENTIAL ANALYSIS

A18.4 OUTLINE OF THE STEVENS CONSTRUCTION

CHAPTER 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 DONGLE24

APPENDIX 19 Reed-Solomon and Hadamard Coding

A.19.0 CODES

A.19.1 REED-SOLOMON CODES

A.19.3 HADAMARD CODES

Exercises and Solutions

PART II, CHAPTER 7

PART II, CHAPTER 8

PART II, CHAPTER 10

PART II, CHAPTER 11

PART II, CHAPTER 12

PART II, CHAPTER 13

PART II, CHAPTER 14

PART II, CHAPTER 15

PART III, CHAPTER 16

PART III, CHAPTER 17

PART III, CHAPTER 18

PART III, CHAPTER 19

Index

HASHING IN COMPUTER SCIENCE

Copyright © 2010 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New Jersey

Published simultaneously in Canada

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data

Konheim, Alan G., 1934–

 Hashing in computer science : fifty years of slicing and dicing / Alan G. Konheim.

p. cm.

 ISBN 978-0-470-34473-6

 ISBN 978-1-118-03183-4(ebk)

 1. Hashing (Computer science) 2. Cryptography. 3. Data encryption (Computer science) 4. Computer security. I. Title.

 QA76.9.H36K65 2010

 005.8′2–dc22

2009052123

To my grandchildren …

Madelyn, David, Joshua, and Karlina