Hashing in Computer Science Fifty Years of Slicing and Dicing

by Konheim, Alan G.

• ISBN13: 9780470344736
• ISBN10: 0470344733
• Edition: 1st
• Format: Hardcover
• Copyright: 2010-07-06
• Publisher: Wiley-Interscience

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 instructors 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 Biography

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

Aperitifs

The Lexicon of Cryptography

Cryptographic Systems

Cryptanalysis

Side Information

Thomas Jefferson and the M-94

Cryptography and History

Cryptography and Computers

The National Security Agency

The Giants

No Sex, Money, Crime or . . . Love

An Example of the Inference Process in Cryptanalysis

Warning!

Columnar Transposition

Shannon?s Classification of Secrecy Transformations

The Rules of Columnar Transposition Encipherment

Cribbing

Examples of Cribbing

Plaintext Language Models

Counting k-Grams

Deriving the Parameters of a Markov Model from Sliding Window Counts

Markov Scoring

The ADFGVX Transposition System

CODA

Columnar Transposition Problems

Monoalphabetic Substitution

Monoalphabetic Substitution

Caesar's Cipher

Cribbing Using Isomorphs

The x2-Test of a Hypothesis

Pruning from the Table of Isomorphs

Partial Maximum Likelihood Estimation of a Monoalphabetic Substitution

The Hidden Markov Model (HMM)

Hill Encipherment of ASCII N-Grams

Gaussian Elimination

Monoalphabetic Substitution Problems

Polyalphabetic Substitution

Running Keys

Blaise de Vigenére

Gilbert S. Vernam

The One-Time Pad

Finding the Key of Vernam-Vigenére Ciphertext with Known Period by Correlation

Coincidence

Venona

Polyalphabetic Substitution Problems

Statistical Tests

Weaknesses in a Cryptosystem

The Kolmogorov-Smirnov Test

NIST's Proposed Statistical Tests

Diagnosis

Statistical Tests Problems

The Emergence Of Cipher Machines

The Rotor

Rotor Systems

Rotor Patents

A Characteristic Property of Conjugacy

Analysis of a 1-Rotor System Ciphertext Only

The Displacement Sequence of a Permutation

Arthur Scherbius

Enigma Key Distribution Protocol

Cryptanalysis of the Enigma

Cribbing Enigma Ciphertext

The Lorenz Schlüsselzusatz

The SZ40 Pin Wheels

SZ40 Cryptanalysis Problems

Cribbing SZ40 Ciphertext

The Japanese Cipher Machines

Japanese Signaling Conventions

Half-Rotors

Components of the RED Machine

Cribbing RED Ciphertext

Generalized Vowels and Consonants

"Climb Mount Itaka" - War!

Components of the PURPLE Machine

The PURPLE Keys

Cribbing PURPLE Finding the V-Stepper

Cribbing PURPLE Finding the C-Steppers

Stream Ciphers

Stream Ciphers

Feedback Shift Registers

The Algebra of Polynomials over Z2

The Characteristic Polynomial of a Linear Feedback Shift Register

Properties of Maximal Length LFSR Sequences

Linear Equivalence

Combining Multiple Linear Feedback Shift Registers

Matrix Representation of the LFSR

Cribbing of Stream Enciphered ASCII Plaintext

Nonlinear Feedback Shift Registers

Nonlinear Key Stream Generation

Irregular Clocking

RC4

Stream Encipherment Problems

Block-Ciphers Clucifer, Des, And Aes

Lucifer

Des

The DES S-Boxes, P-Box, and Initial Permutation (IP)

DES Key Schedule

Sample DES Encipherment

Chaining

Is DES a Random Mapping?

DES in the Output-Feedback Mode (OFB)

Cryptanalysis of DES

Differential Cryptanalysis

The EFS DES-Cracker

What Now?

The Future Advanced Data Encryption Standard

And the Winner Is!

The Rijndael Operations

The Rijndael Cipher

Rijndael's Strength Propagation of Patterns

When is a Product Block-Cipher Secure?

Generating the Symmetric Group

A Class of Block Ciphers

The IDEA Block Cipher

The Paradigm Of Public Key Cryptography

In the Beginning. .

Key Distribution

E-Commerce

Public-Key Cryptosystems Easy and Hard Computational Problems

Do PKCS Solve the Problem of Key Distribution?

P.S

The Knapsack Cryptosystem

Subset Sum and Knapsack Problems

Modular Arithmetic and the Euclidean Algorithm

A Modular Arithmetic Knapsack Problem

Trap-Door Knapsacks

Knapsack Encipherment and Decipherment of ASCII-Plaintext

Cryptanalysis of the Merkle-Hellman Knapsack System Modular Mapping

Diophantine Approximation

Short Vectors in a Lattice

Knapsack-Like Cryptosystems

Knapsack Cryptosystem Problems

The Rsa Cryptosystem

A Short Number-Theoretic Digression

RSA

The RSA Encipherment and Decipherment of ASCII-Plaintext

Attack on RSA

Williams Variation of RSA

Multiprecision Modular Arithmetic

Prime Numbers And Factorization

Number Theory and Cryptography

Prime Numbers and the Sieve of Eratosthenes

Pollard's p 2 1 Method

Pollard's r-Algorithm

Quadratic Residues

Random Factorization

The Quadratic Sieve (QS)

Testing if an Integer is a Prime

The RSA Challenge

Perfect Numbers and the Mersenne Primes

Multiprecision Arithmetic

Prime Number Testing and Factorization Problems

The Discrete Logarithm Problem

The Discrete Logarithm Problem Modulo p

Solution of the DLP Modulo p Given a Factorization of p 2 1

Adelman's Subexponential Algorithm for the Discrete Logarithm Problem

The Baby-Step, Giant-Step Algorithm

The Index-Calculus Method

Pollard's r -Algorithm

Extension Fields

The Current State of Discrete Logarithm Research

Elliptic Curve Cryptography

Elliptic Curves

The Elliptic Group over the Reals

Lenstra's Factorization Algorithm

The Elliptic Group over Zp ( p . 3)

Elliptic Groups over the Field Zm,2

Computations in the Elliptic Group EZm,2(a, b)

Supersingular Elliptic Curves

Diffie-Hellman Key Exchange Using an Elliptic Curve

The Menezes-Vanstone Elliptic Curve Cryptosystem

The Elliptic Curve Digital Signature Algorithm

The Certicom Challenge

NSA and Elliptic Curve Cryptography

Key Exchange In A Network

Key Distribution in a Network

U.S. Patent '770

Spoofing

El Gamal's Extension of Diffie-Hellman

Shamir's Autonomous Key Exchange

X9.17 Key Exchange Architecture

The Needham-Schroeder Key Distribution Protocol

Digital Signatures And Authentication

The Need for Signatures

Threats to Network Transactions

Secrecy, Digital Signatures, and Authentication

The Desiderata of a Digital Signature

Public-Key Cryptography and Signature Systems

Rabin's Quadratic Residue Signature Protocol

Hash Functions

MD5

The Secure Hash Algorithm

NIST's Digital Signature Algorithm

El Gamal's Signature Protocol

The Fiat-Shamir Identification and Signature Schema

The Oblivious Transfer

Applications Of Cryptography

UNIX Password Encipherment

Magnetic Stripe Technology

Protecting ATM Transactions

Keyed-Access Cards

Smart Cards

Who Can You Trust? Kohnfelder's Certificates

X.509 Certificates

The Secure Socket Layer (SSL)

Making a Secure Credit Card Payment on the Web

Cryptographic Patents

What is a Patent?

Patentability of Ideas

The Format of a Patent

Patentable versus Nonpatentable Subjects

Infringement

The Role of Patents in Cryptography

U.S. Patent 3,543,904

U.S. Patent 4,200,770

U.S. Patent 4,218,582

U.S. Patent 4,405,829

PKS/RSADSI Litigation

Leon Stambler

Index

Table of Contents provided by Publisher. All Rights Reserved.