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.

Joy | Happy |
---|---|

P and G are the public keys available | P and G are the public keys available |

a is the private key selected | b is the private key selected |

The created key: x = G^{a} mod P | The created key: y = G^{b} mod P |

### The Generated Keys are Exchanged

Joy | Happy |
---|---|

y is the key received | x is the key received |

The created key: k_{a} = y^{a} mod P | The created key: k_{b} = x^{b} mod P |

### 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.