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

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