git.distorted.org.uk Git - u/mdw/catacomb/blob - des.c

   1 /* -*-c-*-
   2  *
   3  * $Id: des.c,v 1.1 1999/09/03 08:41:11 mdw Exp $
   4  *
   5  * The Data Encryption Standard
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: des.c,v $
  33  * Revision 1.1  1999/09/03 08:41:11  mdw
  34  * Initial import.
  35  *
  36  */
  37
  38 /*----- Header files ------------------------------------------------------*/
  39
  40 #include <assert.h>
  41 #include <stdio.h>
  42 #include <stdlib.h>
  43 #include <string.h>
  44
  45 #include <mLib/bits.h>
  46
  47 #include "blkc.h"
  48 #include "des-base.h"
  49 #include "des.h"
  50
  51 /*----- Main code ---------------------------------------------------------*/
  52
  53 /* --- @permute@ --- *
  54  *
  55  * Arguments:   @const char *p@ = pointer to permutation table
  56  *              @uint32 a, b@ = source value to permute
  57  *              @uint32 *d@ = destination for value
  58  *
  59  * Returns:     ---
  60  *
  61  * Use:         Performs a 64-bit permutation.  The table is given in the
  62  *              normal (but bizarre) DES bit numbering system.  That's not to
  63  *              say that the tables in this source file are like the normal
  64  *              DES tables, because they're not.
  65  */
  66
  67 static void permute(const char *p, uint32 a, uint32 b, uint32 *d)
  68 {
  69   uint32 x = 0, y = 0;
  70   int i;
  71
  72   for (i = 0; i < 32; i++) {
  73     int q = p[i];
  74     uint32 t;
  75     if (!q)
  76       continue;
  77     else if (q <= 32)
  78       t = a;
  79     else {
  80       t = b;
  81       q -= 32;
  82     }
  83     if (t & (1 << (32 - q)))
  84       x |= (1 << (31 - i));
  85   }
  86
  87   p += 32;
  88
  89   for (i = 0; i < 32; i++) {
  90     int q = p[i];
  91     uint32 t;
  92     if (!q)
  93       continue;
  94     else if (q <= 32)
  95       t = a;
  96     else {
  97       t = b;
  98       q -= 32;
  99     }
 100     if (t & (1 << (32 - q)))
 101       y |= (1 << (31 - i));
 102   }
 103
 104   d[0] = x;
 105   d[1] = y;
 106 }
 107
 108 /* --- @des_init@ --- *
 109  *
 110  * Arguments:   @des_ctx *k@ = pointer to key block
 111  *              @const void *buf@ = pointer to key buffer
 112  *              @size_t sz@ = size of key material
 113  *
 114  * Returns:     ---
 115  *
 116  * Use:         Initializes a DES key buffer.  The key buffer may be either 7
 117  *              or 8 bytes long.  If it's 8 bytes, the key is assumed to be
 118  *              padded with parity bits in the low order bit of each octet.
 119  *              These are stripped out without checking prior to the actual
 120  *              key scheduling.
 121  */
 122
 123 void des_init(des_ctx *k, const void *buf, size_t sz)
 124 {
 125   uint32 x, y;
 126   uint32 *kp = k->k;
 127   int i;
 128
 129   /* --- @pc1@ --- *
 130    *
 131    * This cryptographically useless permutation is used to mangle the key
 132    * before it's subjected to the key schedule proper.  I've not actually
 133    * messed it about much except for inserting padding at the beginning of
 134    * the two halves of the key.
 135    */
 136
 137   static const char pc1[] = {
 138      0,  0,  0,  0,
 139     57, 49, 41, 33, 25, 17,  9,
 140      1, 58, 50, 42, 34, 26, 18,
 141     10,  2, 59, 51, 43, 35, 27,
 142     19, 11,  3, 60, 52, 44, 36,
 143      0,  0,  0,  0,
 144     63, 55, 47, 39, 31, 23, 15,
 145      7, 62, 54, 46, 38, 30, 22,
 146     14,  6, 61, 53, 45, 37, 29,
 147     21, 13,  5, 28, 20, 12,  4
 148   };
 149
 150   /* --- @pc2@ --- *
 151    *
 152    * This irritating but necessary permutation mangles the key between the
 153    * simple rotation-based schedule and the actual XOR with which it modifies
 154    * the behaviour of the cipher.
 155    *
 156    * This version of the table doesn't look much like the original.  This is
 157    * because some parts of the world have been permuted in order to make
 158    * things simpler for the round function.  In particular, everything is
 159    * rotated left one place to avoid problems with the wraparound of the
 160    * expansion permutation, and the key is split between odd and even S-boxes
 161    * rather than high and low ones.  That's without the complication of the
 162    * padding bits in the representation of the 56-bit proto-key.
 163    */
 164
 165   static const char pc2[] = {
 166      0,  0,  3 + 4, 28 + 4, 15 + 4,  6 + 4, 21 + 4, 10 + 4, /* S-box 2 */
 167      0,  0, 16 + 4,  7 + 4, 27 + 4, 20 + 4, 13 + 4,  2 + 4, /* S-box 4 */
 168      0,  0, 30 + 8, 40 + 8, 51 + 8, 45 + 8, 33 + 8, 48 + 8, /* S-box 6 */
 169      0,  0, 46 + 8, 42 + 8, 50 + 8, 36 + 8, 29 + 8, 32 + 8, /* S-box 8 */
 170      0,  0, 14 + 4, 17 + 4, 11 + 4, 24 + 4,  1 + 4,  5 + 4, /* S-box 1 */
 171      0,  0, 23 + 4, 19 + 4, 12 + 4,  4 + 4, 26 + 4,  8 + 4, /* S-box 3 */
 172      0,  0, 41 + 8, 52 + 8, 31 + 8, 37 + 8, 47 + 8, 55 + 8, /* S-box 5 */
 173      0,  0, 44 + 8, 49 + 8, 39 + 8, 56 + 8, 34 + 8, 53 + 8  /* S-box 7 */
 174   };
 175
 176   /* --- @v@ --- *
 177    *
 178    * Contains the rotation amounts for the key halves.
 179    */
 180
 181   static const char v[] = {
 182     1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
 183   };
 184
 185   /* --- Extract the key into my registers --- *
 186    *
 187    * The 7 byte case is rather horrible.  It expands the key to the 8 byte
 188    * case before going any further.  It could probably do with its own @pc1@
 189    * table.
 190    */
 191
 192   assert(((void)"DES key must be 56 or 64 bits", sz == 7 || sz == 8));
 193
 194   if (sz == 8) {
 195     const octet *p = buf;
 196     x = LOAD32(p); y = LOAD32(p + 4);
 197   } else {
 198     const octet *p = buf;
 199     x = LOAD32(p);
 200     x = (x & 0xfe000000) | ((x & 0x01fffff0) >> 1);
 201     x = (x & 0xfffe0000) | ((x & 0x0001fff8) >> 1);
 202     x = (x & 0xfffffe00) | ((x & 0x000001fc) >> 1);
 203     y = LOAD32(p + 3) << 1; /* Note: misaligned */
 204     y = (y & 0x000000fe) | ((y & 0x1fffff00) << 1);
 205     y = (y & 0x0000fefe) | ((y & 0x3fff0000) << 1);
 206     y = (y & 0x00fefefe) | ((y & 0x7f000000) << 1);
 207   }
 208
 209   /* --- Permute using the pointless PC1 --- */
 210
 211   {
 212     uint32 ka[2];
 213     permute(pc1, x, y, ka);
 214     x = ka[0]; y = ka[1];
 215   }
 216
 217   /* --- Now for the key schedule proper --- */
 218
 219   for (i = 0; i < 16; i++) {
 220     if (v[i] == 1) {
 221       x = ((x << 1) | (x >> 27)) & 0x0fffffff;
 222       y = ((y << 1) | (y >> 27)) & 0x0fffffff;
 223     } else {
 224       x = ((x << 2) | (x >> 26)) & 0x0fffffff;
 225       y = ((y << 2) | (y >> 26)) & 0x0fffffff;
 226     }
 227     permute(pc2, x, y, kp);
 228     kp += 2;
 229   }
 230 }
 231
 232 /* --- @des_eblk@, @des_dblk@ --- *
 233  *
 234  * Arguments:   @const des_ctx *k@ = pointer to key block
 235  *              @const uint32 s[2]@ = pointer to source block
 236  *              @uint32 d[2]@ = pointer to destination block
 237  *
 238  * Returns:     ---
 239  *
 240  * Use:         Low-level block encryption and decryption.
 241  */
 242
 243 void des_eblk(const des_ctx *k, const uint32 *s, uint32 *d)
 244 {
 245   uint32 x = s[0], y = s[1];
 246   DES_IP(x, y);
 247   DES_EBLK(k->k, x, y, x, y);
 248   DES_IPINV(x, y);
 249   d[0] = x, d[1] = y;
 250 }
 251
 252 void des_dblk(const des_ctx *k, const uint32 *s, uint32 *d)
 253 {
 254   uint32 x = s[0], y = s[1];
 255   DES_IP(x, y);
 256   DES_DBLK(k->k, x, y, x, y);
 257   DES_IPINV(x, y);
 258   d[0] = x, d[1] = y;
 259 }
 260
 261 BLKC_TEST(DES, des)
 262
 263 /*----- That's all, folks -------------------------------------------------*/