I am recently doing feature on authentication between MGC (Media Gateway Controller) and MG (Media Gateway). One important thing involved in Diffie-Hellman key exchange. Not sure if because the key formula ‘g^a mod(P)’ looks simple and stupid, it is hard for me to find any real, useful and practical code implementation for this (maybe it is a piece of cake for anybody else:) Anyway, I have implemented 2 different functions below for DH algorithm using C. May it help!

/*
* dh.c
* Example source file for D-H algorithm in key exchange
* Example fields: IPsec, MG<->MGC authentication
* Example usage: ./dh 10000 8888 523
* dhKey = g^a mod(p)
*      g – unsigned long, like 2-4294967295
*      a – unsigned int, like 2-65535
*      p – unsigned int, prime number, like 2-65535
* Build cmd: gcc -o dh -lm dh.c
* Input sequence: g a p
* 2011/04/20
* dave.tian@alcatel-lucentc.om
* 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 dh2( unsigned long, unsigned int, unsigned int);

int main( int argc, char **argv)
{
if ( argc != 4)
{
printf(“Errorn”);
return 1;
}

// Get the input from cli
unsigned long g = strtoul( argv[ 1], NULL, 10);
unsigned int a = strtoul( argv[ 2], NULL, 10);
unsigned int p = strtoul( argv[ 3], NULL, 10);
printf(“g = %luna = %unp = %un”, g, a, p);

// Check if p is a prime number
// C++ may have a function called isPrime? – not sure of that:)
unsigned int i = 0;
unsigned int r = (unsigned int)sqrt( p);
for( i = 2; i <= r; i++)
{
if ( p%i == 0)
{
printf(“‘p’ is not a prime: %un”, p);
return 1;
}
}

// D-H algorithm: g^a mod(p);
// Time measurement could be added here to compare
// the different performance between the 2 implementations
// However, memory consideration comparison is missed here
// between the 2 functions…Personally I assume recurrsion
// function should consume more dynamic memory because of
// large number of stacks, which may cause memory overflow.

unsigned long dhKey = 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 );
dhKey = dh1( g, a, p);
time_end = times( &time_buf_end );
printf(“dh1(), 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(“dh1 = %lun”, dhKey);

time_head = times( &time_buf_head );
dhKey = dh2( g, a, p);
time_end = times( &time_buf_end );
printf(“dh2(), 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(“dh2 = %lun”, dhKey);

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
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 dh2( 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
if ( a == 0)
{
printf(“Errorn”);
return 0;
}

unsigned long z = g%p;
if ( a == 1)
{
return z;
}

unsigned int idx = 0;
unsigned long tmp = z;
for ( idx = 2; idx <= a; idx++)
{
tmp = (tmp*z)%p;
}

return tmp;
}