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