Talk:Diffie–Hellman key exchange

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing articles
???	This article has not yet received a rating on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the project's importance scale.

Cryptography: Computer science Unassessed

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
???	This article has not yet received a rating on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the importance scale.
	This article is supported by WikiProject Computer science.

Template:CryptographyReader

Archives

Archive 1

This page has archives. Sections older than 90 days may be automatically archived by when more than 5 sections are present.

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)[reply]

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

  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)[reply]

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)[reply]

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
		g^a mod p
	…
(g^b mod p)^a mod p

$\rightarrow$

$\leftarrow$

=

Bob
Calculus	Public	Secret
	p, g
		b
	…
g^b mod p
		(g^a mod p)^b mod p

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

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)[reply]

Error in section description?

This section states:

Alice picks a random natural number a and sends g^a to Bob.
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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

Junk at the bottom

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