Crypto-IT

• without authentication

The Diffie-Hellman Algorithm is one of the most popular key-agreement algorithms. It is used by many protocols, including SSL/TLS. It is considered to be slightly faster than RSA, which can be used for the same purpose.

The Diffie-Hellman Protocol may be also used for message encryption using the public key.

The algorithm was first published by the American cryptographers Whitfield Diffie and Martin Hellman in 1976. However, it was revealed that the cipher had been discovered even earlier, by the British intelligence agency (James H. Ellis, Clifford Cocks, and Malcolm J. Williamson) but remained undisclosed.

The Diffie-Hellman algorithm describes a way of communication between two parties which allows to create a shared secret key. The key may be later use during the further communication, protected by the symmetric encryption. It is impossible to deduce the key by a potential eavesdropper.

The algorithm uses mathematical theory about discrete logarithms in given groups.

The protocol of the exchange of information between two parties (commonly referred to as Alice and Bob) is presented below. To determine the shared secret key using the Diffie-Hellman protocol, the following steps should be performed:

1. Alice and Bob agree on a common prime number p and a generating element g.
2. Alice picks a random and secret natural number a and then sends A = g^a mod p to Bob.
3. Bob picks a random and secret natural number b and then sends B = g^b mod p to Alice.
4. Alice computes a number k = B^a mod p.
5. Bob computes the same number k = A^b mod p.
6. At this point, both Alice and Bob possess the secret number k.

The number k computed by both parties is very big - the numbers a and b used in the algorithm have at least 100 digits and the prime number p has at least 300 digits. The value k can be changed into the symmetric key using a hash function. The symmetric key is used for the encryption of further communication.

It is possible to use the Diffie-Hellman protocol for message encryption using the public and private keys.

In such a case, Bob could send a message to Alice, encrypting it with Alice's public key, which contains three numbers: g, p, g^a mod p. To send a secret message to Alice, Bob chooses a random number b, and then sends an unencrypted number g^b mod p to Alice. Eventually, the message itself can be sent, being encrypted by a symmetric key (g^a)^b mod p.

Only Alice will be able to determine the value of b and decrypt the message. Using the public key protects the sides from man-in-the-middle attacks.

The algorithm allows asymmetric encryption of data. As present however, RSA is much more popular algorithm that allows encryption using public and private keys.

The protocol is considered secure if the initial numbers are chosen properly. The numbers have to be random and very big. The attacker would have to solve the discrete logarithm problem in a given group (it means that all mathematical operations are followed by reduction modulo another big number). However, no efficient general algorithm for computing discrete logarithms on conventional computers is known.

After establishing the symmetric key, both parties destroy the values a and b. This prevents the initial numbers from being stolen by the intruder.

Because the protocol does not provide authentication of the communicating parties, it is vulnerable to man-in-the-middle attacks. The attacker may establish two sessions of the protocol (one with Alice and one with Bob) and pretend to be the opposite side to each of them. He sets two symmetric keys and uses them in the communication with them (still pretending to be the opposite side to each of them).

Raising a number to the power modulo a prime number is one of the most important operations in modern cryptography. It is described by the general laws of numbers manipulation in modulo arithmetic. Both the base and the exponent are positive integers. The result is also a natural number.

The operation of raising a number to the power modulo a prime number may be presented as a sequence of operations which consist of raising to the square and then dividing modulo the prime number all the subsequent results.

For example, raising 4 to the power of 9 modulo 7 can be calculated in the following way:
    4⁹ mod 7:
    4² mod 7 = 16 mod 7 = 2
    4⁴ mod 7 = 2² mod 7 = 4 mod 7 = 4
    4⁸ mod 7 = 4² mod 7 = 16 mod 7 = 2
    4⁹ mod 7 = (4¹ mod 7 * 4⁸ mod 7) mod 7 = 4 * 2 mod 7 = 1