Encryption/Decryption Mechanisms

This chapter specifies the (cryptographic) encryption/decryption mechanisms supported by DCE. Currently, only one such mechanism is supported, namely the Data Encryption Standard (DES) (or Data Encryption Algorithm (DEA)), and its Cipher Block Chaining (CBC) Mode of Operation, so this whole chapter is devoted to that.

Note:

This chapter is based on, and (unless stated otherwise) is technically aligned with, ANSI X3.92 and ANSI X3.106. However, for editorial reasons, this chapter stands independently, and no familiarity with those documents is required. (Thus, the part of this chapter that duplicates information in the cited documents is intended to be technically equivalent to those documents, rewritten for the expository purposes of DCE, and any technical discrepancies between the two are inadvertent and to be reconciled.)

Basic DES

In the context of DES, a bit-vector of length 64 to be encrypted or decrypted is called a (DES) block. For terminology, notation and conventions regarding sequences of bits, see Checksum Mechanisms . In particular, when bit-sequences (especially, bytes) are interpreted as integers in this chapter, the big-endian mapping is always used. (This chapter does not interpret byte-sequences as integers, so their endianness should be considered.)

The "basic DES" algorithm (specified in detail in Details of Basic DES Algorithm ) is an encryption mechanism, parameterised by a 64-bit vector, K, taking single-block plaintext inputs, P, and producing single-block ciphertext outputs, Q, for which the following notation is adopted:

 

Q = DES(K, P)

The corresponding (inverse) decryption mechanism is denoted:

 

P = DES-1(K, Q)

The bit vector K = <k₀, ···, k₆₃>, while nominally 64 bits long, has only 56 active (that is, "cryptographically significant") bits, in the sense that while the algorithm defining DES makes sense for an arbitrary 64-bit vector K, the algorithm ignores K's 8 passive bits k_j, j equivalence 7 (mod 8), which are the low-order bits (not the high-order bits, notably) of the 8 bytes of K; similarly for the algorithm defining DES^-1. In other words, the DES algorithm makes active use of only 56 of K's bits, namely the 56 bits k_j for j '/equivalence' 7 (mod 8). By definition, a 64-bit vector K is said to be a DES key if it has odd parity; that is, if every byte of K, <k_8j+0, ···, k_8j+7> (0 <= k <= 7), has odd bit sum (mod 2)-k_8j+0 + ··· + k_8j+7 equivalence 1 (mod 2). Obviously, the 8 passive bits of an arbitrary 64-bit vector K can always be uniquely chosen such that the resulting 64-bit vector, K´ say, has odd parity (in this context, K's passive bits are also called its parity bits); of course, as observed above, DES(K, P) = DES(K´, P) for all plaintexts P. K´ is then called the (unique) (odd-parity) normal form of K. When explicit DES keys are written down in DCE, they are always expressed as 8-byte vectors (never as integers) in their odd-parity normal form.

Note:

As a practical matter, note that even though the DES algorithm itself defining DES(K, P) makes sense for an arbitrary 64-bit vector K, some implementations check for parity, rejecting any key that is not a DES key (that is, does not have odd parity).

CBC Mode

The CBC mode of DES (specified in detail in Details of CBC Mode Algorithm ) is an extension of the basic DES algorithm, for the purpose of encrypting and decrypting bit-sequences of length a (strictly) positive multiple of 64 (that is, a positive number of blocks). It is parameterised not only by the key K, but also by a 64-bit initialisation vector (or seed), IV (all of whose bits are "active"). DES CBC encryption is denoted by:

 

Q = DES-CBC(K, IV, P)

and its corresponding decryption by:

 

P = DES-CBC-1(K, IV, Q)

The length of Q is the same as that of P.

Note:

As seen in Details of CBC Mode Algorithm , the role of the initialisation vector is to "initialise" the CBC algorithm, by using it to "scramble" the first block of plaintext. There are two common ways to use initialisation vectors, both of which are actually used in this specification:

1. The first common usage is as confounders. In this usage, initialisation vectors are chosen randomly, so that knowledge of common patterns that are present in the first blocks of many plaintexts (that is, "known plaintexts", such as occur in standard headers of protocol data units) cannot potentially be used in a cryptanalytic attack. Thus, in this usage, the initialisation vector improves the CBC algorithm's "ergodicity" (but does not increase the size of the DES key space). For examples of the usage of initialisation vectors as confounders, see Registered Checksum Types and Registered Encryption Types .

2. The second common usage is as links of chains, whereby complex messages can be encrypted in pieces, yet the end result is the same as if the whole message had been encrypted monolithically, as a consequence of the chaining property stated in Composition Laws (Chaining Properties) . For examples of the usage of initialisation vectors as links in chains, see CL dce_c_authn_level_privacy and CO dce_c_authn_level_pkt_privacy .

X3.106 itself does not specify any standard way to encrypt/decrypt plaintext/ciphertext of length other than a positive multiple of 64 (bits), merely stating that "the final partial data block should be encrypted in a manner specified for the application". Accordingly, DCE adopts the following convention. The meaning of (DES) padding is a bit-vector R of minimal length appended to a given bit vector M in order to bring the total bit-length of <M, R> up to a positive multiple of 64. Note that the bit-length of R, lambda(R), is either 64 (in the case lambda(M) = 0) or (-lambda(M))(mod 64) (in the case lambda(M) > 0). In DCE, the DES padding required in a given situation will usually be explicitly specified. Nevertheless, it is convenient to also specify a default padding vector. Therefore, unless stated otherwise, DCE takes the (DES) padding vector R be a 0-vector of the appropriate length. Notationally, if P is a plaintext (or Q is a ciphertext) of length other than a positive multiple of 64, the following is defined:

• DES-CBC(K, IV, P) = DES-CBC(K, IV, <P, <0, ···, 0>>)

• DES-CBC^-1(K, IV, Q) = DES-CBC^-1(K, IV, <Q, <0, ···, 0>>)

When the initialisation vector IV is the (64-bit) 0-vector <0, ···, 0> (consisting entirely of "0" bits), the term IV is sometimes omitted from the above notations:

• DES-CBC(K, P) = DES-CBC(K, <0, ···, 0>, P)

• DES-CBC^-1(K, Q) = DES-CBC^-1(K, <0, ···, 0>, Q)

DES-CBC Checksum

The DES-CBC checksum of a plaintext P, with respect to a key K and an initialisation vector IV, is by definition the final block of DES-CBC(K, IV, P). It is denoted:

 

DES-CBC-CKSUM(K, IV, P)

It differs from MD4 and MD5(P) in being key- (and initialisation vector-)based, and in being only 8 bytes long instead of 16. When IV is a 0-vector, it is sometimes omitted from the notation:

 

DES-CBC-CKSUM(K, P)

Composition Laws (Chaining Properties)

The following DES composition laws or chaining properties are immediately seen to follow from the detailed description of the CBC mode algorithm given in Details of CBC Mode Algorithm . For vectors of blocks P and P´ of positive length:

• DES-CBC(K, IV, <P, P´>) =
  <DES-CBC(K, IV, P), DES-CBC(K, DES-CBC-CKSUM(K, IV, P), P´)>

• DES-CBC-CKSUM(K, IV, <P, P´>) =
  DES-CBC-CKSUM(K, DES-CBC-CKSUM(K, IV, P), P´)

Keys to be Avoided

There are certain DES keys (64 of them, in normal form) that "should be" avoided in any use of DES encryption, because they have poor cryptographic characteristics. Some of these are called weak keys, some are called semi-weak keys, and there are some others with no generally accepted moniker but which are called here possibly weak keys (rigorous definitions are given below). The complete list of such keys are listed below.

Note:

To say that the keys in question "should be" avoided means, for the purposes of DCE, that it is recommended (though not required) that implementations not generate these keys as session, conversation or long-term keys; in particular, implementations should reject passwords that map to these keys (via the password-to-key mappings specified in Registered Password-to-Key Mappings ). However, all implementations are required to accept all keys generated by other implementations (for interoperability with implementations that do generate the keys that should be avoided).

There is no mention of these keys in ANSI X3.92 (though they have been noted elsewhere in the literature).

The rigorous definition of key weakness is as follows. As seen in the remainder of this chapter, the cryptographic strength of DES depends on the "complexity" (measured by the involvement of the S-boxes-see Rounds (T): Cipher Function (F), Expansion (E), Permutation (P) and Selection/Substitution (S) ) of the algorithm defining it. That algorithm involves, among other things, manipulating the key, K, via the key schedule subalgorithm, to generate 16 48-bit subkeys, K₀, ···, K₁₅. Define the strength of K, denoted sigma(K), to be the cardinality (number of elements) of this set of subkeys. If sigma(K) >= sigma(K´), then the DES algorithm for K is more complex than that for K´, so K is said to be stronger than K´. Obviously 1 <= sigma(K) <= 16, and the strongest keys are those for which sigma(K) = 16; that is, those for which the subkeys K_i are all distinct, because that maximises the overall complexity of the DES algorithm. Using this measure of strength, the rigorous definitions of weak, semi-weak and possibly weak keys are that sigma(K) = 1, 2 and 4, respectively.

Note that the weak and semi-weak keys have the following characteristics. The weak keys K are those for which encryption is the same as decryption: DES(K, B) = DES^-1(K, B) for every block B. The semi-weak keys K are those for which there exists another key K´ != K which gives identical encryption and decryption: DES(K, B) = DES(K´, B) and DES^-1(K, B) = DES^-1(K´, B) for all blocks B-hence, K´ can decrypt any message encrypted by K, and vice versa.

Weak Keys

The following are the 4 (normal form) weak keys:

 

<0x01,0x01,0x01,0x01,0x01,0x01,0x01,0x01>
<0x1f,0x1f,0x1f,0x1f,0x0e,0x0e,0x0e,0x0e>
<0xe0,0xe0,0xe0,0xe0,0xf1,0xf1,0xf1,0xf1>
<0xfe,0xfe,0xfe,0xfe,0xfe,0xfe,0xfe,0xfe>

Semi-Weak Keys

The following are the 12 (normal form) semi-weak keys:

<0x01,0x1f,0x01,0x1f,0x01,0x0e,0x01,0x0e>
<0x01,0xe0,0x01,0xe0,0x01,0xf1,0x01,0xf1>
<0x01,0xfe,0x01,0xfe,0x01,0xfe,0x01,0xfe>
<0x1f,0x01,0x1f,0x01,0x0e,0x01,0x0e,0x01>
<0x1f,0xe0,0x1f,0xe0,0x0e,0xf1,0x0e,0xf1>
<0x1f,0xfe,0x1f,0xfe,0x0e,0xfe,0x0e,0xfe>
<0xe0,0x01,0xe0,0x01,0xf1,0x01,0xf1,0x01>
<0xe0,0x1f,0xe0,0x1f,0xf1,0x0e,0xf1,0x0e>
<0xe0,0xfe,0xe0,0xfe,0xf1,0xfe,0xf1,0xfe>
<0xfe,0x01,0xfe,0x01,0xfe,0x01,0xfe,0x01>
<0xfe,0x1f,0xfe,0x1f,0xfe,0x0e,0xfe,0x0e>
<0xfe,0xe0,0xfe,0xe0,0xfe,0xf1,0xfe,0xf1>

Possibly Weak Keys

The following are the 48 (normal form) possibly weak keys:

<0x01,0x01,0x1f,0x1f,0x01,0x01,0x0e,0x0e>
<0x01,0x01,0xe0,0xe0,0x01,0x01,0xf1,0xf1>
<0x01,0x01,0xfe,0xfe,0x01,0x01,0xfe,0xfe>
<0x01,0x1f,0x1f,0x01,0x01,0x0e,0x0e,0x01>
<0x01,0x1f,0xe0,0xfe,0x01,0x0e,0xf1,0xfe>
<0x01,0x1f,0xfe,0xe0,0x01,0x0e,0xfe,0xf1>
<0x01,0xe0,0x1f,0xfe,0x01,0xf1,0x0e,0xfe>
<0x01,0xe0,0xe0,0x01,0x01,0xf1,0xf1,0x01>
<0x01,0xe0,0xfe,0x1f,0x01,0xf1,0xfe,0x0e>
<0x01,0xfe,0x1f,0xe0,0x01,0xfe,0x0e,0xf1>
<0x01,0xfe,0xe0,0x1f,0x01,0xfe,0xf1,0x0e>
<0x01,0xfe,0xfe,0x01,0x01,0xfe,0xfe,0x01>
<0x1f,0x01,0x01,0x1f,0x0e,0x01,0x01,0x0e>
<0x1f,0x01,0xe0,0xfe,0x0e,0x01,0xf1,0xfe>
<0x1f,0x01,0xfe,0xe0,0x0e,0x01,0xfe,0xf1>
<0x1f,0x1f,0x01,0x01,0x0e,0x0e,0x01,0x01>
<0x1f,0x1f,0xe0,0xe0,0x0e,0x0e,0xf1,0xf1>
<0x1f,0x1f,0xfe,0xfe,0x0e,0x0e,0xfe,0xfe>
<0x1f,0xe0,0x01,0xfe,0x0e,0xf1,0x01,0xfe>
<0x1f,0xe0,0xe0,0x1f,0x0e,0xf1,0xf1,0x0e>
<0x1f,0xe0,0xfe,0x01,0x0e,0xf1,0xfe,0x01>
<0x1f,0xfe,0x01,0xe0,0x0e,0xfe,0x01,0xf1>
<0x1f,0xfe,0xe0,0x01,0x0e,0xfe,0xf1,0x01>
<0x1f,0xfe,0xfe,0x1f,0x0e,0xfe,0xfe,0x0e>
<0xe0,0x01,0x01,0xe0,0xf1,0x01,0x01,0xf1>
<0xe0,0x01,0x1f,0xfe,0xf1,0x01,0x0e,0xfe>
<0xe0,0x01,0xfe,0x1f,0xf1,0x01,0xfe,0x0e>
<0xe0,0x1f,0x01,0xfe,0xf1,0x0e,0x01,0xfe>
<0xe0,0x1f,0x1f,0xe0,0xf1,0x0e,0x0e,0xf1>
<0xe0,0x1f,0xfe,0x01,0xf1,0x0e,0xfe,0x01>
<0xe0,0xe0,0x01,0x01,0xf1,0xf1,0x01,0x01>
<0xe0,0xe0,0x1f,0x1f,0xf1,0xf1,0x0e,0x0e>
<0xe0,0xe0,0xfe,0xfe,0xf1,0xf1,0xfe,0xfe>
<0xe0,0xfe,0x01,0x1f,0xf1,0xfe,0x01,0x0e>
<0xe0,0xfe,0x1f,0x01,0xf1,0xfe,0x0e,0x01>
<0xe0,0xfe,0xfe,0xe0,0xf1,0xfe,0xfe,0xf1>
<0xfe,0x01,0x01,0xfe,0xfe,0x01,0x01,0xfe>
<0xfe,0x01,0x1f,0xe0,0xfe,0x01,0x0e,0xf1>
<0xfe,0x01,0xe0,0x1f,0xfe,0x01,0xf1,0x0e>
<0xfe,0x1f,0x01,0xe0,0xfe,0x0e,0x01,0xf1>
<0xfe,0x1f,0x1f,0xfe,0xfe,0x0e,0x0e,0xfe>
<0xfe,0x1f,0xe0,0x01,0xfe,0x0e,0xf1,0x01>
<0xfe,0xe0,0x01,0x1f,0xfe,0xf1,0x01,0x0e>
<0xfe,0xe0,0x1f,0x01,0xfe,0xf1,0x0e,0x01>
<0xfe,0xe0,0xe0,0xfe,0xfe,0xf1,0xf1,0xfe>
<0xfe,0xfe,0x01,0x01,0xfe,0xfe,0x01,0x01>
<0xfe,0xfe,0x1f,0x1f,0xfe,0xfe,0x0e,0x0e>
<0xfe,0xfe,0xe0,0xe0,0xfe,0xfe,0xf1,0xf1>

Details of Basic DES Algorithm

Let K = <k₀, ···, k₆₃> be a DES key, and let P = <p₀, ···, p₆₃> be a plaintext DES block. The value of DES(K, P) will now be described as a functional composition of 33 (invertible) transformations from blocks to blocks, as follows:

DES(K, P) = (FP '+.2'°'-.2' T_K,15 '+.2'°'-.2' theta₁₄ '+.2'°'-.2' T_K,14 '+.2'°'-.2' theta₁₃ '+.2'°'-.2' ··· '+.2'°'-.2' T_K,1 '+.2'°'-.2' theta₀ '+.2'°'-.2' T_K,0 '+.2'°'-.2' IP)(P)

Of these 33 transformations, 15 of them are equal to the simple cyclic permutation (or transposition), theta_i = theta (0 <= i <= 14), which interchanges the left and right halfblocks of a block: if B = <L_B, R_B> where L_B and R_B are 32-bit vectors, then:

 

theta(B) = <RB, LB>

That is:

theta(<b₀, ···, b₆₃>) =

<b₃₂, ···, b₆₃, b₀, ···, b₃₁>

Initial Permutation (IP) and Final Permutation (FP)

The initial permutation, IP, mapping blocks to blocks, is defined as follows:

IP(<p₀, ···, p₆₃>) =

<p₅₇, p₄₉, p₄₁, p₃₃, p₂₅, p₁₇, p₉, p₁, p₅₉, p₅₁, p₄₃, p₃₅, p₂₇, p₁₉, p₁₁, p₃,
p₆₁, p₅₃, p₄₅, p₃₇, p₂₉, p₂₁, p₁₃, p₅, p₆₃, p₅₅, p₄₇, p₃₉, p₃₁, p₂₃, p₁₅, p₇,
p₅₆, p₄₈, p₄₀, p₃₂, p₂₄, p₁₆, p₈, p₀, p₅₈, p₅₀, p₄₂, p₃₄, p₂₆, p₁₈, p₁₀, p₂,
p₆₀, p₅₂, p₄₄, p₃₆, p₂₈, p₂₀, p₁₂, p₄, p₆₂, p₅₄, p₄₆, p₃₈, p₃₀, p₂₂, p₁₄, p₆>

The final permutation (or inverse initial permutation), FP, is defined to be the inverse of IP, FP = IP^-1, and is therefore given by:

FP(<q₀, ···, q₆₃>) =

<q₃₉, q₇, q₄₇, q₁₅, q₅₅, q₂₃, q₆₃, q₃₁, q₃₈, q₆, q₄₆, q₁₄, q₅₄, q₂₂, q₆₂, q₃₀,
q₃₇, q₅, q₄₅, q₁₃, q₅₃, q₂₁, q₆₁, q₂₉, q₃₆, q₄, q₄₄, q₁₂, q₅₂, q₂₀, q₆₀, q₂₈,
q₃₅, q₃, q₄₃, q₁₁, q₅₁, q₁₉, q₅₉, q₂₇, q₃₄, q₂, q₄₂, q₁₀, q₅₀, q₁₈, q₅₈, q₂₆,
q₃₃, q₁, q₄₁, q₉, q₄₉, q₁₇, q₅₇, q₂₅, q₃₂, q₀, q₄₀, q₈, q₄₈, q₁₆, q₅₆, q₂₄>

Note:

As seen in DES Decryption , IP and FP are the only two transformations among DES's 33 component transformations that are not self-inverse. This fact highlights the functional significance of IP and FP, but it does not explain the cryptographic significance of IP and FP-and indeed they appear to have no known cryptographic significance.

Key Schedule (KS): Permuted Choices (PC1, PC2) and Left Shift (LS)

The remaining transformations T_K,i depend on a key schedule of 16 48-bit subkeys K_i = K_K,i = KS(K, i) (0 <= i <= 15), which are defined as follows.

First, two 28-bit auxiliary vectors, C_K,-1 and D_K,-1, are defined by:

 

<CK,-1, DK,-1> = PC1(K)

where PC1 is the first permuted choice mapping from 64-bit (key) vectors to 56-bit (auxiliary) vectors, defined as follows:

PC1(<k₀, ···, k₆₃>) =

<k₅₆, k₄₈, k₄₀, k₃₂, k₂₄, k₁₆, k₈, k₀, k₅₇, k₄₉, k₄₁, k₃₃, k₂₅, k₁₇,
k₉, k₁, k₅₈, k₅₀, k₄₂, k₃₄, k₂₆, k₁₈, k₁₀, k₂, k₅₉, k₅₁, k₄₃, k₃₅,
k₆₂, k₅₄, k₄₆, k₃₈, k₃₀, k₂₂, k₁₄, k₆, k₆₁, k₅₃, k₄₅, k₃₇, k₂₉, k₂₁,
k₁₃, k₅, k₆₀, k₅₂, k₄₄, k₃₆, k₂₈, k₂₀, k₁₂, k₄, k₂₇, k₁₉, k₁₁, k₃>

Note, in particular, that PC1 "destroys" the passive bits of K (and this shows why they do not figure into the cryptographic properties of DES).

Now, the remaining 28-bit auxiliary vectors, C_K,i and D_K,i, and the subkeys K_i = K_K,i = KS(K, i), are defined by:

• C_K,i = LS_i(C_K,i-1)

• D_K,i = LS_i(D_K,i-1)

• K_i = K_K,i = KS(K, i) = PC2(<C_K,i, D_K,i>)

where LS_i is the (circular bitwise) left shift (or bitwise left rotation) mapping 28-bit vectors to 28-bit vectors:

LS_i(<e₀, ···, e₂₇>) = <e₀, ···, e₂₇> <<<< s_i

according to the shift schedule:

<s₀, ···, s₁₅> = <1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1>

and where PC2 is the second permuted choice mapping from 56-bit (auxiliary) vectors to 48-bit (subkey) vectors, defined as follows:

PC2(<l₀, ···, l₅₅>) =

<l₁₃, l₁₆, l₁₀, l₂₃, l₀, l₄, l₂, l₂₇, l₁₄, l₅, l₂₀, l₉,
l₂₂, l₁₈, l₁₁, l₃, l₂₅, l₇, l₁₅, l₆, l₂₆, l₁₉, l₁₂, l₁,
l₄₀, l₅₁, l₃₀, l₃₆, l₄₆, l₅₄, l₂₉, l₃₉, l₅₀, l₄₄, l₃₂, l₄₇,
l₄₃, l₄₈, l₃₈, l₅₅, l₃₃, l₅₂, l₄₅, l₄₁, l₄₉, l₃₅, l₂₈, l₃₁>

Rounds (T): Cipher Function (F), Expansion (E), Permutation (P) and Selection/Substitution (S)

With the subkeys K_i in hand, the rounds T_K,i, which map blocks to blocks, can now be defined as follows. Let B be a block, then by definition for 0 <= i <= 15 ("^" denoting bitwise boolean XOR of bit-vectors):

T_K,i(B) = <L_B ^ F_K,i(R_B), R_B>

where the cipher functions F_K,i (0 <= i <= 15) map 32-bit (halfblock) vectors to 32-bit (halfblock) vectors, and are defined by the formula (note this is the only place the subkeys K_i are used):

F_K,i(R) = P(S(K_i ^ E(R)))

with E, P and S defined immediately below.

E is the expansion mapping from 32-bit (halfblock) vectors to 48-bit (subkey) vectors given by:

E(<r₀, ···, r₃₁>) =

<r₃₁, r₀, r₁, r₂, r₃, r₄, r₃, r₄, r₅, r₆, r₇, r₈,
r₇, r₈, r₉, r₁₀, r₁₁, r₁₂, r₁₁, r₁₂, r₁₃, r₁₄, r₁₅, r₁₆,
r₁₅, r₁₆, r₁₇, r₁₈, r₁₉, r₂₀, r₁₉, r₂₀, r₂₁, r₂₂, r₂₃, r₂₄,
r₂₃, r₂₄, r₂₅, r₂₆, r₂₇, r₂₈, r₂₇, r₂₈, r₂₉, r₃₀, r₃₁, r₀>

P is the permutation mapping from 32-bit (halfblock) vectors to 32-bit (halfblock) vectors given by:

P(<t₀, ···, t₃₁>) =

<t₁₅, t₆, t₁₉, t₂₀, t₂₈, t₁₁, t₂₇, t₁₆,
t₀, t₁₄, t₂₂, t₂₅, t₄, t₁₇, t₃₀, t₉,
t₁, t₇, t₂₃, t₁₃, t₃₁, t₂₆, t₂, t₈,
t₁₈, t₁₂, t₂₉, t₅, t₂₁, t₁₀, t₃, t₂₄>

S is the selection/substitution mapping from 48-bit (subkey) vectors to 32-bit (halfblock) vectors defined as follows:

S(<z₀, ···, z₄₇>) =

<S₀(<z₀, ···, z₅>), S₁(<z₆, ···, z₁₁>), S₂(<z₁₂, ···, z₁₇>), S₃(<z₁₈, ···, z₂₃>),
S₄(<z₂₄, ···, z₂₉>), S₅(<z₃₀, ···, z₃₅>), S₆(<z₃₆, ···, z₄₁>), S₇(<z₄₂, ···, z₄₇>)>

In this expression, each submapping S_h (0 <= h <= 7) is a mapping of 6-bit vectors to 4-bit vectors, defined in terms of a 4code &#215;16 matrix, Sh (whose entry in its f^th row and g^th column, Sh[f,g] (0 <= f <= 3, 0 <= g <= 15), is a 4-bit vector (or, equivalently, an integer in the range [0, 15])), given by the rule:

S_h(<y₀, ···, y₅>) = Sh[<y₀, y₅>, <y₁, y₂, y₃, y₄>]

In this rule, the identification of 2-bit and of 4-bit vectors with integers is made via the big-endian mappings (namely, f = <u₀, u₁> = 2¹u₀ + 2⁰u₁ and g = <v₀, v₁, v₂, v₃> = 2³v₀ + 2²v₁ + 2¹v₂ + 2⁰v₃).

The matrices Sh (0 <= h <= 7) are called S-boxes. They lie at the very heart of DES, in the sense of being the major source of its complexity-besides greatly adding to the egodicity of DES, they comprise its only component of non-linearity (with respect to block space, the 64-dimensional vector space Fx₂'|xu'⁶⁴ over the bit field F₂). The S-boxes have the following values (in pseudocode):

S0 = {{14, 4,13, 1, 2,15,11, 8, 3,10, 6,12, 5, 9, 0, 7},
      { 0,15, 7, 4,14, 2,13, 1,10, 6,12,11, 9, 5, 3, 8},
      { 4, 1,14, 8,13, 6, 2,11,15,12, 9, 7, 3,10, 5, 0},
      {15,12, 8, 2, 4, 9, 1, 7, 5,11, 3,14,10, 0, 6,13}};

S1 = {{15, 1, 8,14, 6,11, 3, 4, 9, 7, 2,13,12, 0, 5,10},
      { 3,13, 4, 7,15, 2, 8,14,12, 0, 1,10, 6, 9,11, 5},
      { 0,14, 7,11,10, 4,13, 1, 5, 8,12, 6, 9, 3, 2,15},
      {13, 8,10, 1, 3,15, 4, 2,11, 6, 7,12, 0, 5,14, 9}};

S2 = {{10, 0, 9,14, 6, 3,15, 5, 1,13,12, 7,11, 4, 2, 8},
      {13, 7, 0, 9, 3, 4, 6,10, 2, 8, 5,14,12,11,15, 1},
      {13, 6, 4, 9, 8,15, 3, 0,11, 1, 2,12, 5,10,14, 7},
      { 1,10,13, 0, 6, 9, 8, 7, 4,15,14, 3,11, 5, 2,12}};

S3 = {{ 7,13,14, 3, 0, 6, 9,10, 1, 2, 8, 5,11,12, 4,15},
      {13, 8,11, 5, 6,15, 0, 3, 4, 7, 2,12, 1,10,14, 9},
      {10, 6, 9, 0,12,11, 7,13,15, 1, 3,14, 5, 2, 8, 4},
      { 3,15, 0, 6,10, 1,13, 8, 9, 4, 5,11,12, 7, 2,14}};

S4 = {{ 2,12, 4, 1, 7,10,11, 6, 8, 5, 3,15,13, 0,14, 9},
      {14,11, 2,12, 4, 7,13, 1, 5, 0,15,10, 3, 9, 8, 6},
      { 4, 2, 1,11,10,13, 7, 8,15, 9,12, 5, 6, 3, 0,14},
      {11, 8,12, 7, 1,14, 2,13, 6,15, 0, 9,10, 4, 5, 3}};

S5 = {{12, 1,10,15, 9, 2, 6, 8, 0,13, 3, 4,14, 7, 5,11},
      {10,15, 4, 2, 7,12, 9, 5, 6, 1,13,14, 0,11, 3, 8},
      { 9,14,15, 5, 2, 8,12, 3, 7, 0, 4,10, 1,13,11, 6},
      { 4, 3, 2,12, 9, 5,15,10,11,14, 1, 7, 6, 0, 8,13}};

S6 = {{ 4,11, 2,14,15, 0, 8,13, 3,12, 9, 7, 5,10, 6, 1},
      {13, 0,11, 7, 4, 9, 1,10,14, 3, 5,12, 2,15, 8, 6},
      { 1, 4,11,13,12, 3, 7,14,10,15, 6, 8, 0, 5, 9, 2},
      { 6,11,13, 8, 1, 4,10, 7, 9, 5, 0,15,14, 2, 3,12}};

S7 = {{13, 2, 8, 4, 6,15,11, 1,10, 9, 3,14, 5, 0,12, 7},
      { 1,15,13, 8,10, 3, 7, 4,12, 5, 6,11, 0,14, 9, 2},
      { 7,11, 4, 1, 9,12,14, 2, 0, 6,10,13,15, 3, 5, 8},
      { 2, 1,14, 7, 4,10, 8,13,15,12, 9, 0, 3, 5, 6,11}};

DES Decryption

It is true, but not quite obvious, that the DES transformation described above is invertible-nor is it obvious, assuming that it is invertible, how to compute its inverse. It will be proved that:

DES^-1(K, Q) = (FP '+.2'°'-.2' T_K,0 '+.2'°'-.2' theta '+.2'°'-.2' T_K,1 '+.2'°'-.2' theta '+.2'°'-.2' ··· '+.2'°'-.2' T_K,14 '+.2'°'-.2' theta '+.2'°'-.2' T_K,15 '+.2'°'-.2' IP)(Q)

Comparing this formula for DES^-1 to the formula defining DES, the situation can be paraphrased by saying: "DES^-1 is the `same' as DES, except that the schedule of subkeys is visited in reverse order".

To prove the formula for DES^-1, one notes first that:

DES^-1(K, Q) =

(FP '+.2'°'-.2' T_K,15 '+.2'°'-.2' theta '+.2'°'-.2' T_K,14 '+.2'°'-.2' theta '+.2'°'-.2' ··· '+.2'°'-.2' T_K,1 '+.2'°'-.2' theta '+.2'°'-.2' T_K,0 '+.2'°'-.2' IP)^-1(Q) =

(IP^-1 '+.2'°'-.2' Tx^-1'|xu'_K,0 '+.2'°'-.2' theta^-1 '+.2'°'-.2' Tx^-1'|xu'_K,1 '+.2'°'-.2' theta^-1 '+.2'°'-.2' ··· '+.2'°'-.2' Tx^-1'|xu'_K,14 '+.2'°'-.2' theta^-1 '+.2'°'-.2' Tx^-1'|xu'_K,15 '+.2'°'-.2' FP^-1)(Q)

Therefore, to prove the claimed formula, it suffices to observe the following inversion equalities:

• IP^-1 = FP

• FP^-1 = IP

• theta^-1 = theta

• Tx^-1'|xu'_K,i = T_K,i

The first three of these equalities are straightforward, and the fourth holds because for any block B:

T_K,i(T_K,i(B)) =

T_K,i(<L_B ^ F_K,i(R_B), R_B>) =

<(L_B ^ F_K,i(R_B)) ^ F_K,i(R_B), R_B> =

<L_B, R_B> =

B

assuming that U ^ U is a 0-vector for any bit-vector U, and U ^ V = U for any 0-vector V.

Details of CBC Mode Algorithm

Let P = <P₀, ···, P_n-1>, n >= 1, be a plaintext which has bit-length a positive multiple of 64, where each P_i is a block. Then the CBC mode encryption of P, Q = DES-CBC(K, IV, P), is defined as follows:

Q = <Q₀, ···, Q_n-1>

where:

• Q₀ = DES(K, IV ^ P₀)

• Q_i = DES(K, Q_i-1 ^ P_i) for 1 <= i <= n-1

The decryption, P = DES-CBC^-1(K, IV, Q) is given by:

• P₀ = IV ^ DES^-1(K, Q₀)

• P_i = Q_i-1 ^ DES^-1(K, Q_i) for 1 <= i <= n-1

These transformations are easily seen to be inverses of one another.