
Что такое DES?
The Data Encryption Standard (any many other crypto systems devised
since) use a process of substitutions (replacing one block of bits
with another) and permutations (rearranging the bits). This process
is iterated a number of times and the key is mixed in at different
points.
This R This L
 
v 
[E Expansion] 
 
\ 
XOR <  key for this round (subkey) 
 
 
        
v v v v v v v v 
========================================= 
 S1  S2  S3  S4  S5  S6  S7  S8  
========================================= 
        
 /
 /
[P Permutation] /
 /
\____________________________________/__
 / \
v / \
XOR <  
v v
Next R Next L
This is the basic structure of DES (if I didnt make a mistake, this
is from memory). Anyway the basic idea is you take half the key
(called L and R for Left and Right, but hey, I'm lysdexic). You
put it through an expansion, this just mixes up the order of the
bits and duplicates a few of them. Then you XOR it with the subkey
(the Key Generator is not shown). Then you split it up into 8 6bit
chunks and do a table lookup in the Sboxes, each Sbox has 6 inputs
and 4 outputs. Then you rearrange the bits in the P permutation.
Finally you XOR that value with the L to get next R, and put the
preXOR'ed value into the next L.
This is 1 iteration and is done 16 times in DES, and 16*25 times in
crypt(3). Crypt(3) also has the salt values which cause the swapping
of two bits in the E expansion for every salt bit that is set. Before
pulling apart the 64 bit input into 2 32 bit halfs (L and R) the data
is passed through an Initial Permutation (IP), and at the end of the
whole thing passed through (IP^1) its inverse (this permutation isnt
cryptographically that significant). The subkeys are generated
by taking the input 56 bits of key, mixing them up and then successively
rotating those bits, and passing them through a permutation. It outputs
48 bits of key each iteration to match the 48 bits after the E expansion.
I hope I didnt make too many mistakes in the above discussion, but
you get the general idea.
Did anyone ever answer the question asked about how the DES sboxes work?
I'll try to make this fairly quick, in case I'm covering old ground....
DES is a Feisteltype cipher, which you probably know. In case you don't:
Each round, the right half of the block being encrypted (32 bits) is used,
along with 48 bits derived from the key, to generate a 32bit value to XOR
against the left half of the block. Then, the left and right halves are
swapped. There are 16 rounds.
You can think of each round as:
L = L XOR F(R, SK_i)
SWAP L,R
The Sboxes, along with the E expansion and the P permutation, make up
the F function. The F function in a nutshell:
1. The right 32 bits are expanded to 48 bits, in effect by duplicating half
the bits. First, the 32bits are split into groups of 4 bits, then they
become groups of 6 bits by taking the outer bits from the two adjacent
groups. This is clearer by example: Part of our input word is:
... efgh ijkl mnop ...
it becomes:... defghi hijklm lmnopq ...
2. The 48 key bits are XORed into the expanded 48 bits.
3. The resulting 48 bits are put fed into the 8 Sboxes, which output
a total of 32 bits. The Sboxes are each 6bit to 4bit nonlinear
substitutions. Each one is set up as 4 nonlinear substitution tables
from 4bits to 4bits, and the outside two bits of each 6bit group
are used to select which of the 4 possible tables to use. (There are
4 different tables for each of the 8 Sboxes.) Each 6bit group is
fed into a different Sbox.
4. The 32bit output from the Sboxes is permuted, so that the output
from each Sbox immediately affects as many others as possible,
on the next round. The output from this permutation is the output
from the F function, and is XORed directly into the left half of the
block.
Now, in case I wasn't clear above, the Sboxes are known to everyone.
There is no secrecy therethey are part of the published specifications
of the algorithm. They are also the only place in the whole cipher where
an output bit is ever the function of more than one input bit.
Quite a bit has been written about why the specific Sboxes used in DES
were chosen. At one point, there was a lot of concern that the NSA had
pressured IBM into accepting Sboxes with some kind of "trapdoor," ie some
nonobvious qualities that made it possible for an attacker to break the
cipher. Not many people seem to believe that now, because a new form of
cryptanalytic attack, called differential cryptanalysis, was published in
(I think) 1989, and this method could be used to break a version of DES
with weak Sboxes. However, the Sboxes used in DES were quite resistant
to differential attack.

