home *** CD-ROM | disk | FTP | other *** search
/ Computer Club Elmshorn Atari PD / CCE_PD.iso / pc / 0600 / CCE_0679.ZIP / CCE_0679.PD / DES301 / ALGORITH.DOC next >
Text File  |  1993-11-10  |  9KB  |  199 lines
  1. This is a quickly hacked up explanation of the changes made to the DES
  2. algorithm layout.  It was written very quickly one morning 
  3. in response to an email message and so may (probably :-) contains
  4. errors but if you are interested, it gives a quick overview of the
  5. changes from the FIPS version of DES that most of the fast DES
  6. implementations make.  You had better have my source code and the
  7. FIPS paper in front of you before you start reading :-).
  8.  
  9.  
  10. On Tue, 12 Oct 1993, AAA ZZZZZZZ wrote:
  11. > I have the book "Numerical Recipes in C" and am trying to match your algorithm
  12. > (in fcrypt.c) with that of the DES algorithm in the book.  It seems that you 
  13. > have replaced a some of the code with table lookups. I was wondering if your 
  14. > could explain how you derived the entries for the arrays "skb" and "SPtrans".
  15. > (I believe that SPtrans is the s-box with some sort of bit-fiddling.)  Also,
  16. > could you possibly map the remainder of your algorithm to the generic DES
  17. > algorithm just to make sure that I do not miss anything ?
  18. Ah, yes, my version has had a few things changed :-).
  19. Ok, first I'll attempt to describe the D_ENCRYPT macro (from des_locl.h)
  20. #define D_ENCRYPT(L,R,S)        \
  21.         u=(R^s[S  ]); \
  22.         t=R^s[S+1]; \
  23.         t=((t>>4)+(t<<28)); \
  24.         L^=     des_SPtrans[1][(t    )&0x3f]| \
  25.                 des_SPtrans[3][(t>> 8)&0x3f]| \
  26.                 des_SPtrans[5][(t>>16)&0x3f]| \
  27.                 des_SPtrans[7][(t>>24)&0x3f]| \
  28.                 des_SPtrans[0][(u    )&0x3f]| \
  29.                 des_SPtrans[2][(u>> 8)&0x3f]| \
  30.                 des_SPtrans[4][(u>>16)&0x3f]| \
  31.                 des_SPtrans[6][(u>>24)&0x3f];
  32. R contains 32 bits that are input into the E function.  If you look at the
  33. E function,
  34. 31  1  2  3  4  5
  35.  4  5  6  7  8  9
  36.  8  9 10 11 12 13
  37. 12 13 14 15 16 17
  38. 16 17 18 19 20 21
  39. 20 21 22 23 24 25
  40. 24 25 26 27 28 29
  41. 28 29 30 31 32  1
  42. If everything is first rotated up by one before we begin, the E
  43. translation becomes
  44.  1  2  3  4  5  6
  45.  5  6  7  8  9 10
  46.  9 10 11 12 13 14
  47. 13 14 15 16 17 18
  48. 17 18 19 20 21 22
  49. 21 22 23 24 25 26
  50. 25 26 27 28 29 30
  51. 29 30 31 32  1  2
  52. Which you will notice relates to
  53.  1  2  3  4  5  6    7  8
  54.  5  6  7  8  9 10   11 12 
  55.  9 10 11 12 13 14   15 16
  56. 13 14 15 16 17 18   19 20
  57. 17 18 19 20 21 22   23 24
  58. 21 22 23 24 25 26   27 28
  59. 25 26 27 28 29 30   31 32
  60. 29 30 31 32  1  2    3  4
  61. So if we organise the 48 bits in the K table to occupy 2 32 bit words with
  62. the 1st, 3rd, 5th and 7th 6bit groups padded with 2 bits so they are on 8 byte
  63. boundaries, and the second word containing the even 6bit groups aligned
  64. in the same way, except that the K data for the second word is rotated up
  65. 4 bits, so
  66. u=R^K[word0]; t=R^K[word1]; produces
  67.  1  2  3  4  5  6  *  *
  68.  9 10 11 12 13 14  *  *
  69. 17 18 19 20 21 22  *  *
  70. 25 26 27 28 29 30  *  *
  71. and
  72.  1  2  *  *  5  6  7  8  
  73.  9 10  *  * 13 14 15 16
  74. 17 18  *  * 21 22 23 24
  75. 25 26  *  * 29 30 31 32
  76. which is then rotated by 4 to produce the required result
  77.  5  6  7  8  9 10  *  *
  78. 13 14 15 16 17 18  *  *
  79. 21 22 23 24 25 26  *  *
  80. 29 30 31 32  1  2  *  *
  81. These 8 'chunks' are used for looking up SPtrans (the input to the S
  82. tables).
  83. You will notice that because crypt uses a modification in the E table, this
  84. section is slightly different.  crypt swaps bits between the top and
  85. bottom 16 bits in R, I achieve this via masks and xor trick I will
  86. explain later.
  87. SPtrans is a table that maps the S boxes directly to the output 32bit by
  88. incorporating the P function.  So, for example, the first S box, 6bits is
  89. used as an index so for the value 0, SPtrans[0][0] gives
  90. 0x00820200 or 100000100000001000000000 or bits 10, 18 and 24
  91. the S table in FIPS gives 14 or 2, 3 and 4.  If I am remembering
  92. correctly, the DES paper always labels the right most bit #1 so we really
  93. have bits 1, 2 and 3, and this maps via the P function to 9, 17 and 23.
  94. Note that an input 6bits of value 23, 010111, maps to row 2, column 13,
  95. not 1, 11 as I would expect (from my little endian upbringing).
  96. You will notice that these values are out by 1 from what is actually kept
  97. in SPtrans, thats because the first 1 bit rotation we did is now built
  98. into SPtrans.  So inside the inner loop, we actually work with data that
  99. is rotated by 1 bit so things work more easily in the E function.  The
  100. SPtrans table was generated via the above translation from the original S
  101. and P tables.  I did it quite some time ago and have lost the perl script
  102. I used to do this but it would not be hard to redo this work.
  103.  
  104. You will notice that after the D_ENCRYPT functions are finished we rotate
  105. the results back into the correct form.
  106.  
  107. Regarding the PERM_OP operation.  I'll copy the comments from des_local.h
  108.         /* IP and FP
  109.         * The problem is more of a geometric problem that random bit fiddling.
  110.          0  1  2  3  4  5  6  7      62 54 46 38 30 22 14  6
  111.          8  9 10 11 12 13 14 15      60 52 44 36 28 20 12  4
  112.         16 17 18 19 20 21 22 23      58 50 42 34 26 18 10  2
  113.         24 25 26 27 28 29 30 31  to  56 48 40 32 24 16  8  0
  114.  
  115.         32 33 34 35 36 37 38 39      63 55 47 39 31 23 15  7
  116.         40 41 42 43 44 45 46 47      61 53 45 37 29 21 13  5
  117.         48 49 50 51 52 53 54 55      59 51 43 35 27 19 11  3
  118.         56 57 58 59 60 61 62 63      57 49 41 33 25 17  9  1
  119.  
  120.         The output has been subject to swaps of the form
  121.         0 1 -> 3 1 but the odd and even bits have been put into
  122.         2 3    2 0
  123.         different words.  The main trick is to remember that
  124.         t=((l>>size)^r)&(mask);
  125.         r^=t;
  126.         l^=(t<<size);
  127.         can be used to swap and move bits between words.
  128.         So l =  0  1  2  3  r = 16 17 18 19
  129.                 4  5  6  7      20 21 22 23
  130.                 8  9 10 11      24 25 26 27
  131.                12 13 14 15      28 29 30 31
  132.         becomes (for size == 2 and mask == 0x3333)
  133.            t =   2^16  3^17 -- --   l =  0  1 16 17  r =  2  3 18 19
  134.                  6^20  7^21 -- --        4  5 20 21       6  7 22 23
  135.                 10^24 11^25 -- --        8  9 24 25      10 11 24 25
  136.                 14^28 15^29 -- --       12 13 28 29      14 15 28 29
  137.  
  138.         Thanks for hints from Richard Outerbridge - he told me IP&FP
  139.         could be done in 15 xor, 10 shifts and 5 ands.
  140.         When I finally started to think of the problem in 2D
  141.         I first got ~42 operations without xors.  When I remembered
  142.         how to use xors :-) I got it to its final state.
  143.         */
  144. It is really quite evil but fast :-).
  145.  
  146. For the creation of the key_schedule (skb), similar optimising techniques
  147. have been used.
  148. PC1 has been done with the old xor trick, some-one has told me it
  149. is possible to get it a few instructions faster but I don't feel like
  150. beating my brain against a wall to work out how when it will only speed
  151. things up 1%-2% and only in the key generation.
  152. skb is basically the PC2 table with indexes 0..3 for C and 4..7 for D.
  153. You will notice if you look at PC2 in FIPS that the bottom 24 bits are
  154. made from C and the top 24 from D, it is sort of 2 table mashed together.
  155. This lets us generate a direct mapping.  The lookup is a little strange
  156. since some bits are just not used and so I did some ugly shifts etc to
  157. remove the holes to help keep the table size down.
  158. The output from the skb lookups is also aligned so that it fits into the
  159. xor in DES easily.
  160. eg, the output from des_skb is byte aligned for the S tables 0213 and 4657.
  161. We convert this to 0246 and 1357 and rotate the 1357 data by 4 bits.
  162.  
  163. > The reason I am asking this is that I was given the task of taking your DES
  164. > algorithm and porting it to the Cray and modifying it to take advantage
  165. > of the vectorisation in an attempt to make the algorithm faster.  Also, I
  166. > have been attempting to optimise the algorithm to squeeze as much performance
  167. > out of the algorithm as possible.  To do this, it would be extremely helpful
  168. > if you would be so kind as to help me.  I will gladly share my results with
  169. > you.
  170. I believe my code still currently works on a Cray.  To do the port I just
  171. made sure I cleared the top 32bits of words when needed and continued to
  172. operate on 32 bit quantities so I believe most of the structures on the
  173. Cray will be only half full.  The problem with the algorithm is that it is
  174. not vectorisable in this form.  It is mostly a random lookup problem.
  175. One speedup that can be done is to combine S tables so you only perform 4
  176. 12 bit (or 14bit if you don't want to do shifting) instead of 8 lookups.
  177. The ufc package does this but my code is often faster because having only
  178. small tables it often fits into on chip caches whereas big random access
  179. tables do not.
  180. There may be other ways to implement the algorithm that will speed it up
  181. but the only obvious optimisation that springs to mind is to take
  182. advantage of the 64bit word size.
  183. BTW it is probably not worth even looking at speeding up set_key since it
  184. is only being run once for each 25 DES's when in crypt so the 1% speedup
  185. in DES has 25 times the effect of 1% speedup in set_key :-).
  186.  
  187. > P.S.  I downloaded your DES library and am going over the code in it.
  188. The most recent version is from 8th of this month (mostly copyright
  189. message changes and addition of triple cbc encryption).
  190.  
  191. > P.S.S.  Could you explain PERM_OP and HPERM_OP ??
  192. As mentioned above they are an neat way of take advantage of the regularity of
  193. some of the permutation, quite non-intuitive :-).
  194.  
  195. hope this helps
  196.  
  197. eric 
  198.  
  199.