Title:
Hashing in computer science : fifty years of slicing and dicing
Personal Author:
Publication Information:
Hoboken, N.J. : John Wiley & Sons, c2010
Physical Description:
xvii, 386 p. : ill. ; 26 cm.
ISBN:
9780470344736
Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
|---|---|---|---|---|---|
Searching... | 30000010236747 | QA76.9.H36 K65 2010 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
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.
Author Notes
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.
Table of Contents
| Foreword |
| Preface |
| About the Author |
| Chapter 1 Aperitifs |
| 1.1 The Lexicon of Cryptography |
| 1.2 Cryptographic Systems |
| 1.3 Cryptanalysis |
| 1.4 Side Information |
| 1.5 Thomas Jefferson and the M-94 |
| 1.6 Cryptography and History |
| 1.7 Cryptography and Computers |
| 1.8 The National Security Agency |
| 1.9 The Giants |
| 1.10 No Sex, Money, Crime or . . . Love |
| 1.11 An Example of the Inference Process in Cryptanalysis |
| 1.12 Warning! |
| Chapter 2 Columnar Transposition |
| 2.1 Shannon?s Classification of Secrecy Transformations |
| 2.2 The Rules of Columnar Transposition Encipherment |
| 2.3 Cribbing |
| 2.4 Examples of Cribbing |
| 2.5 Plaintext Language Models |
| 2.6 Counting k-Grams |
| 2.7 Deriving the Parameters of a Markov Model from Sliding Window Counts |
| 2.8 Markov Scoring |
| 2.9 The ADFGVX Transposition System |
| 2.10 CODA |
| 2.11 Columnar Transposition Problems |
| Chapter 3 Monoalphabetic Substitution |
| 3.1 Monoalphabetic Substitution |
| 3.2 Caesar's Cipher |
| 3.3 Cribbing Using Isomorphs |
| 3.4 The x2-Test of a Hypothesis |
| 3.5 Pruning from the Table of Isomorphs |
| 3.6 Partial Maximum Likelihood Estimation of a Monoalphabetic Substitution |
| 3.7 The Hidden Markov Model (HMM) |
| 3.8 Hill Encipherment of ASCII N-Grams |
| 3.9 Gaussian Elimination |
| 3.10 Monoalphabetic Substitution Problems |
| Chapter 4 Polyalphabetic Substitution |
| 4.1 Running Keys |
| 4.2 Blaise de Vigenére |
| 4.3 Gilbert S. Vernam |
| 4.4 The One-Time Pad |
| 4.5 Finding the Key of Vernam-Vigenére Ciphertext with Known Period by Correlation |
| 4.6 Coincidence |
| 4.7 Venona |
| 4.8 Polyalphabetic Substitution Problems |
| Chapter 5 Statistical Tests |
| 5.1 Weaknesses in a Cryptosystem |
| 5.2 The Kolmogorov-Smirnov Test |
| 5.3 NIST's Proposed Statistical Tests |
| 5.4 Diagnosis |
| 5.5 Statistical Tests Problems |
| Chapter 6 The Emergence Of Cipher Machines |
| 6.1 The Rotor |
| 6.2 Rotor Systems |
| 6.3 Rotor Patents |
| 6.4 A Characteristic Property of Conjugacy |
| 6.5 Analysis of a 1-Rotor System Ciphertext Only |
| 6.6 The Displacement Sequence of a Permutation |
| 6.7 Arthur Scherbius |
| 6.8 Enigma Key Distribution Protocol |
| 6.9 Cryptanalysis of the Enigma |
| 6.10 Cribbing Enigma Ciphertext |
| 6.11 The Lorenz Schlüsselzusatz |
| 6.12 The SZ40 Pin Wheels |
| 6.13 SZ40 Cryptanalysis Problems |
| 6.14 Cribbing SZ40 Ciphertext |
| Chapter 7 The Japanese Cipher Machines |
| 7.1 Japanese Signaling Conventions |
| 7.2 Half-Rotors |
| 7.3 Components of the RED Machine |
| 7.4 Cribbing RED Ciphertext |
| 7.5 Generalized Vowels and Consonants |
| 7.6 "Climb Mount Itaka" - War! |
| 7.7 Components of the PURPLE Machine |
| 7.8 The PURPLE Keys |
| 7.9 Cribbing PURPLE Finding the V-Stepper |
| 7.10 Cribbing PURPLE Finding the C-Steppers |
| Chapter 8 Stream Ciphers |
| 8.1 Stream Ciphers |
| 8.2 Feedback Shift Registers |
| 8.3 The Algebra of Polynomials over Z2 |
| 8.4 The Characteristic Polynomial of a Linear Feedback Shift Register |
| 8.5 Properties of Maximal Length LFSR Sequences |
| 8.6 Linear Equivalence |
| 8.7 Combining Multiple Linear Feedback Shift Registers |
| 8.8 Matrix Representation of the LFSR |
| 8.9 Cribbing of Stream Enciphered ASCII Plaintext |
| 8.10 Nonlinear Feedback Shift Registers |
| 8.11 Nonlinear Key Stream Generation |
| 8.12 Irregular Clocking |
| 8.13 RC4 |
| 8.14 Stream Encipherment Problems |
| Chapter 9 Block-Ciphers Clucifer, Des, And Aes |
| 9.1 Lucifer |
| 9.2 Des |
| 9.3 The DES S-Boxes, P-Box, and Initial Permutation (IP) |
| 9.4 DES Key Schedule |
| 9.5 Sample DES Encipherment |
| 9.6 Chaining |
| 9.7 Is DES a Random Mapping? |
| 9.8 DES in the Output-Feedback Mode (OFB) |
| 9.9 Cryptanalysis of DES |
| 9.10 Differential Cryptanalysis |
| 9.11 The EFS DES-Cracker |
| 9.12 What Now? |
| 9.13 The Future Advanced Data Encryption Standard |
| 9.14 And the Winner Is! |
| 9.15 The Rijndael Operations |
| 9.16 The Rijndael Cipher |
| 9.17 Rijndael's Strength Propagation of Patterns |
| 9.18 When is a Product Block-Cipher Secure? |
| 9.19 Generating the Symmetric Group |
| 9.20 A Class of Block Ciphers |
| 9.21 The IDEA Block Cipher |
| Chapter 10 The Paradigm Of Public Key Cryptography |
| 10.1 In the Beginning. . |
| 10.2 Key Distribution |
| 10.3 E-Commerce |
| 10.4 Public-Key Cryptosystems Easy and Hard Computational Problems |
| 10.5 Do PKCS Solve the Problem of Key Distribution? |
| 10.6 P.S |
| Chapter 11 The Knapsack Cryptosystem |
| 11.1 Subset Sum and Knapsack Problems |
| 11.2 Modular Arithmetic and the Euclidean Algorithm |
| 11.3 A Modular Arithmetic Knapsack Problem |
| 11.4 Trap-Door Knapsacks |
| 11.5 Knapsack Encipherment and Decipherment of ASCII-Plaintext |
| 11.6 Cryptanalysis of the Merkle-Hellman Knapsack System Modular Mapping |
| 11.7 Diophantine Approximation |
| 11.8 Short Vectors in a Lattice |
| 11.9 Knapsack-Like Cryptosystems |
| 11.10 Knapsack Cryptosystem Problems |
| Chapter 12 The Rsa Cryptosystem |
| 12.1 A Short Number-Theoretic Digression |
| 12.2 RSA |
| 12.3 The RSA Encipherment and Decipherment of ASCII-Plaintext |
| 12.4 Attack on RSA |
| 12.5 Williams Variation of RSA |
| 12.6 Multiprecision Modular Arithmetic |
| Chapter 13 Prime Numbers And Factorization |
| 13.1 Number Theory and Cryptography |
| 13.2 Prime Numbers and the Sieve of Eratosthenes |
| 13.3 Pollard's p 2 1 Method |
| 13.4 Pollard's r-Algorithm |
| 13.5 Quadratic Residues |
| 13.6 Random Factorization |
| 13.7 The Quadratic Sieve (QS) |
| 13.8 Testing if an Integer is a Prime |
| 13.9 The RSA Challenge |
| 13.10 Perfect Numbers and the Mersenne Primes |
| 13.11 Multiprecision Arithmetic |
| 13.12 Prime Number Testing and Factorization Problems |
| Chapter 14 The Discrete Logarithm Problem |
| 14.1 The Discrete Logarithm Problem Modulo p |
| 14.2 Solution of the DLP Modulo p Given a Factorization of p 2 1 |
| 14.3 Adelman's Subexponential Algorithm for the Discrete Logarithm Problem |
| 14.4 The Baby-Step, Giant-Step Algorithm |
| 14.5 The Index-Calculus Method |
| 14.6 Pollard's r -Algorithm |
| 14.7 Extension Fields |
| 14.8 The Current State of Discrete Logarithm Research |
| Chapter 15 Elliptic Curve Cryptography |
| 15.1 Elliptic Curves |
| 15.2 The Elliptic Group over the Reals |
| 15.3 Lenstra's Factorization Algorithm |
| 15.4 The Elliptic Group over Zp ( p . 3) |
| 15.5 Elliptic Groups over the Field Zm,2 |
| 15.6 Computations in the Elliptic Group EZm,2(a, b) |
| 15.7 Supersingular Elliptic Curves |
| 15.8 Diffie-Hellman Key Exchange Using an Elliptic Curve |
| 15.9 The Menezes-Vanstone Elliptic Curve Cryptosystem |
| 15.10 The Elliptic Curve Digital Signature Algorithm |
| 15.11 The Certicom Challenge |
| 15.12 NSA and Elliptic Curve Cryptography |
| Chapter 16 Key Exchange In A Network |
| 16.1 Key Distribution in a Network |
| 16.2 U.S. Patent '770 |
| 16.3 Spoofing |
| 16.4 El Gamal's Extension of Diffie-Hellman |
| 16.5 Shamir's Autonomous Key Exchange |
| 16.6 X9.17 Key Exchange Architecture |
| 16.7 The Needham-Schroeder Key Distribution Protocol |
| Chapter 17 Digital Signatures And Authentication |
| 17.1 The Need for Signatures |
| 17.2 Threats to Network Transactions |
| 17.3 Secrecy, Digital Signatures, and Authentication |
| 17.4 The Desiderata of a Digital Signature |
| 17.5 Public-Key Cryptography and Signature Systems |
| 17.6 Rabin's Quadratic Residue Signature Protocol |
| 17.7 Hash Functions |
| 17.8 MD5 |
| 17.9 The Secure Hash Algorithm |
| 17.10 NIST's Digital Signature Algorithm |
| 17.11 El Gamal's Signature Protocol |
| 17.12 The Fiat-Shamir Identification and Signature Schema |
| 17.13 The Oblivious Transfer |
| Chapter 18 Applications Of Cryptography |
| 18.1 UNIX Password Encipherment |
| 18.2 Magnetic Stripe Technology |
| 18.3 Protecting ATM Transactions |
| 18.4 Keyed-Access Cards |
| 18.5 Smart Cards |
| 18.6 Who Can You Trust? Kohnfelder's Certificates |
| 18.7 X.509 Certificates |
| 18.8 The Secure Socket Layer (SSL) |
| 18.9 Making a Secure Credit Card Payment on the Web |
| Chapter 19 Cryptographic Patents |
| 19.1 What is a Patent? |
| 19.2 Patentability of Ideas |
| 19.3 The Format of a Patent |
| 19.4 Patentable versus Nonpatentable Subjects |
| 19.5 Infringement |
| 19.6 The Role of Patents in Cryptography |
| 19.7 U.S. Patent 3,543,904 |
| 19.8 U.S. Patent 4,200,770 |
| 19.9 U.S. Patent 4,218,582 |
| 19.10 U.S. Patent 4,405,829 |
| 19.11 PKS/RSADSI Litigation |
| 19.12 Leon Stambler |
| Index |
