Talk:Diffie–Hellman key exchange

Template:CryptographyReader

Correct choice for g in G

The article states that g is frequently small, just 2 or 5. While the algorithm would work with those values, it would be more secure to actually choose g as a primitive root of the group. This is unlikely to be 2 or 5 for a 300+ digit prime P. And furthermore, with only a 100-digit "a" and "b" on each side, that small value for g is unlikely to give a good mashing up of its value through modular exponentiation (i.e., bit rotation and chopping).

And even if you were to use much larger values for "a" and "b" exponents, the poor choice of g might very likely give a shorter period than the group size of (P-1), whereas using a primitive root for g assures a maximal length sequence.

A primitive root g is such that, for all prime factors, p, of (P-1) one has g^((P-1)/p) mod P /= 1. That can be found by randomly probing, as in the Lucas-Lehmer test for prime assurance.

Of course, getting those prime factors of (P-1) might be a bit of a challenge for a 300-digit P. But by careful construction of the prime you can make it relatively easy. Just use a seed prime U of some fewer digits in length and start searching for some multiple k, where (2*k*U + 1) is prime. Then the prime factors of (P-1) become 2, those of k, and U itself. From there Lucas-Lehmer with random probing should find a suitable primitive root g within an average of 3 looks, and nearly always in less than 20 looks. —Preceding unsigned comment added by Dbmcclain (talk • contribs) 16:01, 30 December 2009 (UTC)

... just my 2c —Preceding unsigned comment added by Dbmcclain (talk • contribs) 15:54, 30 December 2009 (UTC)

  Is this guaranteed for any prime g if G is known prime?  —Preceding unsigned comment added by 75.45.0.228 (talk) 23:18, 8 August 2010 (UTC) 

Natural numbers?

The article says, Alice picks a random natural number a and sends ga to Bob, with a link to natural number. Unfortunately, natural number starts out by saying there's two definitions (including or excluding zero). We should be more explicit which one we mean. -- RoySmith (talk) 20:52, 7 April 2010 (UTC)

Example table

I feel that the table used as an example might be incorrect. It shows (g^b mod p)^a mod p as being public, but isn't that the key? As you'll notice, that value is never sent in plaintext in the rest of the example. I believe this would be an appropriate change, but I don't want to make it without checking it with others.

Alice Secret Public Calculus p, g a ga mod p … (gb mod p)a mod p

$\rightarrow$ $\leftarrow$ =

Bob Calculus Public Secret p, g b … gb mod p (ga mod p)b mod p

146.186.210.55 (talk) 01:57, 24 April 2010 (UTC)

I think you are right, and even though I'm no expert either, this has been unanswered for months and if it is wrong it needs to be taken off, so I have changed you correction also. Ufotds (talk) 16:45, 16 July 2010 (UTC)

Error in section description?

This section states:

1. Alice picks a random natural number a and sends g^a to Bob.
2. Bob picks a random natural number b and sends g^b to Alice.

since a and b are secret and g is public, sending g^a would lead to disclosure of a. I think this needs to say "g^a mod p". Ufotds (talk) 08:56, 5 July 2010 (UTC)

You're correct. The article does state $A=g^{a}\%p$ and $B=g^{b}\%p$ elsewhere. WP:Be Bold and make it right. -- Autopilot (talk) 12:22, 5 July 2010 (UTC)

I know this policy, but I am not bold enough to change an encyclopedic article on cryptography whenever the formulas don't make sense to me. I have changed it now.94.226.185.23 Ufotds (talk) 21:58, 6 July 2010 (UTC)

Error in reference?

Wouldn't the reference on Hellman's paper be: Martin Hellman, An overview of Publick Key Cryptography, IEEE Communications Magazine, NOV 1978, p. 24--32 (based on retrieving this paper from the IEEE)? —Preceding unsigned comment added by 24.37.252.19 (talk) 11:47, 18 September 2010 (UTC)

Broken links to US patent

The two links to the US patent are broken. –134.60.1.151 (talk) 16:27, 25 November 2010 (UTC)

Junk at the bottom

Why is their spammy-looking junk at the very bottom of the article?