🚀 go-pugleaf

A day or two ago, I mentioned a use of DES in FFT style.  I was asked
to elaborate.  Rather than write a long description of that, I wrote
the following code.  This is not encryption code, itself.  (Therefore
it can be freely exported. :-)  It is a program which transposes bytes
of stdin in blocks up to 8KB using butterfly transposition, ala the FFT.
If you do DES|FTT|DES|... that's similar to the program to which I had
alluded.

The purpose of this particular transposition is to achieve maximum
diffusion of bit changes.  If you have a block of 8KB and do 10 rounds of
this single FTT layer with some mixing function in the middle (eg., DES),
any change in any input bit in the block will affect all output bits of the
block.  (Each application of (FTT|DES) doubles the number of bits affected
-- up to the size of the block and the first DES affects 8 bytes.)

If DES is used in CBC mode, any bit change will affect every bit after that
-- but FTT propagates bit changes backward as well.

For blocks shorter than 8KB, I haven't analyzed the effect of this code
fully.  I don't know how many rounds it would take to get complete
diffusion.

--Carl

---- Cut Here and unpack ----
#!/bin/sh
# shar:	Shell Archiver  (v1.22)
#
#                                                                          
#                                                                          
#
#	Run the following text with /bin/sh to create:
#	  Makefile
#	  ftt.c
#
if test -r s2_seq_.tmp
then echo "Must unpack archives in sequence!"
     next=`cat s2_seq_.tmp`; echo "Please unpack part $next next"
     exit 1; fi
echo "x - extracting Makefile (Text)"
sed 's/^X//' << 'SHAR_EOF' > Makefile &&
Xall: ftt iftt
X
Xftt: ftt.c
X	cc -O ftt.c -o ftt
X
Xiftt: ftt
X	ln -s ftt iftt
SHAR_EOF
chmod 0644 Makefile || echo "restore of Makefile fails"
set `wc -c Makefile`;Sum=$1
if test "$Sum" != "73"
then echo original size 73, current size $Sum;fi
echo "x - extracting ftt.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > ftt.c &&
X/* Copyright (c) 1992  Carl M. Ellison */
X/* This software may be copied, distributed and used for any purpose  */
X/* provided that this copyright and statement are included in all such  */
X/* copies. */
X
X
X/* ftt (a.k.a. iftt) -- transpose bytes in a butterfly fashion, like that */
X/* used in an FFT. */
X
X/* This version does just one layer.  An FFT does log2(BLOCKSIZE) layers */
X/* of operation to get full mixing within the block. */
X
X/* This program can be used in a UNIX pipe, typically log2(BLOCKSIZE) times */
X/* mixed with some encryption algorithm like DES -- eg., */
X/* des|ftt|des|ftt|des|ftt|des|ftt|des|ftt|des|ftt|des|ftt|des */
X/* with each DES operating in CBC mode and with individual keys and IVs */
X/* of course, this can all be merged into one program to save typing */
X
X/* No attempt have been made to make this code efficient. */
X/* This implementation is for illustration only.  */
X
X
X#include <stdio.h>
X
X#define BLOCKSIZE (8192)	/* up to 8K in each FFT-like block */
X#define MODSIZE (2)		/* "word" size within the block halves */
X			/* MODSIZE of 2 makes sense for byte transpositions; */
X			/* MODSIZE of 8 makes sense for DES-combinations */
X
Xchar buf[BLOCKSIZE];
Xchar obuf[BLOCKSIZE];
X
Xmain(argc, argv)
Xlong argc;
Xchar *argv[];
X{
X  long a, b, c, i, len;
X  short encr = ( *(argv[0]) != 'i' ) ;
X
X  len = fread( buf, 1, BLOCKSIZE, stdin ) ;
X
X  do
X    {
X      a = len % MODSIZE ;
X      b = ( len - a ) / 2 ;
X      c = a + b ;
X      for ( i = 0 ; i < b ; i++ )
X	{
X	  /* transpose two bytes in a butterfly fashion */
X	  if (encr)
X	    {
X	      obuf[2*i] = buf[i] ;
X	      obuf[(2*i)+1] = buf[i+c] ;
X	    }
X	  else
X	    {
X	      obuf[i] = buf[2*i] ;
X	      obuf[i+c] = buf[(2*i)+1] ;
X	    }
X	} /* for i -- bulk bytes -- in two halves */
X
X      for ( i = 0 ; i < a ; i++ )
X	{
X	  /* move the unused bytes */
X	  if (encr)
X	    obuf[(2*b)+i] = buf[b+i] ;
X	  else
X	    obuf[b+i] = buf[(2*b)+i] ;
X	} /* for i -- remainder bytes */
X
X      fwrite( obuf, 1, len, stdout );
X    } while ( len = fread( buf, 1, BLOCKSIZE, stdin ) );
X}
X
SHAR_EOF
chmod 0644 ftt.c || echo "restore of ftt.c fails"
set `wc -c ftt.c`;Sum=$1
if test "$Sum" != "2044"
then echo original size 2044, current size $Sum;fi
exit 0