The Data Encryption Standard (DES) is a symmetric-key algorithm for the encryption of digital data. Symmetric-key algorithms use the same key for both encryption and decryption, which necessitates secure key management. DES is a block cipher, meaning it encrypts data in fixed-size blocks. Specifically, DES processes data in 64-bit blocks, utilizing a 56-bit key to perform the encryption and decryption processes. The key length is actually 64 bits, but 8 of those bits are used solely for parity checking and do not contribute to the effective key strength.
The DES algorithm employs a series of complex transformations to ensure the security of the encryption. One of the fundamental components of DES is the use of subkeys. Subkeys are derived from the main key and are used in the various rounds of the encryption process. In DES, the encryption process involves 16 rounds of permutation and substitution, and a unique subkey is used in each round.
To understand how subkeys are generated and used in DES, one must consider the key schedule algorithm. The key schedule is a important part of DES that describes how the main key is transformed into the 16 subkeys. Here is a detailed explanation of this process:
1. Initial Key Permutation (PC-1): The first step in generating subkeys is to permute the original 56-bit key using a fixed table known as Permuted Choice 1 (PC-1). This permutation rearranges the bits of the key to produce a 56-bit output. The bits are not simply shuffled; they are selected and reordered according to the PC-1 table. The 64-bit key, with 8 parity bits removed, is reduced to 56 bits.
2. Splitting the Key: The 56-bit permuted key is then divided into two 28-bit halves, denoted as and . These halves will be used to generate the subkeys for each round.
3. Key Shifts: For each of the 16 rounds, the two halves and are cyclically shifted left by one or two positions. The number of positions shifted depends on the round number. Specifically, the shift values are determined by a predefined schedule. For example, in the first round, both halves are shifted left by one position, while in the second round, they are shifted by two positions, and so on. This shifting process ensures that each subkey is derived from a different permutation of the original key.
4. Permuted Choice 2 (PC-2): After the left shifts, the two 28-bit halves are combined to form a 56-bit concatenated key. This 56-bit key is then permuted again using another fixed table known as Permuted Choice 2 (PC-2). PC-2 selects 48 bits from the 56-bit concatenated key to form the subkey for that round. The selection and reordering of bits are done according to the PC-2 table, ensuring that each subkey is unique and derived from the original key in a complex manner.
5. Subkey Generation: This process is repeated for each of the 16 rounds, resulting in 16 unique 48-bit subkeys. These subkeys are denoted as , where represents the subkey used in the -th round of the DES algorithm.
The use of subkeys in DES is integral to the encryption process. During each round of DES, a subkey is combined with the data block using a series of transformations, including the Feistel function. The Feistel function is a critical component of DES and involves several steps:
1. Expansion: The 32-bit half-block of data is expanded to 48 bits using an expansion permutation. This permutation replicates certain bits to increase the size of the half-block, ensuring that it matches the size of the subkey.
2. Key Mixing: The expanded 48-bit data block is XORed with the 48-bit subkey for that round. This operation combines the data with the subkey in a way that is difficult to reverse without knowledge of the subkey.
3. Substitution: The result of the XOR operation is divided into eight 6-bit segments. Each segment is then passed through a substitution box (S-box), which maps the 6-bit input to a 4-bit output. DES uses eight different S-boxes, each with a unique substitution pattern. The S-boxes introduce non-linearity into the encryption process, which is important for the security of DES.
4. Permutation: The 32-bit output from the S-boxes is then permuted using a fixed permutation table known as the P-box. This permutation reorders the bits to further obscure the relationship between the plaintext and the ciphertext.
5. Feistel Structure: The output of the P-box is XORed with the other half-block of data. This completes one round of the Feistel structure, and the process is repeated for each of the 16 rounds, using a different subkey each time.
The repeated use of subkeys in conjunction with the Feistel function ensures that the encryption process is highly secure. Each round introduces additional complexity and diffusion, making it extremely difficult for an attacker to reverse the encryption without knowledge of the key.
To illustrate the subkey generation process with an example, consider a simplified version of DES with a shorter key and fewer rounds. Suppose we have an 8-bit key and 4 rounds of encryption. The key schedule might look like this:
1. Initial Key: 10110110 (8 bits)
2. Initial Permutation (PC-1): Rearrange the bits to form the 6-bit key: 110110 (6 bits)
3. Splitting the Key: Divide the 6-bit key into two 3-bit halves: and
4. Key Shifts:
– Round 1: Shift left by 1 position: and
– Round 2: Shift left by 2 positions: and
– Round 3: Shift left by 1 position: and
– Round 4: Shift left by 2 positions: and
5. Permuted Choice 2 (PC-2): Select 4 bits from the combined 6-bit key for each round:
– Round 1 Subkey: 1010
– Round 2 Subkey: 0011
– Round 3 Subkey: 1010
– Round 4 Subkey: 0011
In this simplified example, the subkeys are generated by permuting and shifting the original key, similar to the process used in DES. Each round uses a different subkey, ensuring that the encryption process is secure and resistant to attacks.
The generation and use of subkeys in DES are fundamental to the security of the algorithm. By transforming the original key into multiple subkeys and using them in a series of complex transformations, DES achieves a high level of security. The intricate process of key schedule and subkey generation ensures that even if an attacker knows the ciphertext, they cannot easily deduce the plaintext or the key.
Other recent questions and answers regarding Data Encryption Standard (DES) - Encryption:
- Can single bit of ciphertext be influenced by many bit of plaintext in DES?
- Does DES depends on multiple combinations of diffusion and confusion?
- Is DES prone to the meet-in-the-middle attack?
- Can permutation be considered as an example of diffusion in a block cipher?
- At the stage of S-boxes in DES since we are reducing fragment of a message by 50% is there a guarantee we don’t loose data and message stays recoverable / decryptable?
- What is the significance of the avalanche effect in the DES encryption process?
- How does the permutation P contribute to the final output of the f function in DES encryption?
- What is the role of the S-boxes in the DES encryption process?
- How does the expansion box contribute to the confusion and diffusion elements of DES encryption?
- What is the purpose of the Initial Permutation (IP) in the DES block cipher cryptosystem?
View more questions and answers in Data Encryption Standard (DES) - Encryption