4
$\begingroup$

I need a mathematical explanation of what does the DES encryption system really do.

This means I need more explanation than the one that offers FIPS, which is more an explanation for computer specialists.

Among other things, I want to know where do these permutation tables come from: $$IP\\ \newcommand\T{\Rule{0pt}{1em}{.3em}} \begin{array}{|c|c|c|c|c|c|c|c|} \hline 58 \T & 50 \T & 42 \T & 34 \T & 26 \T & 18 \T & 10 \T & 2 \\\hline 60 \T & 52 \T & 44 \T & 36 \T & 28 \T & 20 \T & 12 \T & 4 \\\hline 62 \T & 54 \T & 46 \T & 38 \T & 30 \T & 22 \T & 14 \T & 6 \\\hline 64 \T & 56 \T & 48 \T & 40 \T & 32 \T & 24 \T & 16 \T & 8 \\\hline 57 \T & 49 \T & 41 \T & 33 \T & 25 \T & 17 \T & 9 \T & 1 \\\hline 59 \T & 51 \T & 43 \T & 35 \T & 27 \T & 19 \T & 11 \T & 3 \\\hline 61 \T & 53 \T & 45 \T & 37 \T & 29 \T & 21 \T & 13 \T & 5 \\\hline 63 \T & 55 \T & 47 \T & 39 \T & 31 \T & 23 \T & 15 \T & 7 \\\hline \end{array} $$

I know this kind of encryption systems have a lot to do with the mathematical concept of a field.

So I would like to know if someones has a PDF or any other real mathematical explanation of the DES encryption system.

$\endgroup$
4
  • 2
    $\begingroup$ No information about where the S-boxes came from was available when DES was first specified; this generated significant amounts of paranoia. It was later found that the exact choices increased the resistance of DES to differential cryptanalysis, but AFAIK the precise way they were selected is still classified (that is, if the details are even written down anywhere). There may be no more to it, mathematically, than "use this magic table lookup". $\endgroup$ Nov 21, 2011 at 14:14
  • $\begingroup$ IIRC there was a description in Schneier's "Applied Cryptography", but I don't know if it touches on mathematical fields. (No copy with me). $\endgroup$
    – S.L. Barth
    Nov 21, 2011 at 14:50
  • $\begingroup$ Welcome to Cryptography Stack Exchange. Your two questions on security.stackexchange.com and math.stackexchange.com were migrated here because the questions related to the internals of a cryptographic algorithms, and thus are fully on-topic here. I then merged both questions. Please register your account here, too, to be able to comment and accept an answer. $\endgroup$ Nov 21, 2011 at 17:08
  • $\begingroup$ @esushi: +1 for the nice $\TeX$; I previously did not realize \newcommand was supported. $\endgroup$
    – fgrieu
    Jun 19, 2015 at 5:06

4 Answers 4

7
$\begingroup$

The DES standard (FIPS 46-3) is actually a rather straightforward description of DES. It tells with precision and detail where each bit goes. It is a specification for implementers (who can be thought as "computer specialists" but anybody who wants to learn about DES should be able to understand that specification). What FIPS 46-3 does not tell is why DES was designed that way. If you want more mathematics, you can have a look at the Handbook of Applied Cryptography (free download !), in particular chapter 7, which goes over the case of DES.

For the initial and final permutations (called "IP" in FIPS 46-3), they were defined not for security (they are fixed, key-less permutations which anyone can readily invert), but to ease implementations in hardware contexts of the 1970s' era: they make it easier to make an hardware implementation which plugs on an 8-bit bus. See this question for some details.

There is nothing about fields in DES. It is all bit-by-bit manipulations; to some extent you could say that a bit is a value in GF(2), the field with two elements (0 and 1), but that's quite stretching it.

$\endgroup$
4
$\begingroup$

Well, (good) encryption schemes serve to obscure and protect the data, while not making it easy to recover the input bits from the output bits. The S-boxes and P-boxes serve to increase the mathematical complexity & along with a key making it very difficult to determine the actual mapping that is occurring between some of the input bits and each output bit. To borrow the oft repeated concept of Shannon & others, "confusion and diffusion".

What really hits at the heart of the issue then is the design rationale/criteria for S-boxes. Non-linearity is a must for S-boxes; S-boxes can't be too small etc etc. You can do a Google search and come up with a slew of decent papers over the last 12 years or so .... or you can hit up Terry Ritter's resource page on S-Box Design literature.

The concept you'll probably be most intrigued with is SAC (Strict Avalanche Criterion).

You may also find the following documents very useful:

  • "Cryptographic Properties of Boolean Functions and S-Boxes", PhD thesis by An Braeken (PDF)

  • "New Analysis Methods on Strict Avalanche Criterion of S-Boxes", article by Phyu Phyu Mar, Khin Maung Latt in WASET 48 2008 (PDF)

$\endgroup$
0
3
$\begingroup$

I have found some explanation by Thomas pornin:

The initial and final permutation have no influence on security (they are unkeyed and can be undone by anybody). The usual explanation is that they make implementation easier in some contexts, namely a hardware circuit which receives data over a 8-bit bus: it can accumulate the bits into eight shift registers, which is more efficient (in terms of circuit area) than a single 64-bit register. This process "naturally" performs the initial permutation of DES.

In more details: Suppose that you are designing a hardware circuit which should do some encryption with DES, and receives data by blocks of 8 bits. This means that there are 8 "lines", each yielding one bit at each clock. A common device for accumulating data is a shift register: the input line plugs into a one-bit register, which itself plugs into another, which plugs into a third register, and so on. At each clock, each register receives the contents from the previous, and the first register accepts the new bit. Hence, the contents are "shifted".

With an 8-bit bus, you would need 8 shift registers, each receiving 8 bits for an input block. The first register will receive bits 1, 9, 17, 25, 33, 41, 49 and 57. The second register receives bits 2, 10, 18,... and so on. After eight clocks, you have received the complete 64-bit block and it is time to proceed with the DES algorithm itself.

If there was no initial permutation, then the first step of the first round would extract the "left half" (32 bits) which, at that point, would consist of the leftest 4 bits of each of the 8 shift registers. The "right half" would also get bits from the 8 shift registers. If you think of it as wires from the shift registers to the units which use the bits, then you end up with a bunch of wires which heavily cross each other. Crossing is doable but requires some circuit area, which is the expensive resource in hardware designs.

However, if you consider that the wires must extract the input bits and permute them as per the DES specification, you will find out that there is no crossing anymore. In other words, the accumulation of bits into the shift registers inherently performs a permutation of the bits, which is exactly the initial permutation of DES. By defining that initial permutation, the DES standard says: "well, now that you have accumulated the bits in eight shift registers, just use them in that order, that's fine".

The same thing is done again at the end of the algorithm.

Remember that DES was designed at a time when 8-bit bus where the top of the technology, and one thousand transistors were an awfully expensive amount of logic

$\endgroup$
7
  • $\begingroup$ Great, thanks in advance. Let me post you an example of what do I really want. Check this PDF file, (page #8, article 5.2). It's about AES, but I need the one of DES. It's in Spanish but you only need to see the numbers and stuff to realize what I'm looking for: grupos.unican.es/amac/articles/aes.pdf $\endgroup$
    – BorjaDES
    Nov 21, 2011 at 14:21
  • $\begingroup$ I am afraid that I don't understand what you want exactly, I thought that you want only the explanation, are you looking for the exact analogue of what you told for the DES algorithm ? , then I think I am not a correct person as I don't know spanish, wait for others to answer then @BorjaDES $\endgroup$
    – iyengar
    Nov 21, 2011 at 14:36
  • $\begingroup$ The article you gave me is just the FIPS article with a plus of examples. I understand all the algorithm but I want to know which is the source or the reason for doing those steps. This means I want to know "WHY sometimes shift 1 and sometimes 2 depending on the round?" "WHY the PC-1 has that numbers and not another ones"? I know this has a mathematical explanation and this is what I want to know. Anyways, if it's not a lot of work, I would be glad to see your work about DES. Thanks iyengar. $\endgroup$
    – BorjaDES
    Nov 21, 2011 at 14:41
  • 1
    $\begingroup$ @BorjaDES: But if you want to listen more about it mathematically, please re-edit the question, and just keep what the point you exactly want, it would be good if you give a suggestion to the users from where to start $\endgroup$
    – iyengar
    Nov 21, 2011 at 15:15
  • 2
    $\begingroup$ @Borja: you write "I know this has a mathematical explanation" -- where do you know this from? Whoever told you this, do you have reason to trust them? $\endgroup$ Nov 21, 2011 at 15:16
2
$\begingroup$

DES SBoxes criteria have been kept secret until Don Coppersmith revealed them (some?) in 2000:

  1. Each S-box should have six bits of input and four bits of output. (In 1974 this was the largest size S-box that could be accommodated if DES were to fit on a single chip.)
  2. No output bit of an S-box should be too close to a linear function of the input bits. (The S-boxes are the only nonlinear part of DES. Their nonlinearity is the algorithm’s strength.)
  3. Each “row” of an S-box should contain all possible outputs. (This randomizes the output.)
  4. If two inputs to an S-box differ in exactly one bit, their outputs should differ in at least two bits.
  5. If two inputs to an S-box differ exactly in the middle two bits, their outputs must differ by at least two bits. (Criteria (4) and (5) provide some diffusion.)
  6. If two inputs to an S-box differ in their first two bits and agree on their last two, the two outputs must differ.
  7. For any nonzero 6-bit difference between inputs, no more than 8 of the 32 pairs of inputs exhibiting that difference may result in the same output difference.

Coppersmith added:

  1. 6 bits in, 4 bits out.
  2. No output bit “too close” to linear function of inputs.
  3. Fix two outer bits (autoclave): the rest is a permutation of 4 bits. In other words, $\Delta_{in} = 0wxyz0 \implies \Delta_{out} \neq 0$. (different from 0)
  4. $\Delta_{in} = 001100 \implies |\Delta_{out} |\geq 2$.
  5. $P(\Delta_{out} = 0\ |\ \Delta_{in}) \leq 8/32$
  6. $P(\Delta_{out} = 0\ |\ \Delta_{in}) \leq$ stricter but ad hoc.
  7. $\Delta_{in} = 11xy00 \implies \Delta_{out} \neq 0$.
  8. Implementation should use at most 47 gates.

This is from Courtois in https://eprint.iacr.org/2003/184.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.