progs/perftest.c: Use from Glibc syscall numbers.

[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 ---------------------------------------------------------*/

/* --- @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)
{
#define REGWD 32
  typedef uint32 regty;

  uint32 x, y, u, v;
  uint32 *kp = k->k;
  int i;

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

  static const char r[] = {
    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 --- *
   *
   * For reference, the original PC1 permutation is
   *
   *	Left half	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
   *
   *	Right half	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
   *
   * The network below implements this pretty directly; the two 28-bit halves
   * end up in the least significant bits of the two output words; the parity
   * bits, which are formally discarded, end up in the top 4 bits of each
   * half in some random order, and are finally masked off so that they don't
   * interfere with the rotation below.  (I did an exhaustive search, and
   * there are no better Beneš networks.)
   */

  SWIZZLE_2(x, y,  1, 0x55005401, 0x55005500);
  SWIZZLE_2(x, y,  2, 0x32320101, 0x33330000);
  TWIZZLE_0(x, y,     0xf0e1f0f1);
  SWIZZLE_2(x, y,  4, 0x0f0e0f0f, 0x08050201);
  SWIZZLE_2(x, y,  8, 0x005a003a, 0x005a005a);
  SWIZZLE_2(x, y, 16, 0x00007c6c, 0x000023cc);
  TWIZZLE_0(x, y,     0x20f1e0f0);
  SWIZZLE_2(x, y,  2, 0x10000333, 0x33201013);
  SWIZZLE_2(x, y,  1, 0x10055005, 0x10455005);
  x &= 0x0fffffff; y &= 0x0fffffff;

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

  for (i = 0; i < 16; i++) {
    if (r[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;
    }

    /* --- Apply PC2, which is another Beneš network --- *
     *
     * The original permutation is described as follows.
     *
     *		S-box 1: 14 17 11 24  1  5
     *		S-box 2:  3 28 15  6 21 10
     *		S-box 3: 23 19 12  4 26  8
     *		S-box 4: 16  7 27 20 13  2
     *		S-box 5: 41 52 31 37 47 55
     *		S-box 6: 30 40 51 45 33 48
     *		S-box 7: 44 49 39 56 34 53
     *		S-box 8: 46 42 50 36 29 32
     *
     * Firstly, note the way that the key bits are arranged in the words @x@
     * and @y@: viewed from the way DES numbers bits from the most-
     * significant end down, there are four padding bits in positions 1--4,
     * and another four in positions 33--36.  Because the bits in the left-
     * hand half of the key all feed into the first four S-boxes, we must
     * adjust the bit positions by 4; and we must adjust the positions of the
     * bits in the right-hand half by 8.
     *
     * Secondly, this isn't how we want to apply the key.  The formal
     * description of DES includes an `expansion' %$E$%: essentially, we take
     * each chunk of four bits in the 32-bit half block, and glue on the
     * nearest bits from the preceding and following chunk to make a six-bit
     * chunk, which we then XOR with six bits of key and feed into the S-box
     * to collapse back down to four bits.  We avoid having to do this in
     * practice by doing the S-boxes in two steps: first, the even-numbered
     * ones and then the odd-numbered ones.  Because these two collections of
     * S-boxes don't involve overlapping input bits, we can just XOR in the
     * correct key bits and apply the substitution.  There's one more little
     * problem, which is that the input to the final S-box needs the topmost
     * bit of the input half-block, which we handle by having previously
     * rotated the message block left by one position.  And that's the
     * permutation that we implement here.
     *
     * There are too many blank spaces to search exhaustively for an optimal
     * network.  Based on my experience with PC1, I don't expect the optimal
     * network to be significantly better than this one.
     */

    u = x; v = y;
    SWIZZLE_2(u, v,  1, 0x10551050, 0x05500504);
    SWIZZLE_2(u, v,  2, 0x12131230, 0x33102201);
    SWIZZLE_2(u, v,  8, 0x00a200ec, 0x009100ba);
    SWIZZLE_2(u, v, 16, 0x000012ab, 0x000028e0);
    SWIZZLE_2(u, v,  4, 0x0a090805, 0x0b040002);
    TWIZZLE_0(u, v,	0x33856c2a);
    SWIZZLE_2(u, v, 16, 0x00003385, 0x00004c6a);
    SWIZZLE_2(u, v,  8, 0x001500c8, 0x004700e8);
    SWIZZLE_2(u, v,  2, 0x20130212, 0x00310022);
    SWIZZLE_2(u, v,  1, 0x05404145, 0x54510510);
    kp[0] = u; kp[1] = v; kp += 2;
  }

#undef REGWD
}

/* --- @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 -------------------------------------------------*/