Editing Data Encryption Standard (section)

==Description==
{{hatnote|For brevity, the following description omits the exact transformations and permutations which specify the algorithm. For further details, see [[DES supplementary material]].}}
<imagemap>
File:DES-main-network.png|thumb|250px|''[[:File:DES-main-network.png|Figure 1]]''— The overall Feistel structure of DES
rect 0 130 639 229 [[DES supplementary material#Initial permutation (IP)|Initial permutation]]
rect 220 300 421 405 [[#The Feistel (F) function|Feistel function]]
rect 220 594 421 701 [[#The Feistel (F) function|Feistel function]]
rect 220 1037 421 1144 [[#The Feistel (F) function|Feistel function]]
rect 220 1330 421 1437 [[#The Feistel (F) function|Feistel function]]
rect 0 1478 639 1577 [[DES supplementary material#Final permutation (IP-1)|Final permutation]]
circle 50 351 26 [[Exclusive or|XOR]]
circle 50 647 26 [[Exclusive or|XOR]]
circle 50 1090 26 [[Exclusive or|XOR]]
circle 50 1383 26 [[Exclusive or|XOR]]
</imagemap>
DES is the archetypal [[block cipher]]—an [[algorithm]] that takes a fixed-length string of [[plaintext]] bits and transforms it through a series of complicated operations into another [[ciphertext]] bitstring of the same length. In the case of DES, the [[block size (cryptography)|block size]] is 64 bits. DES also uses a [[key (cryptography)|key]] to customize the transformation, so that decryption can supposedly only be performed by those who know the particular key used to encrypt. The key ostensibly consists of 64 bits; however, only 56 of these are actually used by the algorithm. Eight bits are used solely for checking [[parity bit|parity]], and are thereafter discarded. Hence the effective [[key length]] is 56 bits.

The key is nominally stored or transmitted as 8 [[byte]]s, each with odd parity. According to ANSI X3.92-1981 (Now, known as ANSI [[INCITS]] 92–1981), section 3.5:

{{blockquote|One bit in each 8-bit byte of the ''KEY'' may be utilized for error detection in key generation, distribution, and storage. Bits 8, 16,..., 64 are for use in ensuring that each byte is of odd parity.}}

Like other block ciphers, DES by itself is not a secure means of encryption, but must instead be used in a [[block cipher mode of operation|mode of operation]]. FIPS-81 specifies several modes for use with DES.<ref>{{cite web|url=http://csrc.nist.gov/publications/fips/fips81/fips81.htm |title=FIPS 81 - Des Modes of Operation |publisher=csrc.nist.gov |access-date=2009-06-02}}</ref> Further comments on the usage of DES are contained in FIPS-74.<ref>{{cite web |url=http://www.itl.nist.gov/fipspubs/fip74.htm |title=FIPS 74 - Guidelines for Implementing and Using the NBS Data |publisher=Itl.nist.gov |access-date=2009-06-02 |archive-url=https://web.archive.org/web/20140103013152/http://www.itl.nist.gov/fipspubs/fip74.htm |archive-date=2014-01-03 |url-status=dead }}</ref>

Decryption uses the same structure as encryption, but with the keys used in reverse order. (This has the advantage that the same hardware or software can be used in both directions.)

=== Overall structure ===
{{more citations needed section|date=August 2009}}
The algorithm's overall structure is shown in Figure 1: there are 16 identical stages of processing, termed ''rounds''. There is also an initial and final [[permutation]], termed ''IP'' and ''FP'', which are [[inverse function|inverses]] (IP "undoes" the action of FP, and vice versa). IP and FP have no cryptographic significance, but were included in order to facilitate loading blocks in and out of mid-1970s 8-bit based hardware.<ref>{{Cite book|last=Schneier|title=Applied Cryptography|edition=1st|page=271}}</ref>

Before the main rounds, the block is divided into two 32-bit halves and processed alternately; this criss-crossing is known as the [[Feistel scheme]]. The Feistel structure ensures that decryption and encryption are very similar processes—the only difference is that the subkeys are applied in the reverse order when decrypting. The rest of the algorithm is identical. This greatly simplifies implementation, particularly in hardware, as there is no need for separate encryption and decryption algorithms.

The ⊕ symbol denotes the [[XOR|
exclusive-OR]] (XOR) operation. The ''F-function'' scrambles half a block together with some of the key. The output from the F-function is then combined with the other half of the block, and the halves are swapped before the next round. After the final round, the halves are swapped; this is a feature of the Feistel structure which makes encryption and decryption similar processes.

=== The Feistel (F) function ===
The F-function, depicted in Figure 2, operates on half a block (32 bits) at a time and consists of four stages:
<imagemap>
File:Data_Encription_Standard_Flow_Diagram.svg|thumb|250px|''[[:File:DES-f-function.png|Figure 2]]''—The Feistel function (F-function) of DES
rect 10 88 322 170 [[DES supplementary material#Expansion function (E)|Expansion function]]
rect 9 340 77 395 [[DES supplementary material#Substitution boxes (S-boxes)|Substitution box 1]]
rect 89 340 157 395 [[DES supplementary material#Substitution boxes (S-boxes)|Substitution box 2]]
rect 169 340 237 395 [[DES supplementary material#Substitution boxes (S-boxes)|Substitution box 3]]
rect 247 340 315 395 [[DES supplementary material#Substitution boxes (S-boxes)|Substitution box 4]]
rect 327 340 395 395 [[DES supplementary material#Substitution boxes (S-boxes)|Substitution box 5]]
rect 405 340 473 395 [[DES supplementary material#Substitution boxes (S-boxes)|Substitution box 6]]
rect 485 340 553 395 [[DES supplementary material#Substitution boxes (S-boxes)|Substitution box 7]]
rect 565 340 633 395 [[DES supplementary material#Substitution boxes (S-boxes)|Substitution box 8]]
rect 9 482 630 565 [[DES supplementary material#Permutation (P)|Permutation]]
circle 319 232 21 [[Exclusive or|XOR]]
</imagemap>
# ''Expansion'': the 32-bit half-block is expanded to 48 bits using the ''expansion permutation'', denoted ''E'' in the diagram, by duplicating half of the bits. The output consists of eight 6-bit (8 × 6 = 48 bits) pieces, each containing a copy of 4 corresponding input bits, plus a copy of the immediately adjacent bit from each of the input pieces to either side.
# ''Key mixing'': the result is combined with a ''subkey'' using an XOR operation. Sixteen 48-bit subkeys—one for each round—are derived from the main key using the ''[[key schedule]]'' (described below).
# ''Substitution'': after mixing in the subkey, the block is divided into eight 6-bit pieces before processing by the ''[[Substitution box|S-boxes]]'', or ''substitution boxes''. Each of the eight S-boxes replaces its six input bits with four output bits according to a non-linear transformation, provided in the form of a [[lookup table]]. The S-boxes provide the core of the security of DES—without them, the cipher would be linear, and trivially breakable.
# ''Permutation'': finally, the 32 outputs from the S-boxes are rearranged according to a fixed [[permutation]], the ''P-box''. This is designed so that, after permutation, the bits from the output of each S-box in this round are spread across four different S-boxes in the next round.

The alternation of substitution from the S-boxes, and permutation of bits from the P-box and E-expansion provides so-called "[[confusion and diffusion]]" respectively, a concept identified by [[Claude Shannon]] in the 1940s as a necessary condition for a secure yet practical cipher.

=== Key schedule ===
<imagemap>
File:DES-key-schedule.png|thumb|250px|''[[:File:DES-key-schedule.png|Figure 3]]''— The key-schedule of DES
rect 96 28 298 58 [[DES supplementary material#Permuted choice 1 (PC-1)|Permuted choice 1]]
rect 127 122 268 155 [[DES supplementary material#Permuted choice 2 (PC-2)|Permuted choice 2]]
rect 127 216 268 249 [[DES supplementary material#Permuted choice 2 (PC-2)|Permuted choice 2]]
rect 127 357 268 390 [[DES supplementary material#Permuted choice 2 (PC-2)|Permuted choice 2]]
rect 127 451 268 484 [[DES supplementary material#Permuted choice 2 (PC-2)|Permuted choice 2]]
rect 96 91 127 116 [[DES supplementary material#Rotations in the key-schedule|Left shift by 1]]
rect 268 91 299 116 [[DES supplementary material#Rotations in the key-schedule|Left shift by 1]]
rect 96 185 127 210 [[DES supplementary material#Rotations in the key-schedule|Left shift by 1]]
rect 268 185 299 210 [[DES supplementary material#Rotations in the key-schedule|Left shift by 1]]
rect 96 326 127 351 [[DES supplementary material#Rotations in the key-schedule|Left shift by 2]]
rect 268 326 299 351 [[DES supplementary material#Rotations in the key-schedule|Left shift by 2]]
rect 96 419 127 444 [[DES supplementary material#Rotations in the key-schedule|Left shift by 1]]
rect 268 419 299 444 [[DES supplementary material#Rotations in the key-schedule|Left shift by 1]]
</imagemap>
Figure 3 illustrates the ''key schedule'' for encryption—the algorithm which generates the subkeys. Initially, 56 bits of the key are selected from the initial 64 by ''Permuted Choice 1'' (''PC-1'')—the remaining eight bits are either discarded or used as [[parity bit|parity]] check bits. The 56 bits are then divided into two 28-bit halves; each half is thereafter treated separately. In successive rounds, both halves are rotated left by one or two bits (specified for each round), and then 48 subkey bits are selected by ''Permuted Choice 2'' (''PC-2'')—24 bits from the left half, and 24 from the right. The rotations (denoted by "<<<" in the diagram) mean that a different set of bits is used in each subkey; each bit is used in approximately 14 out of the 16 subkeys.

The key schedule for decryption is similar—the subkeys are in reverse order compared to encryption. Apart from that change, the process is the same as for encryption. The same 28 bits are passed to all rotation boxes.

=== Pseudocode ===
[[Pseudocode]] for the DES algorithm follows.

{{syntaxhighlight|lang=golang|code=
// All variables are unsigned 64 bits

// Pre-processing: padding with the size difference in bytes
pad message to reach multiple of 64 bits in length

var key // The keys given by the user
var keys[16]
var left, right

// Generate Keys

// PC1 (64 bits to 56 bits) 
key := permutation(key, PC1)
left := (key rightshift 28) and 0xFFFFFFF
right := key and 0xFFFFFFF

for i from 1 to 16 do
	right := right leftrotate KEY_shift[i]
	left := left leftrotate  KEY_shift[i]
	var concat := (left leftshift 28) or right
	// PC2 (56bits to 48bits)
	keys[i] := permutation(concat, PC2)
end for

// To decrypt a message reverse the order of the keys
if decrypt do
	reverse keys
end if

// Encrypt or Decrypt
for each 64-bit chunk of padded message do
	var tmp

	// IP
	chunk := permutation(chunk, IP)
	left := chunk rightshift 32
	right := chunk and 0xFFFFFFFF
	for i from 1 to 16 do
		tmp := right
		// E (32bits to 48bits)
		right := expansion(right, E)
		right := right xor keys[i]
		// Substitution (48bits to 32bits)
		right := substitution(right)
		// P
		right := permutation(right, P)
		right := right xor left
		left := tmp
	end for
	// Concat right and left
	var cipher_chunk := (right leftshift 32) or left
	// FP
	cipher_chunk := permutation(cipher_chunk, FP)
end for
}}