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

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