Implementation of Diffie-Hellman Algorithm
Diffie-Hellman algorithm:
The Diffie-Hellman algorithm is being used to establish a shared secret that can be used for secret communications while exchanging data over a public network using the elliptic curve to generate points and get the secret key using the parameters.
- For the sake of simplicity and practical implementation of the algorithm, we will consider only 4 variables, one prime P and G (a primitive root of P) and two private values a and b.
- P and G are both publicly available numbers. Users (say Alice and Bob) pick private values a and b and they generate a key and exchange it publicly. The opposite person receives the key and that generates a secret key, after which they have the same secret key to encrypt.
Step-by-Step explanation is as follows:
Alice | Bob |
---|---|
Public Keys available = P, G | Public Keys available = P, G |
Private Key Selected = a | Private Key Selected = b |
Key generated = | Key generated = |
Exchange of generated keys takes place | |
Key received = y | key received = x |
Generated Secret Key = | Generated Secret Key = |
Algebraically, it can be shown that | |
Users now have a symmetric secret key to encrypt |
Example:
Step 1: Alice and Bob get public numbers P = 23, G = 9
Step 2: Alice selected a private key a = 4 and
Bob selected a private key b = 3
Step 3: Alice and Bob compute public values
Alice: x =(9^4 mod 23) = (6561 mod 23) = 6
Bob: y = (9^3 mod 23) = (729 mod 23) = 16
Step 4: Alice and Bob exchange public numbers
Step 5: Alice receives public key y =16 and
Bob receives public key x = 6
Step 6: Alice and Bob compute symmetric keys
Alice: ka = y^a mod p = 65536 mod 23 = 9
Bob: kb = x^b mod p = 216 mod 23 = 9
Step 7: 9 is the shared secret.
Implementation:
C++
/* This program calculates the Key for two persons using the Diffie-Hellman Key exchange algorithm using C++ */ #include <cmath> #include <iostream> using namespace std; // Power function to return value of a ^ b mod P long long int power( long long int a, long long int b, long long int P) { if (b == 1) return a; else return ((( long long int ) pow (a, b)) % P); } // Driver program int main() { long long int P, G, x, a, y, b, ka, kb; // Both the persons will be agreed upon the // public keys G and P P = 23; // A prime number P is taken cout << "The value of P : " << P << endl; G = 9; // A primitive root for P, G is taken cout << "The value of G : " << G << endl; // Alice will choose the private key a a = 4; // a is the chosen private key cout << "The private key a for Alice : " << a << endl; x = power(G, a, P); // gets the generated key // Bob will choose the private key b b = 3; // b is the chosen private key cout << "The private key b for Bob : " << b << endl; y = power(G, b, P); // gets the generated key // Generating the secret key after the exchange // of keys ka = power(y, a, P); // Secret key for Alice kb = power(x, b, P); // Secret key for Bob cout << "Secret key for the Alice is : " << ka << endl; cout << "Secret key for the Bob is : " << kb << endl; return 0; } // This code is contributed by Pranay Arora |
C
/* This program calculates the Key for two persons using the Diffie-Hellman Key exchange algorithm */ #include <math.h> #include <stdio.h> // Power function to return value of a ^ b mod P long long int power( long long int a, long long int b, long long int P) { if (b == 1) return a; else return ((( long long int ) pow (a, b)) % P); } // Driver program int main() { long long int P, G, x, a, y, b, ka, kb; // Both the persons will be agreed upon the // public keys G and P P = 23; // A prime number P is taken printf ( "The value of P : %lld\n" , P); G = 9; // A primitive root for P, G is taken printf ( "The value of G : %lld\n\n" , G); // Alice will choose the private key a a = 4; // a is the chosen private key printf ( "The private key a for Alice : %lld\n" , a); x = power(G, a, P); // gets the generated key // Bob will choose the private key b b = 3; // b is the chosen private key printf ( "The private key b for Bob : %lld\n\n" , b); y = power(G, b, P); // gets the generated key // Generating the secret key after the exchange // of keys ka = power(y, a, P); // Secret key for Alice kb = power(x, b, P); // Secret key for Bob printf ( "Secret key for the Alice is : %lld\n" , ka); printf ( "Secret Key for the Bob is : %lld\n" , kb); return 0; } |
Java
// This program calculates the Key for two persons // using the Diffie-Hellman Key exchange algorithm class GFG { // Power function to return value of a ^ b mod P private static long power( long a, long b, long p) { if (b == 1 ) return a; else return ((( long )Math.pow(a, b)) % p); } // Driver code public static void main(String[] args) { long P, G, x, a, y, b, ka, kb; // Both the persons will be agreed upon the // public keys G and P // A prime number P is taken P = 23 ; System.out.println( "The value of P:" + P); // A primitive root for P, G is taken G = 9 ; System.out.println( "The value of G:" + G); // Alice will choose the private key a // a is the chosen private key a = 4 ; System.out.println( "The private key a for Alice:" + a); // Gets the generated key x = power(G, a, P); // Bob will choose the private key b // b is the chosen private key b = 3 ; System.out.println( "The private key b for Bob:" + b); // Gets the generated key y = power(G, b, P); // Generating the secret key after the exchange // of keys ka = power(y, a, P); // Secret key for Alice kb = power(x, b, P); // Secret key for Bob System.out.println( "Secret key for the Alice is:" + ka); System.out.println( "Secret key for the Bob is:" + kb); } } // This code is contributed by raghav14 |
Python3
# Diffie-Hellman Code def prime_checker(p): # Checks If the number entered is a Prime Number or not if p < 1 : return - 1 elif p > 1 : if p = = 2 : return 1 for i in range ( 2 , p): if p % i = = 0 : return - 1 return 1 def primitive_check(g, p, L): # Checks If The Entered Number Is A Primitive Root Or Not for i in range ( 1 , p): L.append( pow (g, i) % p) for i in range ( 1 , p): if L.count(i) > 1 : L.clear() return - 1 return 1 l = [] while 1 : P = int ( input ( "Enter P : " )) if prime_checker(P) = = - 1 : print ( "Number Is Not Prime, Please Enter Again!" ) continue break while 1 : G = int ( input (f "Enter The Primitive Root Of {P} : " )) if primitive_check(G, P, l) = = - 1 : print (f "Number Is Not A Primitive Root Of {P}, Please Try Again!" ) continue break # Private Keys x1, x2 = int ( input ( "Enter The Private Key Of User 1 : " )), int ( input ( "Enter The Private Key Of User 2 : " )) while 1 : if x1 > = P or x2 > = P: print (f "Private Key Of Both The Users Should Be Less Than {P}!" ) continue break # Calculate Public Keys y1, y2 = pow (G, x1) % P, pow (G, x2) % P # Generate Secret Keys k1, k2 = pow (y2, x1) % P, pow (y1, x2) % P print (f "\nSecret Key For User 1 Is {k1}\nSecret Key For User 2 Is {k2}\n" ) if k1 = = k2: print ( "Keys Have Been Exchanged Successfully" ) else : print ( "Keys Have Not Been Exchanged Successfully" ) |
C#
// C# implementation to calculate the Key for two persons // using the Diffie-Hellman Key exchange algorithm using System; class GFG { // Power function to return value of a ^ b mod P private static long power( long a, long b, long P) { if (b == 1) return a; else return ((( long )Math.Pow(a, b)) % P); } public static void Main() { long P, G, x, a, y, b, ka, kb; // Both the persons will be agreed upon the // public keys G and P P = 23; // A prime number P is taken Console.WriteLine( "The value of P:" + P); G = 9; // A primitive root for P, G is taken Console.WriteLine( "The value of G:" + G); // Alice will choose the private key a a = 4; // a is the chosen private key Console.WriteLine( "\nThe private key a for Alice:" + a); x = power(G, a, P); // gets the generated key // Bob will choose the private key b b = 3; // b is the chosen private key Console.WriteLine( "The private key b for Bob:" + b); y = power(G, b, P); // gets the generated key // Generating the secret key after the exchange // of keys ka = power(y, a, P); // Secret key for Alice kb = power(x, b, P); // Secret key for Bob Console.WriteLine( "\nSecret key for the Alice is:" + ka); Console.WriteLine( "Secret key for the Alice is:" + kb); } } // This code is contributed by Pranay Arora |
Javascript
<script> // This program calculates the Key for two persons // using the Diffie-Hellman Key exchange algorithm // Power function to return value of a ^ b mod P function power(a, b, p) { if (b == 1) return a; else return ((Math.pow(a, b)) % p); } // Driver code var P, G, x, a, y, b, ka, kb; // Both the persons will be agreed upon the // public keys G and P // A prime number P is taken P = 23; document.write( "The value of P:" + P + "<br>" ); // A primitive root for P, G is taken G = 9; document.write( "The value of G:" + G + "<br>" ); // Alice will choose the private key a // a is the chosen private key a = 4; document.write( "The private key a for Alice:" + a + "<br>" ); // Gets the generated key x = power(G, a, P); // Bob will choose the private key b // b is the chosen private key b = 3; document.write( "The private key b for Bob:" + b + "<br>" ); // Gets the generated key y = power(G, b, P); // Generating the secret key after the exchange // of keys ka = power(y, a, P); // Secret key for Alice kb = power(x, b, P); // Secret key for Bob document.write( "Secret key for the Alice is:" + ka + "<br>" ); document.write( "Secret key for the Bob is:" + kb + "<br>" ); // This code is contributed by Ankita saini </script> |
Output:
The value of P : 23
The value of G : 9
The private key a for Alice : 4
The private key b for Bob : 3
Secret key for the Alice is : 9
Secret Key for the Bob is : 9