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

So it sounds like you've already narrowed it down to the shared_secret_key function. If you can give us a sample input, the desired output, and the current output to this function maybe someone will be able to spot the problem. That is, I bet you can reduce thes 180 lines to about 15 lines that demonstrate the problem.

David

Looks like good old-fashioned round-off and/or overflow error. I changed things to integer types and got rid of the pow, ceil, and abs calls and they match.

/**********************************************************
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(int pn, int gn, int s_key)
{
/*    int64_t exp = ceil(pow(gn,s_key));
    int64_t pub_key = abs(exp % pn);*/
    int i;
    int pub_key = 1;
    for(i = 0; i < s_key; i++)
    {
          pub_key = (pub_key * gn) % pn;
    }
    
    return pub_key;
}
/***********************************************************
Diffie–Hellman ~ Compute shared secret key
***********************************************************/
int shared_secret_key(int pn, int s_key, int pub_key)
{
/*    int64_t exp = ceil(pow(pub_key,s_key));
    int64_t shared_secret_key = abs(exp % pn);*/
    int i;
    int shared_secret_key = 1;
    for(i = 0; i < s_key; i++)
    {
          shared_secret_key = (shared_secret_key * pub_key) % 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);
    int p_number = 1039;//Static prime number
    cout << "Random Prime Number is:: " << p_number << endl;
    int g_base = 5;//public [base number should set to 2 or 5]

    /**
    Create alice a public key
    */
    int 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
    */
    int 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
    */
    int 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
    */
    int 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
    */
    getchar();
    return 0;
}

Hi

Many thanks for your contributions & in particular to VernonDozier, your amendments to the code have solved the problem & now it returns the correct values, Thanks.

Best Regards
Steve

Dear Friends,
I am Anes, Saw your post and program in URL : Diffie–Hellman key exchange algorithm, can't find bug in program. I got the answer , but my doubt is

  1. how u can say the value of 'g' should be 5. [line number : 151 (int g_base = 5;//public [base number should set to 2 or 5] ]

  2. The selection of secret for Alice (6) and Bob (15) , what the criteria of it ?

Please reply me with your answer ....

Waiting your reply asap .

Thanks
Anes

Edited 2 Years Ago by logicslab: To remove email id

This question has already been answered. Start a new discussion instead.