22-05-2012, 03:00 PM
Handbook of Applied Cryptography
Handbook of Applied Cryptography.pdf (Size: 480.34 KB / Downloads: 24)
Introduction and overview
Symmetric-key block ciphers are the most prominent and important elements in many cryptographic
systems. Individually, they provide confidentiality. As a fundamental building
block, their versatility allows construction of pseudorandom number generators, stream ciphers,
MACs, and hash functions. They may furthermore serve as a central component in
message authentication techniques, data integrity mechanisms, entity authentication protocols,
and (symmetric-key)digital signature schemes. This chapter examines symmetric-key
block ciphers, including both general concepts and details of specific algorithms. Publickey
block ciphers are discussed in Chapter 8.
No block cipher is ideally suited for all applications, even one offering a high level of
security. This is a result of inevitable tradeoffs required in practical applications, including
those arising from, for example, speed requirements and memory limitations (e.g., code
size, data size, cache memory), constraints imposed by implementation platforms (e.g.,
hardware, software, chipcards), and differing tolerances of applications to properties of various
modes of operation. In addition, efficiencymust typically be traded off against security.
Thus it is beneficial to have a number of candidate ciphers from which to draw.
Of the many block ciphers currently available, focus in this chapter is given to a subset
of high profile and/or well-studied algorithms. While not guaranteed to be more secure
than other published candidate ciphers (indeed, this status changes as new attacks become
known), emphasis is given to those of greatest practical interest. Among these, DES is
paramount; FEAL has received both serious commercial backing and a large amount of independent
cryptographic analysis; and IDEA (originally proposed as aDES replacement) is
widely known and highly regarded. Other recently proposed ciphers of both high promise
and high profile (in part due to the reputation of their designers) are SAFER and RC5. Additional
ciphers are presented in less detail.
Chapter outline
Basic background on block ciphers and algorithm-independent concepts are presented in
x7.2, including modes of operation, multiple encryption, and exhaustive search techniques.
Classical ciphers and cryptanalysis thereof are addressed in x7.3, including historical details
on cipher machines. Modern block ciphers covered in chronological order are DES (x7.4),
FEAL (x7.5), and IDEA (x7.6), followed by SAFER, RC5, and other ciphers in x7.7, collectively
illustrating a wide range of modern block cipher design approaches. Further notes,
including details on additional ciphers (e.g., Lucifer) and references for the chapter, may be
found in x7.8.
Background and general concepts
Introductory material on block ciphers is followed by subsections addressing modes of operation,
and discussion of exhaustive key search attacks and multiple encryption.
7.2.1 Introduction to block ciphers
Block ciphers can be either symmetric-key or public-key. The main focus of this chapter is
symmetric-key block ciphers; public-key encryption is addressed in Chapter
(i) Block cipher definitions
A block cipher is a function (see x1.3.1) which maps n-bit plaintext blocks to n-bit ciphertext
blocks; n is called the blocklength. It may be viewed as a simple substitution cipher
with large character size. The function is parameterized by a k-bit key K,1 taking values
from a subset K (the key space) of the set of all k-bit vectors Vk. It is generally assumed
that the key is chosen at random. Use of plaintext and ciphertext blocks of equal size avoids
data expansion.
To allow unique decryption, the encryption function must be one-to-one (i.e., invertible).
For n-bit plaintext and ciphertext blocks and a fixed key, the encryption function is
a bijection, defining a permutation on n-bit vectors. Each key potentially defines a different
bijection. The number of keys is jKj, and the effective key size is lg jKj; this equals the
key length if all k-bit vectors are valid keys (K = Vk). If keys are equiprobable and each
defines a different bijection, the entropy of the key space is also lg jKj.
Definition
An n-bit block cipher is a function E : Vn K ! Vn, such that for each
key K 2 K, E(P;K) is an invertible mapping (the encryption function for K) from Vn
to Vn, written EK(P). The inverse mapping is the decryption function, denoted DK©.
C = EK(P) denotes that ciphertext C results from encrypting plaintext P under K.
Whereas block ciphers generally process plaintext in relatively large blocks (e.g., n
64), stream ciphers typically process smaller units (see Note 6.1); the distinction, however,
is not definitive (see Remark 7.25). For plaintext messages exceeding one block