June 16th, 2012, 09:05 AM

Why use prime and primitive root in DiffieHellman Algorithm
Hi guys, I just learned about this PKCS and I have 2 question to ask.....
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
June 16th, 2012, 10:38 PM

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 iti.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 DiffieHellman is typically used with numbers hundreds (if not thousands) of bits in length. Even if you were capable of computing the exponentmodulus operation in one nanosecond, it would take about 15 years just to break a 50bit DiffieHellman by the brute force method you describe. Look up the discrete logarithm problem for more effective approaches.
sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}>(\&Meh);
June 17th, 2012, 08:10 AM

Thanks for your explanation , appreciate