Handbook of Applied Cryptography: 1st Edition (Hardback) book cover

Handbook of Applied Cryptography

1st Edition

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

CRC Press

810 pages

Purchasing Options:$ = USD
Hardback: 9780849385230
pub: 1996-10-16
SAVE ~$22.00

FREE Standard Shipping!


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:

  • It serves as an introduction to the more practical aspects of both conventional and public-key cryptography

  • It is a valuable source of the latest techniques and algorithms for the serious practitioner

  • It provides an integrated treatment of the field, while still presenting each major topic as a self-contained unit

  • It provides a mathematical treatment to accompany practical discussions

  • It contains enough abstraction to be a valuable reference for theoreticians while containing enough detail to actually allow implementation of the algorithms discussed

    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.

  • 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

    Table of Contents

    Foreword by Ronald L. Rivest

    Overview of Cryptography


    Information security and cryptography

    Background on functions

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



    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


    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


    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




    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


    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


    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



    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


    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


    Product ciphers and Feistel ciphers

    DES algorithm

    DES properties and strength



    SAFER, RC5, and other block ciphers



    Other block ciphers

    Notes and further references

    Public-Key Encryption


    Basic principles

    RSA public-key encryption


    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


    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


    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


    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


    Signatures with additional functionality

    Blind signature schemes

    Undeniable signature schemes

    Fail-stop signature schemes

    Notes and further references

    Key Establishment Protocols


    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


    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


    Multiple-precision integer arithmetic

    Radix representation

    Addition and subtraction




    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


    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


    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



    About the Series

    Discrete Mathematics and Its Applications

    Learn more…

    Subject Categories

    BISAC Subject Codes/Headings:
    COMPUTERS / Operating Systems / General
    COMPUTERS / Security / General
    MATHEMATICS / General
    MATHEMATICS / Combinatorics