chiark - git - mdw - catacomb/blob - symm/des-base.h

   1 /* -*-c-*-
   2  *
   3  * Common features for DES implementation
   4  *
   5  * (c) 1999 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 #ifndef CATACOMB_DES_BASE_H
  29 #define CATACOMB_DES_BASE_H
  30
  31 #ifdef __cplusplus
  32   extern "C" {
  33 #endif
  34
  35 /*----- Header files ------------------------------------------------------*/
  36
  37 #include <mLib/bits.h>
  38
  39 #ifndef CATACOMB_PERMUTE_H
  40 #  include "permute.h"
  41 #endif
  42
  43 /*----- External data -----------------------------------------------------*/
  44
  45 extern const uint32 des_sp[8][64];
  46
  47 /*----- Macros ------------------------------------------------------------*/
  48
  49 /* --- @DES_ROUND@ --- *
  50  *
  51  * This is the basic DES round function.  The inputs are the two subkey
  52  * halves, and the left and right block halves.  Note that the block halves
  53  * are rotated left one place at this point.  This wraps what's meant to be
  54  * the top bit around to the bottom, so I get a clear run at the S-boxes.
  55  */
  56
  57 #define DES_ROUND(ka, kb, x, y) do {                                    \
  58   uint32 _t = (y) ^ (ka);                                               \
  59   (x) ^= des_sp[7][(_t >>  0) & 0x3f] ^                                 \
  60          des_sp[5][(_t >>  8) & 0x3f] ^                                 \
  61          des_sp[3][(_t >> 16) & 0x3f] ^                                 \
  62          des_sp[1][(_t >> 24) & 0x3f];                                  \
  63   _t = ROR32((y), 4) ^ (kb);                                            \
  64   (x) ^= des_sp[6][(_t >>  0) & 0x3f] ^                                 \
  65          des_sp[4][(_t >>  8) & 0x3f] ^                                 \
  66          des_sp[2][(_t >> 16) & 0x3f] ^                                 \
  67          des_sp[0][(_t >> 24) & 0x3f];                                  \
  68 } while (0)
  69
  70 /* --- @DES_IP@, @DES_IPINV@ --- *
  71  *
  72  * The cryptographically useless initial and final permutations.  The initial
  73  * permutation also rotates the two block halves left by one place.  This is
  74  * undone by the inverse permutation at the end.
  75  *
  76  * The initial permutation is traditionally given by the table
  77  *
  78  *      58 50 42 34 26 18 10  2
  79  *      60 52 44 36 28 20 12  4
  80  *      62 54 46 38 30 22 14  6
  81  *      64 56 48 40 32 24 16  8
  82  *      57 49 41 33 25 17  9  1
  83  *      59 51 43 35 27 19 11  3
  84  *      61 53 45 37 29 21 13  5
  85  *      63 55 47 39 31 23 15  7
  86  *
  87  * The bit numbering is terrible.  If the two halves are X and Y, then the
  88  * numbering starts with the most significant bit of X, which is bit 1,
  89  * working down towards the least significant bit, and then continuing with
  90  * the bits of Y, again in order of decreasing significance.  The table
  91  * entries are in this same order, indicating that `bit 1' of the output is
  92  * `bit 58' of the input and so on.
  93  *
  94  * I opt instead to number the bits starting from the least significant bit
  95  * of Y, which is bit 0, up to the most significant bit of X, which is
  96  * bit 63.  This means that we need to reverse the table (because we're going
  97  * to read it in the other direction) and subtract each entry from 64 (to
  98  * correct the bit numbering).  The resulting table is
  99  *
 100  *      57 49 41 33 25 17  9  1
 101  *      59 51 43 35 27 19 11  3
 102  *      61 53 45 37 29 21 13  5
 103  *      63 55 47 39 31 23 15  7
 104  *      56 48 40 32 24 16  8  0
 105  *      58 50 42 34 26 18 10  2
 106  *      60 52 44 36 28 20 12  4
 107  *      62 54 46 38 30 22 14  6
 108  *
 109  * which, interestingly, is /also/ what you get if you just subtract one from
 110  * each of the original table's entries.
 111  *
 112  * If we look at this table in binary, the patterns are much clearer.
 113  *
 114  *      111001 110001 101001 100001 011001 010001 001001 000001
 115  *      111011 110011 101011 100011 011011 010011 001011 000011
 116  *      111101 110101 101101 100101 011101 010101 001101 000101
 117  *      111111 110111 101111 100111 011111 010111 001111 000111
 118  *      111000 110000 101000 100000 011000 010000 001000 000000
 119  *      111010 110010 101010 100010 011010 010010 001010 000010
 120  *      111100 110100 101100 100100 011100 010100 001100 000100
 121  *      111110 110110 101110 100110 011110 010110 001110 000110
 122  *
 123  * We can implement this efficiently using our permutation machinery.
 124  * Writing ~k for index bit @k@ inverted, this permutation reflects the index
 125  * transformation given by ~0, 2, 1, ~5, ~4, ~3.  There's a traditional
 126  * swizzle sequence for this, which we used to use, namely:
 127  *
 128  *                                      //  5,  4,  3,  2,  1,  0
 129  *      TWIZZLE_XCPL (x, y, 2);         // ~2,  4,  3, ~5,  1,  0
 130  *      SWIZZLE_XCPL2(x, y, 1, 4);      // ~2, ~1,  3, ~5, ~4,  0
 131  *      SWIZZLE_XCPL2(x, y, 0, 3);      // ~2, ~1, ~0, ~5, ~4, ~3
 132  *      SWIZZLE_XCPL2(x, y, 3, 4);      // ~2,  0,  1, ~5, ~4, ~3
 133  *      TWIZZLE_XCPL (x, y, 4);         // ~0,  2,  1, ~5, ~4, ~3
 134  *
 135  * Essentially this is an antitranspose -- a reflection about the
 136  * antidiagonal -- followed by a couple of fixup stages.  But the non-twizzle
 137  * steps require more operations, and it's easy to find a sequence which
 138  * always acts on the (current) index bit 5, moving it to where it's wanted,
 139  * and inverting it if necessary, so we only need twizzles.
 140  */
 141
 142 #define DES_IP(x, y) do {                                               \
 143   TWIZZLE_XCPL(x, y, 2);                /* ~2,  4,  3, ~5,  1,  0 */    \
 144   TWIZZLE_XCPL(x, y, 4);                /* ~4,  2,  3, ~5,  1,  0 */    \
 145   TWIZZLE_EXCH(x, y, 1);                /*  1,  2,  3, ~5, ~4,  0 */    \
 146   TWIZZLE_EXCH(x, y, 3);                /*  3,  2,  1, ~5, ~4,  0 */    \
 147   TWIZZLE_XCPL(x, y, 0);                /* ~0,  2,  1, ~5, ~4, ~3 */    \
 148   x = ROL32(x, 1); y = ROL32(y, 1);                                     \
 149 } while (0)
 150
 151 #define DES_IPINV(x, y) do {                                            \
 152   x = ROR32(x, 1); y = ROR32(y, 1);     /* ~0,  2,  1, ~5, ~4, ~3 */    \
 153   TWIZZLE_XCPL(x, y, 0);                /*  3,  2,  1, ~5, ~4,  0 */    \
 154   TWIZZLE_EXCH(x, y, 3);                /*  1,  2,  3, ~5, ~4,  0 */    \
 155   TWIZZLE_EXCH(x, y, 1);                /* ~4,  2,  3, ~5,  1,  0 */    \
 156   TWIZZLE_XCPL(x, y, 4);                /*  3,  2,  1, ~5, ~4,  0 */    \
 157   TWIZZLE_XCPL(x, y, 2);                /*  5,  4,  3,  2,  1,  0 */    \
 158 } while (0)
 159
 160 /* --- @DES_EBLK@, @DES_DBLK@ --- *
 161  *
 162  * Whole block encryption and decryption.
 163  */
 164
 165 #define DES_EBLK(k, a, b, c, d) do {                                    \
 166   const uint32 *_k = (k);                                               \
 167   uint32 _x = (a), _y = (b);                                            \
 168   DES_ROUND(_k[0], _k[1], _x, _y); _k += 2;                             \
 169   DES_ROUND(_k[0], _k[1], _y, _x); _k += 2;                             \
 170   DES_ROUND(_k[0], _k[1], _x, _y); _k += 2;                             \
 171   DES_ROUND(_k[0], _k[1], _y, _x); _k += 2;                             \
 172   DES_ROUND(_k[0], _k[1], _x, _y); _k += 2;                             \
 173   DES_ROUND(_k[0], _k[1], _y, _x); _k += 2;                             \
 174   DES_ROUND(_k[0], _k[1], _x, _y); _k += 2;                             \
 175   DES_ROUND(_k[0], _k[1], _y, _x); _k += 2;                             \
 176   DES_ROUND(_k[0], _k[1], _x, _y); _k += 2;                             \
 177   DES_ROUND(_k[0], _k[1], _y, _x); _k += 2;                             \
 178   DES_ROUND(_k[0], _k[1], _x, _y); _k += 2;                             \
 179   DES_ROUND(_k[0], _k[1], _y, _x); _k += 2;                             \
 180   DES_ROUND(_k[0], _k[1], _x, _y); _k += 2;                             \
 181   DES_ROUND(_k[0], _k[1], _y, _x); _k += 2;                             \
 182   DES_ROUND(_k[0], _k[1], _x, _y); _k += 2;                             \
 183   DES_ROUND(_k[0], _k[1], _y, _x); _k += 2;                             \
 184   (c) = _y;                                                             \
 185   (d) = _x;                                                             \
 186 } while (0)
 187
 188 #define DES_DBLK(k, a, b, c, d) do {                                    \
 189   const uint32 *_k = (k) + 32;                                          \
 190   uint32 _x = (a), _y = (b);                                            \
 191   _k -= 2; DES_ROUND(_k[0], _k[1], _x, _y);                             \
 192   _k -= 2; DES_ROUND(_k[0], _k[1], _y, _x);                             \
 193   _k -= 2; DES_ROUND(_k[0], _k[1], _x, _y);                             \
 194   _k -= 2; DES_ROUND(_k[0], _k[1], _y, _x);                             \
 195   _k -= 2; DES_ROUND(_k[0], _k[1], _x, _y);                             \
 196   _k -= 2; DES_ROUND(_k[0], _k[1], _y, _x);                             \
 197   _k -= 2; DES_ROUND(_k[0], _k[1], _x, _y);                             \
 198   _k -= 2; DES_ROUND(_k[0], _k[1], _y, _x);                             \
 199   _k -= 2; DES_ROUND(_k[0], _k[1], _x, _y);                             \
 200   _k -= 2; DES_ROUND(_k[0], _k[1], _y, _x);                             \
 201   _k -= 2; DES_ROUND(_k[0], _k[1], _x, _y);                             \
 202   _k -= 2; DES_ROUND(_k[0], _k[1], _y, _x);                             \
 203   _k -= 2; DES_ROUND(_k[0], _k[1], _x, _y);                             \
 204   _k -= 2; DES_ROUND(_k[0], _k[1], _y, _x);                             \
 205   _k -= 2; DES_ROUND(_k[0], _k[1], _x, _y);                             \
 206   _k -= 2; DES_ROUND(_k[0], _k[1], _y, _x);                             \
 207   (c) = _y;                                                             \
 208   (d) = _x;                                                             \
 209 } while (0)
 210
 211 /*----- That's all, folks -------------------------------------------------*/
 212
 213 #ifdef __cplusplus
 214   }
 215 #endif
 216
 217 #endif