Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In the Wikipedia article on Diffie-Hellman, the algorithm calls for a large prime modulus, $p$, and a generator, $g$, which is a primitive root of $p$.

As far as my knowledge of number theory goes, to find a primitive root of a prime number, you first need to determine the prime factors of $\phi(p)$, or $p-1$.

Obviously, 2 divides $\phi(p)$, but after that you are left with the problem of factoring a number that is the same bit size as the original $p$.

I was under the impression that the security of the system was dependent upon the difficulty of finding the prime factors of a big number in the first place.

What am I missing?

share|improve this question

migrated from security.stackexchange.com Feb 23 at 10:08

This question came from our site for information security professionals.

    
related: crypto.stackexchange.com/questions/820/… – cygnusv Feb 23 at 11:06
2  
We typically use safe primes for Diffie-Hellman, i.e. primes where $\frac{p-1}{2}$ is prime. In that case factoring is trivial. – CodesInChaos Feb 23 at 11:27

Diffie Hellman is not dependent on the difficulty of factorisation of large numbers (sort of*).

It relies on the fact that there is no efficient algorithm know to the human race as of today that can efficiently deduce the discrete logarithm of a number. That is given an element $y \in G$ where G is a cyclic group of prime order $q$ , it is not computationally feasible to find a number $x \in Z^*_q$ such that $y = g^x$.

They key point here is that the order of the group needs to be a prime number. This means that the group $Z^*_p$ is not secure for any prime $p$since its order is obviously not prime.

To deal with this trouble one can choose a prime $p$ such that $p= kq + 1$. This means that there exists a unique subgroup (called schnorr group) of $Z^*_p$ of order $q$ since there exists exactly one subgroup for each divisor of $φ(p) = p-1$.

To find a generator for that group is trivial. Choose a random value $1 <h < p$ such that $h^r \mod{p} \neq 1$. If you find such a number then this inequality means that the order of $h$ is greater than $r$. However the only possible order greater than $r$ is $q$. As a result $h$ has order $q$ and can generate a secure subgroup of $Z^*_p$. If $h^r \mod{p} = 1$ then simply generate another random $h$ and try again until you find a generator.

*One can show that if the order of the group has only small prime divisors then the discrete logarithm problem is much easier to solve than other groups. However by selecting a subgroup of a large prime order as we did above by selecting $p= kq + 1$ means that the subgroup we are generating only has one large factor (itself), which in turn means that you need not worry of these factorisation attacks.

share|improve this answer

You're missing that the party which will choose g also got to choose p.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.