# DES Explanation

This page explains *this* DES implementation at the bit level.
If you find any errors, bugs, security holes, or have any questions or comments please
contact me.

- References
- Platform and Browser compatibility
- Summary
- Triple DES
- Creating the Keys - PC1
- Creating the Keys - Left Shifts
- Creating the Keys - PC2
- Encrypting the message - IP1
- Encrypting the message - E
- Encrypting the message - S Selection Functions
- Encrypting the message - P
- Encrypting the message - IP-1
- DES Modes
- Padding
- Algorithm Speed
- Functions Provided
- Back to main DES page

**References**

To understand this implementation, you'll first need to understand bit operations
and read some more general explanations of DES. I highly recommend
The DES Algorithm Illustrated by J. Orlin Grabbe or
Data Encryption Standard, a FIPS publication.
For a detailed explanation of the different modes, see
DES Modes of Operation, also a FIPS publication.

**Platform and Browser Compatibility**

Javascript DES has been tested on Internet Explorer and Netscape on a PC. It was
recently fixed to work on Macintoshes as well (by changing all references to numbers
greater than 0x80000000 into their negative equivalents). It has been tested against
the PHP mcrypt library, and Microsoft's .NET. If you have problems comparing
the results of Javascript DES to any other implementation, be sure you are using
the same mode and padding.

**Summary**

In general, DES takes as input a 64 bit key, of which only 56 bits are used. From these
56 bits, 16 48 bit subkeys are created. The message is split into 64 bit chunks, and a
complex series of steps enciphers the message using each subkey. As Javascript only
supports 32 bit integers, all 48 or 64 bit integers are represented by two 32 bit integers
stored as different variables.

**Triple DES**

Triple DES is very similar to the processes described below, except everything is done
three times. So Triple DES expects a 24 bytes (192 bit) key, of which 168 bits are used.
Every eight bytes of the message are operated on three times (for instance, a triple
DES encryption will encrypt, decrypt, and encrypt the data) before being appended
to the result. CBC mode uses the result of the first 8 byte triple DES encryption to feed back into the
algorithm.

Many thanks to Walter Horodyski who ran tests (against PHP's mcrypt libary) to see what would happen if the user does not pass in a key of exactly 8 or 24 bytes. The Javascript DES used to run single DES if the key was less than 24 bytes or else triple DES. The mcrypt single DES algorithm only every runs single DES. It looks like the mcrypt triple DES algorithm runs single DES for keys of 8 bytes or less, or else triple DES. So I have now changed the Javascript version to behave like mcrypt's triple DES and run triple DES if the key is over 8 bytes.

**Creating the Keys - PC1**

DES must first create the 16 subkeys.
First, the 8 character string representing the key is turned into two integers which are
passed to the *des_createKeys* function. The bits of these two integers are then
reorganised according to PC1 (permuted choice 1). The bits end up in the following places:

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 | 0 | 0 | 0 | 0 |

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 | 0 | 0 | 0 | 0 |

This means that the first 57th bit of the original key becomes the first bit, etc.
The permuting is done using a permutation sequence, which is a clever way of rotating
and switching bits between 2 integers. For instance,
*temp = ((left >>> 4) ^ right) & 0x0f0f0f0f; right ^= temp; left ^= (temp << 4);*
rotates 4x4 blocks of bits:

33 | 34 | 35 | 36 | 1 | 2 | 3 | 4 |

41 | 42 | 43 | 44 | 9 | 10 | 11 | 12 |

49 | 50 | 51 | 52 | 17 | 18 | 19 | 20 |

57 | 58 | 59 | 60 | 25 | 26 | 27 | 28 |

37 | 38 | 39 | 40 | 5 | 6 | 7 | 8 |

45 | 46 | 47 | 48 | 13 | 14 | 15 | 16 |

53 | 54 | 55 | 56 | 21 | 22 | 23 | 24 |

61 | 62 | 63 | 64 | 29 | 30 | 31 | 32 |

I found this permutation function in Eric Young's C implementation. He gives credit to John Fletcher for determining the most efficient way to do PC1.

**Creating the Keys - Left Shifts**

In other DES explanations, the first 28 bits out of PC1 is called C, and the last 28 bits is D.
(Note that PC1 only uses 56 of the original 64 bits.) These are then left shifted
according to a schedule until 16 subkeys are created. For instance, C1 and D1 are created
by left shifting C and D by one place, C2 and D2 by a further one place, etc. Here is
what C1 and D1 look like relative to C and D:

2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |

18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |

26 | 27 | 28 | 1 | 0 | 0 | 0 | 0 |

34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 |

42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 |

50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 |

58 | 59 | 60 | 33 | 0 | 0 | 0 | 0 |

**Creating the Keys - PC2**

The 16 subkeys (C1 and D1 through to C16 and D16) are then permuted according
to PC2 to create 16 subkeys of 48 bits each.
PC2 seems to be a random bit sequence and so the permutation sequence above can't be
used. Instead the bits are permuted 4 at a time using the *pc2bytes* array of arrays.
*pc2bytes* contains 14 subarrays (one for each 4 bits of the 56 bit subkeys). Each
subarray contains 16 elements. Every four bits of a subkey are looked up in the corresponding
array and the results are all added together. For example, if the first four bits of
C1 are 0100 in binary, then the fourth element of *pc2bytes[0]*, 0x00010000 is added
to the result. This has the result of moving the 2nd bit of C1 to the 16th bit of the result
(some bit shifting is also applied at the end to put everything in the right place).
Here is what the resulting K1 though K16 look like relative to C1 and D1 through C16 and D16.
Note that this is different from the PC2 given in other DES explanations, the reason for
this is explained further down.

0 | 0 | 3 | 28 | 15 | 6 | 21 | 10 |

0 | 0 | 16 | 7 | 27 | 20 | 13 | 2 |

0 | 0 | 34 | 44 | 55 | 49 | 37 | 52 |

0 | 0 | 50 | 46 | 54 | 40 | 33 | 36 |

0 | 0 | 14 | 17 | 11 | 24 | 1 | 5 |

0 | 0 | 23 | 19 | 12 | 4 | 26 | 8 |

0 | 0 | 45 | 56 | 35 | 41 | 51 | 59 |

0 | 0 | 48 | 53 | 43 | 60 | 38 | 57 |

**Encrypting the Message - IP1**

With 16 subkeys created, we are now ready to deal with the message.
The message is encrypted or decrypted 64 bits (8 characters) at a time. The first step
is to perform the permuation IP. This again uses the permutation sequence. Eric
Young gives credit to Richard Outerbridge for helping make this more efficient.

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 |

**Encrypting the Message - E**

The resulting 64 bits are then encrypted or decrypted using the 16 subkeys. This requires
16 steps, during which the left and right half of the 64 bit message are alternatively operated on.
The operation involves taking 32 bits (called R in other explanations), permuting it according
to E (which expands R from 32 to 48 bits), XORing with one of the 48 bit subkeys to produce
a different 48 bits, then passing it through the S selection functions to get it back down to
32 bits, and finally permuting through P. Note that the E used here (displayed below) is different from
other Es, for the reason explained below.

0 | 0 | 3 | 4 | 5 | 6 | 7 | 8 |

0 | 0 | 11 | 12 | 13 | 14 | 15 | 16 |

0 | 0 | 19 | 20 | 21 | 22 | 23 | 24 |

0 | 0 | 27 | 28 | 29 | 30 | 31 | 32 |

0 | 0 | 31 | 32 | 1 | 2 | 3 | 4 |

0 | 0 | 7 | 8 | 9 | 10 | 11 | 12 |

0 | 0 | 15 | 16 | 17 | 18 | 19 | 20 |

0 | 0 | 23 | 24 | 25 | 26 | 27 | 28 |

**Encrypting the Message - S Selection Functions**

The step above expands 32 bits into 48 bits, and then XORs them with a subkey. The result
is passed through the S selection functions. There are 8 of these functions (labelled
S1 through S8 would you believe) which convert 6 bits into 4 bits. (Their randomness is part
of the reason why DES is so powerful, because a 1 bit uncertainty in the input yields 4 bits
of uncertainty in the output.) The first 6 bits of the output from the E permuation above are
passed through S2, the next 6 through S4, then S6, S8, S1, S3, S5 and S7. Using this ordering
makes it easier to perform E (as it is essentially done by duplicating the 32 bits), and PC2
was also changed to compensate for this. As with PC2, a series of 8 *spfunction* arrays of 64 elements
are used to perform the S functions. I can't show the output of the S functions
because it is not about bit movements. The 6 input bits to each S function could
produce any one of 16 results. Note that a further efficiency is applied by shifting the
input one bit to the left before encrypting, instead of during each encryption step
(and the *spfunction* are also shifted one left to compensate).

**Encrypting the Message - P**

The 32 bit output from the S functions is permuted again according to P. For efficiency,
this permuation is done as part of the S functions array. For example, the first 6 bits
out of E are looked up in the second S array, *spfunction2*. If these 6 bits are
all zero, then 0x40084010 is added to the result. If you refer to other DES descriptions,
they will tell you exactly what the S functions are, and you would see that the zeroth
element of S2 is 15. This means that if you pass binary 000000 into S2, you get 1111 as
output. These four bits are then moved around according to P (remembering to shift them
left once as well) and the result is 0x80108020.
Specifically, the bits are moved to positions 12, 27, 1, and 17.

**Encrypting the Message - IP-1**

After going through the above steps 16 times, the 64 bits are passed through IP-1 to
produce the cipher text. Decryption is performed using exactly the same process
but the subkeys are applied in the reverse order.

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 |

**DES Modes**

There are several different modes in which DES can be run. ECB (Electronic Codebook) mode
is the simplest mode. In this mode, each 64 bit chunk of the input message is treated
independently, thus it is also the least secure. In CBC (Cipher Block Chaining) mode,
you supply a 64 bit input vector. The first 64 bits of the message are XORed with this
before encrypting. The second 64 bits are then XORed with the cipher text from the first
64 bit before encrypting it, and so on.

**Padding**

The DES algorithm works on blocks of 8 bytes. If the input is not a multiple of 8,
there are several different padding options you can use. Pass in the last
parameter as 0 for to pad with null or zero bytes (/0) (as PHP's mcrypt library),
1 to for PKCS7 padding (see below), 2 for spaces and 3 for none. (This option
was added 16 June 2007.)

Microsoft's .NET has three padding options: none, PKCS7 and zeros. PKCS7 pads a string with a sequence of bytes, each of which is equal to the total number of padding bytes added. For example if 24 bits (3 bytes) of padding are needed, the padding string is 0x030303. The zeros option pads the string with null bytes and is the default for this implementation of DES. (Thanks to Serge Kaing for finding this information.)

**Algorithm Speed**

The first Javascript DES implemention worked fine for small data sets, but slowed down
incredibly on larger blocks. By making a few changes, the speed has been increased
dramatically. These changes were: storing the message and result as strings rather than
arrays (which take a comparitively long time to look things up); creating the result
string in blocks rather than one character at a time (periodically adding 512 characters
to a 32000 character string is much faster than adding one character at a time); and bringing
all global variables inside the functions (which also meant undoing the previous *permute*
function). Below is a table showing the speed increase on a Pentium 200 with Windows 98 and
Internet Explorer 5. I also tested it in the Galleon browser under Redhat Linux 7.2 on the same machine (sadly
it was quite a bit slower).
This times the single DES algorithm in ECB mode, in milliseconds.

Windows 98, IE 5.5 | Redhat 7.2Galleon | |||||

Before | After | |||||

Bytes | ms | ms/kb | ms | ms/kb | ms | ms/kb |

256 | 110 | 440 | 77 | 307 | 176 | 704 |

512 | 184 | 367 | 110 | 220 | 296 | 591 |

1024 | 384 | 384 | 204 | 204 | 598 | 598 |

2048 | 770 | 385 | 400 | 200 | 1,138 | 569 |

4096 | 1,647 | 412 | 827 | 207 | 2,195 | 549 |

8192 | 3,770 | 472 | 1,590 | 199 | 4,352 | 544 |

16384 | 10,254 | 641 | 3,260 | 204 | 8,596 | 538 |

32768 | 39,677 | 1,240 | 6,517 | 204 | 17,490 | 547 |

**Functions Provided**

Below are descriptions of each of the functions used in this DES implementation. The
first two are the core DES functions. The rest are not required to run DES
but were of great help in debugging and creating the *pc2bytes* and *spfunction* arrays.
The source code of these extra functions is provided below. (Find the DES source
on the DES usage page).

*des*- takes it's input as strings and performs DES encryption/decryption*des_createKeys*- given the left and right 32 bits of the key, creates an array of 16 subkeys

*stringToHex*- converts a string into hexidecimal*hexToString*- converts a string of hexidecimal digits into a string*integerToHex*- converts an integer into hexidecimal, makes numbers greater than 0x80000000 negative*integerArrayToHex*- converts an array of integers into a Javascript array definition of hexidecimals*integerToBinary*- converts an integer into binary*moveBits*- this is used to produce an array such as*pc2bytes*which can move bits around*convertStable*- converts an S table as found in other DES explanations into the right order*createSfunction*- produces the*spfunction*array given the P bit movements and an S selection function*wherethingsgo*- used throughout this page to show what a piece of code does to the bits*timeTrial*- times how long encryption took for different sized input