Implementing of Data Encryption Standard, DES Algorithm in Cryptography

The symmetric key encryption algorithm, the data encryption standard (DES), is widely known. It was created in the 1970s to protect sensitive information. DES uses a 56-bit key and works on 64-bit blocks of data which means that it forms an integral component to initial cryptographic systems. Today, this method is regarded as less safe; however, knowledge about DES is necessary to understand the fundamentals of encryption and other cryptosystems.

In this article, we are going to explain what DES means, its history, and how it works. Additionally, we will give you step-by-step instructions on how to implement this algorithm so that every part of the process becomes clear to you. At the end of the reading, you will be well-versed with DES and its importance in cryptography.

Data Encryption Standard (DES) refers to a symmetric key encryption algorithm that was developed by the National Institute of Standards and Technology (NIST) in 1977 as an official standard for encrypting data. In symmetric-key algorithms, the same keys are used for both encryption and decryption thus, secure communication heavily relies on proper key management.

DES operates on blocks of 64 bits using a key length of 56 bits. There are 16 rounds where substitution and permutation steps are applied to convert plaintext into ciphertext during each round of processing done by the algorithm. Although AES has replaced it with stronger methods such as triple DES (3DES), some old systems still use this technology because it remains significant within cryptographic history. People need to understand more about what DES is in order for them to know when different types were developed.

Implementing DES Algorithm (For Encryption)

To understand the DES algorithm, let’s use a simple example. We’ll start with a 64-bit block of plaintext and a 56-bit key.

We’ll walk through each step, explaining the process in detail.

Initial Permutation (IP)

The first step in DES is the Initial Permutation (IP). This step rearranges the bits of the plaintext based on a predefined table. Let’s say our plaintext is:

• Plaintext (in Hexadecimal): 0123456789ABCDEF

We convert the hex to binary:

• Plaintext (in binary): 00000001 00100011 01000101 01100111 10001001 10101111 11001101 11101111

The Initial Permutation table, which is pre-defined, is:

To perform the initial permutation, we rearrange the bits of the plaintext according to the table. For instance, the bit in position 58 of the original plaintext moves to position 1 of the permuted text.

Permutation example:

• Bit at position 58 (original) -> Bit at position 1 (permuted)
• Bit at position 50 (original) -> Bit at position 2 (permuted)

…continue for all 64 bits.

• After Initial Permutation (example): 11001100 11110000 10101010 11001100 10101010 11001100 11110000 11001100

Splitting

Next, we split the permuted plaintext into two halves. Each half is 32 bits.

• Left half (L0): 11001100 11110000 10101010 11001100
• Right half (R0): 10101010 11001100 11110000 11001100

Key Generation

The initial 64-bit key, which you can choose randomly, is transformed into a 56-bit key by discarding every 8th bit. This process reduces the key to 56 bits, which is then divided into two 28-bit halves.

• Initial Key (in hex): 133457799BBCDFF1

Convert to binary and drop every 8th bit:

• Key (in binary): 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001

Drop every 8th bit:

• 56-bit Key: 00010010 01101001 01011011 11001001 10110111 10110111 11110001

In DES, each of the 16 rounds uses a different 48-bit sub-key derived from the original 56-bit key. This process adds complexity and ensures that the encryption is secure.

48-bit key generation process for each round

Splitting into Halves:

The 56-bit key is divided into two 28-bit halves:

• C0 (first 28 bits): 00010010 01101001 01011011 1100 (28 bits)
• D0 (second 28 bits): 1001 10110111 10110111 11110001 (28 bits)

Shifting:

For each of the 16 rounds, the halves are circularly shifted left by one or two positions, depending on the round number. The number of shifts per round is predetermined as follows:

Example for Rounds 1 and 2:

Round 1:

• Shift C0 and D0 left by 1 position.
• C1: 00100100 11010010 10110111 1000
• D1: 00110111 01111001 10111111 1111

Round 2:

• Shift C1 and D1 left by 1 position.
• C2: 01001001 10100101 01101111 0000
• D2: 01101110 11110011 01111111 1110

This shifting process is repeated for all 16 rounds.

Compression Permutation

After shifting, the 56-bit key (combined C and D halves) is compressed to 48 bits using a permutation table. This table selects 48 specific bits out of the 56-bit combined key to create the 48-bit round key.

Compression Permutation Table:

This table is used to select and reorder the bits from the combined 56-bit key to produce the 48-bit round key.

Example:

Assume the combined 56-bit key after shifting for round 1 is:

• Combined C1 and D1: 00100100 11010010 10110111 10000011 01111001 10111111

Apply the compression permutation to select and rearrange the bits:

• 48-bit Round Key (example bits selected): 111000110010001010110010000100110011010000101111

By repeating this process for each round, we generate a unique 48-bit round key for each of the 16 rounds, which are then used in the encryption process.

Also read- What is public key cryptography

Rounds (Round 1 as an Example)

DES involves 16 rounds of key transformations. For each round, a 48-bit sub-key is generated from the 56-bit key.

After splitting the blocks, we use the round function. In each round, the left half remains as it is, and we need to perform the operations below on the right half.

1. Expansion Permutation (E)
2. Key mixing (⊕
3. Substitution (S1, S2,…,S8)
4. Permutation (P)

After getting the final result from the right half, we need to perform an XOR operation of the left and right half.

Expansion Permutation (E)

The 32-bit right half (R0) is expanded to 48 bits using the expansion table. Here, each bit is substituted with the one given at the respected position in the table. The expansion table duplicates certain bits to increase the size from 32 to 48 bits.

Expansion Table:

Apply the expansion permutation on R0:

• R0 (32 bits): 10101010 10101010 10101010 10101010
• Expanded R0 (48 bits): 01010101 01011010 10100101 01101010 01011010 10101010

Key Mixing (⊕)

The expanded R0 is XORed with the round key (48-bit). Using the example from the previous step, our round key for Round 1 is:

• Round Key (48 bits): 111000110010001010110010000100110011010000101111

Perform XOR operation:

• Result: 10110101 00010000 00011111 01111000 01010000 00011101

Substitution (S-Boxes):

The result is divided into eight 6-bit blocks, and each block is substituted using the S-Boxes. Here’s an example using S1:

S1 Table:

Each 6-bit block is used to look up the corresponding 4-bit output from the S-Box. For example, you need to take a look at the first sub-table. Let’s take the example of the first 6-bit block:

First 6-bit block: 101101

• Row: 11 (first and last bits)
• Column: 0110 (middle four bits)
• Output (S1[11][0110]): 0100

Perform this for all 8 blocks and combine the results to get a 32-bit block.

Permutation (P)

The 32-bit result of the S-Boxes is permuted using a fixed table:

Permutation Table:

Applying this permutation provides the final 32-bit output of the round function (F).

XOR Operation

After getting the final result from the right half, we need to perform an XOR operation of the left half (L0) and the result from the right half.

• Final 32-bit output from F: <32-bit result from P>
• L0 (32 bits): 11001100 00000000 11001100 11110000
• XOR Result: <L0 XOR 32-bit result from F>

Result after Round 1 (Swapping required)

The result after Round 1 is the combination of the original right half (R0) and the XOR result:

• L1: <Original R0>
• R1: <XOR Result>

This process is repeated for all 16 rounds. Each round uses a different 48-bit sub-key, and the final result is obtained after the 16th round, followed by the final permutation (FP).

By following these steps, the plaintext is transformed into ciphertext using DES.

Implementing DES Algorithm (For Decryption)

Just like encryption, the decryption process in DES involves 16 rounds and uses the same steps but in reverse order. We’ll walk through each step of the decryption process, ensuring it’s clear and beginner-friendly.

Initial Permutation (IP)

The first step in decryption is the Initial Permutation (IP). This step rearranges the bits of the ciphertext based on the same predefined table used in encryption.

Initial Permutation Table:

To perform the initial permutation, rearrange the bits of the ciphertext according to the table. For instance, the bit in position 58 of the original ciphertext moves to position 1 of the permuted text.

• After Initial Permutation (example): 11001100 11110000 10101010 11001100 10101010 11001100 11110000 11001100

Splitting

Next, we split the permuted ciphertext into two halves. Each half is 32 bits.

• Left half (L0): 11001100 11110000 10101010 11001100
• Right half (R0): 10101010 11001100 11110000 11001100

Round Function (Round 1)

In Round 1, we perform the following operations on the right half (R0) in reverse order of encryption:

Expansion Permutation (E):

The 32-bit right half (R0) is expanded to 48 bits using the expansion table. This table duplicates certain bits to increase the size from 32 to 48 bits.

Expansion Table:

Apply the expansion permutation on R0:

• R0 (32 bits): 10101010 11001100 11110000 11001100
• Expanded R0 (48 bits): 01011010 10101100 10101100 10111100 01100110 01100101

Key Mixing (⊕):

The expanded R0 is XORed with the round key (48-bit). For decryption, we use the round keys in reverse order, starting from Round 16 to Round 1.

• Example Round Key for Decryption (48 bits, Round 16): 111000110010001010110010000100110011010000101111

Perform XOR operation:

• Result of XOR operation: 10111010 01101001 00011110 10101110 10001101 01000010

Substitution (S-Boxes):

The result from the XOR operation is divided into eight 6-bit blocks, and each block is substituted using the S-Boxes.

S1 Table:

Each 6-bit block is used to look up the corresponding 4-bit output from the S-Box. For example, the first 6-bit block might be:

• First 6-bit block: 101110
• Row: 10 (first and last bits)
• Column: 0111 (middle four bits)
• Output (S1[10][0111]): 1100

Perform this for all 8 blocks and combine the results to get a 32-bit block.

Permutation (P):

The 32-bit result of the S-Boxes is permuted using a fixed table.

Permutation Table:

Applying this permutation provides the final 32-bit output of the round function (F).

XOR Operation

After getting the final result from the right half, we need to perform an XOR operation with the left half (L0).

• Final 32-bit output from F: <32-bit result from P>
• L0 (32 bits): 11001100 11110000 10101010 11001100
• XOR Result: <L0 XOR 32-bit result from F>

Result after Round 1 (Swapping required)

The result after Round 1 is the combination of the original right half (R0) and the XOR result:

• L1: <Original R0>
• R1: <XOR Result>

Perform these operations for all 16 rounds.

Final Permutation (FP)

The final permutation rearranges the bits of the combined result from the last round using a predefined table, which is the inverse of the initial permutation table.

Final Permutation Table:

By applying this permutation, we obtain the final decrypted plaintext.

Code

Java:

public class DES {

private static final int[] IP = { 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 };

private static final int[] E = { 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 };

private static final int[] P = { 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 };

private static final int[] FP = { 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 };

private static final int[][][] S_BOXES = {

{{ 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}}

};

private static final int[] PC1 = { 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 };

private static final int[] PC2 = { 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 };

private static final int[] SHIFTS = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 };

// Method to perform the initial permutation on a 64-bit block

private static long initialPermutation(long block) {

return permutation(block, IP);

}

// Method to perform the final permutation on a 64-bit block

private static long finalPermutation(long block) {

return permutation(block, FP);

}

// General method to apply a permutation to a 64-bit block

private static long permutation(long block, int[] permutationTable) {

long result = 0;

for (int i = 0; i < permutationTable.length; i++) {

result <<= 1;

result |= (block >> (64 – permutationTable[i])) & 0x01;

}

return result;

}

// Method to expand a 32-bit block to 48 bits using the expansion table

private static long expansion(long halfBlock) {

return permutation(halfBlock, E);

}

// Method to apply the P permutation to a 32-bit block

private static int permuteP(int block) {

return (int) permutation(block & 0xFFFFFFFFL, P);

}

// Method to generate the 16 subkeys from the original 64-bit key

private static long[] generateSubkeys(long key) {

long[] subkeys = new long[16];

// Apply PC1 permutation

key = permutation(key, PC1);

// Split into C and D halves

int C = (int) (key >> 28) & 0x0FFFFFFF;

int D = (int) key & 0x0FFFFFFF;

// Generate each subkey

for (int round = 0; round < 16; round++) {

// Perform the left circular shift

C = ((C << SHIFTS[round]) | (C >> (28 – SHIFTS[round]))) & 0x0FFFFFFF;

D = ((D << SHIFTS[round]) | (D >> (28 – SHIFTS[round]))) & 0x0FFFFFFF;

// Combine C and D and apply PC2 permutation to get the subkey

long CD = ((long) C << 28) | D;

subkeys[round] = permutation(CD, PC2);

}

return subkeys;

}

// Method to perform the S-box substitution

private static int sBoxSubstitution(long block) {

int result = 0;

for (int i = 0; i < 8; i++) {

int sBoxInput = (int) ((block >> (42 – 6 * i)) & 0x3F);

int row = ((sBoxInput & 0x20) >> 4) | (sBoxInput & 0x01);

int col = (sBoxInput >> 1) & 0x0F;

result <<= 4;

result |= S_BOXES[i][row][col];

}

return result;

}

// The DES function that encrypts or decrypts a 64-bit block

private static long desFunction(long block, long[] subkeys, boolean isEncrypt) {

// Apply the initial permutation

block = initialPermutation(block);

// Split into L and R halves

int L = (int) (block >> 32) & 0xFFFFFFFF;

int R = (int) block & 0xFFFFFFFF;

// Perform the 16 rounds

for (int round = 0; round < 16; round++) {

int tempR = R;

// Expand R and apply the round key

R = (int) expansion(R);

if (isEncrypt) {

R ^= subkeys[round];

} else {

R ^= subkeys[15 – round];

}

// Apply the S-box substitution and P permutation

R = sBoxSubstitution(R);

R = permuteP(R);

// XOR with L and swap halves

R ^= L;

L = tempR;

}

// Combine L and R and apply the final permutation

block = ((long) R << 32) | (L & 0xFFFFFFFFL);

block = finalPermutation(block);

return block;

}

// Method to encrypt a 64-bit block

public static long encrypt(long plaintext, long key) {

long[] subkeys = generateSubkeys(key);

return desFunction(plaintext, subkeys, true);

}

// Method to decrypt a 64-bit block

public static long decrypt(long ciphertext, long key) {

long[] subkeys = generateSubkeys(key);

return desFunction(ciphertext, subkeys, false);

}

public static void main(String[] args) {

// Example usage

long plaintext = 0x0123456789ABCDEFL;

long key = 0x133457799BBCDFF1L;

System.out.printf(“Plaintext: 0x%016Xn”, plaintext);

long ciphertext = encrypt(plaintext, key);

System.out.printf(“Ciphertext: 0x%016Xn”, ciphertext);

long decrypted = decrypt(ciphertext, key);

System.out.printf(“Decrypted: 0x%016Xn”, decrypted);

// Verify if the decryption result matches the original plaintext

if (plaintext == decrypted) {

System.out.println(“Decryption successful: The decrypted text matches the original plaintext.”);

} else {

System.out.println(“Decryption failed: The decrypted text does not match the original plaintext.”);

}

}

}

Output:

Plaintext: 0x0123456789ABCDEF

Ciphertext: 0x02138A9B4657CEDF

Decrypted: 0x0123456789ABCDEF

Decryption successful: The decrypted text matches the original plaintext.

Conclusion

In this blog, we explored the Data Encryption Standard (DES) algorithm, a crucial milestone in cryptography. We explored the key generation process and detailed step-by-step implementation for both encryption and decryption.

Although DES is considered less secure by today’s standards, understanding its mechanics provides a solid foundation for learning more advanced cryptographic techniques. By following this guide, you now have the knowledge to implement DES and appreciate its significance in the evolution of data encryption.