|
Что такое 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 (re-arranging 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 sub-key
(the Key Generator is not shown). Then you split it up into 8 6-bit
chunks and do a table lookup in the S-boxes, each Sbox has 6 inputs
and 4 outputs. Then you re-arrange the bits in the P permutation.
Finally you XOR that value with the L to get next R, and put the
pre-XOR'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 s-boxes work?
I'll try to make this fairly quick, in case I'm covering old ground....
DES is a Feistel-type 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 32-bit 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 S-boxes, 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 32-bits 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 S-boxes, which output
a total of 32 bits. The S-boxes are each 6-bit to 4-bit nonlinear
substitutions. Each one is set up as 4 nonlinear substitution tables
from 4-bits to 4-bits, and the outside two bits of each 6-bit group
are used to select which of the 4 possible tables to use. (There are
4 different tables for each of the 8 S-boxes.) Each 6-bit group is
fed into a different S-box.
4. The 32-bit output from the S-boxes is permuted, so that the output
from each S-box 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 S-boxes are known to everyone.
There is no secrecy there--they 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 S-boxes used in DES
were chosen. At one point, there was a lot of concern that the NSA had
pressured IBM into accepting S-boxes with some kind of "trapdoor," ie some
non-obvious 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 S-boxes. However, the S-boxes used in DES were quite resistant
to differential attack.
 |
|