src/lib/crypto/des/f_tables.h

   1 /*
   2  * Copyright (c) 1990 Dennis Ferguson.  All rights reserved.
   3  *
   4  * Commercial use is permitted only if products which are derived from
   5  * or include this software are made available for purchase and/or use
   6  * in Canada.  Otherwise, redistribution and use in source and binary
   7  * forms are permitted.
   8  */
   9
  10 /*
  11  * des_tables.h - declarations to import the DES tables, used internally
  12  *                by some of the library routines.
  13  */
  14 #ifndef __DES_TABLES_H__
  15 #define __DES_TABLES_H__        /* nothing */
  16
  17 #ifndef const
  18 #ifndef __STDC__
  19 #define const /* nothing */
  20 #endif
  21 #endif
  22
  23 /*
  24  * These may be declared const if you wish.  Be sure to change the
  25  * declarations in des_tables.c as well.
  26  */
  27 extern const unsigned KRB_INT32 des_IP_table[256];
  28 extern const unsigned KRB_INT32 des_FP_table[256];
  29 extern const unsigned KRB_INT32 des_SP_table[8][64];
  30
  31 /*
  32  * Use standard shortforms to reference these to save typing
  33  */
  34 #define IP      des_IP_table
  35 #define FP      des_FP_table
  36 #define SP      des_SP_table
  37
  38 /*
  39  * Code to do a DES round using the tables.  Note that the E expansion
  40  * is easy to compute algorithmically, especially if done out-of-order.
  41  * Take a look at its form and compare it to everything involving temp
  42  * below.  Since SP[0-7] don't have any bits in common set it is okay
  43  * to do the successive xor's.
  44  *
  45  * Note too that the SP table has been reordered to match the order of
  46  * the keys (if the original order of SP was 12345678, the reordered
  47  * table is 71354682).  This is unnecessary, but was done since some
  48  * compilers seem to like you going through the matrix from beginning
  49  * to end.
  50  *
  51  * There is a difference in the best way to do this depending on whether
  52  * one is encrypting or decrypting.  If encrypting we move forward through
  53  * the keys and hence should move forward through the table.  If decrypting
  54  * we go back.  Part of the need for this comes from trying to emulate
  55  * existing software which generates a single key schedule and uses it
  56  * both for encrypting and decrypting.  Generating separate encryption
  57  * and decryption key schedules would allow one to use the same code
  58  * for both.
  59  *
  60  * left, right and temp should be unsigned KRB_INT32 values.  left and right
  61  * should be the high and low order parts of the cipher block at the
  62  * current stage of processing (this makes sense if you read the spec).
  63  * kp should be an unsigned KRB_INT32 pointer which points at the current
  64  * set of subkeys in the key schedule.  It is advanced to the next set
  65  * (i.e. by 8 bytes) when this is done.
  66  *
  67  * This occurs in the innermost loop of the DES function.  The four
  68  * variables should really be in registers.
  69  *
  70  * When using this, the inner loop of the DES function might look like:
  71  *
  72  *      for (i = 0; i < 8; i++) {
  73  *              DES_SP_{EN,DE}CRYPT_ROUND(left, right, temp, kp);
  74  *              DES_SP_{EN,DE}CRYPT_ROUND(right, left, temp, kp);
  75  *      }
  76  *
  77  * Note the trick above.  You are supposed to do 16 rounds, swapping
  78  * left and right at the end of each round.  By doing two rounds at
  79  * a time and swapping left and right in the code we can avoid the
  80  * swaps altogether.
  81  */
  82 #define DES_SP_ENCRYPT_ROUND(left, right, temp, kp) \
  83         (temp) = (((right) >> 11) | ((right) << 21)) ^ *(kp)++; \
  84         (left) ^= SP[0][((temp) >> 24) & 0x3f] \
  85                 | SP[1][((temp) >> 16) & 0x3f] \
  86                 | SP[2][((temp) >>  8) & 0x3f] \
  87                 | SP[3][((temp)      ) & 0x3f]; \
  88         (temp) = (((right) >> 23) | ((right) << 9)) ^ *(kp)++; \
  89         (left) ^= SP[4][((temp) >> 24) & 0x3f] \
  90                 | SP[5][((temp) >> 16) & 0x3f] \
  91                 | SP[6][((temp) >>  8) & 0x3f] \
  92                 | SP[7][((temp)      ) & 0x3f]
  93
  94 #define DES_SP_DECRYPT_ROUND(left, right, temp, kp) \
  95         (temp) = (((right) >> 23) | ((right) << 9)) ^ *(--(kp)); \
  96         (left) ^= SP[7][((temp)      ) & 0x3f] \
  97                 | SP[6][((temp) >>  8) & 0x3f] \
  98                 | SP[5][((temp) >> 16) & 0x3f] \
  99                 | SP[4][((temp) >> 24) & 0x3f]; \
 100         (temp) = (((right) >> 11) | ((right) << 21)) ^ *(--(kp)); \
 101         (left) ^= SP[3][((temp)      ) & 0x3f] \
 102                 | SP[2][((temp) >>  8) & 0x3f] \
 103                 | SP[1][((temp) >> 16) & 0x3f] \
 104                 | SP[0][((temp) >> 24) & 0x3f]
 105
 106 /*
 107  * Macros to help deal with the initial permutation table.  Note
 108  * the IP table only deals with 32 bits at a time, allowing us to
 109  * collect the bits we need to deal with each half into an unsigned
 110  * KRB_INT32.  By carefully selecting how the bits are ordered we also
 111  * take advantages of symmetries in the table so that we can use a
 112  * single table to compute the permutation of all bytes.  This sounds
 113  * complicated, but if you go through the process of designing the
 114  * table you'll find the symmetries fall right out.
 115  *
 116  * The follow macros compute the set of bits used to index the
 117  * table for produce the left and right permuted result.
 118  */
 119 #define DES_IP_LEFT_BITS(left, right) \
 120         ((((left) & 0x55555555) << 1) | ((right) & 0x55555555))
 121 #define DES_IP_RIGHT_BITS(left, right) \
 122         (((left) & 0xaaaaaaaa) | (((right) & 0xaaaaaaaa) >> 1))
 123
 124 /*
 125  * The following macro does an in-place initial permutation given
 126  * the current left and right parts of the block and a single
 127  * temporary.  Use this more as a guide for rolling your own, though.
 128  * The best way to do the IP depends on the form of the data you
 129  * are dealing with.  If you use this, though, try to make left,
 130  * right and temp register unsigned KRB_INT32s.
 131  */
 132 #define DES_INITIAL_PERM(left, right, temp) \
 133         (temp) = DES_IP_RIGHT_BITS((left), (right)); \
 134         (right) = DES_IP_LEFT_BITS((left), (right)); \
 135         (left) = IP[((right) >> 24) & 0xff] \
 136                | (IP[((right) >> 16) & 0xff] << 1) \
 137                | (IP[((right) >>  8) & 0xff] << 2) \
 138                | (IP[(right) & 0xff] << 3); \
 139         (right) = IP[((temp) >> 24) & 0xff] \
 140                 | (IP[((temp) >> 16) & 0xff] << 1) \
 141                 | (IP[((temp) >>  8) & 0xff] << 2) \
 142                 | (IP[(temp) & 0xff] << 3)
 143
 144
 145 /*
 146  * Now the final permutation stuff.  The same comments apply to
 147  * this as to the initial permutation, except that we use different
 148  * bits and shifts.
 149  */
 150 #define DES_FP_LEFT_BITS(left, right) \
 151         ((((left) & 0x0f0f0f0f) << 4) | ((right) & 0x0f0f0f0f))
 152 #define DES_FP_RIGHT_BITS(left, right) \
 153         (((left) & 0xf0f0f0f0) | (((right) & 0xf0f0f0f0) >> 4))
 154
 155
 156 /*
 157  * Here is a sample final permutation.  Note that there is a trick
 158  * here.  DES requires swapping the left and right parts after the
 159  * last cipher round but before the final permutation.  We do this
 160  * swapping internally, which is why left and right are confused
 161  * at the beginning.
 162  */
 163 #define DES_FINAL_PERM(left, right, temp) \
 164         (temp) = DES_FP_RIGHT_BITS((right), (left)); \
 165         (right) = DES_FP_LEFT_BITS((right), (left)); \
 166         (left) = (FP[((right) >> 24) & 0xff] << 6) \
 167                | (FP[((right) >> 16) & 0xff] << 4) \
 168                | (FP[((right) >>  8) & 0xff] << 2) \
 169                |  FP[(right) & 0xff]; \
 170         (right) = (FP[((temp) >> 24) & 0xff] << 6) \
 171                 | (FP[((temp) >> 16) & 0xff] << 4) \
 172                 | (FP[((temp) >>  8) & 0xff] << 2) \
 173                 |  FP[temp & 0xff]
 174
 175
 176 /*
 177  * Finally, as a sample of how all this might be held together, the
 178  * following two macros do in-place encryptions and decryptions.  left
 179  * and right are two unsigned KRB_INT32 variables which at the beginning
 180  * are expected to hold the clear (encrypted) block in host byte order
 181  * (left the high order four bytes, right the low order).  At the end
 182  * they will contain the encrypted (clear) block.  temp is an unsigned KRB_INT32
 183  * used as a temporary.  kp is an unsigned KRB_INT32 pointer pointing at
 184  * the start of the key schedule.  All these should be in registers.
 185  *
 186  * You can probably do better than these by rewriting for particular
 187  * situations.  These aren't bad, though.
 188  */
 189 #define DES_DO_ENCRYPT(left, right, temp, kp) \
 190         do { \
 191                 register int i; \
 192                 DES_INITIAL_PERM((left), (right), (temp)); \
 193                 for (i = 0; i < 8; i++) { \
 194                         DES_SP_ENCRYPT_ROUND((left), (right), (temp), (kp)); \
 195                         DES_SP_ENCRYPT_ROUND((right), (left), (temp), (kp)); \
 196                 } \
 197                 DES_FINAL_PERM((left), (right), (temp)); \
 198                 (kp) -= (2 * 16); \
 199         } while (0)
 200
 201 #define DES_DO_DECRYPT(left, right, temp, kp) \
 202         do { \
 203                 register int i; \
 204                 DES_INITIAL_PERM((left), (right), (temp)); \
 205                 (kp) += (2 * 16); \
 206                 for (i = 0; i < 8; i++) { \
 207                         DES_SP_DECRYPT_ROUND((left), (right), (temp), (kp)); \
 208                         DES_SP_DECRYPT_ROUND((right), (left), (temp), (kp)); \
 209                 } \
 210                 DES_FINAL_PERM((left), (right), (temp)); \
 211         } while (0)
 212
 213 /*
 214  * These are handy dandy utility thingies for straightening out bytes.
 215  * Included here because they're used a couple of places.
 216  */
 217 #define GET_HALF_BLOCK(lr, ip) \
 218         (lr) = ((unsigned KRB_INT32)(*(ip)++)) << 24; \
 219         (lr) |= ((unsigned KRB_INT32)(*(ip)++)) << 16; \
 220         (lr) |= ((unsigned KRB_INT32)(*(ip)++)) << 8; \
 221         (lr) |= (unsigned KRB_INT32)(*(ip)++)
 222
 223 #define PUT_HALF_BLOCK(lr, op) \
 224         *(op)++ = ((lr) >> 24) & 0xff; \
 225         *(op)++ = ((lr) >> 16) & 0xff; \
 226         *(op)++ = ((lr) >> 8) & 0xff; \
 227         *(op)++ = (lr) & 0xff
 228
 229 #endif  /* __DES_TABLES_H__ */