Implementation and Analysis of DES
Considering the amount of bit twiddling in DES, it probably comes as no surprise that it is frequently implemented in hardware. Even the figures and terminology associated with DES (diagrams drawn with boxes and lines, and terms such as S-boxes and P-boxes) tend to suggest a certain affinity toward hardware implementations. Nevertheless, software implementations have their place as well. In software, it is helpful to have several basic operations to assist in carrying out the numerous permutations, transformations, and substitutions that DES requires. For this purpose, the implementation presented here makes use of the bit operations presented in Chapter 14. The details of each permutation, transformation, and substitution are defined by the tables at the beginning of Example 15.2. These match the tables presented earlier in the text.
des_encipher
The des_encipher operation (see Example
15.2) enciphers a 64-bit block of plaintext using DES. Since
one of the nice properties of DES is that the same process can be
used both to encipher and decipher data,
des_encipher simply calls
des_main, which
des_decipher calls as well. The
des_main function uses its direction
argument to determine whether to encipher or decipher the data
provided in source. The
direction argument simply alters the
order in which subkeys are applied. In the case of
des_encipher, we set
direction to
encipher.
The des_main function begins by testing
whether key is NULL. This allows a caller
of des_encipher to reuse subkeys computed
during a previous call. To accommodate this, we declare the
subkeys array as static. If
key is not NULL, we compute the subkeys.
To do this, we perform the steps presented earlier. The key
transformation is performed using the function
permute , which permutes bits in a buffer according to a
specified table. Assuming that in each position
i of a table there is some value
p, permute permutes the
buffer passed to it by moving the bit at position
p to position i.
To transform the key, we pass permute the
table Des_Transform (the same table as in
Table 15.1). The necessary
rotations are performed by calling the bit operation
bit_rot_left. This operation rotates a buffer
to the left by a specified number of bits. To rotate the 28-bit
subkey blocks the correct amount for each round, we pass
bit_rot_left the appropriate element from the
table Des_Rotations (the same table as in
Table 15.2). We apply the permuted
choice to each subkey by calling permute and
passing it the table Des_Permuted (the
same table as in Table
15.3).
To encipher a data block, we begin by performing the initial
permutation. To do this, we call permute and
pass it the table Des_Initial (the same
table as in Table 15.4). Next, we
divide the data into two 32-bit blocks,
lblk and rblk.
Recall that most of the work in enciphering data takes place in a
series of operations repeated over 16 rounds. The majority of each
round is spent computing the value of the function
f, which is stored in
fblk as we go.
We begin each round by performing an expansion permutation on
rblk. To do this, we call
permute and pass it the table
Des_Expansion (the same table as in Table 15.5). Next, we call the bit
operation bit_xor to compute the XOR of the
expanded right block and the appropriate subkey. The subkey depends
on the round we are executing and whether we are enciphering or
deciphering data. Once the XOR has been computed, we perform a
series of S-box substitutions on the result.
Des_Sbox defines the eight S-boxes used
by DES (the same S-boxes as in Table
15.6). We look up each substitution exactly as described
earlier. That is, for each six-bit block
j in the current
fblk, the first and last bits are joined
to determine the appropriate row in the table defined by
Des_Sbox, and the middle four bits are
joined to form the column. We complete the computation of
f by performing the P-box permutation. To do this, we call
permute and pass it the table
Des_Pbox (the same table as in Table 15.7). We complete each round by
computing the XOR of lblk and the value
of function f, and swapping
lblk and
rblk.
We repeat this process 16 times, once for each round. After
all 16 rounds are complete, we copy rblk
into the first 32 bits of target and
lblk into the second 32 bits (effectively
negating the last swap of the left and right blocks, as is
required). At last, we perform the final permutation by calling
permute and passing it the table
Des_Final (the same table as in Table 15.8).
The runtime complexity of des_encipher is O (1) because all of the steps in enciphering a block of data run in a constant amount of time.
des_decipher
The des_decipher operation (see
Example 15.2) deciphers a 64-bit
block of ciphertext enciphered using DES. Like
des_encipher, des_decipher
actually calls des_main to decipher the data,
but with direction set to
decipher. Thus,
des_decipher works just like
des_encipher, except that the subkeys are
applied in reverse order. Specifically, in
des_main, for each round
i (starting at 0), we apply the subkey in
element 15 - i of
subkeys.
The runtime complexity of des_decipher is O (1) because all of the steps in deciphering a block of data run in a constant amount of time.
/*****************************************************************************
* *
* --------------------------------- des.c -------------------------------- *
* *
*****************************************************************************/
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include "bit.h"
#include "encrypt.h"
/*****************************************************************************
* *
* Define a mapping for the key transformation. *
* *
*****************************************************************************/
static const int DesTransform[56] = {
57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18,
10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36,
63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,
14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4
};
/*****************************************************************************
* *
* Define the number of rotations for computing subkeys. *
* *
*****************************************************************************/
static const int DesRotations[16] = {
1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
};
/*****************************************************************************
* *
* Define a mapping for the permuted choice for subkeys. *
* *
*****************************************************************************/
static const int DesPermuted[48] = {
14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,
23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2,
41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
};
/*****************************************************************************
* *
* Define a mapping for the initial permutation of data blocks. *
* *
*****************************************************************************/
static const int DesInitial[64] = {
58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,
62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,
57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3,
61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7
};
/*****************************************************************************
* *
* Define a mapping for the expansion permutation of data blocks. *
* *
*****************************************************************************/
static const int DesExpansion[48] = {
32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9,
8, 9, 10, 11, 12, 13, 12, 13, 14, 15, 16, 17,
16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25,
24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1
};
/*****************************************************************************
* *
* Define tables for the S-box substitutions performed for data blocks. *
* *
*****************************************************************************/
static const int DesSbox[8][4][16] = {
{
{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},
},
{
{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},
},
{
{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},
},
{
{ 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},
},
{
{ 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},
},
{
{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},
},
{
{ 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},
},
{
{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},
},
};
/*****************************************************************************
* *
* Define a mapping for the P-box permutation of data blocks. *
* *
*****************************************************************************/
static const int DesPbox[32] = {
16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10,
2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25
};
/*****************************************************************************
* *
* Define a mapping for the final permutation of data blocks. *
* *
*****************************************************************************/
static const int DesFinal[64] = {
40, 8, 48, 16, 56, 24, 64, 32, 39, 7, 47, 15, 55, 23, 63, 31,
38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29,
36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51, 19, 59, 27,
34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41, 9, 49, 17, 57, 25
};
/*****************************************************************************
* *
* Define a type for whether to encipher or decipher data. *
* *
*****************************************************************************/
typedef enum DesEorD_ {encipher, decipher} DesEorD;
/*****************************************************************************
* *
* -------------------------------- permute ------------------------------- *
* *
*****************************************************************************/
static void permute(unsigned char *bits, const int *mapping, int n) {
unsigned char temp[8];
int i;
/*****************************************************************************
* *
* Permute the buffer using an n-entry mapping. *
* *
*****************************************************************************/
memset(temp, 0, (int)ceil(n / 8));
for (i = 0; i < n; i++)
bit_set(temp, i, bit_get(bits, mapping[i] - 1));
memcpy(bits, temp, (int)ceil(n / 8));
return;
}
/*****************************************************************************
* *
* ------------------------------- des_main ------------------------------- *
* *
*****************************************************************************/
static int des_main(const unsigned char *source, unsigned char *target, const
unsigned char *key, DesEorD direction) {
static unsigned char subkeys[16][7];
unsigned char temp[8],
lkey[4],
rkey[4],
lblk[6],
rblk[6],
fblk[6],
xblk[6],
sblk;
int row,
col,
i,
j,
k,
p;
/*****************************************************************************
* *
* If key is NULL, use the subkeys as computed in a previous call. *
* *
*****************************************************************************/
if (key != NULL) {
/**************************************************************************
* *
* Make a local copy of the key. *
* *
**************************************************************************/
memcpy(temp, key, 8);
/**************************************************************************
* *
* Permute and compress the key into 56 bits. *
* *
**************************************************************************/
permute(temp, DesTransform, 56);
/**************************************************************************
* *
* Split the key into two 28-bit blocks. *
* *
**************************************************************************/
memset(lkey, 0, 4);
memset(rkey, 0, 4);
for (j = 0; j < 28; j++)
bit_set(lkey, j, bit_get(temp, j));
for (j = 0; j < 28; j++)
bit_set(rkey, j, bit_get(temp, j + 28));
/**************************************************************************
* *
* Compute the subkeys for each round. *
* *
**************************************************************************/
for (i = 0; i < 16; i++) {
/***********************************************************************
* *
* Rotate each block according to its round. *
* *
***********************************************************************/
bit_rot_left(lkey, 28, DesRotations[i]);
bit_rot_left(rkey, 28, DesRotations[i]);
/***********************************************************************
* *
* Concatenate the blocks into a single subkey. *
* *
***********************************************************************/
for (j = 0; j < 28; j++)
bit_set(subkeys[i], j, bit_get(lkey, j));
for (j = 0; j < 28; j++)
bit_set(subkeys[i], j + 28, bit_get(rkey, j));
/***********************************************************************
* *
* Do the permuted choice permutation. *
* *
***********************************************************************/
permute(subkeys[i], DesPermuted, 48);
}
}
/*****************************************************************************
* *
* Make a local copy of the source text. *
* *
*****************************************************************************/
memcpy(temp, source, 8);
/*****************************************************************************
* *
* Do the initial permutation. *
* *
*****************************************************************************/
permute(temp, DesInitial, 64);
/*****************************************************************************
* *
* Split the source text into a left and right block of 32 bits. *
* *
*****************************************************************************/
memcpy(lblk, &temp[0], 4);
memcpy(rblk, &temp[4], 4);
/*****************************************************************************
* *
* Encipher or decipher the source text. *
* *
*****************************************************************************/
for (i = 0; i < 16; i++) {
/**************************************************************************
* *
* Begin the computation of f. *
* *
**************************************************************************/
memcpy(fblk, rblk, 4);
/**************************************************************************
* *
* Permute and expand the copy of the right block into 48 bits. *
* *
**************************************************************************/
permute(fblk, DesExpansion, 48);
/**************************************************************************
* *
* Apply the appropriate subkey for the round. *
* *
**************************************************************************/
if (direction == encipher) {
/***********************************************************************
* *
* For enciphering, subkeys are applied in increasing order. *
* *
***********************************************************************/
bit_xor(fblk, subkeys[i], xblk, 48);
memcpy(fblk, xblk, 6);
}
else {
/***********************************************************************
* *
* For deciphering, subkeys are applied in decreasing order. *
* *
***********************************************************************/
bit_xor(fblk, subkeys[15 - i], xblk, 48);
memcpy(fblk, xblk, 6);
}
/**************************************************************************
* *
* Do the S-box substitutions. *
* *
**************************************************************************/
p = 0;
for (j = 0; j < 8; j++) {
/***********************************************************************
* *
* Compute a row and column into the S-box tables. *
* *
***********************************************************************/
row = (bit_get(fblk, (j * 6)+0) * 2) + (bit_get(fblk, (j * 6)+5) * 1);
col = (bit_get(fblk, (j * 6)+1) * 8) + (bit_get(fblk, (j * 6)+2) * 4) +
(bit_get(fblk, (j * 6)+3) * 2) + (bit_get(fblk, (j * 6)+4) * 1);
/***********************************************************************
* *
* Do the S-box substitution for the current six-bit block. *
* *
***********************************************************************/
sblk = (unsigned char)DesSbox[j][row][col];
for (k = 4; k < 8; k++) {
bit_set(fblk, p, bit_get(&sblk, k));
p++;
}
}
/**************************************************************************
* *
* Do the P-box permutation to complete f. *
* *
**************************************************************************/
permute(fblk, DesPbox, 32);
/**************************************************************************
* *
* Compute the XOR of the left block and f. *
* *
**************************************************************************/
bit_xor(lblk, fblk, xblk, 32);
/**************************************************************************
* *
* Set the left block for the round. *
* *
**************************************************************************/
memcpy(lblk, rblk, 4);
/**************************************************************************
* *
* Set the right block for the round. *
* *
**************************************************************************/
memcpy(rblk, xblk, 4);
}
/*****************************************************************************
* *
* Set the target text to the rejoined final right and left blocks. *
* *
*****************************************************************************/
memcpy(&target[0], rblk, 4);
memcpy(&target[4], lblk, 4);
/*****************************************************************************
* *
* Do the final permutation. *
* *
*****************************************************************************/
permute(target, DesFinal, 64);
return 0;
}
/*****************************************************************************
* *
* ----------------------------- des_encipher ----------------------------- *
* *
*****************************************************************************/
void des_encipher(const unsigned char *plaintext, unsigned char *ciphertext,
const unsigned char *key) {
des_main(plaintext, ciphertext, key, encipher);
return;
}
/*****************************************************************************
* *
* ----------------------------- des_decipher ----------------------------- *
* *
*****************************************************************************/
void des_decipher(const unsigned char *ciphertext, unsigned char *plaintext,
const unsigned char *key) {
des_main(ciphertext, plaintext, key, decipher);
return;
}