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 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 = <k0, ···,
k63>, 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
kj, 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 kj 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,
<k8j+0, ···,
k8j+7> (0 <= k <= 7), has odd bit sum
(mod 2)-k8j+0 + ··· +
k8j+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:
-
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 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, K0, ···, K15.
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
Ki 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 = <k0, ···, k63>
be a DES key, and let
P = <p0, ···, p63>
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'
TK,15 '+.2'°'-.2'
theta14 '+.2'°'-.2'
TK,14 '+.2'°'-.2'
theta13 '+.2'°'-.2' ···
'+.2'°'-.2'
TK,1 '+.2'°'-.2'
theta0 '+.2'°'-.2'
TK,0 '+.2'°'-.2'
IP)(P)
Of these 33 transformations, 15 of them are equal to the simple
cyclic permutation (or transposition),
thetai = theta (0 <= i <= 14), which
interchanges the left and right halfblocks of a block: if
B = <LB, RB> where
LB and RB are 32-bit vectors, then:
-
-
theta(B) = <RB, LB>
That is:
-
-
theta(<b0,
···,
b63>) =
-
-
<b32,
···,
b63,
b0,
···,
b31>
Initial Permutation (IP) and Final Permutation (FP)
The initial permutation, IP, mapping blocks to blocks, is defined
as follows:
-
-
IP(<p0, ···, p63>) =
-
-
<p57,
p49,
p41,
p33,
p25,
p17,
p9,
p1,
p59,
p51,
p43,
p35,
p27,
p19,
p11,
p3,
p61,
p53,
p45,
p37,
p29,
p21,
p13,
p5,
p63,
p55,
p47,
p39,
p31,
p23,
p15,
p7,
p56,
p48,
p40,
p32,
p24,
p16,
p8,
p0,
p58,
p50,
p42,
p34,
p26,
p18,
p10,
p2,
p60,
p52,
p44,
p36,
p28,
p20,
p12,
p4,
p62,
p54,
p46,
p38,
p30,
p22,
p14,
p6>
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(<q0, ···, q63>) =
-
-
<q39,
q7,
q47,
q15,
q55,
q23,
q63,
q31,
q38,
q6,
q46,
q14,
q54,
q22,
q62,
q30,
q37,
q5,
q45,
q13,
q53,
q21,
q61,
q29,
q36,
q4,
q44,
q12,
q52,
q20,
q60,
q28,
q35,
q3,
q43,
q11,
q51,
q19,
q59,
q27,
q34,
q2,
q42,
q10,
q50,
q18,
q58,
q26,
q33,
q1,
q41,
q9,
q49,
q17,
q57,
q25,
q32,
q0,
q40,
q8,
q48,
q16,
q56,
q24>
- 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 TK,i depend on a
key schedule of 16 48-bit subkeys
Ki = KK,i =
KS(K, i) (0 <= i <= 15), which are defined as follows.
First, two 28-bit auxiliary vectors, CK,-1 and
DK,-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(<k0, ···, k63>) =
-
-
<k56,
k48,
k40,
k32,
k24,
k16,
k8,
k0,
k57,
k49,
k41,
k33,
k25,
k17,
k9,
k1,
k58,
k50,
k42,
k34,
k26,
k18,
k10,
k2,
k59,
k51,
k43,
k35,
k62,
k54,
k46,
k38,
k30,
k22,
k14,
k6,
k61,
k53,
k45,
k37,
k29,
k21,
k13,
k5,
k60,
k52,
k44,
k36,
k28,
k20,
k12,
k4,
k27,
k19,
k11,
k3>
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,
CK,i and DK,i,
and the subkeys Ki =
KK,i = KS(K, i), are defined by:
-
CK,i =
LSi(CK,i-1)
-
DK,i =
LSi(DK,i-1)
-
Ki =
KK,i =
KS(K, i) =
PC2(<CK,i, DK,i>)
where LSi is the (circular bitwise)
left shift (or bitwise left rotation) mapping 28-bit
vectors to 28-bit vectors:
-
-
LSi(<e0, ···,
e27>) =
<e0, ···, e27> <<<<
si
according to the shift schedule:
-
-
<s0, ···, s15> =
<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(<l0, ···, l55>) =
-
-
<l13,
l16,
l10,
l23,
l0,
l4,
l2,
l27,
l14,
l5,
l20,
l9,
l22,
l18,
l11,
l3,
l25,
l7,
l15,
l6,
l26,
l19,
l12,
l1,
l40,
l51,
l30,
l36,
l46,
l54,
l29,
l39,
l50,
l44,
l32,
l47,
l43,
l48,
l38,
l55,
l33,
l52,
l45,
l41,
l49,
l35,
l28,
l31>
Rounds (T): Cipher Function (F), Expansion (E), Permutation (P) and Selection/Substitution (S)
With the subkeys Ki in hand, the rounds
TK,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):
-
-
TK,i(B) =
<LB ^
FK,i(RB),
RB>
where the cipher functions FK,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
Ki are used):
-
-
FK,i(R) =
P(S(Ki ^ 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(<r0, ···, r31>) =
-
-
<r31,
r0,
r1,
r2,
r3,
r4,
r3,
r4,
r5,
r6,
r7,
r8,
r7,
r8,
r9,
r10,
r11,
r12,
r11,
r12,
r13,
r14,
r15,
r16,
r15,
r16,
r17,
r18,
r19,
r20,
r19,
r20,
r21,
r22,
r23,
r24,
r23,
r24,
r25,
r26,
r27,
r28,
r27,
r28,
r29,
r30,
r31,
r0>
P is the permutation mapping from 32-bit (halfblock) vectors
to 32-bit (halfblock) vectors given by:
-
-
P(<t0, ···, t31>) =
-
-
<t15,
t6,
t19,
t20,
t28,
t11,
t27,
t16,
t0,
t14,
t22,
t25,
t4,
t17,
t30,
t9,
t1,
t7,
t23,
t13,
t31,
t26,
t2,
t8,
t18,
t12,
t29,
t5,
t21,
t10,
t3,
t24>
S is the selection/substitution mapping from 48-bit (subkey)
vectors to 32-bit (halfblock) vectors defined as follows:
-
-
S(<z0, ···, z47>) =
-
-
<S0(<z0, ···, z5>),
S1(<z6, ···, z11>),
S2(<z12, ···, z17>),
S3(<z18, ···, z23>),
S4(<z24, ···, z29>),
S5(<z30, ···, z35>),
S6(<z36, ···, z41>),
S7(<z42, ···, z47>)>
In this expression, each submapping Sh
(0 <= h <= 7)
is a mapping of 6-bit vectors to 4-bit vectors, defined in terms of a
4code ×16 matrix, Sh (whose entry in its fth
row and gth 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:
-
-
Sh(<y0, ···,
y5>) =
Sh[<y0, y5>,
<y1, y2,
y3, y4>]
In this rule, the identification of 2-bit and of 4-bit vectors
with integers is made via the big-endian mappings (namely,
f = <u0, u1> =
21u0 +
20u1 and
g = <v0, v1,
v2, v3> =
23v0 +
22v1 +
21v2 +
20v3).
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
Fx2'|xu'64
over the bit field F2).
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'
TK,0 '+.2'°'-.2'
theta '+.2'°'-.2'
TK,1 '+.2'°'-.2'
theta '+.2'°'-.2'
···
'+.2'°'-.2'
TK,14 '+.2'°'-.2'
theta '+.2'°'-.2'
TK,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'
TK,15 '+.2'°'-.2'
theta '+.2'°'-.2'
TK,14 '+.2'°'-.2'
theta '+.2'°'-.2'
···
'+.2'°'-.2'
TK,1 '+.2'°'-.2'
theta '+.2'°'-.2'
TK,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 =
TK,i
The first three of these equalities are straightforward,
and the fourth holds because for any block B:
-
-
TK,i(TK,i(B)) =
TK,i(<LB ^
FK,i(RB),
RB>) =
<(LB ^
FK,i(RB)) ^
FK,i(RB),
RB> =
<LB, RB> =
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 = <P0, ···,
Pn-1>, n >= 1, be a plaintext which has
bit-length a positive multiple of 64, where each
Pi is a block. Then the CBC mode encryption of
P, Q = DES-CBC(K, IV, P), is defined as
follows:
-
-
Q = <Q0, ···,
Qn-1>
where:
-
Q0 = DES(K, IV ^ P0)
-
Qi = DES(K,
Qi-1 ^ Pi)
for 1 <= i <= n-1
The decryption, P = DES-CBC-1(K, IV,
Q) is given by:
-
P0 = IV ^
DES-1(K, Q0)
-
Pi = Qi-1 ^
DES-1(K, Qi)
for 1 <= i <= n-1
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 CD-ROM
from The Open Group.