davejingtian.org

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;
}