Hi
I've written this small program to demonstrate the Diffie–Hellman key exchange algorithm. The desired output from the program is for most runs correct.
However occasionally there are some discrepancies in output of the shared secret keys values in that they don't match, when they should.
I've found that certain prime numbers cause this behaviour one being the value 1039. I've done the
calculation by hand & found the problem seems to be in the shared_secret_key function when it calculates Bob's shared_secret_key.
I was wondering if any of you guy's could spot the problem/s?
Many thanks in advance.
programs output...
Random Prime Number is:: 1039
Alice's public key = 40
Bobs's public key = 512
Alice's shared secret key = 66
Bob's shared secret key = 544//wrong value
desired output...
Random Prime Number is:: 1039
Alice's public key = 40
Bobs's public key = 512
Alice's shared secret key = 66
Bob's shared secret key = 66//correct value/**********************************************************
Diffie–Hellman key exchange algorithm
-------------------------------------
This program demonstrates the Diffie-Hellman exchange key
algorithm
Tips to improve security
-------------------------
[1] Pseudo random number generator[Prime Number] should be
changed to a true random source
Ref::http://www.random.org/
[2] An Arbitrary-precision arithmetic library should be used
to increase the [Prime number] key strength to 1024 bits
Ref::http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic
Diffie–Hellman key exchange process,this is what the program is suppose to do
-----------------------------------------------------------------------------
[1.]Alice and Bob agree to use a prime number p=23 and base g=5.
[2.]Alice chooses a secret integer a=6, then sends Bob A = ga mod p
A = 56 mod 23
A = 8
[3.]Bob chooses a secret integer b=15, then sends Alice B = gb mod p
B = 515 mod 23
B = 19
[4.]Alice computes s = B a mod p
s = 196 mod 23
s = 2
[5]Bob computes s = A b mod p
s = 815 mod 23
s = 2
Ref::http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange
***********************************************************/
#include <iostream>
#include <math.h>
#include <cstdlib>
#include <ctime>
using namespace std;
/***********************************************************
Check to see if a valid prime number
***********************************************************/
int64_t is_prime(int64_t _iVal)
{
char bPrime;
bPrime = true;
for (int ii(2); ii < _iVal / 2; ii++)
{
if (!(_iVal % ii)){
bPrime = false;
break;
}
}
return bPrime;
}
/***********************************************************
Get random prime number
***********************************************************/
int64_t get_prime_number(int64_t MAX)
{
int64_t rPrime;
char result;
srand ( time(NULL) );
while (1)/** Until we get valid prime number */
{
/**
Randomize a number
*/
rPrime = rand() % MAX + 1;
/**
Deal with the Even Number returned
*/
if ( rPrime % 2 == 0 ){
/**
Let's not waste this number change
it to a ODD value by adding 1 & check
if prime number
*/
rPrime = rPrime + 1;
/**
Check if prime number
*/
result = is_prime(rPrime);
if(result == true){
break;
}
/**
Deal with the Odd Number returned
*/
}else{
/**
Check if prime number
*/
result = is_prime(rPrime);
if(result == true){
break;
}
}
}
return rPrime;
}
/***********************************************************
Diffie–Hellman ~ Create public key
***********************************************************/
int create_public_key(int64_t pn, int64_t gn, int64_t s_key)
{
int64_t exp = ceil(pow(gn,s_key));
int64_t pub_key = abs(exp % pn);
return pub_key;
}
/***********************************************************
Diffie–Hellman ~ Compute shared secret key
***********************************************************/
int shared_secret_key(int64_t pn, int64_t s_key, int64_t pub_key)
{
int64_t exp = ceil(pow(pub_key,s_key));
int64_t shared_secret_key = abs(exp % pn);
return shared_secret_key;
}
/***********************************************************
Main Program
***********************************************************/
int main()
{
/**
Get a random prime number & set g_base to 2 or 5
*/
//int p_number = get_prime_number(99999999);
int64_t p_number = 1039;//Static prime number
cout << "Random Prime Number is:: " << p_number << endl;
int64_t g_base = 5;//public [base number should set to 2 or 5]
/**
Create alice a public key
*/
int64_t alice_pub_key = create_public_key(p_number, g_base, 6/*secret_key*/);
cout << "Alice's public key = " << alice_pub_key << endl;
/**
Alice sends bob Public values p = p_number, g = g_base, A = alice_pub_key
*/
/**
Create bob a public key
*/
int64_t bob_pub_key = create_public_key(p_number, g_base, 15/*secret_key*/);
cout << "Bobs's public key = " << bob_pub_key << endl;
/**
Bob sends Alice his Public value B = bob_pub_key
*/
/**
Compute Alice's shared secret key
*/
int64_t alice_secret_key = shared_secret_key(p_number, 6/*secret_key*/, bob_pub_key);
cout << "Alice's shared secret key = " << alice_secret_key << endl;
/**
Compute Bob's shared secret key
*/
int64_t bob_secret_key = shared_secret_key(p_number, 15/*secret_key*/, alice_pub_key);
cout << "Bob's shared secret key = " << bob_secret_key << endl;
/**
NOTE
----
Both Alice & Bob shared secret keys should match if the program
has done it's job properly
*/
return 0;
}
