Cryptology: The Block Cipher (The Data Encryption Standard)

[an error occurred while processing this directive]

digital cryptography

The Data Encryption Standard (DES), adopted by the American National Standards Institute (ANSI) in 1976, is a block cipher algorithm that has been widely used as a secure way to transfer data. The DES is based on an algorithm developed by IBM in the early 1970s, called LUCIFER. It was adopted by ANSI for its high level and key-based security (the security resides in the key), its efficiency, and its exportability.

The DES is a block cipher. The DES takes in 64 bits of plaintext at a time, and returns 64 bits of ciphertext. A 64-bit key is used to encrypt the data (although only 56 bits are actually used). The DES has 16 rounds. Each round, the block is enciphered using a similar method. There is only a slight difference each round in the way the key is used. Although not every detail is covered on this page, you should get a general idea of how the DES works.

The first step of the DES is to take in a 64-bit block, and permute it. This step is referred to as the initial permutation. In actuality, this first step is just a transposition cipher. Each of the 64 bits (with the exception of the 22nd bit) is moved to a different spot in the block. The following table illustrates to what position each bit is moved in this transposition cipher:

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 60 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7

The following steps are all repeated each of the 16 rounds of DES. The initial permutation is only used once. The first step in the loop is a transposition cipher of the 56-bit key (every eighth bit is removed for error checking prior to starting the algorithm). The following table illustrates where each bit of the key is moved:

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

Next, the key is divided into two halves and shifted left one or two digits, depending on the round number. Forty-eight of the 56 bits are chosen to assist in the round of encryption.

The left half of the permuted block (32 bits) now goes through an expansion permutation, meaning some of the bits are repeated in other places. The block increases in size from 32 bits to 48 bits. Notice how both the left half of the block and the key are now the same size. Naturally, since both are now 48 bits, they are XORed with each other.

The result of the XOR now becomes the left half of our block. This 48-bit block is now divided into eight 6-bit blocks. Each of these blocks will go through a substitution box, or an S-Box. In the DES, each S-Box is a table with 16 columns and 4 rows. Each cell holds a 4-bit number (0-15). Each of the 6-bit blocks has a different S-Box. To save space, we will only illustrate one of the S-Boxes, #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

With this S-Box, we take the first 6-bit block, and separate it into two numbers. We first take the first and last bit of the block. This 2-bit number represents the row number of the S-Box. The middle four bits represent the column number. For example, if our 6-bit block is 111100, then our row is 10 (corresponding to row 3), and our column is 1110 (corresponding to column 15). In this case, the corresponding cell would contain the value 5. This number is converted to a four-bit binary number (0101), and substituted in place of the previous 6-bit number. When all the 6-bit numbers go through their S-box substitution, we are left back with a 32-bit block.

Our 32-bit number now goes through a simple transposition cipher. Each and every bit is moved somewhere else. The following table illustrates where each bit is moved:

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

Lastly, the result of this transposition cipher is XORed with the initial left half of the 64-bit block. The result of the XOR and the right half of the initial 64-block are switched.

This process repeats 16 times. After all 16 rounds, the left and right half are combined, and the 64-bit block of ciphertext goes through one final permutation. This permutation is actually the inverse of the initial permutation, meaning every bit of ciphertext goes back to where its initial bit of plaintext was. Here is a table illustrating where each bit goes:

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

After this final permutation, the process is done. Assuming your key is not known by others, you now have an extremely secure piece of ciphertext. So, you're probably wondering how to decrypt it. DES decryption is virtually the same as DES encryption. The same process will decrypt your message, but there is one slight change. During decryption, the keys used during each round are reversed, meaning you start with the sixteenth key and work backwards until you use the original key. Additionally, the key permutation table is reversed, and the key is shifted to the right, not the left.

Now that you know all about block ciphers and about one of the most secure encryption algorithms, you are ready for a CryptAgent Challenge! This challenge is worth 15 points. If you can't figure it out, just remember: it's not as difficult as cracking the DES! Here it is!

If you're not a CryptAgent, you can find out more and register if you like. It's free, and it's fun!

[an error occurred while processing this directive]