don@allegra.UUCP (D. Mitchell) (04/23/84)
In the hopes of simulating some discussion, let me answer a question someone recently asked me on net.crypt. The question is, "why does DES perform 16 rounds?" A round of DES is a one-to-one and onto mapping of 64 bits to 64 bits. Ignoring many details, this mapping is made up of two steps, an "S Box" stage, and a "P Box" stage. The S-Box step maps four-bit groups onto four-bit groups. The P-Box step then scrambles the ordering of all the bits so the output of one S Box will feed into other S-Boxes in the next round. The bits coming out of one round can be thought of as polynomial functions of input bits. This is done in the S Boxes, and each bit will be a tetralinear function of four input bits: y = Axyzt + Bxyz + Cyzt + ... + Mx + Ny + Ot + P Here multiplication and addition are .AND. and .XOR. operations, and so terms like x**2 will not appear. "A" thru "P" are zero or one. (DES is actually tetralinear in twelve variables, but it's hard to explain) The values of "A" thru "P" depend in complex ways on the key and text. When one round feeds into the next, the functions are composed. The polynomial will then be octalinear. After three rounds, it will be degree 12, and so one. After 16 rounds the polynomial will be degree 64, and that is the maximum degree that a 64-bit to 64-bit mapping can have.
outer@utcsrgv.UUCP (Richard Outerbridge) (04/23/84)
That raises another question: why use 32 "S"-boxes? You have to use enough to avoid invertible one-to-one mappings, and the DES fudges eight groups of four bits in parallel. From Konheim, exercise 6.1, "any least three" (at least three? any three?) of these eight must be many-(ie two)-to-one mappings. That's a minimum of sixteen. Are the others only along to make life interesting? Richard Outerbridge <outer@utcsrgv> -- Richard Outerbridge <outer@utcsrgv> 416 978 2742