Data Encryption Standard

By Raewyn Smith

This page stems from an essay I did at Auckland University for the Stage 4 History of Computing paper (in 1996). Most the information is reasonably accurate, but some of it may be my own interpretation of events. Please don't take anything stated here as absolute fact. Look up DES in your library if you want a completely accurate unbiased account.

Feel free to ask me any questions to clarify aspects of the algorithm as outlined here. Just remember I am no expert in cryptography, in fact my knowledge of the subject goes little beyond what's presented here.

I don't have any implementations of this algorthim - I have never written one. Please don't email with requests for implementations - they'll go unanswered.

Here is a link to an implementation of DES in BASIC.

DES is the Data Encryption Standard. This encryption technique was developed in the 1970's.

Cryptography Background

During the Second World War, much advancement was made in the field of cryptography. This was due to the advent of radio as a communications device. The great thing about radio was that anyone could coummunicate with anyone, anywhere else. Unfortunately this meant that the enemy could also listen in on your communications. So the obvious thing to do was to disguise your message by encrypting it. However, if the enemy found out how to break your code, you would be in big trouble, so the government was extremely catious about allowing any information about their encryption techniques to be known by the general public. So all through World War 2, the area of cryptography was shrouded in secrecy, and even after the war ended, the British and American government were still very paranoid, and kept all research in this area a big seceret.

New Demand for Cryptography Techniques

The traditional use of cryptography was to make messages unreadable to the enemy during wartime. However the introduction of the computing age changed this perspective dramatically. Through the use of computers, a whole new use for information hiding was evolved. Around the early 1970's the private sector began to feel the need for cryptographic methods to protect their data. This could include 'sensitive information' (corporate secrets), password files or personal records. However at this time, no information on encryption techniques was available for public use. So, they complained, and the government finally gave permission for a data encryption standard to be developed.

The DEA

The original ideas behind the Data Encryption Algorithm were developed by IBM in the 1960's. The used concepts which had been described by Claude Shannon in the 1940's. They called their technique Lucifer. Lucifer was refined, renamed the DEA (Data Encryption Algorithm) and adopted as the standard in 1976.

Inside the Algorithm

The DEA performs a transformation on a block of 64 bits using a 56 bit key. I.E. it takes 64 bits of the plain text (data to be encrypted) and changes it into a different 64 bits (the cipher text), using a key (known only by the person 'sending' the 'message' and the person 'receiving' it). It does this in several steps, using several kinds of transformations.

Crucial to the DEA is the concept of a permutation. This just means that the bits are put in a different order, ie juggled up. The permutations performed in the algorithm are all defined by the specification. These are the IP, Key Transformation, P, Expansion Function and IP inverse.

The algorithm as a whole

Firstly the IP (explained below) is applied to the 64 bit plaintext. The result is then divided into two 32 bit halves, named L₀ and R₀. Then, the following happens 16 times:
(Iteration number i)

Key transformation number i (a permutation, but dropping 8 bits off - defined in the specification) is applied to the key to produce 48 bits.
Let A be L_i and J be the transformed key. Apply the function f(A,J) (explained below) to produce a 32 bit output.
Exclusive Or R_i and f(A,J), and call this R_i+1.
Make L_i+1 = R_i

A diagram showing how the DEA works

After the 16 iterations, IP inverse is applied (the reverse of IP).

IP - the Initial Permutation

This step just takes the 64 bits, and changes their order around according to a fixed permutation. So the 58th bit becomes the first bit, the 50th bit becomes the 2nd bit, etc.

The function f

Next, 16 iterations of a function f are applied. f takes 32 bits of the plaintext (A) and 48 bits of the key (J). An expansion function is applied to A, which swaps some of the bits around, and adds an extra 16 of them, which expands it out to 48 bits. The expanded A and J are then combined, using Exclusive Or. This 48 bit block is then put through some S boxes (explained soon) to produce an output of 32 bits. Finally another permutation called P is applied.
A diagram of the function f

S-Boxes

An S-Box takes a 6 bit input and gives a 4 bit output. This process uses a table (called an S Box) with 4 rows and 16 columns, like this one:

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

To get the 4 bit output, take the first and last bits of the 6 bit input to decide on the row, take the middle 4 bits to decide on the column, and do a table lookup. For example, with input of 110111 and the above S-Box, the first and last bits are 11 (row 3) and the middle four bits are 1011 (column 11) so the output number is 14 (ie 1110 in binary). (note - rows and columns are indexed started from 0, so the first row is row 0 and the first columns is column 0)

The way the S-Boxes are used in the function f, is that the 48 bits of input are divided into 6 bit chunks, put through 8 S-Boxes (these are defined in the specification of the algorithm), and 8 4 bit chunks are returned, producing the 32 bit output.

Controversy

There has been much speculation about the DES, and how secure it is. Several people have proposed ways of breaking the code - these all involve lots of money, very powerful computers and a long time. However it is not unthinkable that such a computer could be built by someone with lots of money and resources (ie the American Government).

Several descisions made in the development of the algorithm shed a bit of doubt on it's security. When originally proposed, the length of the key was 64 bits. Before it was made the standard, this was revised to be only 56 bits. Why the change? It has been suggested that the USA Government may have prompted this descision. A 64 bit key means that there are far, far too many keys for anyone to think about trying to do an exhaustive search (ie going through all the keys one, by one, trying to find the right one). However a 56 bit key, although still very big, makes an exhaustive search almost feasible on an extremely fast computer. Since no one but the Government Agencies possess such fast computers, this puts suspicion on them. They may have wanted to reduce the key space to allow them to be able to crack a code if necessary.

The other controversial aspect of the release of the DES was that the complete design criteria were never published. Since not all of the steps in the algorithm seem logical, or obvious, this is slightly suspicious. Could the government somehow have encoded a "trapdoor" into the algorithm? The government could have some kind of knowledge about the structure of the S-Boxes that allows them to easily decrypt any encoded message. However no evidence of such a thing has been found (despite extensive study of the algorithm), although no proof that it doesn't exist has been found either.

Present Day use of the DES

The doubt on the complete security of the DES meant that many people were deterred from using it. In fact public key encryption became popular before the DES even had a chance to get off the ground. There are a few commercial uses of the encryption scheme (such as the coding of video signals in pay TV), however it is not expected to remain a standard past 1998, when it is being reviewed again.

Back to my home page