home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / crypt / 2762 < prev    next >
Encoding:
Internet Message Format  |  1992-07-28  |  4.6 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!mips!sdd.hp.com!uakari.primate.wisc.edu!samsung!transfer!ellisun.sw.stratus.com!cme
  2. From: cme@ellisun.sw.stratus.com (Carl Ellison)
  3. Newsgroups: sci.crypt
  4. Subject: FFT-like use of DES, etc.
  5. Message-ID: <5194@transfer.stratus.com>
  6. Date: 28 Jul 92 19:38:43 GMT
  7. Sender: usenet@transfer.stratus.com
  8. Organization: Stratus Computer, Software Engineering
  9. Lines: 135
  10.  
  11. A day or two ago, I mentioned a use of DES in FFT style.  I was asked
  12. to elaborate.  Rather than write a long description of that, I wrote
  13. the following code.  This is not encryption code, itself.  (Therefore
  14. it can be freely exported. :-)  It is a program which transposes bytes
  15. of stdin in blocks up to 8KB using butterfly transposition, ala the FFT.
  16. If you do DES|FTT|DES|... that's similar to the program to which I had
  17. alluded.
  18.  
  19. The purpose of this particular transposition is to achieve maximum
  20. diffusion of bit changes.  If you have a block of 8KB and do 10 rounds of
  21. this single FTT layer with some mixing function in the middle (eg., DES),
  22. any change in any input bit in the block will affect all output bits of the
  23. block.  (Each application of (FTT|DES) doubles the number of bits affected
  24. -- up to the size of the block and the first DES affects 8 bytes.)
  25.  
  26. If DES is used in CBC mode, any bit change will affect every bit after that
  27. -- but FTT propagates bit changes backward as well.
  28.  
  29. For blocks shorter than 8KB, I haven't analyzed the effect of this code
  30. fully.  I don't know how many rounds it would take to get complete
  31. diffusion.
  32.  
  33. --Carl
  34.  
  35. ---- Cut Here and unpack ----
  36. #!/bin/sh
  37. # shar:    Shell Archiver  (v1.22)
  38. #
  39. #                                                                          
  40. #                                                                          
  41. #
  42. #    Run the following text with /bin/sh to create:
  43. #      Makefile
  44. #      ftt.c
  45. #
  46. if test -r s2_seq_.tmp
  47. then echo "Must unpack archives in sequence!"
  48.      next=`cat s2_seq_.tmp`; echo "Please unpack part $next next"
  49.      exit 1; fi
  50. echo "x - extracting Makefile (Text)"
  51. sed 's/^X//' << 'SHAR_EOF' > Makefile &&
  52. Xall: ftt iftt
  53. X
  54. Xftt: ftt.c
  55. X    cc -O ftt.c -o ftt
  56. X
  57. Xiftt: ftt
  58. X    ln -s ftt iftt
  59. SHAR_EOF
  60. chmod 0644 Makefile || echo "restore of Makefile fails"
  61. set `wc -c Makefile`;Sum=$1
  62. if test "$Sum" != "73"
  63. then echo original size 73, current size $Sum;fi
  64. echo "x - extracting ftt.c (Text)"
  65. sed 's/^X//' << 'SHAR_EOF' > ftt.c &&
  66. X/* Copyright (c) 1992  Carl M. Ellison */
  67. X/* This software may be copied, distributed and used for any purpose  */
  68. X/* provided that this copyright and statement are included in all such  */
  69. X/* copies. */
  70. X
  71. X
  72. X/* ftt (a.k.a. iftt) -- transpose bytes in a butterfly fashion, like that */
  73. X/* used in an FFT. */
  74. X
  75. X/* This version does just one layer.  An FFT does log2(BLOCKSIZE) layers */
  76. X/* of operation to get full mixing within the block. */
  77. X
  78. X/* This program can be used in a UNIX pipe, typically log2(BLOCKSIZE) times */
  79. X/* mixed with some encryption algorithm like DES -- eg., */
  80. X/* des|ftt|des|ftt|des|ftt|des|ftt|des|ftt|des|ftt|des|ftt|des */
  81. X/* with each DES operating in CBC mode and with individual keys and IVs */
  82. X/* of course, this can all be merged into one program to save typing */
  83. X
  84. X/* No attempt have been made to make this code efficient. */
  85. X/* This implementation is for illustration only.  */
  86. X
  87. X
  88. X#include <stdio.h>
  89. X
  90. X#define BLOCKSIZE (8192)    /* up to 8K in each FFT-like block */
  91. X#define MODSIZE (2)        /* "word" size within the block halves */
  92. X            /* MODSIZE of 2 makes sense for byte transpositions; */
  93. X            /* MODSIZE of 8 makes sense for DES-combinations */
  94. X
  95. Xchar buf[BLOCKSIZE];
  96. Xchar obuf[BLOCKSIZE];
  97. X
  98. Xmain(argc, argv)
  99. Xlong argc;
  100. Xchar *argv[];
  101. X{
  102. X  long a, b, c, i, len;
  103. X  short encr = ( *(argv[0]) != 'i' ) ;
  104. X
  105. X  len = fread( buf, 1, BLOCKSIZE, stdin ) ;
  106. X
  107. X  do
  108. X    {
  109. X      a = len % MODSIZE ;
  110. X      b = ( len - a ) / 2 ;
  111. X      c = a + b ;
  112. X      for ( i = 0 ; i < b ; i++ )
  113. X    {
  114. X      /* transpose two bytes in a butterfly fashion */
  115. X      if (encr)
  116. X        {
  117. X          obuf[2*i] = buf[i] ;
  118. X          obuf[(2*i)+1] = buf[i+c] ;
  119. X        }
  120. X      else
  121. X        {
  122. X          obuf[i] = buf[2*i] ;
  123. X          obuf[i+c] = buf[(2*i)+1] ;
  124. X        }
  125. X    } /* for i -- bulk bytes -- in two halves */
  126. X
  127. X      for ( i = 0 ; i < a ; i++ )
  128. X    {
  129. X      /* move the unused bytes */
  130. X      if (encr)
  131. X        obuf[(2*b)+i] = buf[b+i] ;
  132. X      else
  133. X        obuf[b+i] = buf[(2*b)+i] ;
  134. X    } /* for i -- remainder bytes */
  135. X
  136. X      fwrite( obuf, 1, len, stdout );
  137. X    } while ( len = fread( buf, 1, BLOCKSIZE, stdin ) );
  138. X}
  139. X
  140. SHAR_EOF
  141. chmod 0644 ftt.c || echo "restore of ftt.c fails"
  142. set `wc -c ftt.c`;Sum=$1
  143. if test "$Sum" != "2044"
  144. then echo original size 2044, current size $Sum;fi
  145. exit 0
  146.