Implementation of Diffie-Hellman Algorithm of Key Exchange

The article is devoted to the development of the library that implements the Diffie – Hellman cryptographic algorithm of key exchange. The library appeared as a result of the necessity to use the Diffie – Hellman algorithm without the involvement of any third-party libraries.

1. Diffie – Hellman algorithm of key exchange

1.1 Description of the algorithm

Diffie – Hellman algorithm is an algorithm that allows two parties to get the shared secret key using the communication channel, which is not protected from the interception but is protected from modification.

Diffie – Hellman algorithm is extremely simple in its idea and with it has rather high level of cryptographic stability, which is based on the supposed complexity of the discrete problem of taking the logarithm.

Supposing there are two participants of the exchange (let’s call them Alice and Bob, as it is traditionally established in cryptography). Both of them know two numbers P and G. These numbers are not secret and can be known to anyone. The goal of Alice and Bob is to obtain the shared secret key to help them to exchange messages in future.

For this, they generate two big random numbers (so called private keys): Alice –  number Xa, Bob – number Xb. After this, Alice computes the value of the public key:

Ya=(G^Xa) mod P

and sends it to Bob.

In his turn, Bob computes the value of his public key:

Yb=(G^Xb) mod P

and sends it to Alice.

At the second stage, on the basis of her private key and the public key, received from Bob, Alice computes the value

Ka=(Yb^Xa) mod P

Similarly, Bob computes the value

Kb=(Ya^Xb) mod P.

Numbers Ka and Kb are equal because

Ka = (Yb^Xa) mod P = (((G^Xb) mod P)^Xa) mod P = (G^XaXb) mod P =
= (((G^Xa) mod P)^Xb) mod P = (Ya^Xb) mod P = Kb.

and they can be used as the secret key by Alice and Bob. In practical implementations, numbers of 10^100 order are used for Xa and Xb, for P – 10^300. The G number often has the value in the range of the first ten.

1.2 Brief survey of some existing implementations

There are many cryptographic libraries that include the Diffie – Hellman algorithm. But we cannot always afford to use the whole third-party library. Using the Windows Crypto API functions can be the alternative. But there are also pitfalls here. For security purposes, Windows Crypto API doesn’t allow to receive the computed private key in its pure form, but only some program entity, which can be used for the organizing of message encryption with the help of this key. Often it is enough but there are situations when before the usage of the computed secret key it is necessary to perform some operations with it, which are not supported by Windows Crypto API, or to use this key as the secret key for your own algorithm of data encryption. I faced just this very situation.

2. C++ library, which implements the algorithm

2.1 Class ULong of long integer with the arbitrary dimension

As Diffie – Hellman algorithm is very simple but operates with very big numbers. Thus the main complexity for its implementation is the creation of the entity, which can perform arithmetical operations over these big numbers.

For this purpose, the template class ULong was created

template<size_t Dimension> class ULong
            {
                   ...
private:
                char m_InternalBuffer[Dimension];
            };

It receives a number of bytes that are allocated for the storage of the number as a parameter of the pattern.. The class implements all simple arithmetical operations, which are intrinsic for the standard unsigned int.

It is worth considering the internal representation of a number in the memory. It is analogous to the standard representation of integers.

For example, the number

0x6578906578997781821055

will be represented in the internal buffer of the ULong class in the following form:

0x55 0x10 0x82 0x81 0x77 0x99 0x78 0x65 0x90 0x78 0x65

Let’s consider the examples of  the usage of the ULong class:

ULong<16> number1(123);
const char buff[16] = {0x01, 0x45, 0x76, 0x87, 
                       0x99, 0x12, 0x11, 0x90, 
                       0x65, 0x65, 0x33, 0x17, 
                       0x82, 0x50, 0x71, 0x03};
ULong<16> number2(buff, 16);
ULong<16> result = (number1 + number2) * number1;

2.2 Implementation of Diffie – Hellman algorithm

For the implementation of Diffie – Hellman algorithm itself, the DiffieHellmanKeysExchanger classwas developed:

template<size_t PModuleLength> class DiffieHellmanKeysExchanger
{
    public:
       DiffieHellmanKeysExchanger(const std::vector<char> cryptoPModule, unsigned long cryptoGModule)
    {
               ...
    }
      bool GenerateExchangeData(std::vector<char>& externalData)
    {
           ...
    }
      bool CompleteExchangeData(const std::vector<char>& externalData, std::vector<char>& sharedKey)
    {
    }
      ...
};

The GenerateExchangeData function generates the public key, which is sent to the second party. The latter, in its turn, can generate its own public key and send it to the first party. Having received this key, the first party can compute the shared secret key with the help of CompleteExchangeData function. By analogy, the second party can compute the same secret key, whereupon both parties can exchange messages that were encrypted with its help.

For the generation of random numbers Xa and Xb , the CryptAcquireContext and CryptGenRandom functions from Windows Crypto API are used:

bool GenerateRandomX(std::vector<char>& xBuff)
{
    HCRYPTPROV provider;
    if (!CryptAcquireContext(&provider, NULL, NULL, PROV_RSA_FULL, NULL))
    {
        if (!CryptAcquireContext(&provider, NULL, NULL, PROV_RSA_FULL, CRYPT_NEWKEYSET))
        {
            return false;
        }
    }
      xBuff.clear();
    xBuff.resize(PModuleLength);
    if (!CryptGenRandom(provider, PModuleLength / 4, (BYTE*)&xBuff.front()))
    {
        return false;
    }
    return true;
}

2.3 Illustration of library usage with an example

The DiffieHellmanKeysExchanger class is simple in its usage and can be integrated as follows:

const size_t PModuleLength = 32;

The binary representation of P number:

unsigned char buffer[PModuleLength] = {0xEE, 0x38, 0x6B, 0xFB, 
                                       0x5A, 0x89, 0x9F, 0xA5, 
                                       0xAE, 0x9F, 0x24, 0x11, 
                                       0x7C, 0x4B, 0x1F, 0xE6,
                                       0x49, 0x28, 0x66, 0x51, 
                                       0xEC, 0xE6, 0x53, 0x81, 
                                       0xFF, 0xFF, 0xFF, 0xFF, 
                                       0xFF, 0xFF, 0xFF, 0xFF
                                      };

In the hexidecimal record, this number looks like:

0xFFFFFFFFFFFFFFFF8153E6EC51662849E61F4B7C11249FAEA59F895AFB6B38EE

Let’s take the G number equal to 2:

unsigned long cryptoGModule = 0x02;

We create objects of the DiffieHellmanKeysExchanger class for Alice and Bob:

DiffieHellmanLib::DiffieHellmanKeysExchanger<PModuleLength> aliceExchanger(cryptoPModule, cryptoGModule);
DiffieHellmanLib::DiffieHellmanKeysExchanger<PModuleLength> bobExchanger(cryptoPModule, cryptoGModule);

We generate public keys for the exchange between Alice and Bob:

std::vector<char> aliceExchangeKey;
aliceExchanger.GenerateExchangeData(aliceExchangeKey);
std::vector<char> bobExchangeKey;
bobExchanger.GenerateExchangeData(bobExchangeKey);

We compute the shared secret key for both parties:

std::vector<char> aliceSharedKey;
aliceExchanger.CompleteExchangeData(bobExchangeKey, aliceSharedKey);
std::vector<char> bobSharedKey;
bobExchanger.CompleteExchangeData(aliceExchangeKey, bobSharedKey);

Let’s consider the result of the program execution:

As it can be seen on the screenshot, the generation of the shared secret key completed successfully, the secret keys of both parties coincided.

3. Structure of project files

src\DiffieHellman.sln – solution file for Microsoft Visual Studio 2008.
src\DiffieHellmanLib – library, which contains the implementation of Diffie – Hellman algorithm.
src\Test – an example of the usage of DiffieHellmanLib library.

Downloads

Source files – ZIP (10 KB)