Diffie Hellman Key Exchange Algorithm for Key Generation
The algorithm is based on Elliptic Curve Cryptography, a method of doing public-key
cryptography based on the algebra structure of elliptic curves over finite fields. The DH also uses
the trapdoor function, just like many other ways to do public-key cryptography. The simple idea
of understanding to the DH Algorithm is the following.
1. The first party picks two prime numbers, g and p and tells them to the second party.
2. The second party then picks a secret number (let’s call it a), and then it computes
ga mod p and sends the result back to the first party; let’s call the result A. Keep in mind
that the secret number is not sent to anyone, only the result is.
3. Then the first party does the same; it selects a secret number b and calculates the
result B similor to the
4. step 2. Then, this result is sent to the second party.
5. The second party takes the received number B and calculates B a mod p
6. The first party takes the received number A and calculates A b mod p
This is where it gets interesting; the answer in step 5 is the same as the answer in step 4.
This means both parties will get the same answer no matter the order of exponentiation.
(ga mod p)b mod p = gab mod p
(gb mod p)a mod p = gba mod p
The number we came within steps 4 and 5 will be taken as the shared secret key. This
key can be used to do any encryption of data that will be transmitted, such as
blowfish, AES, etc.
Diffie Hellman Algorithm
1. key =(YA)XBmod q -> this is the same as calculated by B
2. Global Public Elements
q: q is a prime number
a: a < q and α is the primitive root of q
3. Key generation for user A
Select a Private key XA Here, XA <q
Now, Calculation of Public key YA YA = aXA mod q
4. Key generation for user B
Select a Private key XB Here, XB <q
Now, Calculation of Public key YB YB = aXb mod q
5. Calculation of Secret Key by A
key =(YB)XA mod q
6. Calculation of Secret Key by B
key =(YA)XB mod q
Example
1. Alice and Bob both use public numbers P = 23, G = 5
2. Alice selected private key a = 4, and Bob selected b = 3 as the private key
3. Both Alice and bob now calculate the value of x and y as follows:
Alice: x = (54 mod 23) = 4
Bob: y = (53 mod 23) = 10
4. Now, both Alice and Bob exchange public numbers with each other.
5. Alice and Bob now calculate the symmetric keys
Alice: ka = ya mod p = 104 mod 23 = 18
Bob: kb = xb mod p = 43 mod 23 = 18
6. 18 is the shared secret key.
Uses of Diffie Hellman Algorithm
Aside from using the algorithm for generating public keys, there are some other places
where DH Algorithm can be used:
Encryption: The Diffie Hellman key exchange algorithm can be used to encrypt;
one of the first schemes to do is ElGamal encryption. One modern example of it
is called Integrated Encryption Scheme, which provides security against chosen
plain text and chosen clipboard attacks.
Password Authenticated Agreement: When two parties share a password, a
password-authenticated key agreement can be used to prevent the Man in the
middle attack. This key Agreement can be in the form of Diffie-Hellman. Secure
Remote Password Protocol is a good example that is based on this technique.
Forward Secrecy: Forward secrecy-based protocols can generate new key pairs
for each new session, and they can automatically discard them when the session
is finished. In these forward Secrecy protocols, more often than not, the Diffie
Hellman key exchange is used.
Advantages of the Diffie Hellman Algorithm
The sender and receiver don’t need any prior knowledge of each other.
Once the keys are exchanged, the communication of data can be done through
an insecure channel.
The sharing of the secret key is safe.
Disadvantages of the Diffie Hellman
Algorithm
The algorithm can not be sued for any asymmetric key exchange.
Similarly, it can not be used for signing digital signatures.
Since it doesn’t authenticate any party in the transmission, the Diffie Hellman key
exchange is susceptible to a man-in-the-middle attack.
