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.
Contents
- 1 DiffieโHellman algorithm of key exchange
- 1.1 Description of the algorithm
- 1.2 Brief survey of some existing implementations
- 2 C++ library, which implements the algorithm
- 2.1 Class
ULong
of long integer with the arbitrary dimension - 2.2 Implementation of Diffie โ Hellman algorithm
- 2.3 Illustration of library usage with an example
- 3 Structure of project files
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