### Thread: Why use prime and primitive root in Diffie-Hellman Algorithm

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jun 2012
Posts
2
Rep Power
0

#### Why use prime and primitive root in Diffie-Hellman Algorithm

p = prime number , q = primitive root of p

user A and B share : q and p
user A and B generate a secret key : i and j
user A and B use "q^i/j mod p" to generate exchange key : Xa and Xb
user A and B exchange key and generate session key.

Problem :
1. Why use prime number and primitive root rather than 2 random number
2. Possible information get by hacker is q, p, Xa and Xb
hacker use brute force attack on Xa^n mod p , the hacker is trying to find out value i or j by keep try
for (n=1;;n+1), so the hacker will get the session key easily if the i and j value is low
SO, what is the minimum value for i and j
2. No Profile Picture
Contributing User
Devshed Novice (500 - 999 posts)

Join Date
May 2007
Posts
765
Rep Power
929
Re 1, Try it. Take values of p and q which are a prime and primitive root (say 11 and 2), and ones that are neither (say 12 and 2). Compute the value of Xa for each possible value of a.

Or if you have a grounding in abstract algebra, it may help you to know that the value you're calling "q" is often called "g" for "generator" (with the same meaning as in group theory).

Re 2, How secure do you want it--i.e. what is the least amount of time it can take for an attacker to succeed that's acceptable. Once you have that determine how large of a value you need so that the average (+whatever additional safety factor you desire) number of computations needed to solve it takes at least that length of time.

Note that Diffie-Hellman is typically used with numbers hundreds (if not thousands) of bits in length. Even if you were capable of computing the exponent-modulus operation in one nanosecond, it would take about 15 years just to break a 50-bit Diffie-Hellman by the brute force method you describe. Look up the discrete logarithm problem for more effective approaches.
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jun 2012
Posts
2
Rep Power
0

Thanks for your explanation , appreciate