Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:14:01
Alex Alten (Alten@home.com)
Wed, 23 Sep 1998 00:05:44 -0700
About a year ago someone on the list suggested a way to improve
DES key setup of the 16 internal subkeys. Basically the idea was
to create a table of entries per bit in the DES key. Each entry
would consist of 16 subkeys with the appropriate bits turned on.
To create the proper subkeys from a key all one has to do is bit
OR certain entries together corresponding to each "1" bit in the
key. Anyway I built some code to test the idea out. I used
Eric Young's fast DES implementation which has combined S and P
boxes (it runs about 15% faster than D3DES by Richard Outerbridge).
It's main drawback was a slower key setup. If one needs to rekey
thousands of small buffers per second, say in a high performance
transaction protocol, then key setup overhead becomes an important
consideration especially for implementations using triple DES.
My implementation uses a table which provides subkeys for all possible
8 bit values within each byte of a DES key. The table is 1 MByte
in size. I generate the table by using the normal fast DES key
setup function (deskey). It included as a header file (keySchdule.h)
for the optimized version of the setup function.
Here are the performance numbers using a Pentium Pro 200 MHz CPU.
For the key setup test I used 65536 random keys, repeated 16 times.
Hopefully this properly emulates a real world fast rekeying case.
Normal fast DES key setup = 200.3 usec/key. (D3DES = 84.9 usec/key)
Optimized fast DES key setup = 9.5 usec/key.
Note that fast DES block enciphering is .346 usec/byte (D3DES is
.458 usec/byte). This is using a random 1 MByte buffer repeated
128 times.
Below is the code. I don't guarentee anything, however it seems
to work fine, passing both test data and Ron Rivest's test vector.
- Alex
P.S. Thanks Eric for the lovely fast DES C code.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> CUT HERE <<<<<<<<<<<<<<<<<<<<<<<<<<<
>>>>> This program generates an array of unsigned long integers <<<<<<
>>>>> to stdout (pipe it to keySchedule.h) <<<<<<
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> CUT HERE <<<<<<<<<<<<<<<<<<<<<<<<<<<
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define _FASTDES_C_
#include "fastdes.h"
static void get8 (unsigned char *);
static void put8 (unsigned char *);
main()
{
unsigned char key[8];
unsigned int x,q,r,s;
static unsigned long keyScheduleEncrypt[16][2], keyScheduleDecrypt[16][2];
unsigned __int64 *pKey = (unsigned __int64 *) key;
unsigned __int8 *(ppKey2[8]);
for (x=0;x<8;x++)
ppKey2[x] = (unsigned __int8 *) &key[x];
printf("\n");
printf("unsigned long keyScheduleEncrypt[8][256][16][2]=");
printf("\n{");
for (x=0;x<8;x++)
{
memset(key, 0, 8);
for(q=0;q<256;q++)
{
*(ppKey2[x]) = (unsigned __int8) q;
printf("\n\n\t// ****> key=0x");
put8(key);
deskey(keyScheduleEncrypt,key,0);
for(r=0;r<16;r++) {
printf("\n\t");
for(s=0;s<2;s++) {
if ((x==7)&&(q==255)&&(r==15)&&(s==1)) // last entry?
printf("0x%8.8x", keyScheduleEncrypt[r][s]);
else
printf("0x%8.8x, ", keyScheduleEncrypt[r][s]);
};
printf("\t// keyScheduleEncrypt[%d][%d][%d][] ", x, q, r);
};
}; // q loop
}; // x loop
printf("\n};");
printf("\n\n\n");
printf("\n");
printf("unsigned long keyScheduleDecrypt[8][256][16][2]=");
printf("\n{");
for (x=0;x<8;x++)
{
memset(key, 0, 8);
for(q=0;q<256;q++)
{
*(ppKey2[x]) = (unsigned __int8) q;
printf("\n\n\t// ****> key=0x");
put8(key);
deskey(keyScheduleDecrypt,key,1);
for(r=0;r<16;r++) {
printf("\n\t");
for(s=0;s<2;s++) {
if ((x==7)&&(q==255)&&(r==15)&&(s==1)) // last entry?
printf("0x%8.8x", keyScheduleDecrypt[r][s]);
else
printf("0x%8.8x, ", keyScheduleDecrypt[r][s]);
};
printf("\t// keyScheduleDecrypt[%d][%d][%d][] ", x, q, r);
};
}; // q loop
}; // x loop
printf("\n};");
return 0;
}
static void
get8(cp)
unsigned char *cp;
{
int i,t;
for(i=0;i<8;i++){
scanf("%2x",&t);
if(feof(stdin))
exit(0);
*cp++ = t;
}
}
static void
put8(cp)
unsigned char *cp;
{
int i;
for(i=7;i>=0;i--){
printf("%02x",cp[i] & 0xff);
}
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> CUT HERE <<<<<<<<<<<<<<<<<<<<<<<<<<<
>>>>>> This is the new optimized fast DES key setup function <<<<<<<<<
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> CUT HERE <<<<<<<<<<<<<<<<<<<<<<<<<<<
#include <string.h>
#define _FASTDES_C_
#include "fastdes.h"
#include "keySchedule.h"
/* Generate key schedule for encryption or decryption
* depending on the value of "decrypt"
*/
void
deskey(schedule,key,decrypt)
unsigned long schedule[16][2]; // DES_KS schedule; /*
Key schedule array */
unsigned char *key; /* 64 bits (will use only 56) */
int decrypt; /* 0 = encrypt, 1 = decrypt */
{
register unsigned int q=0,r=0,s=0;
unsigned __int64 *pKey = (unsigned __int64 *)key;
unsigned __int8 x;
memset(schedule, 0, sizeof(DES_KS));
switch (decrypt)
{
default:
case 0: // encrypt
for (q=0;q<8;q++)
{
x = (unsigned __int8) (*pKey >> q*8);
// OR bits of each precomputed schedule to new schedule.
for (r=0;r<16;r++)
for (s=0;s<2;s++)
schedule[r][s] = schedule[r][s] |
keyScheduleEncrypt[q][x][r][s];
}
break;
case 1: // decrypt
for (q=0;q<8;q++)
{
x = (unsigned __int8) (*pKey >> q*8);
// OR bits of each precomputed schedule to new schedule.
for (r=0;r<16;r++)
for (s=0;s<2;s++)
schedule[r][s] = schedule[r][s] |
keyScheduleDecrypt[q][x][r][s];
}
break;
};
return;
}
/* Generate key schedule for triple DES in E-D-E (or D-E-D) mode.
*
* The key argument is taken to be 24 bytes. The first 8 bytes are K1
* for the first stage, the second 8 bytes are K2 for the middle stage
* and the third 8 bytes are K3 for the last stage
*/
void
des3key(k,key,decrypt)
DES3_KS k;
unsigned char *key; /* 192 bits (will use only 168) */
int decrypt; /* 0 = encrypt, 1 = decrypt */
{
if(!decrypt){
deskey(&k[0],&key[0],0);
deskey(&k[16],&key[8],1);
deskey(&k[32],&key[16],0);
} else {
deskey(&k[32],&key[0],1);
deskey(&k[16],&key[8],0);
deskey(&k[0],&key[16],1);
}
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> CUT HERE <<<<<<<<<<<<<<<<<<<<<<<<<<<
>>>>>>>> This is the original fast DES key setup function <<<<<<<<<<<<
>>>>>>>> This is linked with the above program to generate <<<<<<<<<<<
>>>>>>>> the key schedule table (keySchedule.h) <<<<<<<<<<<<
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> CUT HERE <<<<<<<<<<<<<<<<<<<<<<<<<<<
/* Portable C code to create DES key schedules from user-provided keys
* This doesn't have to be fast unless you're cracking keys or UNIX
* passwords
*/
#include <string.h>
#define _FASTDES_C_
#include "fastdes.h"
/* Key schedule-related tables from FIPS-46 */
/* permuted choice table (key) */
static unsigned char pc1[] = {
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,
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
};
/* number left rotations of pc1 */
static unsigned char totrot[] = {
1,2,4,6,8,10,12,14,15,17,19,21,23,25,27,28
};
/* permuted choice key (table) */
static unsigned char pc2[] = {
14, 17, 11, 24, 1, 5,
3, 28, 15, 6, 21, 10,
23, 19, 12, 4, 26, 8,
16, 7, 27, 20, 13, 2,
41, 52, 31, 37, 47, 55,
30, 40, 51, 45, 33, 48,
44, 49, 39, 56, 34, 53,
46, 42, 50, 36, 29, 32
};
/* End of DES-defined tables */
/* bit 0 is left-most in byte */
static int bytebit[] = {
0200,0100,040,020,010,04,02,01
};
/* Generate key schedule for encryption or decryption
* depending on the value of "decrypt"
*/
void
deskey(k,key,decrypt)
DES_KS k; /* Key schedule array */
unsigned char *key; /* 64 bits (will use only 56) */
int decrypt; /* 0 = encrypt, 1 = decrypt */
{
unsigned char pc1m[56]; /* place to modify pc1 into */
unsigned char pcr[56]; /* place to rotate pc1 into */
register int i,j,l;
int m;
unsigned char ks[8];
for (j=0; j<56; j++) { /* convert pc1 to bits of key */
l=pc1[j]-1; /* integer bit location */
m = l & 07; /* find bit */
pc1m[j]=(key[l>>3] & /* find which key byte l is in */
bytebit[m]) /* and which bit of that byte */
? 1 : 0; /* and store 1-bit result */
}
for (i=0; i<16; i++) { /* key chunk for each iteration */
memset(ks,0,sizeof(ks)); /* Clear key schedule */
for (j=0; j<56; j++) /* rotate pc1 the right amount */
pcr[j] = pc1m[(l=j+totrot[decrypt? 15-i :
i])<(j<28? 28 : 56) ? l: l-28];
/* rotate left and right halves independently */
for (j=0; j<48; j++){ /* select bits individually */
/* check bit that goes to ks[j] */
if (pcr[pc2[j]-1]){
/* mask it in if it's there */
l= j % 6;
ks[j/6] |= bytebit[l] >> 2;
}
}
/* Now convert to packed odd/even interleaved form */
k[i][0] = ((long)ks[0] << 24)
| ((long)ks[2] << 16)
| ((long)ks[4] << 8)
| ((long)ks[6]);
k[i][1] = ((long)ks[1] << 24)
| ((long)ks[3] << 16)
| ((long)ks[5] << 8)
| ((long)ks[7]);
if(Asmversion){
/* The assembler versions pre-shift each subkey 2 bits
* so the Spbox indexes are already computed
*/
k[i][0] <<= 2;
k[i][1] <<= 2;
}
}
}
/* Generate key schedule for triple DES in E-D-E (or D-E-D) mode.
*
* The key argument is taken to be 24 bytes. The first 8 bytes are K1
* for the first stage, the second 8 bytes are K2 for the middle stage
* and the third 8 bytes are K3 for the last stage
*/
void
des3key(k,key,decrypt)
DES3_KS k;
unsigned char *key; /* 192 bits (will use only 168) */
int decrypt; /* 0 = encrypt, 1 = decrypt */
{
if(!decrypt){
deskey(&k[0],&key[0],0);
deskey(&k[16],&key[8],1);
deskey(&k[32],&key[16],0);
} else {
deskey(&k[32],&key[0],1);
deskey(&k[16],&key[8],0);
deskey(&k[0],&key[16],1);
}
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> CUT HERE <<<<<<<<<<<<<<<<<<<<<<<<<<<
>>>>>>>> This is the fast DES header file <<<<<<<<<<<<
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> CUT HERE <<<<<<<<<<<<<<<<<<<<<<<<<<<
typedef unsigned long DES_KS[16][2]; /* Single-key DES key schedule */
typedef unsigned long DES3_KS[48][2]; /* Triple-DES key schedule */
#ifdef _FASTDES_C_
/* In deskey.c: */
void deskey(DES_KS, unsigned char *, int);
void des3key(DES3_KS, unsigned char *, int);
/* In desport.c, desborl.cas or desgnu.s: */
void des(DES_KS, unsigned char *, unsigned char *);
/* In des3port.c, des3borl.cas or des3gnu.s: */
void des3(DES3_KS, unsigned char *, unsigned char *);
extern int Asmversion; /* 1 if we're linked with an asm version, 0 if C */
#else
extern "C" {
/* In deskey.c: */
void deskey(DES_KS, unsigned char *, int);
void des3key(DES3_KS, unsigned char *, int);
/* In desport.c, desborl.cas or desgnu.s: */
void des(DES_KS, unsigned char *, unsigned char *);
/* In des3port.c, des3borl.cas or des3gnu.s: */
void des3(DES3_KS, unsigned char *, unsigned char *);
};
#endif // _FASTDES_C_
--Alex Alten
Alten@Home.Com Alten@TriStrata.Com
P.O. Box 11406 Pleasanton, CA 94588 USA (925) 417-0159
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:14:01