Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site allegra.UUCP
Path: utzoo!watmath!clyde!akgua!mcnc!unc!ulysses!allegra!don
From: don@allegra.UUCP (D. Mitchell)
Newsgroups: net.crypt
Subject: why 16 rounds in DES
Message-ID: <2434@allegra.UUCP>
Date: Sun, 22-Apr-84 17:23:34 EST
Article-I.D.: allegra.2434
Posted: Sun Apr 22 17:23:34 1984
Date-Received: Mon, 23-Apr-84 07:13:31 EST
Organization: AT&T Bell Laboratories, Murray Hill
Lines: 27

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.