chiark - git - mdw - catacomb/blob - symm/des.c

   1 /* -*-c-*-
   2  *
   3  * The Data Encryption Standard
   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 /*----- Header files ------------------------------------------------------*/
  29
  30 #include <assert.h>
  31 #include <stdio.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34
  35 #include <mLib/bits.h>
  36
  37 #include "blkc.h"
  38 #include "des-base.h"
  39 #include "des.h"
  40 #include "permute.h"
  41 #include "gcipher.h"
  42
  43 /*----- Global variables --------------------------------------------------*/
  44
  45 const octet des_keysz[] = { KSZ_SET, 7, 8, 0 };
  46
  47 /*----- Main code ---------------------------------------------------------*/
  48
  49 /* --- @des_expand@ --- *
  50  *
  51  * Arguments:   @const octet *k@ = pointer to key material
  52  *              @size_t n@ = number of octets of key material (7 or 8)
  53  *              @uint32 *xx, *yy@ = where to put the results
  54  *
  55  * Returns:     ---
  56  *
  57  * Use:         Extracts 64 bits of key material from the given buffer,
  58  *              possibly expanding it from 56 to 64 bits on the way.
  59  *              Parity is set correctly if the key is expanded.
  60  */
  61
  62 void des_expand(const octet *k, size_t n, uint32 *xx, uint32 *yy)
  63 {
  64   uint32 x, y, z;
  65
  66   if (n == 8) {
  67     x = LOAD32(k + 0);
  68     y = LOAD32(k + 4);
  69   } else {
  70     x = LOAD32(k + 0);
  71     x = (x & 0xfe000000) | ((x & 0x01fffff0) >> 1);
  72     x = (x & 0xfffe0000) | ((x & 0x0001fff8) >> 1);
  73     x = (x & 0xfffffe00) | ((x & 0x000001fc) >> 1);
  74     z = x; z ^= z >> 4; z ^= z >> 2; z ^= z >> 1;
  75     x |= (z & 0x01010101) ^ 0x01010101;
  76     y = LOAD32(k + 3) << 1; /* Note: misaligned */
  77     y = (y & 0x000000fe) | ((y & 0x1fffff00) << 1);
  78     y = (y & 0x0000fefe) | ((y & 0x3fff0000) << 1);
  79     y = (y & 0x00fefefe) | ((y & 0x7f000000) << 1);
  80     z = y; z ^= z >> 4; z ^= z >> 2; z ^= z >> 1;
  81     y |= (z & 0x01010101) ^ 0x01010101;
  82   }
  83   *xx = x; *yy = y;
  84 }
  85
  86 /* --- @des_init@ --- *
  87  *
  88  * Arguments:   @des_ctx *k@ = pointer to key block
  89  *              @const void *buf@ = pointer to key buffer
  90  *              @size_t sz@ = size of key material
  91  *
  92  * Returns:     ---
  93  *
  94  * Use:         Initializes a DES key buffer.  The key buffer may be either 7
  95  *              or 8 bytes long.  If it's 8 bytes, the key is assumed to be
  96  *              padded with parity bits in the low order bit of each octet.
  97  *              These are stripped out without checking prior to the actual
  98  *              key scheduling.
  99  */
 100
 101 void des_init(des_ctx *k, const void *buf, size_t sz)
 102 {
 103 #define REGWD 32
 104   typedef uint32 regty;
 105
 106   uint32 x, y, u, v;
 107   uint32 *kp = k->k;
 108   int i;
 109
 110   /* --- @r@ --- *
 111    *
 112    * Contains the rotation amounts for the key halves.
 113    */
 114
 115   static const char r[] = {
 116     1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
 117   };
 118
 119   /* --- Extract the key into my registers --- *
 120    *
 121    * The 7 byte case is rather horrible.  It expands the key to the 8 byte
 122    * case before going any further.  It could probably do with its own @pc1@
 123    * table.
 124    */
 125
 126   KSZ_ASSERT(des, sz);
 127   des_expand(buf, sz, &x, &y);
 128
 129   /* --- Permute using the pointless PC1 --- *
 130    *
 131    * For reference, the original PC1 permutation is
 132    *
 133    *    Left half       57 49 41 33 25 17  9
 134    *                     1 58 50 42 34 26 18
 135    *                    10  2 59 51 43 35 27
 136    *                    19 11  3 60 52 44 36
 137    *
 138    *    Right half      63 55 47 39 31 23 15
 139    *                     7 62 54 46 38 30 22
 140    *                    14  6 61 53 45 37 29
 141    *                    21 13  5 28 20 12  4
 142    *
 143    * The network below implements this pretty directly; the two 28-bit halves
 144    * end up in the least significant bits of the two output words; the parity
 145    * bits, which are formally discarded, end up in the top 4 bits of each
 146    * half in some random order, and are finally masked off so that they don't
 147    * interfere with the rotation below.  (I did an exhaustive search, and
 148    * there are no better Beneš networks.)
 149    */
 150
 151   SWIZZLE_2(x, y,  1, 0x55005401, 0x55005500);
 152   SWIZZLE_2(x, y,  2, 0x32320101, 0x33330000);
 153   TWIZZLE_0(x, y,     0xf0e1f0f1);
 154   SWIZZLE_2(x, y,  4, 0x0f0e0f0f, 0x08050201);
 155   SWIZZLE_2(x, y,  8, 0x005a003a, 0x005a005a);
 156   SWIZZLE_2(x, y, 16, 0x00007c6c, 0x000023cc);
 157   TWIZZLE_0(x, y,     0x20f1e0f0);
 158   SWIZZLE_2(x, y,  2, 0x10000333, 0x33201013);
 159   SWIZZLE_2(x, y,  1, 0x10055005, 0x10455005);
 160   x &= 0x0fffffff; y &= 0x0fffffff;
 161
 162   /* --- Now for the key schedule proper --- */
 163
 164   for (i = 0; i < 16; i++) {
 165     if (r[i] == 1) {
 166       x = ((x << 1) | (x >> 27)) & 0x0fffffff;
 167       y = ((y << 1) | (y >> 27)) & 0x0fffffff;
 168     } else {
 169       x = ((x << 2) | (x >> 26)) & 0x0fffffff;
 170       y = ((y << 2) | (y >> 26)) & 0x0fffffff;
 171     }
 172
 173     /* --- Apply PC2, which is another Beneš network --- *
 174      *
 175      * The original permutation is described as follows.
 176      *
 177      *          S-box 1: 14 17 11 24  1  5
 178      *          S-box 2:  3 28 15  6 21 10
 179      *          S-box 3: 23 19 12  4 26  8
 180      *          S-box 4: 16  7 27 20 13  2
 181      *          S-box 5: 41 52 31 37 47 55
 182      *          S-box 6: 30 40 51 45 33 48
 183      *          S-box 7: 44 49 39 56 34 53
 184      *          S-box 8: 46 42 50 36 29 32
 185      *
 186      * Firstly, note the way that the key bits are arranged in the words @x@
 187      * and @y@: viewed from the way DES numbers bits from the most-
 188      * significant end down, there are four padding bits in positions 1--4,
 189      * and another four in positions 33--36.  Because the bits in the left-
 190      * hand half of the key all feed into the first four S-boxes, we must
 191      * adjust the bit positions by 4; and we must adjust the positions of the
 192      * bits in the right-hand half by 8.
 193      *
 194      * Secondly, this isn't how we want to apply the key.  The formal
 195      * description of DES includes an `expansion' %$E$%: essentially, we take
 196      * each chunk of four bits in the 32-bit half block, and glue on the
 197      * nearest bits from the preceding and following chunk to make a six-bit
 198      * chunk, which we then XOR with six bits of key and feed into the S-box
 199      * to collapse back down to four bits.  We avoid having to do this in
 200      * practice by doing the S-boxes in two steps: first, the even-numbered
 201      * ones and then the odd-numbered ones.  Because these two collections of
 202      * S-boxes don't involve overlapping input bits, we can just XOR in the
 203      * correct key bits and apply the substitution.  There's one more little
 204      * problem, which is that the input to the final S-box needs the topmost
 205      * bit of the input half-block, which we handle by having previously
 206      * rotated the message block left by one position.  And that's the
 207      * permutation that we implement here.
 208      *
 209      * There are too many blank spaces to search exhaustively for an optimal
 210      * network.  Based on my experience with PC1, I don't expect the optimal
 211      * network to be significantly better than this one.
 212      */
 213
 214     u = x; v = y;
 215     SWIZZLE_2(u, v,  1, 0x10551050, 0x05500504);
 216     SWIZZLE_2(u, v,  2, 0x12131230, 0x33102201);
 217     SWIZZLE_2(u, v,  8, 0x00a200ec, 0x009100ba);
 218     SWIZZLE_2(u, v, 16, 0x000012ab, 0x000028e0);
 219     SWIZZLE_2(u, v,  4, 0x0a090805, 0x0b040002);
 220     TWIZZLE_0(u, v,     0x33856c2a);
 221     SWIZZLE_2(u, v, 16, 0x00003385, 0x00004c6a);
 222     SWIZZLE_2(u, v,  8, 0x001500c8, 0x004700e8);
 223     SWIZZLE_2(u, v,  2, 0x20130212, 0x00310022);
 224     SWIZZLE_2(u, v,  1, 0x05404145, 0x54510510);
 225     kp[0] = u; kp[1] = v; kp += 2;
 226   }
 227
 228 #undef REGWD
 229 }
 230
 231 /* --- @des_eblk@, @des_dblk@ --- *
 232  *
 233  * Arguments:   @const des_ctx *k@ = pointer to key block
 234  *              @const uint32 s[2]@ = pointer to source block
 235  *              @uint32 d[2]@ = pointer to destination block
 236  *
 237  * Returns:     ---
 238  *
 239  * Use:         Low-level block encryption and decryption.
 240  */
 241
 242 void des_eblk(const des_ctx *k, const uint32 *s, uint32 *d)
 243 {
 244 #define REGWD 32
 245   typedef uint32 regty;
 246
 247   uint32 x = s[0], y = s[1];
 248   DES_IP(x, y);
 249   DES_EBLK(k->k, x, y, x, y);
 250   DES_IPINV(x, y);
 251   d[0] = x, d[1] = y;
 252
 253 #undef REGWD
 254 }
 255
 256 void des_dblk(const des_ctx *k, const uint32 *s, uint32 *d)
 257 {
 258 #define REGWD 32
 259   typedef uint32 regty;
 260
 261   uint32 x = s[0], y = s[1];
 262   DES_IP(x, y);
 263   DES_DBLK(k->k, x, y, x, y);
 264   DES_IPINV(x, y);
 265   d[0] = x, d[1] = y;
 266
 267 #undef REGWD
 268 }
 269
 270 BLKC_TEST(DES, des)
 271
 272 /*----- That's all, folks -------------------------------------------------*/