# Handbook of Applied Cryptography

## Preview

## Book Description

Cryptography, in particular public-key cryptography, has emerged in the last 20 years as an important discipline that is not only the subject of an enormous amount of research, but provides the foundation for information security in many applications. Standards are emerging to meet the demands for cryptographic protection in most areas of data communications. Public-key cryptographic techniques are now in widespread use, especially in the financial services industry, in the public sector, and by individuals for their personal privacy, such as in electronic mail. This Handbook will serve as a valuable reference for the novice as well as for the expert who needs a wider scope of coverage within the area of cryptography. It is a necessary and timely guide for professionals who practice the art of cryptography.

The Handbook of Applied Cryptography provides a treatment that is multifunctional:

Now in its third printing, this is the definitive cryptography reference that the novice as well as experienced developers, designers, researchers, engineers, computer scientists, and mathematicians alike will use.

## Table of Contents

Foreword by Ronald L. Rivest

Overview of Cryptography

Introduction

Information security and cryptography

Background on functions

Functions(1-1, one-way, trapdoor one-way)

Permutations

Involutions

Basic terminology and concepts

Symmetric-key encryption

Overview of block ciphers and stream ciphers

Substitution ciphers and transposition ciphers

Composition of ciphers

Stream ciphers

The key space

Digital signatures

Authentication and identification

Identification

Data origin authentication

Public-key cryptography

Public-key encryption

The necessity of authentication in public-key systems

Digital signatures from reversible public-key encryption

Symmetric-key versus public-key cryptography

Hash functions

Protocols and mechanisms

Key establishment, management, and certification

Key management through symmetric-key techniques

Key management through public-key techniques

Trusted third parties and public-key certificates

Pseudorandom numbers and sequences

Classes of attacks and security models

Attacks on encryption schemes

Attacks on protocols

Models for evaluating security

Perspective for computational security

Notes and further references

Mathematical Background

Probability theory

Basic definitions

Conditional probability

Random variables

Binomial distribution

Birthday attacks

Random mappings

Information theory

Entropy

Mutual information

Complexity theory

Basic definitions

Asymptotic notation

Complexity classes

Randomized algorithms

Number theory

The integers

Algorithms in Z

The integers modulo n

Algorithms in Zn

The Legendre and Jacobi symbols

Blum integers

Abstract algebra

Groups

Rings

Fields

Polynomial rings

Vector spaces

Finite fields

Basic properties

The Euclidean algorithm for polynomials

Arithmetic of polynomials

Notes and further references

Number-Theoretic Reference Problems

Introduction and overview

The integer factorization problem

Trial division

Pollard's rho factoring algorithm

Pollard's p - 1 factoring algorithm

Elliptic curve factoring

Random square factoring methods

Quadratic sieve factoring

Number field sieve factoring

The RSA problem

The quadratic residuosity problem

Computing square roots in Zn

Case (i): n prime

Case (ii): n composite

The discrete logarithm problem

Exhaustive search

Baby-step giant-step algorithm

Pollard's rho algorithm for logarithms

Pohlig-Hellman algorithm

Index-calculus algorithm

Discrete logarithm problem in subgroups of Z*p

The Diffie-Hellman problem

Composite moduli

Computing individual bits

The discrete logarithm problem in Z*p - individual bits

The RSA problem - individual bits

The Rabin problem - individual bits

The subset sum problem

The L3-Iattice basis reduction algorithm

Solving subset sum problems of low density

Simultaneous diophantine approximation

Factoring polynomials over finite fields

Square-free factorization

Beriekamp's Q-matrix algorithm

Notes and further references

Public-Key Parameters

Introduction

Generating large prime numbers naively

Distribution of prime numbers

Probabilistic primality tests

Fermat's test

Solovay-Strassen test

Miller-Rabin test

Comparison: Fermat, Solovay-Strassen and Miller-Rabin

(True) Primality tests

Testing Mersenne numbers

Primality testing using the factorization of n - 1

Jacobi sum test

Tests using elliptic curves

Prime number generation

Random search for probable primes

Strong primes

NIST method for generating DSA primes

Constructive techniques for provable primes

Irreducible polynomials over Zp

Irreducible polynomials

Irreducible trinomials

Primitive polynomials

Generators and elements of high order

Selecting a prime p and generator of Z*p

Notes and further references

Pseudorandom Bits and Sequences

Introduction

Classification and framework

Random bit generation

Pseudorandom bit generation

ANSI X9.17

FIPS 186

Statistical tests

The normal and chi-square distributions

Hypothesis testing

Golomb's randomness postulates

Five basic tests

Maurer's universal statistical test

Cryptographically secure pseudorandom bit generation

RSA pseudorandom bit generator

Blum-Blum-Shub pseudorandom bit generator

Notes and further references

Stream Ciphers

Introduction

Classification

Feedback shift registers

Linear feedback shift registers

Linear complexity

Berlekamp-Massey algorithm

Nonlinear feedback shift registers

Stream ciphers based on LFSRs

Nonlinear combination generators

Nonlinear filter generators

Clock-controlled generators

Other stream ciphers

SEAL

Notes and further references

Block Ciphers

Introduction and overview

Background and general concepts

Introduction to block ciphers

Modes of operation

Exhaustive key search and multiple encryption

Classical ciphers and historical development

Transposition ciphers

Substitution ciphers

Polyalphabetic substitutions and Vigenère ciphers

Polyalphabetic cipher machines and rotors (historical)

Cryptanalysis of classical ciphers

DES

Product ciphers and Feistel ciphers

DES algorithm

DES properties and strength

FEAL

IDEA

SAFER, RC5, and other block ciphers

SAFER

RC5

Other block ciphers

Notes and further references

Public-Key Encryption

Introduction

Basic principles

RSA public-key encryption

Description

Security of RSA

RSA encryption in practice

Rabin public-key encryption

ElGamal public-key encryption

Basic ElGamal encryption

Generalized ElGamal encryption

McEliece public-key encryption

Knapsack public-key encryption

Merkle-Hellman knapsack encryption

Chor-Rivest knapsack encryption

Probabilistic public-key encryption

Goldwasser-Micali probabilistic encryption

Blum-Goldwasser probabilistic encryption

Plaintext-aware encryption

Notes and further references

Hash Functions and Data Integrity

Introduction

Classification and framework

General classification

Basic properties and definitions

Hash properties required for specific applications

One-way functions and compression functions

Relationships between properties

Other hash function properties and applications

Basic constructions and general results

General model for iterated hash functions

General constructions and extensions

Formatting and initialization details

Security objectives and basic attacks

Bitsizes required for practical security

Unkeyed hash functions (MDCs)

Hash functions based on block ciphers

Customized hash functions based on MD4

Hash functions based on modular arithmetic

Keyed hash functions (MACS)

MACs based on block ciphers

Constructing MACs from MDCs

Customized MACs

MACs for stream ciphers

Data integrity and message authentication

Background and definitions

Non-malicious vs. malicious threats to data integrity

Data integrity using a MAC alone

Data integrity using an MDC and an authentic channel

Data integrity combined with encryption

Advanced attacks on hash functions

Birthday attacks

Pseudo-collisions and compression function attacks

Chaining attacks

Attacks based on properties of underlying cipher

Notes and further references

Identification and Entity Authentication

Introduction

Identification objectives and applications

Properties of identification protocols

Passwords (weak authentication)

Fixed password schemes: techniques

Fixed password schemes: attacks

Case study - UNIX passwords

PINs and passkeys

One-time passwords (towards strong authentication)

Challenge-response identification (strong authentication)

Background on time-variant parameters

Challenge-response by symmetric-key techniques

Challenge-response by public-key techniques

Customized and zero-knowledge identification protocols

Overview of zero-knowledge concepts

Feige-Fiat-Shamir identification protocol

GQ identification protocol

Schnorr identification protocol

Comparison: Fiat-Shamir, GQ, and Schnorr

Attacks on identification protocols

Notes and further references

Digital Signatures

Introduction

A framework for digital signature mechanisms

Basic definitions

Digital signatures schemes with appendix

Digital signature schemes with message recovery

Types of attacks on signature schemes

RSA and related signature schemes

The RSA signature scheme

Possible attacks on RSA signatures

RSA signatures in practice

The Rabin public-key signature scheme

ISO/lEC 9796 formatting

PKCS #1 formatting

Fiat-Shamir signature schemes

Feige-Fiat-Shamir signature scheme

GQ signature scheme

The DSA and related signature schemes

The Digital Signature Algorithm (DSA)

The ElGamal signature scheme

The generalized ElGamal signature scheme

The Schnorr signature scheme

The ElGamal signature scheme with message recovery

One-time digital signatures

The Rabin one-time signature scheme

The Merkle one-time signature scheme

Authentication trees and one-time signatures

The GMR one-time signature scheme

Other signature schemes

Arbitrated digital signatures

ESIGN

Signatures with additional functionality

Blind signature schemes

Undeniable signature schemes

Fail-stop signature schemes

Notes and further references

Key Establishment Protocols

Introduction

Classification and framework

General classification and fundamental concepts

Objectives and properties

Assumptions and adversaries in key establishment protocols

Key transport based on symmetric encryption

Symmetric key transport and derivation without a server

Kerberos and related server-based protocols

Key agreement based on symmetric techniques

Key transport based on public-key encryption

Key transport using PK encryption without signatures

Protocols combining PK encryption and signatures

Hybrid key transport protocols using PK encryption

Key agreement based on asymmetric techniques

Diffie-Hellman and related key agreement protocols

Implicitly-certified public keys

Diffie-Hellman protocols using implicitly certified keys

Secret sharing

Simple shared control schemes

Threshold schemes

Generalized secret sharing

Conference keying

Analysis of key establishment protocols

Attack strategies and classic protocol flaws

Analysis objectives and methods

Notes and further references

Key Management Techniques

Introduction

Background and basic concepts

Classifying keys by algorithm type and intended use

Key management objectives, threats, and policy

Simple key establishment models

Roles of third parties

Tradeoffs among key establishment protocols

Techniques for distributing confidential keys

Key layering and cryptoperiods

Key translation centers and symmetric-key certificates

Techniques for distributing public keys

Authentication trees

Public-key certificates

Identity-based systems

Implicitly certified public keys

Comparison of techniques for distributing public keys

Techniques for controlling key usage

Key separation and constraints on key usage

Techniques for controlling use of symmetric keys

Key management involving multiple domains

Trust between two domains

Trust models involving multiple certification authorities

Certificate distribution and revocation

Key life cycle issues

Lifetime protection requirements

Key management life cycle

Advanced trusted third party services

Trusted timestamping service

Non-repudiation and notarization of digital signatures

Key escrow

Notes and further references

Efficient Implementation

Introduction

Multiple-precision integer arithmetic

Radix representation

Addition and subtraction

Multiplication

Squaring

Division

Multiple-precision modular arithmetic

Classical modular multiplication

Montgomery reduction

Barrett reduction

Reduction methods for moduli of special form

Greatest common divisor algorithms

Binary gcd algorithm

Lehmer's gcd algorithm

Binary extended gcd algorithm

Chinese remainder theorem for integers

Residue number systems

Garner's algorithm

Exponentiation

Basic techniques for exponentiation

Fixed-exponent exponentiation algorithms

Fixed-base exponentiation algorithms

Exponent recoding

Signed-digit representation

String-replacement representation

Notes and further references

Patents and Standards

Introduction

Patents on cryptographic techniques

Five fundamental patents

Ten prominent patents

Ten selected patents

Ordering and acquiring patents

Cryptographic standards

International standards - cryptographic techniques

Banking security standards (ANSI, ISO)

International security architectures and frameworks

U.S. government standards (FIPS)

Industry standards and RFCs

De facto standards

Ordering and acquiring standards

Notes and further references

A. Bibliography of Papers from Selected Cryptographic Forums

Asiacrypt/Auscrypt Proceedings

Crypto Proceedings

Eurocrypt Proceedings

Fast Software Encryption Proceedings

Journal of Cryptology papers

References

Index

## Author(s)

### Biography

Alfred J Menezes, Paul C. van Oorschot, Scott A. Vanstone

## Reviews

"…very well suited for the reader who wants an encyclopedic description of the state of the art of applied modern cryptography."

-Mathematical Reviews, Issue 99g

"[This book] is an incredible achievement. … [T]he handbook is complete. If I want to check what problems there were with a proposed system, determine how the variations on a particular algorithm developed, see what research preceded and followed an idea, I go to the Handbook. The Handbook has accurate, clear, and correct information. It is wonderful. … If I were limited to only one cryptography text on my shelves, it would be the Handbook of Applied Cryptography."

- Bulletin of the AMS