base/permute.h, utils/permute.lisp, symm/...: Formalize bit permutations.

[catacomb] / symm / des.c

/* -*-c-*-
 *
 * The Data Encryption Standard
 *
 * (c) 1999 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------*
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * Catacomb is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Header files ------------------------------------------------------*/

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <mLib/bits.h>

#include "blkc.h"
#include "des-base.h"
#include "des.h"
#include "permute.h"
#include "gcipher.h"

/*----- Global variables --------------------------------------------------*/

const octet des_keysz[] = { KSZ_SET, 7, 8, 0 };

/*----- Main code ---------------------------------------------------------*/

/* --- @permute@ --- *
 *
 * Arguments:	@const char *p@ = pointer to permutation table
 *		@uint32 a, b@ = source value to permute
 *		@uint32 *d@ = destination for value
 *
 * Returns:	---
 *
 * Use:		Performs a 64-bit permutation.  The table is given in the
 *		normal (but bizarre) DES bit numbering system.  That's not to
 *		say that the tables in this source file are like the normal
 *		DES tables, because they're not.
 */

static void permute(const char *p, uint32 a, uint32 b, uint32 *d)
{
  uint32 x = 0, y = 0;
  int i;

  for (i = 0; i < 32; i++) {
    int q = p[i];
    uint32 t;
    if (!q)
      continue;
    else if (q <= 32)
      t = a;
    else {
      t = b;
      q -= 32;
    }
    if (t & (1 << (32 - q)))
      x |= (1 << (31 - i));
  }

  p += 32;

  for (i = 0; i < 32; i++) {
    int q = p[i];
    uint32 t;
    if (!q)
      continue;
    else if (q <= 32)
      t = a;
    else {
      t = b;
      q -= 32;
    }
    if (t & (1 << (32 - q)))
      y |= (1 << (31 - i));
  }

  d[0] = x;
  d[1] = y;
}

/* --- @des_expand@ --- *
 *
 * Arguments:	@const octet *k@ = pointer to key material
 *		@size_t n@ = number of octets of key material (7 or 8)
 *		@uint32 *xx, *yy@ = where to put the results
 *
 * Returns:	---
 *
 * Use:		Extracts 64 bits of key material from the given buffer,
 *		possibly expanding it from 56 to 64 bits on the way.
 *		Parity is set correctly if the key is expanded.
 */

void des_expand(const octet *k, size_t n, uint32 *xx, uint32 *yy)
{
  uint32 x, y, z;

  if (n == 8) {
    x = LOAD32(k + 0);
    y = LOAD32(k + 4);
  } else {
    x = LOAD32(k + 0);
    x = (x & 0xfe000000) | ((x & 0x01fffff0) >> 1);
    x = (x & 0xfffe0000) | ((x & 0x0001fff8) >> 1);
    x = (x & 0xfffffe00) | ((x & 0x000001fc) >> 1);
    z = x; z ^= z >> 4; z ^= z >> 2; z ^= z >> 1;
    x |= (z & 0x01010101) ^ 0x01010101;
    y = LOAD32(k + 3) << 1; /* Note: misaligned */
    y = (y & 0x000000fe) | ((y & 0x1fffff00) << 1);
    y = (y & 0x0000fefe) | ((y & 0x3fff0000) << 1);
    y = (y & 0x00fefefe) | ((y & 0x7f000000) << 1);
    z = y; z ^= z >> 4; z ^= z >> 2; z ^= z >> 1;
    y |= (z & 0x01010101) ^ 0x01010101;
  }
  *xx = x; *yy = y;
}

/* --- @des_init@ --- *
 *
 * Arguments:	@des_ctx *k@ = pointer to key block
 *		@const void *buf@ = pointer to key buffer
 *		@size_t sz@ = size of key material
 *
 * Returns:	---
 *
 * Use:		Initializes a DES key buffer.  The key buffer may be either 7
 *		or 8 bytes long.  If it's 8 bytes, the key is assumed to be
 *		padded with parity bits in the low order bit of each octet.
 *		These are stripped out without checking prior to the actual
 *		key scheduling.
 */

void des_init(des_ctx *k, const void *buf, size_t sz)
{
  uint32 x, y;
  uint32 *kp = k->k;
  uint32 ka[2];
  int i;

  /* --- @pc1@ --- *
   *
   * This cryptographically useless permutation is used to mangle the key
   * before it's subjected to the key schedule proper.  I've not actually
   * messed it about much except for inserting padding at the beginning of
   * the two halves of the key.
   */

  static const char pc1[] = {
     0,	 0,  0,	 0,
    57, 49, 41, 33, 25, 17,  9,
     1, 58, 50, 42, 34, 26, 18,
    10,	 2, 59, 51, 43, 35, 27,
    19, 11,  3, 60, 52, 44, 36,
     0,	 0,  0,	 0,
    63, 55, 47, 39, 31, 23, 15,
     7, 62, 54, 46, 38, 30, 22,
    14,	 6, 61, 53, 45, 37, 29,
    21, 13,  5, 28, 20, 12,  4
  };

  /* --- @pc2@ --- *
   *
   * This irritating but necessary permutation mangles the key between the
   * simple rotation-based schedule and the actual XOR with which it modifies
   * the behaviour of the cipher.
   *
   * This version of the table doesn't look much like the original.  This is
   * because some parts of the world have been permuted in order to make
   * things simpler for the round function.  In particular, everything is
   * rotated left one place to avoid problems with the wraparound of the
   * expansion permutation, and the key is split between odd and even S-boxes
   * rather than high and low ones.  That's without the complication of the
   * padding bits in the representation of the 56-bit proto-key.
   */

  static const char pc2[] = {
     0,	 0,  3 + 4, 28 + 4, 15 + 4,  6 + 4, 21 + 4, 10 + 4, /* S-box 2 */
     0,	 0, 16 + 4,  7 + 4, 27 + 4, 20 + 4, 13 + 4,  2 + 4, /* S-box 4 */
     0,	 0, 30 + 8, 40 + 8, 51 + 8, 45 + 8, 33 + 8, 48 + 8, /* S-box 6 */
     0,	 0, 46 + 8, 42 + 8, 50 + 8, 36 + 8, 29 + 8, 32 + 8, /* S-box 8 */
     0,	 0, 14 + 4, 17 + 4, 11 + 4, 24 + 4,  1 + 4,  5 + 4, /* S-box 1 */
     0,	 0, 23 + 4, 19 + 4, 12 + 4,  4 + 4, 26 + 4,  8 + 4, /* S-box 3 */
     0,	 0, 41 + 8, 52 + 8, 31 + 8, 37 + 8, 47 + 8, 55 + 8, /* S-box 5 */
     0,	 0, 44 + 8, 49 + 8, 39 + 8, 56 + 8, 34 + 8, 53 + 8  /* S-box 7 */
  };

  /* --- @v@ --- *
   *
   * Contains the rotation amounts for the key halves.
   */

  static const char v[] = {
    1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
  };

  /* --- Extract the key into my registers --- *
   *
   * The 7 byte case is rather horrible.  It expands the key to the 8 byte
   * case before going any further.  It could probably do with its own @pc1@
   * table.
   */

  KSZ_ASSERT(des, sz);
  des_expand(buf, sz, &x, &y);

  /* --- Permute using the pointless PC1 --- */

  permute(pc1, x, y, ka);
  x = ka[0]; y = ka[1];

  /* --- Now for the key schedule proper --- */

  for (i = 0; i < 16; i++) {
    if (v[i] == 1) {
      x = ((x << 1) | (x >> 27)) & 0x0fffffff;
      y = ((y << 1) | (y >> 27)) & 0x0fffffff;
    } else {
      x = ((x << 2) | (x >> 26)) & 0x0fffffff;
      y = ((y << 2) | (y >> 26)) & 0x0fffffff;
    }
    permute(pc2, x, y, kp);
    kp += 2;
  }
}

/* --- @des_eblk@, @des_dblk@ --- *
 *
 * Arguments:	@const des_ctx *k@ = pointer to key block
 *		@const uint32 s[2]@ = pointer to source block
 *		@uint32 d[2]@ = pointer to destination block
 *
 * Returns:	---
 *
 * Use:		Low-level block encryption and decryption.
 */

void des_eblk(const des_ctx *k, const uint32 *s, uint32 *d)
{
#define REGWD 32
  typedef uint32 regty;

  uint32 x = s[0], y = s[1];
  DES_IP(x, y);
  DES_EBLK(k->k, x, y, x, y);
  DES_IPINV(x, y);
  d[0] = x, d[1] = y;

#undef REGWD
}

void des_dblk(const des_ctx *k, const uint32 *s, uint32 *d)
{
#define REGWD 32
  typedef uint32 regty;

  uint32 x = s[0], y = s[1];
  DES_IP(x, y);
  DES_DBLK(k->k, x, y, x, y);
  DES_IPINV(x, y);
  d[0] = x, d[1] = y;

#undef REGWD
}

BLKC_TEST(DES, des)

/*----- That's all, folks -------------------------------------------------*/