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)
Thu, 24 Sep 1998 00:30:24 -0700
At 11:40 AM 9/23/98 -0400, Trei, Peter wrote:
>Alex:
>
>Some musings on your post...
>
>I'm the 'someone' you speak of. I actually invented this
Is this your fast DES code? I couldn't remember
whom I got it from, there was no author name in the
comments for the source.
>Your method creates tables on a bytewise basis rather than
>bitwise. You must therefore store 256 tables for each of the
>7 bytes in the 56 bit keys. This occupies 256 * 7 * 128 =
>229,376 bytes (not the 1M you state).
>
I'm not being very efficient with memory. There is an
encrypt and a decrypt table. I don't eliminate the
parity bits, so I end up with some extra zeroed entries.
So 2 * 256 * 8 * 128 = 524,288 bytes. Oops, I was off
by a factor of 2.
>
>So, in theory, bytewise tables should run two to four
>as fast as bitwise tables, all else being equal.
>
I measured 44 usec/key for my bitwise attempt,
about 4-5 times slower than the bytewise version.
>
>The absolute *best* code I've found for generating DES key
>schedules from scratch is Svend Mikkelsen's at
>http://inet.uni2.dk/~svolaf/deskey1.zip It uses very clever
>assembler. I time it at as low as 359 clock cycles per key
>(PPro, NT4). This compares favorably with the 1900 clock
>cycles you report.
>
>I suggest you give it a try.
>
Thanks, I'll take a look at it. Generally speaking,
recently I've been finding that carefully written C
comes quite close to assembler. I usually use the
latest MSVC.
>
>> 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.
>
>Did you use each key 16 times in a row, and then move to the
>next one, or did you run the entire table 16 times? It makes
>a difference to what's in cache.
The latter one, since I was emulating getting different keys out of
the blue.
>
>> 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.
>
>En/decrypt speed is orthogonal to the key schedule setup time - ie,
>it's irrelevent.
Right, I just stuck the numbers in since I had the timings.
>
>> 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.
>
>It would help a lot if you had included your timing code, so people
>can figure out just what's being tested. I'm not flaming you! It's
>just that it's really difficult to understand the meaning of your
>reported speeds without it.
>
OK. Here it is below.
- Alex
>>>>>>>>>>>>>>>>>>>>>> CUT HERE <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <time.h>
#include <sys/timeb.h>
#define _FASTDES_C_
#include "fastdes.h"
static void get8 (unsigned char *);
static void put8 (unsigned char *);
static unsigned int selfTest(void);
#define MAX_LOOPS2 0x100
#define MAX_TEST_BUFFER_LENGTH (0x100000)
#define MAX_LOOPS 0x10
#define MAX_KEYS 0x10000
#define MAX_KEY_BUFFER_LENGTH (8*MAX_KEYS)
main()
{
unsigned char key[8],plain[8],cipher[8],work[8],result[8];
int test;
int fail;
static unsigned long kne[16][2],knd[16][2];
time_t ltime1, ltime2, ltime3;
unsigned int q=0, r=0;
unsigned __int8 *pTestBuffer;
unsigned __int8 *pKeyBuffer;
printf("\n\tRIVEST TEST:");
if (selfTest()!=0)
printf("\n\t*****> FAILS <*****");
else
printf("\n\t*****> OK <*****");
printf("\n");
/*
for(test=0;!feof(stdin);test++){
fail = 0;
get8(key);
printf(" K: "); put8(key);
deskey(kne,key,0);
deskey(knd,key,1);
get8(plain);
printf(" P: "); put8(plain);
get8(cipher);
printf(" C: "); put8(cipher);
memcpy(work,plain,8);
des(kne,work,result);
if(memcmp(result,cipher,8) !=0){
printf(" Encrypt FAIL");
printf(" c: "); put8(result);
fail++;
}
des(knd,result,work);
if(memcmp(work,plain,8) != 0){
printf(" Decrypt FAIL");
printf(" p: "); put8(work);
fail++;
}
if(fail == 0)
printf(" OK");
printf("\n");
}
*/
printf("\n setup timing.");
srand(0x3985058);
// timing tests
pTestBuffer = (unsigned __int8 *) malloc(MAX_TEST_BUFFER_LENGTH);
for (q=0;q<MAX_TEST_BUFFER_LENGTH;q++)
pTestBuffer[q]=rand();
pKeyBuffer = (unsigned __int8 *) malloc(MAX_KEY_BUFFER_LENGTH);
for (q=0;q<MAX_KEY_BUFFER_LENGTH;q++)
pKeyBuffer[q]=rand();
printf("\n start key timing.");
time( <ime1 );
for (q=0;q<MAX_LOOPS;q++) {
for (r=0;r<MAX_KEYS;r++) {
deskey(kne,&pKeyBuffer[r*8],0);
// deskey(knd,&pKeyBuffer[r*8],1);
};
};
time( <ime2 );
ltime3 = (ltime2 - ltime1);
printf("\nfast DES key setup");
printf("\n%ld secs = %ld keys ", ltime3, q*r);
/*
printf("\n start block cipher timing.");
deskey(kne,&pKeyBuffer[0],0);
time( <ime1 );
for (q=0;q<MAX_LOOPS2;q++) {
for (r=0;r<(MAX_TEST_BUFFER_LENGTH/8);r++) {
des(kne,&pTestBuffer[r*8],result);
};
};
time( <ime2 );
ltime3 = (ltime2 - ltime1);
printf("\nfast DES enciphering");
printf("\n%ld secs = %ld bytes ", ltime3, q*MAX_TEST_BUFFER_LENGTH);
*/
free(pTestBuffer);
free(pKeyBuffer);
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=0;i<8;i++){
printf("%02x",*cp++ & 0xff);
}
}
// Field maintenance check of underlying DES algorithm...
unsigned int selfTest()
{
register unsigned int q=0;
unsigned __int64 X[17];
DES_KS keySchedEncrypt;
DES_KS keySchedDecrypt;
X[0] = 0x7DCA3BC7E8B87494;
for (q=0;q<16;q++) {
if (q%2==0) {
deskey(keySchedEncrypt, (unsigned char *) &X[q], 0);
des(keySchedEncrypt, (unsigned char *) &X[q], (unsigned char *)
&X[q+1]); // FROM --> TO
}
else {
deskey(keySchedDecrypt, (unsigned char *) &X[q], 1);
des(keySchedDecrypt, (unsigned char *) &X[q], (unsigned char *)
&X[q+1]); // FROM --> TO
};
};
if (X[16]!=0x3824644CDB2D1A1B)
return (unsigned int) (-1);
return 0;
};
--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