Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 specialits.

Among other things, I want to know where does the PERMUTATION TABLES come from: http://i.imgur.com/oknZ9.png

I know this kind of encription systems have a lot to do with mathematic fields .
So I would like to know if someones has a PDF or any other REAL MATHEMATICAL explanation of the DES encryption system.

Thanks in advance.

share|improve this question

migrated from security.stackexchange.com Nov 21 '11 at 15:07

This question came from our site for Information security professionals.

2  
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". –  Henning Makholm Nov 21 '11 at 14:14
    
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). –  S.L. Barth Nov 21 '11 at 14:50
    
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. –  Paŭlo Ebermann Nov 21 '11 at 17:08
    
Additional dupes at cstheory.SE and the original on SO. –  Ilmari Karonen Nov 21 '11 at 19:28

3 Answers 3

I have learnt a lot about these algorithms, let me edit this answer in a full-fledged format after some time as I need to prepare some image files, but until then the best thing you can read is this, comment if you want to hear more.

Thanking you.


I have found some Explanation by Thomas pornin , which is as follows


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

share|improve this answer
    
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 –  BorjaDES Nov 21 '11 at 14:21
    
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 –  iyengar Nov 21 '11 at 14:36
    
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. –  BorjaDES Nov 21 '11 at 14:41
1  
@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 –  iyengar Nov 21 '11 at 15:15
1  
@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? –  Henning Makholm Nov 21 '11 at 15:16

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.

share|improve this answer

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)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.