Diffie-Hellman Algorithm Implementation

The Diffie-Hellman Algorithm is a secure way of cryptographic keys exchange across a public channel. It was among the very first public-key protocols. Ralph Merkle came up with the Diffie-hellman key exchange and it was named after Whitfield Diffie and Martin Hellman. Within the fields of cryptography, DH (Diffie-Hellman) is the earliest example of public key exchange. This was the first publicly known work that put forward the idea of a corresponding pair of public and private keys.

Generally, between two parties, secure encrypted communication requires that they exchange keys through some physical and safe means, such as paper key lists that are transported by a trusted as well as protected courier. The DH key exchange method enables the 2 parties who possess zero knowledge of each other to together set up a shared secret over an insecure (public) channel. Using a symmetric-key cipher, the communication can be then encrypted using this key.

Introduction

For exchanging data in secret communication across a public domain, Diffie–Hellman key exchange establishes a secret that is shared between the two parties. Diffie-Hellman is used in creating several Internet-related services. Still, the October 2015 published research suggests that in Diffie-Hellman applications, the parameters used at that time were not sufficiently strong to protect from attackers who are well-funded, like the agents of security services of some countries. However, the DH key agreement is a non-authentication key-agreement protocol, it provides the basis for a variety of authenticated protocols and is used to give forward secrecy in transport layer Security’s ephemeral modes.

Diffie–Hellman Algorithm

Description of the Algorithm

ECC (Elliptic Curve Cryptography) is an address to public-key cryptography. It is based on the algebraic structure of elliptical curves over finite fields. Elliptic Curve Cryptography needs a small key when compared to non-Elliptic Curve Cryptography to provide equivalent security (a 256-bit ECC security is equal to 3072-bit RSA cryptography). The Diffie-Hellman is used to set up a shared secret that can be used for secret communication while exchanging data across a public channel using this elliptic curve to produce points and use the parameters to obtain the secret key.

Step by Step Explanation

For a practical as well as simple implementation of the algorithm, let us take into consideration 4 variables, a prime number P, and Q – a primitive root of P (if for a prime number n, the primitive root of n will be r and it will lie within range [1,n-1] such that all the values of $r^x(modn)$, where x lies within the range [0,n-2] are all different), and a and b which are private values. P as well as G both are numbers available in public. Users (let us assume Joy and Happy) pick private values b and a create a key and publicly exchange it. The other individual receives the key, and a secret key is created. Now both persons possess the same key that can be used for encryption.

The Generated Keys are Exchanged

It Can Be Proven Algebraically That

k_a = k_b
Users now have a symmetric secret key to encrypt

Example

• Joy and Happy obtain P = 23 and G=9 public numbers respectively.
• Joy and Happy select private keys a=4 and b=3 respectively.
• Joy and Happy calculated public values
  Joy: x =($9^4$ % 23) = (6561 % 23) = 6.
  Happy: y = ($9^3$ % 23) = (729 % 23) = 16.
• Joy and Happy exchanged public numbers
• Joy and Happy get public keys y=16 and x=6 respectively.
• Joy and Happy calculate symmetric keys
  Joy: ka = $y^a$ % p = 65536 % 23 = 9
  Happy: kb = $x^b$ % p = 216 % 23 = 9
• 9 is the secret shared.

Implementation

Java Code

class Main {

    // func is a function used to return calculated value of ((a ^ b) mod P)
    private static long func(long a1, long a2, long x)
    {
        if (a1 == 1)
            return a1;
        else
            return (((long)Math.pow(a1, a2)) % x);
    }

    // Main Code
    public static void main(String[] args)
    {
        long Ps, Gs, p, g, q, h, K_A, K_B;

        // Both persons agrees on public keys Gs and Ps

        // A prime number Ps
        Ps = 23;
        System.out.println("Value of Ps is: " + Ps);

        // Gs is primitive root for Ps
        Gs = 9;
        System.out.println("Value of Gs is: " + Gs);

        // g is the private key chosen by Joy
        // The chosen private key is g
        g = 4;
        System.out.println("Private key g is: " + g);

        // fetches the generated key
        p = func(Gs, g, Ps);

        // h will be the chosen private key by Happy
        // The chosen private key is h   
        h = 3;
        System.out.println("Private key h is: " + h);

        // fetches the generated key
        q = func(Gs, h, Ps);

        // After the exchange of keys, generating the secret key
        K_A = func(q, g, Ps); // Joy's Secret key
        K_B = func(p, h, Ps); // Happy's Secret key

        System.out.println("Joy's Secret key is: " + K_A);
        System.out.println("Happy's Secret key is: " + K_B);
    }
}

Python Code

from random import randint

if __name__ == '__main__':

    # Both persons agrees on public keys Gs and Ps
    # Prime number P
    Ps = 23

    # Gs is primitive root for Ps
    Gs = 9


    print('Value of Ps is : %d'%(Ps))
    print('Value of Gs is : %d'%(Gs))

    # g is the private key chosen by Joy
    g = 4
    print('Private Key g is: %d'%(g))

    # fetches the generated key
    p = int(pow(Gs,g,Ps)) 

    # h will be the chosen private key by Happy
    h = 3
    print('Private Key h is : %d'%(h))

    # fetches the generated key
    q = int(pow(Gs,h,Ps)) 


    # Joy's Secret key
    K_A = int(pow(q,g,Ps))

    #  Happy's Secret key
    K_B = int(pow(p,h,Ps))

    print('Joy\'s Secret key is : %d'%(K_A))
    print('Happy\'s Secret key is : %d'%(K_B))

C++ Code

#include <cmath>
#include <iostream>
using namespace std;

// func is a function used to return calculated value of ((a ^ b) mod P)
long long int func(long long int g, long long int h,
                    long long int Ps)
{
    if (h == 1)
        return g;

    else
        return (((long long int)pow(g, h)) % Ps);
}

//Main Code
int main()
{
    long long int Ps, Gs, p, g, q, h, K_A, K_B;

    // Both persons agrees on public keys Gs and Ps
    Ps = 23; // A prime number Ps
    cout << "Value of Ps is: " << Ps << endl;

    Gs = 9; // Gs is primitive root for Ps
    cout << "Value of Gs is: " << Gs << endl;

    // g is the private key chosen by Joy
    g = 4; // The chosen private key is g
    cout << "Private key g is: " << g << endl;

    p = func(Gs, g, Ps); // fetches the generated key

    // h will be the chosen private key by Happy
    h = 3; // The chosen private key is h
    cout << "Private key h is: " << h << endl;

    q = func(Gs, h, Ps); // fetches the generated key

    // After the exchange of keys, generating the secret key
    K_A = func(q, g, Ps); // Joy's Secret key
    K_B = func(p, h, Ps); // Happy's Secret key
    cout << "Joy's Secret key is: " << K_A << endl;

    cout << "Happy's Secret key is: " << K_B << endl;

    return 0;
}

Output

Value of Ps is: 23
Value of Gs is: 9
Private key g is: 4
Private key h is: 3
Joy's Secret key is: 9
Happy's Secret key is: 9

Other Uses

Encryption

A Diffie-Hellman key exchange-based public key encryption scheme has been proposed. ElGamal encryption is the first such scheme. Integrated Encryption Scheme is another modern variant.

Forward Secrecy

Protocols that attain forward secrecy create new key pairs for each session and cancel them at the end of the session. For such protocols, the Diffie-Hellman key exchange is a good choice because of its fast key generation.

Password-Authenticated Key Agreement

When Joy and Happy share a password, they may use DH’s password-authenticated key agreement to avoid man-in-the-middle attacks. A simple scheme is to compare the password calculated with the hash of s (where ‘s’ is the shared secret) concatenated independently on both ends of the channel. A feature of these schemes is that an attacker at each specific iteration can test only one specific password with the other party, and thus the system gives good security with weak passwords. In ITU-T recommendation X.1035, this approach is described which is used by the G.hn home networking standard.

Secure Remote Password protocol is an example of such a protocol.

Conclusion

• The Diffie-Hellman Algorithm is a secure way of cryptographic keys exchange across a public channel.
• The DH key exchange method allows the two parties that have zero knowledge of each other to set up a shared secret over an insecure (public) channel.
• For exchanging data in secret communication across a public channel domain, Diffie–Hellman key exchange establishes a shared secret between the two parties.
• Diffie-Hellman is used in creating a variety of Internet services.
• DH key agreement is a non-authentication key-agreement protocol, it forms the foundation for many authenticated protocols and is used in transport layer Security’s ephemeral modes to provide forward secrecy.
• ECC (Elliptic Curve Cryptography) is an address to public-key cryptography. It is based on the algebraic structure of elliptical curves over finite fields.
• The Diffie-Hellman is used to set up a shared secret that can be used for secret communication while exchanging data across a public channel using this elliptic curve to generate points and get the secret key using the parameters.
• A Diffie-Hellman key exchange-based public key encryption scheme has been proposed. ElGamal encryption is the first such scheme. Integrated Encryption Scheme is another modern variant.
• Protocols that attain forward secrecy crate new key pairs for each session and cancel them at the end of the session. For such protocols, the Diffie-Hellman key exchange is a good choice because of its fast key generation.
• A simple scheme is to compare the password calculated with the hash of s (where ‘s’ is the shared secret) concatenated independently on both ends of the channel. A feature of these schemes is that an attacker at each specific iteration can test only one specific password with the other party, and thus the system gives good security with weak passwords.