In my last post on D-H algorithm (http://daveti.blog.com/2011/04/21/diffiehellman-key-exchange-dh-algorithm-in-c/), we talked about 2 implementation using C. However, I’ve been thinking about one thing here these days – if there is any potential integer overflow risk in both functions (though for unsigned value, there is ‘over’ but no ‘flow’ indeed). Clearly, it would be perfect if a complete mathematic induction and deduction with formulas could be provided for D-H algorithm to find out the max value. But that is not the point here – we are going thru all the possible inputs given the certain ranges and rewrite a new dh4 function with better performance and integer overflow detection. We may need another post to talk about integer overflow with details. Anyway, check it out:)
/*
* dh4.c
* Example source file for D-H algorithm in key exchange
* Deeper into potential integer overflow detection
* Example fields: IPsec, MG<->MGC authentication
* Example usage: ./dh
* dhKey = g^a mod(p)
* g – unsigned long, like 2-4294967295(0xffffffff)
* a – unsigned int, like 2-65535(0xffff)
* p – unsigned int, prime number, like 2-65535
* Destination: we will going thru all the possible values
* for g, a and p and try to figure out if there is potential
* integer overflow using dh2 implementation.
* Build cmd: gcc -o dh -lm dh.c
* 2011/04/28
* dave.tian@alcatel-lucent.com
* http://daveti.blog.com
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/times.h>
#include <unistd.h>
unsigned long dh1( unsigned long, unsigned int, unsigned int);
unsigned long dh4( unsigned long, unsigned int, unsigned int);
int main( int argc, char **argv)
{
// g: 2~0xffffffff
// a: 2~0xffff
// p: 2~0xffff
// D-H algorithm: g^a mod(p);
unsigned long gIdx = 0;
unsigned int aIdx = 0;
unsigned int pIdx = 0;
unsigned int pRoot = 0;
unsigned int pRootIdx = 0;
unsigned long dhKey = 0;
int isPrime = 0;
// To accelerate the speed of the computation, it is good to
// find out all the possible prime numbers and store them in
// a array. Please note when the range of prime need to search
// is very large (much larger than 0~0xffff in our case). Stack
// size may not support this. Think about 2 ways here – either
// static data area or link structure with malloc allocation.
// daveti on 2011/04/28
unsigned int primeArray[ 0xffff] = {0};
unsigned int primeTotal = 0;
unsigned int arrayIdx = 0;
struct tms time_buf_head, time_buf_end;
clock_t time_head, time_end;
long tck = sysconf (_SC_CLK_TCK);
time_head = times( &time_buf_head );
// Find the prime numbers first and store them
// Here we do not think 1 is a prime number!
for ( pIdx = 2; pIdx <= 0xffff; pIdx++)
{
isPrime = 1;
pRoot = (unsigned int)sqrt( pIdx);
for ( pRootIdx = 2; pRootIdx <= pRoot; pRootIdx++)
{
if ( pIdx%pRootIdx == 0)
{
// This is not a prime number!
isPrime = 0;
break;
}
}
if ( (isPrime == 1) && (arrayIdx < 0xffff))
{
// This is a prime number. Store it!
primeArray[ arrayIdx] = pIdx;
primeTotal++;
arrayIdx++;
}
}
time_end = times( &time_buf_end );
printf("Prime searching: user time: %f, sys time: %f, child user time: %f, child sys time: %fn",
((time_buf_end.tms_utime – time_buf_head.tms_utime) / (double)tck),
((time_buf_end.tms_stime – time_buf_head.tms_stime) / (double)tck),
((time_buf_end.tms_cutime – time_buf_head.tms_cutime) / (double)tck),
((time_buf_end.tms_cstime – time_buf_head.tms_cstime) / (double)tck) );
printf("Dump the first 10 prime numbers: ");
for ( arrayIdx = 0; arrayIdx < 10; arrayIdx++)
{
printf("%u, ", primeArray[ arrayIdx]);
}
printf("nPrime found in total: %un", primeTotal);
time_head = times( &time_buf_head );
for ( gIdx = 2; gIdx <= 0xffffffff; gIdx++)
{
for ( aIdx = 2; aIdx <= 0xffff; aIdx++)
{
for ( pIdx = 0; pIdx < primeTotal; pIdx++)
{
dhKey = dh4( gIdx, aIdx, primeArray[ pIdx]);
}
}
}
time_end = times( &time_buf_end );
printf("Loop: user time: %f, sys time: %f, child user time: %f, child sys time: %fn",
((time_buf_end.tms_utime – time_buf_head.tms_utime) / (double)tck),
((time_buf_end.tms_stime – time_buf_head.tms_stime) / (double)tck),
((time_buf_end.tms_cutime – time_buf_head.tms_cutime) / (double)tck),
((time_buf_end.tms_cstime – time_buf_head.tms_cstime) / (double)tck) );
return 0;
}
unsigned long dh1( unsigned long g, unsigned int a, unsigned int p)
{
// This is a recurssion version of D-H algorithm
// implemented by daveti on 2011/04/20
// Is there a way using C code to detect the potential
// integer overflow here? I do not think so. Assembly
// code may help here. Even if it does, the code is NOT
// portable anymore – CPU architecture specified.
// daveti on 2011/04/26
if ( a == 0)
{
printf("Errorn");
return 0;
}
if ( a == 1)
{
return g%p;
}
// (a*b)%c == ((a%c)*(b%c))%c
return ((g%p)*(dh1( g, a-1, p)))%p;
}
unsigned long dh4( unsigned long g, unsigned int a, unsigned int p)
{
// This is non-recurssion version of D-H algorithm
// implemented by daveti on 2011/04/21
// g^4%p = (g%p*((g%p*((g%p*(g%p))%p))%p))%p
// let z = g%p
// g^4%p = (z*((z*((z*z)%p))%p))%p
// = (((((z*z)%p)*z)%p)*z)%p
// What about this function – any way to detect potential
// integer overflow here? I think so:) Generally, we are
// going back to the old question – how do we detect potential
// integer overflow for ‘a+b’ and/or ‘a*b’…
// daveti on 2011/04/26
if ( a == 0)
{
printf("Errorn");
return 0;
}
unsigned long z = g%p;
// Check for possible zero value to fast the output
// and to avoid floating exception during devision
// computation in the overflow detection.
// daveti on 2011/04/27
if ( (a == 1) || (z == 0))
{
return z;
}
unsigned int idx = 0;
unsigned long tmp = z;
unsigned long overflow = 0;
for ( idx = 2; idx <= a; idx++)
{
// tmp = (tmp*z)%p;
// Add potential overflow detection for each loop
// Isn’t this method clever:)
overflow = tmp*z;
if ( overflow/tmp != z)
{
printf("Error: Integer overflow on ‘tmp*z’"
" – tmp=%lu, z=%lun", tmp, z);
return 0;
}
tmp = overflow%p;
}
return tmp;
}
davejingtian.org 