October 31, 2011

Yes Diffie-Hellman is secure

When it comes to the Diffie-Hellman algorithm, there seem to be many confusions from newbies in Cryptography as to whether an attacker could easily recompute the shared key by intercepting the prime numbers + public keys. While the answer is “no”, understanding why, requires an understanding the discrete logarithm problem. So here we go.

###Discrete Logarithm Problem###

The discrete logarithm problem can be summarized as follow:

Given $$a, b \in \mathbb{Z}/p\mathbb{Z} \wedge P$$ a prime, compute $$\log_b a$$

In other words, $$b$$ is defined to be a primitive root of the finite group $$( \mathbb{Z}/p\mathbb{Z} ) ^ {}, a \in ( \mathbb{Z}/p\mathbb{Z} ) ^ {}$$ of order $$p$$ and we need to calculate the exponential $$n$$ such as $$0< n<=p-1$$ resolving $$a=b^{n}$$.

The logarithm is then calculated modulo the order of $$b$$ in the finite group such that $$\log_b a \equiv x$$ if $$n = \left | b \right |$$.

Because the discrete logarithm is not NP-complete, it is not possible to compute our $$\log_ba$$ in polynomial time and therefore generating a big prime number to be used in generating a cryptographic key renders exhaustive search attack completely useless.

###DH Overview###

Before we dive further, here is a very short reminder of the DH algorithm:

User1 and User2 agree on a prime number $$p$$ and a generator $$g$$ such as there exist an exponent $$x$$ so that $$0 < g ^{x} \mod {p} <= p - 1$$.

Both users secretly generate a random key, let’s call it $$k$$ ($$k_1$$ for User1 and $$k_2$$ for User2); from there on, $$p$$ and $$g$$ are used by both users to generate their public keys.

The public key equation is:  $$g ^{k} \mod {p}$$, let’s call it $$l$$

After both users compute $$l$$ ($$l_1$$ for User1 and $$l_2$$ for User2), they exchange their public keys. The shared secret key can then be generated from the opposite user’s public key.

The secret key equation is: $$l ^{k} \mod{p}$$

  1. User1: $$l_2 ^{k_1} \mod{p} \Rightarrow g ^{k_2*k_1} \mod{p}$$
  2. User2: $$g ^{k_1*k_2} \mod{p}$$

As you can see, to recompute the shared key, the attacker would need to resolve the discrete logarithm problem as discussed earlier, that is, detect  $$k_1$$ and $$k_2$$ from $$l_1$$ and $$l_2$$, since it is not possible to directly compute $$g ^{k_1*k_2} \mod{p}$$; after all $$g ^{k_1} * g ^{k_2} = g ^{k_1+k_2}$$ and not $$g ^{k_1*k_2} \mod{p}$$.

There are of course many algorithms that attempt to resolve the discrete logarithm, such as the “squarre root attack”, but this is the subject for another post.

I hope this clarifies to new comers why DH is secure enough to be used in key exchange.