Previous section.
DCE 1.1: Authentication and Security Services
Copyright © 1997 The Open Group
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 bitvector 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 bitsequences
(especially, bytes) are interpreted as integers in this chapter, the
bigendian mapping is always used. (This chapter does not interpret
bytesequences 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 64bit vector,
K, taking singleblock plaintext inputs, P, and producing
singleblock 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_{0}, ···,
k_{63}>, 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
64bit vector K, the algorithm ignores K's 8 passive bits
k_{j}, j equivalence 7 (mod 8), which are the
loworder bits (not the highorder 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 64bit 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 64bit vector K can
always be uniquely chosen such that the resulting 64bit 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)
(oddparity) normal form of K.
When explicit DES keys are written down in DCE, they are always
expressed as 8byte vectors (never as integers) in their oddparity
normal form.
 Note:
 As a practical matter, note that even though the DES algorithm itself
defining DES(K, P) makes sense for an arbitrary 64bit 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 bitsequences 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 64bit
initialisation vector (or seed), IV (all of whose bits
are "active"). DES CBC encryption is denoted by:


Q = DESCBC(K, IV, P)
and its corresponding decryption by:


P = DESCBC^{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:

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
.

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 bitvector R
of minimal length appended to a given bit vector M in order
to bring the total bitlength of <M, R> up
to a positive multiple of 64.
Note that the bitlength 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
0vector 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:

DESCBC(K, IV, P) =
DESCBC(K, IV, <P, <0, ···, 0>>)

DESCBC^{1}(K, IV, Q) =
DESCBC^{1}(K, IV, <Q, <0, ···, 0>>)
When the initialisation vector IV is the (64bit) 0vector
<0, ···, 0> (consisting entirely of "0" bits), the term
IV is sometimes omitted from the above notations:

DESCBC(K, P) =
DESCBC(K, <0, ···, 0>, P)

DESCBC^{1}(K, Q) =
DESCBC^{1}(K, <0, ···, 0>, Q)
DESCBC Checksum
The DESCBC checksum of a plaintext P, with respect to a key
K and an initialisation vector IV, is by definition the
final block of DESCBC(K, IV, P). It is denoted:


DESCBCCKSUM(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 0vector, it is sometimes omitted from the notation:


DESCBCCKSUM(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:

DESCBC(K, IV, <P, P´>) =
<DESCBC(K, IV, P),
DESCBC(K, DESCBCCKSUM(K, IV, P), P´)>

DESCBCCKSUM(K, IV, <P, P´>) =
DESCBCCKSUM(K, DESCBCCKSUM(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 semiweak 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 longterm keys; in particular,
implementations should reject passwords that map to these keys
(via the passwordtokey mappings specified in
Registered PasswordtoKey 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 Sboxessee
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 48bit
subkeys, K_{0}, ···, K_{15}.
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, semiweak and possibly weak keys are that
sigma(K) = 1, 2 and 4, respectively.
Note that the weak and semiweak 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 semiweak 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 Bhence, 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>
SemiWeak Keys
The following are the 12 (normal form) semiweak 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_{0}, ···, k_{63}>
be a DES key, and let
P = <p_{0}, ···, p_{63}>
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_{14} '+.2'°'.2'
T_{K,14} '+.2'°'.2'
theta_{13} '+.2'°'.2' ···
'+.2'°'.2'
T_{K,1} '+.2'°'.2'
theta_{0} '+.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 32bit vectors, then:


theta(B) = <R_{B}, L_{B}>
That is:


theta(<b_{0},
···,
b_{63}>) =


<b_{32},
···,
b_{63},
b_{0},
···,
b_{31}>
Initial Permutation (IP) and Final Permutation (FP)
The initial permutation, IP, mapping blocks to blocks, is defined
as follows:


IP(<p_{0}, ···, p_{63}>) =


<p_{57},
p_{49},
p_{41},
p_{33},
p_{25},
p_{17},
p_{9},
p_{1},
p_{59},
p_{51},
p_{43},
p_{35},
p_{27},
p_{19},
p_{11},
p_{3},
p_{61},
p_{53},
p_{45},
p_{37},
p_{29},
p_{21},
p_{13},
p_{5},
p_{63},
p_{55},
p_{47},
p_{39},
p_{31},
p_{23},
p_{15},
p_{7},
p_{56},
p_{48},
p_{40},
p_{32},
p_{24},
p_{16},
p_{8},
p_{0},
p_{58},
p_{50},
p_{42},
p_{34},
p_{26},
p_{18},
p_{10},
p_{2},
p_{60},
p_{52},
p_{44},
p_{36},
p_{28},
p_{20},
p_{12},
p_{4},
p_{62},
p_{54},
p_{46},
p_{38},
p_{30},
p_{22},
p_{14},
p_{6}>
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_{0}, ···, q_{63}>) =


<q_{39},
q_{7},
q_{47},
q_{15},
q_{55},
q_{23},
q_{63},
q_{31},
q_{38},
q_{6},
q_{46},
q_{14},
q_{54},
q_{22},
q_{62},
q_{30},
q_{37},
q_{5},
q_{45},
q_{13},
q_{53},
q_{21},
q_{61},
q_{29},
q_{36},
q_{4},
q_{44},
q_{12},
q_{52},
q_{20},
q_{60},
q_{28},
q_{35},
q_{3},
q_{43},
q_{11},
q_{51},
q_{19},
q_{59},
q_{27},
q_{34},
q_{2},
q_{42},
q_{10},
q_{50},
q_{18},
q_{58},
q_{26},
q_{33},
q_{1},
q_{41},
q_{9},
q_{49},
q_{17},
q_{57},
q_{25},
q_{32},
q_{0},
q_{40},
q_{8},
q_{48},
q_{16},
q_{56},
q_{24}>
 Note:
 As seen in
DES Decryption
,
IP and FP are the only two transformations among DES's 33 component
transformations that are not selfinverse. This fact highlights the
functional significance of IP and FP, but it does not explain the
cryptographic significance of IP and FPand
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 48bit subkeys
K_{i} = K_{K,i} =
KS(K, i) (0 <= i <= 15), which are defined as follows.
First, two 28bit auxiliary vectors, C_{K,1} and
D_{K,1}, are defined by:


<C_{K,1}, D_{K,1}> = PC1(K)
where PC1 is the first permuted choice mapping from 64bit (key)
vectors to 56bit (auxiliary) vectors, defined as follows:


PC1(<k_{0}, ···, k_{63}>) =


<k_{56},
k_{48},
k_{40},
k_{32},
k_{24},
k_{16},
k_{8},
k_{0},
k_{57},
k_{49},
k_{41},
k_{33},
k_{25},
k_{17},
k_{9},
k_{1},
k_{58},
k_{50},
k_{42},
k_{34},
k_{26},
k_{18},
k_{10},
k_{2},
k_{59},
k_{51},
k_{43},
k_{35},
k_{62},
k_{54},
k_{46},
k_{38},
k_{30},
k_{22},
k_{14},
k_{6},
k_{61},
k_{53},
k_{45},
k_{37},
k_{29},
k_{21},
k_{13},
k_{5},
k_{60},
k_{52},
k_{44},
k_{36},
k_{28},
k_{20},
k_{12},
k_{4},
k_{27},
k_{19},
k_{11},
k_{3}>
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 28bit 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,i1})

D_{K,i} =
LS_{i}(D_{K,i1})

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 28bit
vectors to 28bit vectors:


LS_{i}(<e_{0}, ···,
e_{27}>) =
<e_{0}, ···, e_{27}> <<<<
s_{i}
according to the shift schedule:


<s_{0}, ···, s_{15}> =
<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 56bit
(auxiliary) vectors to 48bit (subkey) vectors, defined as follows:


PC2(<l_{0}, ···, l_{55}>) =


<l_{13},
l_{16},
l_{10},
l_{23},
l_{0},
l_{4},
l_{2},
l_{27},
l_{14},
l_{5},
l_{20},
l_{9},
l_{22},
l_{18},
l_{11},
l_{3},
l_{25},
l_{7},
l_{15},
l_{6},
l_{26},
l_{19},
l_{12},
l_{1},
l_{40},
l_{51},
l_{30},
l_{36},
l_{46},
l_{54},
l_{29},
l_{39},
l_{50},
l_{44},
l_{32},
l_{47},
l_{43},
l_{48},
l_{38},
l_{55},
l_{33},
l_{52},
l_{45},
l_{41},
l_{49},
l_{35},
l_{28},
l_{31}>
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 bitvectors):


T_{K,i}(B) =
<L_{B} ^
F_{K,i}(R_{B}),
R_{B}>
where the cipher functions F_{K,i}
(0 <= i <= 15) map 32bit (halfblock) vectors to 32bit
(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 32bit (halfblock) vectors
to 48bit (subkey) vectors given by:


E(<r_{0}, ···, r_{31}>) =


<r_{31},
r_{0},
r_{1},
r_{2},
r_{3},
r_{4},
r_{3},
r_{4},
r_{5},
r_{6},
r_{7},
r_{8},
r_{7},
r_{8},
r_{9},
r_{10},
r_{11},
r_{12},
r_{11},
r_{12},
r_{13},
r_{14},
r_{15},
r_{16},
r_{15},
r_{16},
r_{17},
r_{18},
r_{19},
r_{20},
r_{19},
r_{20},
r_{21},
r_{22},
r_{23},
r_{24},
r_{23},
r_{24},
r_{25},
r_{26},
r_{27},
r_{28},
r_{27},
r_{28},
r_{29},
r_{30},
r_{31},
r_{0}>
P is the permutation mapping from 32bit (halfblock) vectors
to 32bit (halfblock) vectors given by:


P(<t_{0}, ···, t_{31}>) =


<t_{15},
t_{6},
t_{19},
t_{20},
t_{28},
t_{11},
t_{27},
t_{16},
t_{0},
t_{14},
t_{22},
t_{25},
t_{4},
t_{17},
t_{30},
t_{9},
t_{1},
t_{7},
t_{23},
t_{13},
t_{31},
t_{26},
t_{2},
t_{8},
t_{18},
t_{12},
t_{29},
t_{5},
t_{21},
t_{10},
t_{3},
t_{24}>
S is the selection/substitution mapping from 48bit (subkey)
vectors to 32bit (halfblock) vectors defined as follows:


S(<z_{0}, ···, z_{47}>) =


<S_{0}(<z_{0}, ···, z_{5}>),
S_{1}(<z_{6}, ···, z_{11}>),
S_{2}(<z_{12}, ···, z_{17}>),
S_{3}(<z_{18}, ···, z_{23}>),
S_{4}(<z_{24}, ···, z_{29}>),
S_{5}(<z_{30}, ···, z_{35}>),
S_{6}(<z_{36}, ···, z_{41}>),
S_{7}(<z_{42}, ···, z_{47}>)>
In this expression, each submapping S_{h}
(0 <= h <= 7)
is a mapping of 6bit vectors to 4bit vectors, defined in terms of a
4code ×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 4bit vector
(or, equivalently, an integer in the range [0, 15])), given
by the rule:


S_{h}(<y_{0}, ···,
y_{5}>) =
Sh[<y_{0}, y_{5}>,
<y_{1}, y_{2},
y_{3}, y_{4}>]
In this rule, the identification of 2bit and of 4bit vectors
with integers is made via the bigendian mappings (namely,
f = <u_{0}, u_{1}> =
2^{1}u_{0} +
2^{0}u_{1} and
g = <v_{0}, v_{1},
v_{2}, v_{3}> =
2^{3}v_{0} +
2^{2}v_{1} +
2^{1}v_{2} +
2^{0}v_{3}).
The matrices Sh (0 <= h <= 7) are called Sboxes.
They lie at the very heart of DES, in the sense of being the major
source of its complexitybesides greatly adding to the egodicity
of DES, they comprise its only component of nonlinearity (with
respect to block space, the 64dimensional vector space
Fx_{2}'xu'^{64}
over the bit field F_{2}).
The Sboxes 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 invertiblenor 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 0vector for any bitvector U,
and U ^ V = U for any 0vector V.
Details of CBC Mode Algorithm
Let P = <P_{0}, ···,
P_{n1}>, n >= 1, be a plaintext which has
bitlength a positive multiple of 64, where each
P_{i} is a block. Then the CBC mode encryption of
P, Q = DESCBC(K, IV, P), is defined as
follows:


Q = <Q_{0}, ···,
Q_{n1}>
where:

Q_{0} = DES(K, IV ^ P_{0})

Q_{i} = DES(K,
Q_{i1} ^ P_{i})
for 1 <= i <= n1
The decryption, P = DESCBC^{1}(K, IV,
Q) is given by:

P_{0} = IV ^
DES^{1}(K, Q_{0})

P_{i} = Q_{i1} ^
DES^{1}(K, Q_{i})
for 1 <= i <= n1
These transformations are easily seen to be inverses of one another.
Please note that the html version of this specification
may contain formatting aberrations. The definitive version
is available as an electronic publication on CDROM
from The Open Group.