desblock.c

des算法实现源码

/*
 * A Fast software implementation of...
 *
 * the National Bureau of Standards Data Encryption Standard
 *
 * From Federal Information Processing Standards Publication 46-1, 22-Jan-88
 *
 * Written by David A. Barrett ([e-mail])
 *
 * Permission is given for all purposes other than selling code based
 * upon optimizations presented here.
 */
#ifdef __cplusplus	/* force C linkage conventions even if C++ */
extern "C" {
#endif

#include <stdlib.h>	/* POSIX: malloc free */
#include <string.h>
#include "desdefs.h"			/* private data structures */

static char ident[] = 
   " @(#) desblock.c  version 1.3 07-Sep-93 by Dave Barrett\n";
static char rcsIdent[] = 
   " @(#) desblock.c  RCS: $Revision: 1.3 $ $Date: 94/03/28 23:43:52 $\n";

/*
 * The sum of all elements must be KEYBITS
 */
keyBitIndex keyRotates[STAGECOUNT] = {
   1, 1, 2, 2, 2, 2, 2, 2,
   1, 2, 2, 2, 2, 2, 2, 1,
};

/*
 * Permuted Choice 1: (PC-1)
 *
 * used only once to permute key  (64-bit to 56-bit permutation)
 * Ignores bits =   mod 8 (used as ascii parity bits)
 */
blockBitIndex keyTr1[KEYBITS] = {
   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, 			/* this missing chunk down below */
   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
};

#if 0
/*
 * debug 
 */
void showBits(vec, size)
   register bit *vec;
   int size;
{
   register bit *end = vec + size;
   int i;

   for (i = 0; i < size; i++) {
      printf("%d", i % 10);
   }
   putchar('\n');
   do {
      printf("%d", *vec++);
   } while (vec < end);
   putchar('\n');
}
#endif

void rotateLeft(x, size)
   bit *x;
   bitIndex  size;
{
   register bit i = x[0];

   memcpy(x, x + 1, size-1);	/* should be memove, but should work */
   x[size-1] = i;
}

void transpose(dst, src, dstSize, srcSize, perm)
   bit 	 	  *src;
   bit		  *dst;
   bitIndex 	  dstSize, srcSize;
   bitIndexVector perm;
{
   bit 	x[BLOCKBITS+BASE];
   register bit *dp = dst + dstSize;
   register bit *pp = perm + dstSize;

   memcpy(x + BASE, src, srcSize * sizeof src[0]);
   do {
      *--dp = x[*--pp];
   } while (pp > perm);
}

/*
 * Optimization 6: key2Transpose (56 to 48 bit permuted choice with packing)
 */
void key2Transpose(d, s)
#ifndef OLDDES
   register u32 *d;
#else
   register u6  *d;
#endif
   register bit *s;
{
#ifndef OLDDES
   register unsigned int i;
   register u32 j;

   i =s[22]; i<<=1; i|=s[18]; i<<=1; i|=s[11]; i<<=1; i|=s[3];  i<<=1; i|=s[25]; i<<=1; i|=s[7];  j =i; j<<=8; /* 2 */
   i =s[40]; i<<=1; i|=s[51]; i<<=1; i|=s[30]; i<<=1; i|=s[36]; i<<=1; i|=s[46]; i<<=1; i|=s[54]; j|=i; j<<=8; /* 4 */
   i =s[43]; i<<=1; i|=s[48]; i<<=1; i|=s[38]; i<<=1; i|=s[55]; i<<=1; i|=s[33]; i<<=1; i|=s[52]; j|=i; j<<=8; /* 6 */
   i =s[13]; i<<=1; i|=s[16]; i<<=1; i|=s[10]; i<<=1; i|=s[23]; i<<=1; i|=s[0];  i<<=1; i|=s[4];  j|=i;        /* 0 */
   *d++ = j;

   i =s[2];  i<<=1; i|=s[27]; i<<=1; i|=s[14]; i<<=1; i|=s[5];  i<<=1; i|=s[20]; i<<=1; i|=s[9];  j =i; j<<=8; /* 1 */
   i =s[15]; i<<=1; i|=s[6];  i<<=1; i|=s[26]; i<<=1; i|=s[19]; i<<=1; i|=s[12]; i<<=1; i|=s[1];  j|=i; j<<=8; /* 3 */
   i =s[29]; i<<=1; i|=s[39]; i<<=1; i|=s[50]; i<<=1; i|=s[44]; i<<=1; i|=s[32]; i<<=1; i|=s[47]; j|=i; j<<=8; /* 5 */
   i =s[45]; i<<=1; i|=s[41]; i<<=1; i|=s[49]; i<<=1; i|=s[35]; i<<=1; i|=s[28]; i<<=1; i|=s[31]; j|=i;        /* 7 */
   *d++ = j;
#else
   register u6 i;

   i =s[13]; i<<=1; i|=s[16]; i<<=1; i|=s[10]; i<<=1; i|=s[23]; i<<=1; i|=s[0];  i<<=1; i|=s[4];  *d++=i; /* 0 */
   i =s[2];  i<<=1; i|=s[27]; i<<=1; i|=s[14]; i<<=1; i|=s[5];  i<<=1; i|=s[20]; i<<=1; i|=s[9];  *d++=i; /* 1 */
   i =s[22]; i<<=1; i|=s[18]; i<<=1; i|=s[11]; i<<=1; i|=s[3];  i<<=1; i|=s[25]; i<<=1; i|=s[7];  *d++=i; /* 2 */
   i =s[15]; i<<=1; i|=s[6];  i<<=1; i|=s[26]; i<<=1; i|=s[19]; i<<=1; i|=s[12]; i<<=1; i|=s[1];  *d++=i; /* 3 */
   i =s[40]; i<<=1; i|=s[51]; i<<=1; i|=s[30]; i<<=1; i|=s[36]; i<<=1; i|=s[46]; i<<=1; i|=s[54]; *d++=i; /* 4 */
   i =s[29]; i<<=1; i|=s[39]; i<<=1; i|=s[50]; i<<=1; i|=s[44]; i<<=1; i|=s[32]; i<<=1; i|=s[47]; *d++=i; /* 5 */
   i =s[43]; i<<=1; i|=s[48]; i<<=1; i|=s[38]; i<<=1; i|=s[55]; i<<=1; i|=s[33]; i<<=1; i|=s[52]; *d++=i; /* 6 */
   i =s[45]; i<<=1; i|=s[41]; i<<=1; i|=s[49]; i<<=1; i|=s[35]; i<<=1; i|=s[28]; i<<=1; i|=s[31]; *d++=i; /* 7 */
#endif
}

/* 
 * Convert a key block to a bit vector
 *
 * dst - the destination address
 * src - the source address
 */
bit *unpackKeyBlock(dst, src)
   register bit *dst;
   register u8  *src;
{
   register u8   b;
   register unsigned c0;
   register unsigned c1;

   c1 = 8;
   dst -= 8;				/* new */
   do {
      dst += 16;			/* new */
      b    = *src++;
      c0   = 8;
      do {
	 *--dst = b & 1;		/* was *dst++ */
	 b >>= 1;
      } while (--c0 != 0);
   } while (--c1 != 0);
   return dst + 8;
}

/*
 * Given a key string, produce a key suitable for encryption, decryption
 *
 * On input, key must be initialized to 0 or a pointer to adequate storage
 *
 * Set decr to 1 for decryption, 0 for encryption
 */
void desMakeKey(key, keyBits, keysize, decr)
   desKeyType    **key;
   u8            *keyBits;
   unsigned      keysize;
   int           decr;
{
   desUnion   keyBlock;
   bit        key64[BLOCKBITS];
   bit        key56[KEYBITS];
   stageRange stage;
   keyBitIndex        j;

   if (*key == (desKeyType *) 0) {
      *key = (desKeyType *) malloc(sizeof (desKeyType));
      if (*key == (desKeyType *) 0) return;
   }

   (*key)->decr = decr;
   if (keysize >= DES_BLOCKSIZE) {
      memcpy((void *) &keyBlock, (void *) keyBits, DES_BLOCKSIZE);
   } else {
      memcpy(keyBlock.bytes, keyBits, keysize);
      memset(keyBlock.bytes + keysize, 0, DES_BLOCKSIZE - keysize);
   }
   unpackKeyBlock(key64, keyBlock.bytes);
   transpose(key56, key64, KEYBITS, BLOCKBITS, keyTr1);	/* 64->56 bits */

   for (stage = 0; stage < STAGECOUNT; stage++) {
      for (j = 0; j < keyRotates[stage]; j++) {
	 rotateLeft(key56, KEYBITS/2);
	 rotateLeft(key56 + KEYBITS/2, KEYBITS/2);
      }
      key2Transpose(
	 &(*key)->bits[!decr ? STAGECOUNT-1-stage : stage][0], key56);
   }
}

/*
 * Given a key, erase it, free the storage, then erase the pointer to it.
 */
void desDestroyKey(key)
   desKeyType    **key;
{
   if (*key != (desKeyType *) 0) {
      (*key)->decr = 0;
      memset((char *) &(*key)->bits[0][0], '\0', sizeof (*key)->bits);
      free((char *) *key);
      *key = (desKeyType *) 0;
   }
}

/*
 * Return the size of an input block
 */
int desInBlockSize(key)
   desKeyType *key;
{
   return DES_BLOCKSIZE;
}

/*
 * Return the size of an output block
 */
int desOutBlockSize(key)
   desKeyType *key;
{
   return DES_BLOCKSIZE;
}

/* 
 * Convert a desPair to a string of bytes
 */
void desUnpackBlock(dst, src)
   u8 		*dst;
   desPair     	*src;
{
   register u8  *dp = dst + 8;
   register u32 s;

   s = src->right;
   *--dp = (u8) s; s >>= 8;
   *--dp = (u8) s; s >>= 8;
   *--dp = (u8) s; s >>= 8;
   *--dp = (u8) s;

   s = src->left;
   *--dp = (u8) s; s >>= 8;
   *--dp = (u8) s; s >>= 8;
   *--dp = (u8) s; s >>= 8;
   *--dp = (u8) s;
}

/* 
 * Convert a string of bytes to a desPair
 */
void desPackBlock(dst, src)
   desPair      *dst;
   u8      	*src;
{
   register u32  d;
   register u8   *sp = src;

   d  = *sp++; d<<= 8;
   d |= *sp++; d<<= 8;
   d |= *sp++; d<<= 8;
   d |= *sp++;
   dst->left = d;
   d  = *sp++; d<<= 8;
   d |= *sp++; d<<= 8;
   d |= *sp++; d<<= 8;
   d |= *sp++;
   dst->right = d;
}

/*
 * Optimization 13:
 *
 * Lots of instructions, but relatively fast.
 *
 * 4 each for a total of 259 instructions (64 are memory fetches)
 *
 * This code does not work very well on the alpha. 15% of total time.
 */
void IP(d, s)
   desPair *d, *s;
{
   register uFast i, j, k;
   u32 l = s->left;
   u32 r = s->right;

   i = 0; 			  j = 0;
   i	|=l&((uFast)1<<10); k=l<<2; j	|=k&0x2000008;    k<<=1;
   i	|=k&0x2000008;    k<<=2;  j	|=k&((uFast)1<<18); k<<=1;
   i	|=k&((uFast)1<<18); k<<=2;  j	|=k&((uFast)1<<11); k<<=1;
   i	|=k&((uFast)1<<11); k<<=2;  j	|=k&((uFast)1<<26); k<<=1;
   i	|=k&((uFast)1<<26); k<<=2;  j	|=k&((uFast)1<<19); k<<=1;
   i	|=k&((uFast)1<<19); k<<=5;  j	|=k&((uFast)1<<27); k<<=1;
   i	|=k&((uFast)1<<27); k=l>>1; j	|=k&((uFast)1<<10); k>>=2;
   i	|=k&((uFast)1<<17); k>>=1;  j	|=k&((uFast)1<<17); k>>=2;
   i	|=k&0x1000004;    k>>=1;  j	|=k&0x1000004;    k>>=2;
   i	|=k&((uFast)1<<9);  k>>=1;  j	|=k&((uFast)1<<9);  k>>=2;
   i	|=k&((uFast)1<<16); k>>=1;  j	|=k&((uFast)1<<16); k>>=2;
   i	|=k&((uFast)1<<1);  k>>=1;  j	|=k&((uFast)1<<1);  k>>=2;
   i	|=k&((uFast)1<<8);  k>>=1;  j	|=k&((uFast)1<<8);  k>>=5;
   i	|=k&1; 	 	  k>>=1;  j	|=k&1;
   				  j	|=r&((uFast)1<<21); k=r<<1;
   i	|=k&((uFast)1<<21); k<<=2;  j	|=k&((uFast)1<<14); k<<=1;
   i	|=k&((uFast)1<<14); k<<=2;  j	|=k&0x20000080;   k<<=1;
   i	|=k&0x20000080;   k<<=2;  j	|=k&((uFast)1<<22); k<<=1;
   i	|=k&((uFast)1<<22); k<<=2;  j	|=k&((uFast)1<<15); k<<=1;
   i	|=k&((uFast)1<<15); k<<=2;  j	|=k&((uFast)1<<30); k<<=1;
   i	|=k&((uFast)1<<30); k<<=2;  j	|=k&((uFast)1<<23); k<<=1;
   i	|=k&((uFast)1<<23); k<<=5;  j	|=k&((uFast)1<<31); k<<=1;
   i	|=k&((uFast)1<<31); k=r>>2; 
   i	|=k&0x10000040;   k>>=1;  j	|=k&0x10000040;   k>>=2;
   i	|=k&((uFast)1<<13); k>>=1;  j	|=k&((uFast)1<<13); k>>=2;
   i	|=k&((uFast)1<<20); k>>=1;  j	|=k&((uFast)1<<20); k>>=2;
   i	|=k&((uFast)1<<5);  k>>=1;  j	|=k&((uFast)1<<5);  k>>=2;
   i	|=k&((uFast)1<<12); k>>=1;  j	|=k&((uFast)1<<12); k>>=5;
   i	|=k&((uFast)1<<4);  k>>=1;  j	|=k&((uFast)1<<4);

   d->left  = i;		  d->right = j;
}

/*
 * Optimization 8: IP inverse = swapTr combined with finalTr 
 * Optimization 9: add l,r;
 * Optimization 13: use packed bits for l and r
 * Optimization 14: packed to packed
 *
 * 259 Instructions (64 are memory stores)
 */
void IPinverse(d, l, r)
   desPair  *d;
   register u32 l, r;
{
   register u32 i;

   i =l<<7&((u32)1<<31);  i|=r<<6&((u32)1<<30);
   i|=l<<13&((u32)1<<29); i|=r<<12&((u32)1<<28);
   i|=l<<19&((u32)1<<27); i|=r<<18&((u32)1<<26);
   i|=l<<25&((u32)1<<25); i|=r<<24&((u32)1<<24);
   i|=l>>2&((u32)1<<23);  i|=r>>3&((u32)1<<22);
   i|=l<<4&((u32)1<<21);  i|=r<<3&((u32)1<<20);
   i|=l<<10&((u32)1<<19); i|=r<<9&((u32)1<<18);
   i|=l<<16&((u32)1<<17); i|=r<<15&((u32)1<<16);
   i|=l>>11&((u32)1<<15); i|=r>>12&((u32)1<<14); 
   i|=l>>5&((u32)1<<13);  i|=r>>6&((u32)1<<12);
   i|=l<<1&((u32)1<<11);  i|=r<<0&((u32)1<<10); 
   i|=l<<7&((u32)1<<9);   i|=r<<6&((u32)1<<8);
   i|=l>>20&((u32)1<<7);  i|=r>>21&((u32)1<<6);
   i|=l>>14&((u32)1<<5);  i|=r>>15&((u32)1<<4);
   i|=l>>8&((u32)1<<3);   i|=r>>9&((u32)1<<2); 
   i|=l>>2&((u32)1<<1);   i|=r>>3&((u32)1<<0);
   d->left = i;
   i =l<<3&((u32)1<<31);  i|=r<<2&((u32)1<<30);
   i|=l<<9&((u32)1<<29);  i|=r<<8&((u32)1<<28);
   i|=l<<15&((u32)1<<27); i|=r<<14&((u32)1<<26);
   i|=l<<21&((u32)1<<25); i|=r<<20&((u32)1<<24);
   i|=l>>6&((u32)1<<23);  i|=r>>7&((u32)1<<22); 
   i|=l<<0&((u32)1<<21);  i|=r>>1&((u32)1<<20);
   i|=l<<6&((u32)1<<19);  i|=r<<5&((u32)1<<18); 
   i|=l<<12&((u32)1<<17); i|=r<<11&((u32)1<<16);
   i|=l>>15&((u32)1<<15); i|=r>>16&((u32)1<<14); 
   i|=l>>9&((u32)1<<13);  i|=r>>10&((u32)1<<12); 
   i|=l>>3&((u32)1<<11);  i|=r>>4&((u32)1<<10);
   i|=l<<3&((u32)1<<9);   i|=r<<2&((u32)1<<8);
   i|=l>>24&((u32)1<<7);  i|=r>>25&((u32)1<<6);
   i|=l>>18&((u32)1<<5);  i|=r>>19&((u32)1<<4);
   i|=l>>12&((u32)1<<3);  i|=r>>13&((u32)1<<2); 
   i|=l>>6&((u32)1<<1);   i|=r>>7&((u32)1<<0);
   d->right = i;
}

/*
 * This function accounts for about 60% of execution time 
 *   (for 788722 bytes, this function is called 1577568 times)
 *
 * Profile  Results:
 *   Machine    %      Instr  Total Time		Total Cycles  MIPS
 *   alpha	46.47%	60 	1.51 (3000/400)	 	 203671752    134.8
 *   mips	52.74%	58	4.61 (DEC240)		 173497854     37.6
 *   sparc2	59%	55	5.4  (sun4c/75) 	 147061424est  27.2
 *   mips	52.74%	58	7.34 (DEC5000)		 173497854     23.6
 *   68030	55%	53	27.0 (HP9000/370)	 152020189est	5.6
 */
u32 desFunc(inp, key)
   register u32 		inp;
#ifndef OLDDES
   u32Key     	key;
#else
   u6Block     	key;
#endif
{
#ifndef OLDDES
   register uFast p, r;

   p  = inp >> 27;
   r  = inp << 5;
   p |= r;
   p ^=  key[0];
   r  = sBoxp[0][p & 63]; p >>= 8;
   r |= sBoxp[6][p & 63]; p >>= 8;
   r |= sBoxp[4][p & 63]; p >>= 8;
   r |= sBoxp[2][p & 63];

   p    = inp >> 31;
   inp  = inp << 1;
   p   |= inp;
   p   ^= key[1];
   r |= sBoxp[7][p & 63]; p >>= 8;
   r |= sBoxp[5][p & 63]; p >>= 8;
   r |= sBoxp[3][p & 63]; p >>= 8;
   r |= sBoxp[1][p & 63];
#else
   register u32	 p, r, q;

   p   = inp; p >>= 27;
   q   = p;   q  &= 3;  q <<= 4;
   r   = inp; r <<= 5;
   p  |= r;
   r  = sBoxp[0][key[0] ^ (p & 63)]; p >>= 4;
   r |= sBoxp[7][key[7] ^ (p & 63)]; p >>= 4;
   r |= sBoxp[6][key[6] ^ (p & 63)]; p >>= 4;
   r |= sBoxp[5][key[5] ^ (p & 63)]; p >>= 4;
   r |= sBoxp[4][key[4] ^ (p & 63)]; p >>= 4;
   r |= sBoxp[3][key[3] ^ (p & 63)]; p >>= 4;
   r |= sBoxp[2][key[2] ^ (p & 63)]; p >>= 4;
   r |= sBoxp[1][key[1] ^ (p | q)];
#endif

   return r;
}

void des(dst, src, key)
   u8          *dst;
   u8	       *src;
   desKeyType  *key;
{
   desPair	dblock, sblock;
   stageRange  	stage = STAGECOUNT;
   register u32	left, right, res;
   desPair  	temp;

   desPackBlock(&sblock, src);
   IP(&temp, &sblock);
   left  = temp.left;
   right = temp.right;

   do {
      res   = desFunc(right, key->bits[--stage]);
      res  ^= left;
      left  = right;
      right = res;
   } while (stage != 0);

   IPinverse(&dblock, left, right);
   desUnpackBlock(dst, &dblock);
}

void desXor(d, s, x, count)
   register char *d, *s, *x;
   register unsigned count;
{
   if (count != 0) do {
      *d++ = *s++ ^ *x++;
   } while (--count != 0);
}
#ifdef __cplusplus
}
#endif