Question

The computational complexity of __________ problem is exploited by Diffie_Hellman algorithm

Answer 1

Discrete Logarithmic Problem, which is NP Hard in complexity.

Logarithmic Problem

If suppose, we have

2ˣ = 32

and here we have to find the value of x: then

x can be written as ㏒₂(32)  = 5.

In general, if we know a,y such that

y = a^x where

y>0 and y≠0,

a>0 and a≠1,

and we need to find x,

then x can be written and found by

x = ㏒ₐ(y).

The above problem stated is well known as Logarithmic Problem.

Napier has worked on logarithms extensively, and if an algorithm involves logarithmic calculations , for each logarithmic expression present algorithm take running time of logarithmic complexity.

Discrete Logarithmic Problem

If y = a^x mod p, where p is a prime number then finding x would become a daunting task , especially when p is very large it takes decades to compute even with a super computer.

Discrete Logarithmic problem takes advantage of complexity which lies in Modular Arithmetic.

This complexity is been take to advantage by Diffie Hellman and they came up with  famous algorithm on asymmetric key cryptography for publicly exchanging the common shared key.

NIST from time to time keep updating the standards on p to be chosen .

Answer 2

The computational complexity of Discrete Logarithmic problem is exploited by Diffie_Hellman algorithm.

Short notes on Discrete Logarithmic Problem:

(a) It plays a vital role in cryptographic protocols and computational number theory.

Example of Diffie_Hellman Problem:

Let P be a prime and g be a multiplicative group GF(P)*.Let f be an element of GF(P)*.

(i) f = g^x mod P, Solving for x is called as Discrete Logarithmic Problem.

Let us assume that the first party has x and computed.

(ii) f₁ = g^x mod P

(iii) f₂ = g^y mod P.

(iv) f₃ = g^xy mod P

which they can use as a common secret key. For a passive eavesdropper to determine this key, he must find f₃ satisfying (iv) with suitable x and y satisfying (ii) & (iii) where the gathered data is just:

(P, g, f₁,f₂).

This problem is called as Diffie_Hellman problem.

Advantages of Diffie_Hellman Algorithm:

(a) The sender and receiver have no prior knowledge of each other.

(b) Sharing of secret key is safe.

Disadvantages of Diffie_Hellman Algorithm:

(a) It is not quantum resistant.

(b) cannot be used for asymmetric key exchange.

Hope it helps!