Cryptography: Theory and Practice:The Data Encryption Standard

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210   Pub Date: 03/17/95  

Previous

Table of Contents

Next

Chapter 3
The Data Encryption Standard

3.1 Introduction

On May 15, 1973, the National Bureau of Standards published a solicitation for cryptosystems in the Federal Register. This lead ultimately to the development of the Data Encryption Standard, or DES, which has become the most widely used cryptosystem in the world. DES was developed at IBM, as a modification of an earlier system known as LUCIFER. DES was first published in the Federal Register of March 17, 1975. After a considerable amount of public discussion, DES was adopted as a standard for “unclassified” applications on January 15, 1977. DES has been reviewed by the National Bureau of Standards (approximately) every five years since its adoption. Its most recent renewal was in January 1994, when it was renewed until 1998. It is anticipated that it will not remain a standard past 1998.

3.2 Description of DES

A complete description of DES is given in the Federal Information Processing Standards Publication 46, dated January 15, 1977. DES encrypts a plaintext bitstring x of length 64 using a key K which is a bitstring of length 56, obtaining a ciphertext bitstring which is again a bitstring of length 64. We first give a “high-level” description of the system.

The algorithm proceeds in three stages:

1.  Given a plaintext x, a bitstring x₀ is constructed by permuting the bits of x according to a (fixed) initial permutation IP. We write x₀ = IP (x) = L₀R₀, where L₀ comprises the first 32 bits of x₀ and R₀ the last 32 bits.

2.  16 iterations of a certain function are then computed. We compute L_iR_i,

Figure 3.1  One round of DES encryption

1 ≤ i ≤ 16, according to the following rule:

where ⊕ denotes the exclusive-or of two bitstrings. f is a function that we will describe later, and K₁, K₂, . . . , K₁₆ are each bitstrings of length 48 computed as a function of the key K. (Actually, each K_i is a permuted selection of bits from K.) K₁, K₂, . . . , K₁₆ comprises the key schedule. One round of encryption is depicted in Figure 3.1

3.  Apply the inverse permutation IP^-1 to the bitstring R₁₆L₁₆, obtaining the ciphertext y. That is, y = IP^-1(R₁₆L₁₆). Note the inverted order of L₁₆ and R₁₆.

The function f takes as input a first argument A, which is a bitstring of length 32, and a second argument J that is a bitstring of length 48, and produces as output a bitstring of length 32. The following steps are executed.

1.  The first argument A is “expanded” to a bitstring of length 48 according to a fixed expansion function E. E(A) consists of the 32 bits from A, permuted in a certain way, with 16 of the bits appearing twice.

Figure 3.2  The DES f function

2.  Compute E(A) ⊕ J and write the result as the concatenation of eight 6-bit strings B = B₁B₂B₃B₄B₅B₆B₇B₈.

3.  The next step uses eight S-boxes S₁, . . . , S₈. Each S_i is a fixed 4 × 16 array whose entries come from the integers 0 - 15. Given a bitstring of length six, say B_j = b₁b₂b₃b₄b₅b₆, we compute S_j(B_j) as follows. The two bits b₁b₆ determine the binary representation of a row r of S_j (0 ≤ r ≤ 3), and the four bits b₂b₃b₄b₅ determine the binary representation of a column c of S_j (0 ≤ c ≤ 15). Then S_j(B_j) is defined to be the entry S_j(r, c), written in binary as a bitstring of length four. (Hence, each S_j can be thought of as a function that accepts as input a bitstring of length two and one of length four, and produces as output a bitstring of length four.) In this fashion, we compute C_j = S_j(B_j), 1 ≤ j ≤ 8.

4.  The bitstring C = C₁C₂C₃C₄C₅C₆C₇C₈ of length 32 is permuted according to a fixed permutation P. The resulting bitstring P(C) is defined to be f(A, J).

The f function is depicted in Figure 3.2. Basically, it consists of a substitution (using an S-box) followed by the (fixed) permutation P. The 16 iterations of f comprise a product cryptosystem, as described in Section 2.5.

Previous

Table of Contents

Next

---

Copyright © CRC Press LLC