Tareque's Personal Portal

DES Alogrithm Illustrated

Disclaimer: All material provided in this post is for educational purpose only. Any other usage is strongly discouraged.

As part of a project for the Network Security course (Spring 2010) at GWU, I implemented DES or Data Encryption Standard in C. DES is an ancient encryption algorithm that is not used anymore since its effective key size is 56 bit which can be easily broken using brute force. However the same algorithm can be used to encrypt data in Triple-DES which has an effective key length of 168 bit and used everywhere.

According to Wikipedia:

The Data Encryption Standard (DES) is a block cipher (a form of shared secret encryption) that was selected by the National Bureau of Standards as an official Federal Information Processing Standard (FIPS) for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is based on a symmetric-key algorithm that uses a 56-bit key. The algorithm was initially controversial with classified design elements, a relatively short key length, and suspicions about a National Security Agency (NSA) backdoor. DES consequently came under intense academic scrutiny which motivated the modern understanding of block ciphers and their cryptanalysis.

You will be surprised by the lack of friendly and comprehendible DES implementations available as on the internet. Thankfully there are really great resources describing the algorithm step by step using examples. The article I used to write this implementation is The DES Algorithm Illustrated by J. Orlin Grabbe. It provides some interesting background on DES and NSA's attempt to create backdoors in the algorithm.

My implementation follows the article at each step. So if you are trying learn and implement DES, then you should be able to follow the code as you go through the article.

For example the section Step 1: Create 16 subkeys, each of which is 48-bits long maps to the function:

void generate_sub_keys(unsigned char* main_key, key_set* key_sets)

located here. Similarly the section Step 2: Encode each 64-bit block of data maps to the function

void process_message(unsigned char* message_piece, unsigned char* processed_piece, key_set* key_sets, int mode)

located here.

This also means that the code is not optimized in anyway. Key generation takes constant time. But encryption/ decryption O(N) where N is the file size. For example, encrypting the Firefox 3.6.3 Mac OSX installer sized at 18.6 MB takes about 30.66 seconds. Decryption takes slightly longer, 31.33 seconds. With a few quick optimizations I was able to cut this time in half. But the optimization severely sacrificed code readability. So I abandoned the plan of optimization. If you want speed, you will have to look for Assembly implementations. I found out that someone in MIT wrote a high performance version in assembly which is capable of en/decrypting files at ~20 MBps.

I have created a repository on GitHub where you can find all the source code, compiling and usage instructions. You can clone the repository or download the archived version des.zip.