#1
  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


    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
  2. #2
  3. 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.
    sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}->(\&Meh);
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2012
    Posts
    2
    Rep Power
    0

    Smile


    Thanks for your explanation , appreciate

IMN logo majestic logo threadwatch logo seochat tools logo