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

}

Wow. I worked a lot with DH this semester for my security class. But didn’t implemented it. (g^a mod p )^b= g^(ab) mod p, (g^b mod p )^a= g^(ab) mod p, so smart 🙂

Yes, lady, on the other hand, mod operation may be one of the most important in number theory. I bet u r that smart 2:)