Handbook of Applied Cryptography: (Discrete Mathematics and Its Applications)

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.

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

Review :
"…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