An In-Depth Exploration of Data Encryption Standard (DES): History, Theory, and Full Python Code
A Step-by-Step Guide with Python code Explanation and Implementation.
History:
DES was developed by IBM in the early 1970s and was adopted as a federal standard for the United States in 1977 by the National Institute of Standards and Technology (NIST). It was designed to provide a secure and efficient method for electronic data encryption.DES gained prominence as the standard encryption algorithm for the U.S. government, military, and various industries. It was widely used to secure sensitive data and communications.
Initial Controversy:
DES faced some controversy due to its relatively short key length of 56 bits. Even at the time of its release, concerns were raised about the potential vulnerability of DES to brute-force attacks.
Contributions and Modifications:
Despite its key size concerns, DES made significant contributions to the field of cryptography and paved the way for subsequent encryption algorithms. Various modifications and adaptations of DES were proposed to enhance its security.
In conclusion, DES played a pivotal role in the history of cryptography, particularly during its era of dominance in the late 20th century. While its use significantly contributed to securing sensitive information, the evolution of technology prompted the adoption of more advanced encryption standards like AES.
Introduction
DES is a symmetric key algorithm used for encrypting electronic data.
The fundamental operation of DES involves taking a 64-bit block of plaintext as input and transforming it into a corresponding 64-bit block of ciphertext.
The DES (Data Encryption Standard) process involves several steps, organized into a series of rounds within a Feistel network structure. Here’s a breakdown of the steps:
1. Initial Permutation (IP):
The 64-bit plaintext block undergoes an initial permutation, where the positions of its bits are rearranged according to a predefined table.
2. Key Generation:
The 56-bit key is expanded and divided into sixteen 48-bit subkeys, one for each round of encryption.
- Initial Key: The process begins with a 64-bit key, which is the user-provided secret key used to initiate the encryption.
- Key Permutation and Compression: 8-bit is being dropped and The 56-bit key undergoes an initial permutation(PC1 permutation) and compression. During this step, certain bits are selected and rearranged according to a predefined table. The result is a 56-bit permutation of the original key.
- Key Splitting: The 56-bit permuted key is then split into two 28-bit halves: a left half (C0) and a right half (D0).
- Left Shift: In each round, both the left and right halves of the key are independently rotated or shifted by a certain number of bits, creating a new combination of bits.
- shift_schedule = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]
- Concatenation and Compression: After the rotation, the left and right halves are concatenated and compressed to create a 48-bit round subkey for that specific round.
- Key Compression: The compression PC2 permutation changes the 56-bit key to the 48-bit key, which is used as a key for the corresponding round. Example: for round 1 we’ll use K1 and so on.
- Round-Specific Subkey Generation: The key expansion process involves creating sixteen round-specific subkeys, one for each round of encryption for C1 and D1 we’ll use C0 and D0 and for C2 and D2 we’ll use C1 and D1, and so on till C15 and D15.
- Sixteen Subkeys: This process is repeated for each of the sixteen rounds, resulting in a set of sixteen 48-bit subkeys (K1, K2, …, K16).
3. Rounds of Encryption:
- The data block is divided into two halves (L and R), and each round involves the transformation of one half based on the other half and the round key.
Round 1
- The right half (R0) is subjected to an expansion operation, increasing its size(32-bit to 48-bit). This expanded right half is then XORed (bitwise exclusive OR) with the round-specific subkey (Ki) derived from the key schedule.
- Substitution (S-boxes): The result of the XOR operation is divided into eight 6-bit blocks. Each block is fed into a corresponding S-box (substitution box), which replaces it with a 4-bit output based on the S-box’s predefined substitution table. The outputs from all S-boxes are concatenated to form a 32-bit output.
- Permutation (P-Box): The 32-bit output from the S-boxes is subjected to a fixed permutation (P-box permutation). This rearranges the bits according to a predetermined permutation table.
- XOR with Left Half: The output of the permutation step is XORed with the original left half (L0).
- Swap Left and Right Halves: The result of the XOR operation becomes the new right half (R1), and the original right half (R0) becomes the new left half (L1) for round 2 we’ll repeat these steps with respective key on L1 and R1 and so on.
- The transformation is accomplished through a combination of substitution (using S-boxes), permutation, and bitwise operations.
- The use of a different subkey for each round adds variability to the encryption process, enhancing security.
5. Final Permutation (FP):
After the 16th round, the left and right halves are swapped one last time. The final result undergoes a final permutation (inverse of the initial permutation) to generate the 64-bit block of ciphertext.
Here comes the codding part:
This is the code for 64-bit input.
For each character, we’ll get the ASCII value of the character and convert it to binary and each character will be converted into 8-bit binary representation.
Here are some tables we’ll need for our program:
#initail permutation
ip_table = [
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
]
# PC1 permutation table
pc1_table = [
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 left shift schedule for each round
shift_schedule = [1, 1, 2, 2,
2, 2, 2, 2,
1, 2, 2, 2,
2, 2, 2, 1]
# PC2 permutation table
pc2_table = [
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
]
#expension
e_box_table = [
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
]
# S-box tables for DES
s_boxes = [
# S-box 1
[
[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]
],
# S-box 2
[
[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]
],
# S-box 3
[
[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]
],
# S-box 4
[
[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]
],
# S-box 5
[
[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]
],
# S-box 6
[
[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]
],
# S-box 7
[
[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]
],
# S-box 8
[
[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]
]
]
p_box_table = [
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
]
ip_inverse_table = [
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
]Function for the conversion of string to binary of 64 bits:
def str_to_bin(user_input):
# Convert the string to binary
binary_representation = ''
for char in user_input:
# Get ASCII value of the character and convert it to binary
binary_char = format(ord(char), '08b')
binary_representation += binary_char
binary_representation = binary_representation[:64]
# Pad or truncate the binary representation to 64 bits
binary_representation = binary_representation[:64].ljust(64, '0')
# Print the binary representation
# print("Binary representation of input string: ", binary_representation)
# print(len(binary_representation), 'bits of input string')
return binary_representationFunction for conversion of binary to ASCII:
def binary_to_ascii(binary_str):
ascii_str = ''.join([chr(int(binary_str[i:i+8], 2)) for i in range(0, len(binary_str), 8)])
return ascii_strFunction for implementation of initial permutation on the binary string:
def ip_on_binary_rep(binary_representation):
ip_result = [None] * 64
for i in range(64):
ip_result[i] = binary_representation[ip_table[i] - 1]
# Convert the result back to a string for better visualization
ip_result_str = ''.join(ip_result)
return ip_result_strFunction for binary representation of key:
def key_in_binary_conv():
# Original key (can be changed but it should be 8 char)
original_key = 'abcdefgh'
binary_representation_key = ''
for char in original_key:
# Convert the characters to binary and concatenate to form a 64-bit binary string
binary_key = format(ord(char), '08b')
binary_representation_key += binary_key
return binary_representation_keyFunction for generating keys for each round and saving them in a list:
def generate_round_keys():
# Key into binary
binary_representation_key = key_in_binary_conv()
pc1_key_str = ''.join(binary_representation_key[bit - 1] for bit in pc1_table)
# Split the 56-bit key into two 28-bit halves
c0 = pc1_key_str[:28]
d0 = pc1_key_str[28:]
round_keys = []
for round_num in range(16):
# Perform left circular shift on C and D
c0 = c0[shift_schedule[round_num]:] + c0[:shift_schedule[round_num]]
d0 = d0[shift_schedule[round_num]:] + d0[:shift_schedule[round_num]]
# Concatenate C and D
cd_concatenated = c0 + d0
# Apply the PC2 permutation
round_key = ''.join(cd_concatenated[bit - 1] for bit in pc2_table)
# Store the round key
round_keys.append(round_key)
return round_keysFunction for encryption(we’ll use previous functions in it):
def encryption(user_input):
binary_rep_of_input = str_to_bin(user_input)
# Initialize lists to store round keys
round_keys = generate_round_keys()
ip_result_str = ip_on_binary_rep(binary_rep_of_input)
# the initial permutation result is devided into 2 halfs
lpt = ip_result_str[:32]
rpt = ip_result_str[32:]
# Assume 'rpt' is the 32-bit right half, 'lpt' is the 32-bit left half, and 'round_keys' is a list of 16 round keys
for round_num in range(16):
# Perform expansion (32 bits to 48 bits)
expanded_result = [rpt[i - 1] for i in e_box_table]
# Convert the result back to a string for better visualization
expanded_result_str = ''.join(expanded_result)
# Round key for the current round
round_key_str = round_keys[round_num]
xor_result_str = ''
for i in range(48):
xor_result_str += str(int(expanded_result_str[i]) ^ int(round_key_str[i]))
# Split the 48-bit string into 8 groups of 6 bits each
six_bit_groups = [xor_result_str[i:i+6] for i in range(0, 48, 6)]
# Initialize the substituted bits string
s_box_substituted = ''
# Apply S-box substitution for each 6-bit group
for i in range(8):
# Extract the row and column bits
row_bits = int(six_bit_groups[i][0] + six_bit_groups[i][-1], 2)
col_bits = int(six_bit_groups[i][1:-1], 2)
# Lookup the S-box value
s_box_value = s_boxes[i][row_bits][col_bits]
# Convert the S-box value to a 4-bit binary string and append to the result
s_box_substituted += format(s_box_value, '04b')
# Apply a P permutation to the result
p_box_result = [s_box_substituted[i - 1] for i in p_box_table]
# # Convert the result back to a string for better visualization
# p_box_result_str = ''.join(p_box_result)
# Convert LPT to a list of bits for the XOR operation
lpt_list = list(lpt)
# Perform XOR operation
new_rpt = [str(int(lpt_list[i]) ^ int(p_box_result[i])) for i in range(32)]
# Convert the result back to a string for better visualization
new_rpt_str = ''.join(new_rpt)
# Update LPT and RPT for the next round
lpt = rpt
rpt = new_rpt_str
# Print or use the RPT for each round
print('\n')
# At this point, 'lpt' and 'rpt' contain the final left and right halves after 16 rounds
# After the final round, reverse the last swap
final_result = rpt + lpt
# Perform the final permutation (IP-1)
final_cipher = [final_result[ip_inverse_table[i] - 1] for i in range(64)]
# Convert the result back to a string for better visualization
final_cipher_str = ''.join(final_cipher)
# Print or use the final cipher(binary)
# print("Final Cipher binary:", final_cipher_str, len(final_cipher_str))
# Convert binary cipher to ascii
final_cipher_ascii = binary_to_ascii(final_cipher_str)
print("Final Cipher text:", final_cipher_ascii , len(final_cipher_ascii))
return final_cipher_asciiFunction for Decryption:
# decryption of cipher to origional
def decryption(final_cipher):
# Initialize lists to store round keys
round_keys = generate_round_keys()
# Apply Initial Permutation
ip_dec_result_str = ip_on_binary_rep(final_cipher)
lpt = ip_dec_result_str[:32]
rpt = ip_dec_result_str[32:]
for round_num in range(16):
# Perform expansion (32 bits to 48 bits)
expanded_result = [rpt[i - 1] for i in e_box_table]
# Convert the result back to a string for better visualization
expanded_result_str = ''.join(expanded_result)
# print(expanded_result_str)
# Round key for the current round
round_key_str = round_keys[15-round_num]
# XOR between key and expanded result
xor_result_str = ''
for i in range(48):
xor_result_str += str(int(expanded_result_str[i]) ^ int(round_key_str[i]))
# Split the 48-bit string into 8 groups of 6 bits each
six_bit_groups = [xor_result_str[i:i+6] for i in range(0, 48, 6)]
# Initialize the substituted bits string
s_box_substituted = ''
# Apply S-box substitution for each 6-bit group
for i in range(8):
# Extract the row and column bits
row_bits = int(six_bit_groups[i][0] + six_bit_groups[i][-1], 2)
col_bits = int(six_bit_groups[i][1:-1], 2)
# Lookup the S-box value
s_box_value = s_boxes[i][row_bits][col_bits]
# Convert the S-box value to a 4-bit binary string and append to the result
s_box_substituted += format(s_box_value, '04b')
# Apply a P permutation to the result
p_box_result = [s_box_substituted[i - 1] for i in p_box_table]
# Convert the result back to a string for better visualization
# p_box_result_str = ''.join(p_box_result)
# Convert LPT to a list of bits for the XOR operation
lpt_list = list(lpt)
# Perform XOR operation
new_rpt = [str(int(lpt_list[i]) ^ int(p_box_result[i])) for i in range(32)]
# Convert the result back to a string for better visualization
new_rpt_str = ''.join(new_rpt)
# Update LPT and RPT for the next round
lpt = rpt
rpt = new_rpt_str
# Print or use the RPT for each round
print('\n')
final_result = rpt + lpt
# Perform the final permutation (IP-1)
final_cipher = [final_result[ip_inverse_table[i] - 1] for i in range(64)]
# Convert the result back to a string for better visualization
final_cipher_str = ''.join(final_cipher)
# Print or use the final cipher
# binary cipher string to ascii
final_cipher_ascii = binary_to_ascii(final_cipher_str)
print("Decryption of Cipher :", final_cipher_ascii)
return final_cipher_asciiStart :
user will enter a string between 1 to 8 characters for encryption and decryption using DES.
# Start
# user input
user_input = input("Enter a string: ")
# Encryption
enc = encryption(user_input)
# Decyption
# First we'll convert Final Cipher text into binary
enc_to_binary = str_to_bin(enc)
# we'll call the decryption function
dec = decryption(enc_to_binary)
