Talk:Diffie–Hellman key exchange/Archive 1

This is an archive of past discussions about Diffie–Hellman key exchange. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

Attributing the system

Martin Hellman has written:

"The system I called the ax1x2 system in this paper has since become known as Diffie-Hellman key exchange. While that system was first described in a paper by Diffie and me, it is a public key distribution system, a concept developed by Merkle, and hence should be called "Diffie-Hellman-Merkle key exchange" if names are to be associated with it. I hope this small pulpit might help in that endeavor to recognize Merkle's equal contribution to the invention of public key cryptography. Space does not permit an explanation of the quirk of fate that seems to have deprived Merkle of the credit he deserves, but a quirk it is."

(See http://www.comsoc.org/livepubs/ci1/public/anniv/pdfs/hellman.pdf, first page.)

In light of Hellman's comment, we should rename the page to "Diffie-Hellman-Merkle key exchange", perhaps with an explanation. (I'll do this if there are no objections.)

Peter Hendrickson

I think we should use the name which is in general use, and I've a feeling this is "Diffie-Hellman key exchange", so I would oppose a name change. I think Hellman's acknowledgment should certainly be mentioned in this article (and perhaps elsewhere too). — Matt 00:09, 23 Jun 2004 (UTC)

I agree that the more widely used term is "Diffie-Hellman".

However, the proper term is "Diffie-Hellman-Merkle". In addition to Hellman's published comment above, US Patent #4200770, which I am told covers this algorithm, credits all three gentlemen as inventors.

The URL of the patent itself: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=/netahtml/srchnum.htm&r=1&f=G&l=50&s1=4200770.WKU.&OS=PN/4200770&RS=PN/4200770

The patent search page: http://patft.uspto.gov/netahtml/srchnum.htm

"Diffie-Hellman-Merkle" is clearly the proper name for the algorithm.

The question then is whether the Wikipedia should use the popular or the proper term.

First, the policy of the Wikipedia should be to use the appropriate term. An important function of the Wikipedia is to educate. Using outdated terminology does not further this purpose. What is more, we can hardly put on the page that the proper name for the algorithm is "Diffie-Hellman-Merkle", when this is not the term we use ourselves.

Second, the policy of the Wikipedia does actually seem to be to use proper names for things. For example, most people (in the US, anyway) refer to "Czechoslovakia" instead of "The Czech Republic". Yet, the Wikipedia page describing the current country whose capital is Prague is called "The Czech Republic". Similarly, most people incorrectly refer to the nation of Myanmar as "Burma". The Wikipedia (correctly) has a Myanmar page, to which "Burma" is redirected.

Third, I do not believe that it is the role of the Wikipedia to perpetuate an injustice. Merkle was a co-discoverer of the Diffie-Hellman-Merkle algorithm and of public key cryptography. I'm sure you will agree that these were both terribly important to the progress of cryptography. It is not just that he should be marginalized in the Wikipedia or anywhere else, particularly when there is no dispute of fact concerning his contribution.

On the practical side, if we rename the page, people who know the algorithm as simply "Diffie-Hellman" will still continue to find it, just as they do now. I fail to see any harm caused by calling the algorithm by its proper name.

Peter Hendrickson

Peter, you say "The question then is whether the Wikipedia should use the popular or the proper term.". Wikipedia has decided, by policy, to name pages using the popular term:

"Use the most common name of a person or thing that does not conflict with the names of other people or things...When choosing a name for a page ask yourself: What word would the average user of the Wikipedia put into the search engine? The Wikipedia is not a place to advocate a title change in order to reflect recent scholarship. The articles themselves reflect recent scholarship but the titles should represent common usage." — Wikipedia:Naming conventions (common names)

There was recently a debate about changing the policy, based around arguments on city names (see Wikipedia:Naming policy poll), but the policy was upheld. In particular, some of your comments were answered here: Wikipedia:Naming policy poll/FAQ — Matt 12:23, 24 Jun 2004 (UTC)

You had me convinced there for a minute, but then I read this:

"In cases where the common name of a subject is misleading (For example: "tidal wave" would be a misleading title since these phenomena have nothing to do with tides), then it is sometimes reasonable to fall back on a well-accepted alternative (tsunami, for example)....it does mean that we need to temper common usage when the commonly used term is unreasonably misleading..." — Wikipedia:Naming conventions (common names)

Calling the algorithm "Diffie-Hellman" is certainly misleading because it suggests it was invented solely by Whitfield Diffie and Martin Hellman. I believe this is also unreasonable. Other than inertia, I know of nobody in possession of the facts who believes the algorithm should be called "Diffie-Hellman", although that is certainly the popular term.

The FAQ you cited does support your interpretation, but it says at the top "This FAQ represents the opinions of some Wikipedians who support the current policy, and is not in itself official Wikipedia policy."

Since we agree the facts belong on the page I'll add a short note at the beginning of the article and then a longer discussion toward the end. Also, I'll create redirection pages for "Diffie-Hellman-Merkle" and "Diffie-Hellman-Merkle key exchange" which will send readers to the "Diffie-Hellman" page. (This is important because if somebody finds "Diffie-Hellman-Merkle" in an article they need to be able to look up the algorithm.)

My sense is that we've reached an impasse on the page title issue, though. I'll re-raise the issue in a few weeks and see if everybody still feels the same way.

Peter Hendrickson

This sounds reasonable. If you feel we've reached an impasse, it might be worth putting a note on Wikipedia:Requests for comments to get some wider community input. — Matt 20:18, 24 Jun 2004 (UTC)

Notice also that in this case the popular usage is very popular; a Wikipedia:Google test for "Diffie-Hellman key exchange" returns 13,300 hits, whereas "Diffie-Hellman-Merkle key exchange" yields only 54. — Matt 20:33, 24 Jun 2004 (UTC)

One other thing: would you also argue that we should also rename the Vigenere cipher, as it was invented by someone else (Giovan Batista Belaso)? — Matt 20:39, 24 Jun 2004 (UTC)

Yes, I agree that "Diffie-Hellman" is certainly the popular usage. Some articles seem to start using "Diffie-Hellman-Merkle" and even then revert to "Diffie-Hellman": [http://www.awprofessional.com/articles/article.asp?p=21409&seqNum=4 Pioneering Public Key: Public Exchange of Secret Keys]

Still, I feel, there are few cases regarding the proper terminology which are as unambiguous as this one. What gives the issue particular weight is the importance of Diffie, Hellman, *and* Merkle's work. A fair number of the pages in the Wikipedia cryptography section - and of the pages still to be written - are about ideas which are a direct consequence of the discovery of public key cryptography. It seems to me especially important that all the discoverers are recognized.

The situation would be less clear if there was a controversy regarding who did what, but I don't think anybody anywhere is arguing that "Diffie-Hellman" is the appropriate term.

Also, if the name change were to result in confusion it would be less clear. For example, the Church-Turing Thesis was anticipated by Babbage. Yet, renaming the page to "The Babbage Thesis" would certainly be pushing the envelope. (It would also be controversial.) If Church and Turing had requested it be called "The Church-Turing-Babbage Thesis", then I would recommend the title of the page be changed.

If Vigenere had publicly requested that the cipher be called the "Vigenere-Belaso Cipher" I would argue that the name be changed. Were Vigenere and Belaso still with us, and had it been unambiguously determined that Vigenere "stole" the discovery, I would probably favor changing the page name to "Belaso Cipher", if it was not controversial.

Peter Hendrickson

Another point: Diffie, Hellman and Merkle weren't the first people to discover public key cryptography; that was done earlier at GCHQ. Accordingly, you could make a case for calling it "Williamson key exchange". Having said that, I don't think Wikipedia is the right place to argue about what it should have been called; we should only note what it is called, (and to make a note of what Hellman thinks it should be called, as well). — Matt 23:38, 24 Jun 2004 (UTC)

Nobody believes it should be called Williamson key exchange. (This has little relationship to what we are discussing, but the reason is that Williamson kept his work secret and it had no effect on the development of the art. People are credited not only with being smart, but also with driving the art forward. It is probable that had public key cryptography not been developed publicly, we would never have known of the work of Williamson and the others.)

On a related point, I disagree with your addition of the word "public" to make "public inventors". This implies Merkle's contribution was not public. As we can see from the patent, his participation has been known since at least 1980. If you want to say something like "named after Diffie and Hellman who published an article describing the algorithm in 1977", I would not object. But, I think it best just to drop the word "public".

Regarding the title of the page, I'm content to let the matter rest for the moment.

Peter Hendrickson

(My mentioning Williamson was just an attempt to point out that it's not always clear-cut what the "proper" name is — I think it can be argued in several ways, and indeed, "Diffie-Hellman-Merkle" would be a strong candidate. But I'm arguing to follow popular usage, in any case.) Regarding "public", it wasn't meant to refer to Merkle, but to the earlier GCHQ work (public academia vs secret government agency); clearly (if at least you misunderstood) it can be worded much better. — Matt 00:00, 25 Jun 2004 (UTC)

Okay, I see the sense of "public" now - that's a good distinction to draw. Perhaps we should change the next line to be "Ralph Merkle is a co-inventor." This kills two birds with one stone, because it would be nice to make clear that Merkle didn't invent it independently. And, it seems like it would be a mistake to clutter up the first paragraph with "...published an article...".

Peter Hendrickson

P.S. I went ahead and made the Merkle change since I doubt we disagree.

Peter Hendrickson

I took another look at Wikipedia:Naming conventions (common names) and these conventions seem to apply to the title of the page only:

The Wikipedia is not a place to advocate a title change in order to reflect recent scholarship. The articles themselves reflect recent scholarship but the titles should represent common usage.

Would there be an objection if I left the title of the page alone, but changed all the "Diffie-Hellman" instances to "Diffie-Hellman-Merkle"? I can live with leaving things as they are, but if it's the case that this change is not a problem, I'd like to make it. (I believe that DHM reflects recent scholarship. For example, Simon Singh's book refers to the algorithm as "Diffie-Hellman-Merkle.")

Peter Hendrickson

Upon further reflection and some private discussion, I have concluded that I am (cough, cough) in error on the Diffie-Hellman-Merkle issue. Sorry about that, Chief! ;-) Peter Hendrickson

No problem; it's useful to note the "-Merkle" name, particularly since at least one author (Singh) has adopted it. From what I've been reading (and I've been moving house, so sorry about the delay in getting back to you), it seems that in terms of specific people who had the "complete" idea: Diffie came up with the idea of public-key cryptography, Hellman with the specific Diffie-Hellman key exchange algorithm, and Merkle designed Merkle's puzzles as a key-exchange algorithm a little bit earlier. All three had been in discussions, and particularly Diffie and Hellman, so it's not really fair to say, for example, Hellman invented D-H. But attribution gets a little messy; for instance, Adleman apparently only broke candidate ideas from Rivest and Shamir until they came up with the RSA algorithm, but he still was credited as an important part of the invention process, even if the actual idea wasn't primarily his invention. — Matt 15:25, 1 July 2004 (UTC)

but what about precedent?

It seems that much of this discussion is moot as Williamson got there first, and it is only a question of how the most widely used misattribution should be phrased. I'm in favor of the WDHM as the term since it properly recognizes Malcolm's precedence and yet includes DHM per the popular (though wrong) term in the literature.

I think we, and Williamson, are stuck with D-H, however unfairly this represents what actually happened first.

Does anyone remember the actual inventor of television, or the man who did the most to develop radio? Nope. Sarnoff iced 'em both.

(ans for those w/o a clue. Philo Farnsworth in the first case, and Edwin Armstrong in the second. In the last case it certainly wasn't Marconi as Tesla beat him to the first pole.) ww 17:19, 1 July 2004 (UTC)

key exchange -> key agreement?

The term key exchange is somewhat misleading as no keys are actually exchanged. Key agreement and key negotiation better capture what this algorithm does. Would anybody object if I were to change exchange to agreement throughout the article, leaving the title of the page unaffected? (I prefer key agreement to key negotiation since the former is more common.)

**Google Test**
Term	Count
key exchange	43,300
key agreement	17,800
key negotiation	12,300

Peter Hendrickson

Peter, I have none. I would suggest that some note be made of the confusing common usages, however. Have at it! ww 18:24, 6 Aug 2004 (UTC)

I ~~exchange~~ agree. — Matt 23:12, 6 August 2004 (UTC)

Abelian requirement

Seems to me the Abelian requirement isn't what makes g^xy=g^yx, since the group operation is multiplication rather than exponentiation. x and y are integers, not even group members, since they specify the number of times g is multiplied by itself. So xy=yx because the integers are commutative, and g^x^y=g^xy because that's just a group property according to Exponentiation. So could somebody better at number theory clarify the Abelian requirement, please? Lunkwill 23:00, 6 Aug 2004 (UTC)

I think you're right. Surely

(g^{x})^{y}=(g^{y})^{x}=g^{xy}

for any semigroup because of associativity? — Matt 23:21, 6 Aug 2004 (UTC)

It only has to be Power associative for this property. However, this is not necessarily secure. The Discrete logarithm page makes reference to finite cyclic groups rather than mere abelian ones. The Handbook of Applied Cryptography (See 3.6) describes the "generalized discrete logarithm problem" in terms of finite cyclic groups. Note 3.54 suggests that the cyclic property is desired because it implies there will always be a solution to a^x = b where x is the unknown. I'll need to think about it some more, but we probably need to make some major changes to the description of the algorithm. What is especially lacking is a description of how to choose G securely. Peter Hendrickson

I've made some changes, but more is needed. Most of the discussion of why finite cyclic groups are used and so forth should probably be on the Diffie-Hellman problem page, which hasn't been written yet. Peter Hendrickson 19:42, 7 August 2004 (UTC)

I may be wrong, but isn't this article .. wrong?

I'm not a matematician. I'm not a cryptographer. I'm however a tad interested in the subject. The description of the algorithm in the article is:

Alice and Bob agree on a finite cyclic group G and a generating element g in G. (This is usually done long before the rest of the protocol; g is assumed to be known by all attackers.) We will write the group G multiplicatively.
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.
Alice computes (g^b)^a.
Bob computes (g^a)^b.

Now, I always thought the key exchange went something like this:

1. Alice and Bob agree on the public variables 'g' and 'p'.
2. Alice picks a random natural number a and sends g^a mod p = A .. to Bob
3. Bob picks a random natural number b and sends g^b mod p = B .. to Alice
4. Alice computes B^a mod p , and gets the shared secret.
5. Bob computes A^b mod p , and gets the shared secret

This is also how it is explained in: http://www.nyx.net/~awestrop/crypt/dh.htm

Are you referring to the "mod p" bit? The explanation in this article is slightly more general in that it assumes only a finite cyclic group. The explanation you provide is a specific instantiation in the multiplicative group of integers mod p. In theory you could use other groups too, as long as there's no easy way to compute g^ab from g, g^a and g^b. I presume there are such groups, but I don't know enough to tell you what they might be! — Matt 12:41, 18 Oct 2004 (UTC)

Also, the example that you (the anonymous IP) wrote in the article was incorrect as written. Instead of rewriting the algorithm verbatim with (mod p) such that p is prime, it suffices to say that one such group is the multiplicative group of integers mod prime p, which is already mentioned in the article. That being said, the description of DHKE on the link you provided is technically incorrect.

Additionally, to just throw out some other groups that DHKE works for, just consider implementations that use elliptic curves or hyperelliptic curves. CryptoDerk 16:53, Oct 18, 2004 (UTC)

An observation: to many readers, discussions of cyclic groups, generating elements and power associativity is scarily technical. We must, of course, have this technical material in the article. An idea: I think it would be worth giving two versions of DH in the article; one quite early on which gives the specific implementation in integers mod p. Then, further on in the article, we can describe how it generalises to any suitable group. This way, we structure the article so that more technical material appears later, and (hopefully) is of maximum use to those without the prerequisite maths knowledge. — Matt 17:37, 18 Oct 2004 (UTC)

Oh, sure, I'm fine with an example of it over the integers if it is stated correctly. In fact, it's a good way to kill two birds with one stone, because this is how the algorithm was first proposed in DH's 1976 paper. CryptoDerk 18:01, Oct 18, 2004 (UTC)

Sorry for my late reply. (New, anonymous IP; same person ;) - I took the liberty of editing the article. If I did it wrongly, please correct it - but please, please have an easy to follow example like the one I inserted. I have absolutely _no clue_ about what a "finite cyclic group" is, and I wouldn't be able to do "pen and paper" tests of the algorithms if I had to read up and try to understand lots upon lots of different articles. However, I AM able to understand the example I've given, and it's easilly checked with pen and paper. :)

Thanks for the suggestion! I think your edit was deleted because it was too similar to the existing definition; perhaps my expanded discussion with concrete values will survive. :) Lunkwill 17:36, 19 Oct 2004 (UTC)

As I stated before, I removed it because it was similar, and more importantly, incorrect. CryptoDerk 20:07, Oct 20, 2004 (UTC)

I really like the concrete example. Why didn't we have that already? ;-) We should think about extensively footnoting the page. Current Wikipedia custom is weak in this regard. What is wanted is a footnote link which goes to a "footnotes" section at the bottom of the page which has all the external links. Specifically, where does the claim of the length of required digits come from and where is the Sophie-Germain material coming from? Peter 16:02, 20 Oct 2004 (UTC)

Lunkwill: Doesn't matter that my edit was deleted - because now you've made a nice rewrite which included a good example which is easily understood by a lay-person. Thanks! -The Anonymous Guy

I kind of feel that the "variable" p is missing in the general description. I'm not quite familiar with group theory; I just have a "vague" understanding that you might have omitted any reference to mod p, assuming it is already understood as the definition of the group operation. I suppose p is the order of G? What about mentioning it explicitly? Erizzaaaaa (talk) 02:05, 1 January 2010 (UTC)

Draft diagram

Image:Dh-mockup.png. — Matt Crypto 12:36, 16 March 2006 (UTC)

I like it. Much faster to grab than the current tables of who knows who. Velle 22:02, 27 August 2006 (UTC)

Algorithms for g and p

Which algorithms are used for g and p (the prime and the primitive)? Thanks, --Abdull 10:48, 29 March 2006 (UTC)

22 or 23 possible values in the example?

A minor point, but the article says:

Of course, much larger values of a,b, and p would be needed to make this example secure, since it is easy to try all the possible values of g^ab mod 23 (there will be, at most, 22 such values, even if a and b are large).

Shouldn't that be 23 such values, since 0 is possible? Or am I missing something? ManaUser 04:26, 21 September 2006 (UTC)

NO. It is 22 because it is the Multiplicative group of integers modulo n --MagnusPI (talk) 11:40, 27 November 2007 (UTC)

Worried about the universe

The article claims

If p was a prime of more than 300 digits, and a and b were at least 100 digits long, then even the best known algorithms for finding a given only g, p, and g^a mod p (known as the discrete logarithm problem) would take longer than the lifetime of the universe to run.

According to Lenstra computing discrete logarithms in modulo a 300 digits (about 1000 bits) is roughly equivalent to a 74 bit symmetric cipher, which is claimed to be secure until about 2006. Thus 300 digits or 1000 bits seems to be just about the minimal size for p today. 67.84.116.166 05:08, 21 September 2006 (UTC)

That is interesting. Do you have a source that supports this claim? --mgarde (talk) 12:59, 30 November 2009 (UTC)

"Jana"?

Any particular reason for the apparently arbitrary renaming of "Alice" to "Jana" in the examples in this article? I was going to revert the article, since "Alice" and "Bob" are overwhelmingly accepted as the standard example names, but since the editor went as far as editing a diagram in the article, I wondered if there was a legitimate reason for it... --stephenw32768^<talk> 23:41, 17 November 2006 (UTC)

Hmm...Personally, I think we're better off with Alice -- it does make for easier reading if you've heard of them before, and, hey, it's pretty much a convention in crypto. — Matt Crypto 23:53, 17 November 2006 (UTC)

G-Men

Okay in the security section it says this:

"The protocol is considered secure against eavesdroppers if G and g are chosen properly."

But in the description section it says that:

"Note that g need not be large at all, and in practice is usually either 2 or 5."

Well which is it? What value should I pick for g?

Either 2 or 5 will be fine in most instances for g; just don't pick some weird g that generates a subgroup with small order. G is somewhat trickier; you generally want a group with order p, such that q=(p-1)/2 is also prime, and such that p is in the neighborhood of 2^2048. Lunkwill 23:38, 18 January 2007 (UTC)

How does Bob get 'a' and how does Alice get 'b'?

This is just to help people, like myself, who are new to crypto and are following the example. I found the tables for Alice and Bob, with columns 'Sec' and 'Calc' to be very helpful. However, I kept scratching my head wondering "how did Bob get 'a' found in row 5?". Then I got it: Bob did not get a, but Bob got A.

I think it would be very helpful to replace the (g^a mod p) with A, and perhaps a note indicating that A = (g^a mod p) as a calculated value. I think this would help newbies like me.

Thanks, --Natersoz 17:31, 14 February 2007 (UTC)

Group Diffie-Hellman key agreement

I removed a link to an online paper describing a Diffie-Hellman key exchange between multiple parties, because the scheme described there is fully anticipated. If there is a wish to include a group Diffie-Hellman key exchange into this article then for example the following paper can be used as a reference: E. Bresson et al., "Provably authenticated group Diffie-Hellman key exchange", Proceedings of the 8th ACM conference, 2001. 85.2.20.96 19:12, 20 March 2007 (UTC)

Speed?

I'm a non-expert, but isn't D-H exchange very slow? I didn't see that scanning through the article, but it's an important drawback -- otherwise people might wonder why we don't all just use D-H to exchange keys for one-time pads or something?

— Preceding unsigned comment added by 71.194.163.223 (talk) 14:50, 19 July 2007 (UTC)

DH Groups

How about a (sub)section on DH Groups? I only know of four and don't exactly know how they are classified or where the classifications are determined. AlephGamma (talk) 00:13, 7 December 2007 (UTC)

Good question. But it is not clear to me what a DH group is. Depending on how Diffie-Hellman is used in a crytographic application it may be necessary to select a group that satisfies the Decisional Diffie-Hellman assumption. But perhaps the Computational Diffie-Hellman assumption or some other requirement is sufficient. The article on the Decisional Diffie-Hellman assumption already contains a list of groups that are believed to satisfy this assumptions, which is a least a starting point. 85.2.1.77 (talk) 07:12, 7 December 2007 (UTC)

On most network devices there are selection elements for DH groups when configuring IKE. Group 1, 2, 5 and 2048 are available - the last of which appears to be only MS centric. Respectively they have 768-bit, 1024-bit, 1536-bit and 2048-bit DH prime modulus group. It's getting late and DH prime modulus group sounds like gobbledygook. But all this is not confirmed from other sources. AlephGamma (talk) 07:38, 7 December 2007 (UTC)

Die-Hellman?

[1] --68.161.148.207 (talk) 09:30, 27 April 2008 (UTC)

Most scientists use TeX/LaTeX, etc to write their articles. There some letter combinations like ffi use special compound characters to make the printout look nicer. Apparently Google Scholar just doesn't know these special characters when parsing the documents. 85.2.88.234 (talk) 12:08, 27 April 2008 (UTC)

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
		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)

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:

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)

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 Public Key Section?

If Alice's public key was $(g^{a},g,p)$ , $a$ would easily be computable by $a={\frac {\ln g^{a}}{\ln g}}$ . Common sense and lecture of the article suggests the public key be $(g^{a}{\bmod {p}},g,p)$ . I changed it (since this is definitely more true than the version before), but I cannot verify that! 79.219.194.112 (talk) 14:05, 3 November 2011 (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? —Preceding unsigned comment added by 128.61.83.190 (talk) 11:26, 28 March 2011 (UTC)

Operation with more than two parties

I just added this section. I didn't cite any references, as I had trouble actually finding any. Google searches lead to very little information; the only reference I could seem to find was that the Java implementation of Diffie-Hellman through javax.crypto.KeyAgreement permits this by setting lastPhase to false; most Web pages talking about multi-party DH merely show examples of how to use the Java classes to do this. Examining the Bouncy Castle JCE provider's source code reveals that the math I show in the article is indeed how the algorithm is implemented, but using source code as an encyclopædic reference seems odd. Hawk777 (talk) 06:11, 7 June 2011 (UTC)

Different variable names used across article?

Through most of the article Alice and Bob are picking a prime p and base g. However, in the SECURITY section they choose G and g. Is G intended to refer to the same thing as p?

Thanks! Fitzhugh (talk) 21:29, 16 February 2012 (UTC)

Problem in C code program example

The problem is that it requires you to enter any random prime value you want for both p and g. The problem with that is while p is supposed to be a random prime, g is supposed to be SPECIFICALLY a number that falls into a category called "primitive root mod p". There is NO PRIMITIVE ROOT GENERATOR algorithm shown in this code. I guess the sample C code hopes you to have entered a "primitive root mod p" for the value of g, and runs with whatever you did enter. However the algorithm will ONLY work properly if g is in fact a "primitive root mod p". It will fail if g is ANYTHING other than that. Please fix this code. I'm trying to implement this my self and am not aware of a good "primitive root mod p" generator algorithm. Please include some sample code for this process so I can read it and then implement it in my own program I'm writing. Animedude5555 (talk) 12:41, 26 August 2013 (UTC)

Yes, g does not have to be a prime. It doesn't have to be a primitive root either. The security requirement is that the order of g is either a large prime or divisible by a large prime. Diffie-Hellman works in either case. Protocols such as IKE often use the former. Anyway, a description how to find primitive roots is on the page primitive root modulo n in the section "Finding primitive roots". For implementing this I'd prefer a language that comes with a BigInteger type in its standard library (e.g. Java or C#). I think the current C code on the wiki page is useless, confusing, misleading and should be deleted. Not only is the verification of g incorret, the code also implements a modular exponentiation that is slow (no square and multiply) and suffers from unchecked overflows. The primality test is equally inapproriate, since it does not work for practical sizes. 2A02:1205:C6BB:6880:1171:7223:F6DE:8031 (talk) 06:50, 29 August 2013 (UTC)

No, "g" should most certainly be a primitive root of "G", and the order of G (not g!) should have a large prime factor (the order will never BE prime since 'p' is itself prime and thus p-1 necessarily cannot be (since the order is relative to TOTIENT(p-1))). Anyway, I've deleted the C code due to it's inherent flaws. As a side note, from my own original research I've found that one can fairly quickly identify a primitive root of any prime modulus P by finding some B that satisfies B^((P-1)/2)%P = P-1 (B can simply be initialized to 2 then incremented until the equality is satisfied). 70.112.97.77 (talk) 17:26, 4 October 2013 (UTC)

A motivation for using a generator g whose order is prime is that the decisional Diffie-Hellman assumption can be applied. This simplifies the analysis of Diffie-Hellman based protocols a bit. This may also be the reason why IKE uses generators that are not primitive. A counter example to your test method is P=43. 2A02:1205:C6BB:6880:2510:7248:B68C:B9AE (talk) 18:51, 4 October 2013 (UTC)

Yes, thank you for the corrections and clarifications. Cheers! 70.112.97.77 (talk) 19:11, 4 October 2013 (UTC)

Missing modulo p?

I think mod p is missing in steps 2 and 3 in section "Explanation including encryption mathematics": 2. Alice picks a random natural number a and sends g[super]a[/super] to Bob. 3. Bob picks a random natural number b and sends g[super]b[/super] to Alice. Otherwise, a and b could easily be calculated as ${}^{g}\!\log A$ and ${}^{g}\!\log B$ , respectively. I' am not quitte sure about this, however, so I didn't change in in the article.

The modulo operator isn't missing, since the text your are pointing out uses a generic group G. This could of course be the multiplicative subgroup modulo a prime, but it could also be the multiplicative subgroup of a binary field or elliptic curve group. However, the page is certainly quite confusing, since it switches from mod p groups to generic groups in the same paragraph. 2A02:120B:2C4C:9840:C97B:EC85:FF4:5C40 (talk) 11:31, 30 March 2014 (UTC)

Rename this article from "Diffie-Hellman key exchange" to "Diffie-Hellman-Merkle Key Agreement", place redirect

Per https://en.wikipedia.org/wiki/Talk:Diffie%E2%80%93Hellman_key_exchange/Archive_1#key_exchange_-.3E_key_agreement.3F , this system is more a key-agreement protocol than an arbitrary-key-exchange protocol. I propose renaming this article to 'agreement' and leaving a redirect.

As well, the 2002 quote by Diffie cited on the page itself says that he (at least) calls it Diffie-Hellman-Merkle. I think that this would be a good thing to rename the article itself to as well. Instead of doing two steps (rename to Agreement, rename to Diffie-Hellman-Merkle), it might be easier done as one step.

Aerowolf (talk) 18:50, 12 February 2014 (UTC)

Renaming the article would not be a good idea in my opinion. Diffie may call it Diffie-Hellman-Merkle, and would hide the article from those interested in reading it. As far as I know, Wikipedia is supposed to reflect the real world, not influence it. If the protocol is reffered to as Diffie-Hellman key exchange by the people that study Cryptography, then the article should remain named that way. Dottn (talk) 18:38, 4 May 2014 (UTC)

g^b mod p when searching for a?

Shouldn't

"even the fastest modern computers cannot find a given only g, p, g^b mod p and g^a mod p"

read

"even the fastest modern computers cannot find a given only g, p and g^a mod p" ?

Holding no information concerning a, g^b mod p isn't of any help for finding a - or is it? --FePo2 (talk) 11:25, 27 March 2015 (UTC)

It’s true

a

doesn’t depend in any way on

b

or

g^{b}

, but the claim as currently written is stronger than the one you are suggesting substituting it with (namely, it assumes the attacker knows more quantities and still can’t win), and still true, so I would prefer it be left as is. Hawk777 (talk) 05:40, 30 March 2015 (UTC)

The text is indeed a bit confusing. It mixes the discrete logarithm problem and the Diffie-Hellman problem. 2A02:120B:2C4F:7900:DFF:1343:2858:ECA0 (talk) 19:41, 4 April 2015 (UTC)

Misleading information?

This is the sentence that seems to suggest that Diffie-Hellman is not vulnerable to MITM:

The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel.

Either the article shoud define "insecure communications channel" as a **signed** communication channel, which -- to me -- doesn't make much sense, or it should be removed/rephrased.

Moebius eye (talk) 20:38, 6 June 2014 (UTC)

The general idea does hold, sort of, and signing is not required. The only security property that is needed from the channel is that the protocol message in at least one direction reach the other mostly unmodified. That is to say, any party that can be assured that one of the two messages reached the other side without substitution (but not necessarily error-free) has the assurance that the resultant key is either junk or confidentially shared between only the two parties. This can also be reinterpreted that on any channel, the key will be shared with the communicating party (whether this is an attacker interposing themselves or some intended party). But in a sense I agree: it might make sense to note in the article that the comparatively mild security property of assured nonsubstitution is required of the channel if a MITM attack is to be thwarted. —Quondum 22:58, 4 April 2015 (UTC)

DH is not public-key cryptography

"Public-key cryptography, also known as asymmetric cryptography, is a class of cryptographic algorithms which requires two separate keys, one of which is secret (or private) and one of which is public."

I acknowledge that some people falsely classify it as such but it is missing two essential details. First, it is not crypto, as it does not involve encrypting data at all. It is an agreement protocol where two parties agree on a secret. Second, it does not use "two separate keys" where one is secret and one is public. I edited the page to clarify that and User;Quondom reverted. I edited the page again to note the fact that some people (at least User:Quondom if no one else) believe it is public-key crypto and this was promptly reverted by an anonymous user.

There are no citations for the belief that DH is public-key crypto and even my CN tags were removed. I am restoring just the CN tag since the fact that there is no citation for a claim in an article is not a matter of opinion. Note that there is a citation on that paragraph but it backs up my version of this page, not the reverted version.

Note that if this tag is removed, that will constitute a violation of WP:3RR. --- Vroo (talk) 20:12, 4 April 2015 (UTC)

Take a breath, and realize that we'll only get somewhere if we approach this in a spirit of cooperation. I'll just make a few (hopefully relatively neutral, non-reactive) comments:

Your perception of what constitutes a cryptographic algorithm is too narrow. The terms "cryptography" and "encryption" are by no means synonymous. You will see in the first few sentences of Cryptography that addresses security properties in addition to confidentiality, which is the defining property of encryption.
Public-key cryptography says: "Some public key algorithms provide key distribution and secrecy (e.g., Diffie–Hellman key exchange), some provide digital signatures (e.g., Digital Signature Algorithm), and some provide both (e.g., RSA)." Your edit comment "DH is not public-key cryptography reading definition there; it does not use public & private key" seems to ignore this, and it does use what is called a public and private key for each party (see further down in the article), albeit ephemeral ones.
The Diffie–Hellman key exchange protocol is considered to be a public-key protocol, and the algorithms used in it have all the defining features of a public-key algorithm.
Also note the distinction between a protocol and an algorithm. D–H is the former, not the latter, though this is a side issue.
Talking about the issue on this talk page is the right approach; user talk pages not so much when it is discussing article content and edits.

—Quondum 21:07, 4 April 2015 (UTC)

Just tried to add similar comments. Despite the fact that there are many references, here is a concrete citation: "Handbook of Applied Cryptography", by A. Menezes, P. van Oorschot, and S. Vanstone, Chapter 1, page 1: "The most striking development in the history of cryptography came in 1976 when Diffie and Hellman published New Directions in Cryptography. This paper introduced the revolutionary concept of public-key cryptography... " 2A02:120B:2C4F:7900:DFF:1343:2858:ECA0 (talk) 21:16, 4 April 2015 (UTC)

I too was a bit confused about whether it is public-key cryptography or not, but this stackexchange answer seems to shed some light. Tony Tan⁹⁸ · talk 23:23, 4 April 2015 (UTC)

Perhaps the choice of names is part of what causes confusion. The terms public-key cryptography and asymmetric cryptography are synonyms, and the latter is possibly the better one to avoid confusion, though the former is more widely used. It is essentially distinguished from symmetric cryptography by the use of two (or more) blobs of information ("keys") by two (or more) parties in a protocol, one or more of which cannot feasibly be derived from the other(s). This separation of a "key" into two "keys" in this way is the core feature. D–H exploits this property, and thus fits the category. The discussion you link here makes reference to the subsequent symmetric use of the agreed key, but this is not part of the D–H key agreement, and might confuse things a little. —Quondum 00:08, 5 April 2015 (UTC)

Incidentally, that link ends with the statement "This is an asymmetric encryption scheme – to encrypt, the sender needs to know only

g x

, while for decryption

x

itself is needed" is incorrect. D–H is not an encryption scheme at all, and no extension to an encryption scheme (e.g. as described using a symmetric algorithm) fits this description. —Quondum 00:15, 5 April 2015 (UTC)

The Menezes, van Oorschot, Vanstone quote doesn't say the DH algorithm is public-key crypto but that the paper introduced public-key crypto (I'm not sure that's accurate given the earlier Merkle work, but that's a different issue). There's a difference between introducing the concept and making that concept practical. Consider: clearly, Merkle introduced the concept of secure key agreement over an insecure channel but the proposed algorithm was impractical. DH introduced a practical solution to key agreement.

The Public-key cryptography page says "The distinguishing technique used in public-key cryptography is the use of asymmetric key algorithms, where the key used to encrypt a message is not the same as the key used to decrypt it." This is the common interpretation. But then take a look at the illustration on that page regarding DH (this is much less informative than the paint illustration on the DH page). It describes DH as having public and private keys. The so-called keys (intermediate values) in the DH algorithm are not used to encrypt or decrypt messages. In fact, there is no way to use the DH algorithm to communicate information at all. The result of the algorithm is agreement on a shared secret but neither party has any way to influence the value of the secret in a way that would allow communication (otherwise, the algorithm would be fundamentally flawed). A dictionary definition of cryptography is "the process of writing or reading secret messages".

Yes, it is a cryptographic algorithm in the sense that it is used in cryptography bit it's not cryptography by itself. Similarly, a cryptographic random number generator is not cryptography but it is cryptographic.

P.S. Regarding "take a breath" it is frustrating to make a simple edit to a page and have it immediately reverted by you and then having my next change immediately reverted by an anonymous user. Frankly, I'm tired of editors protecting pages from anyone else editing them by reverting changes they disagree with. Your comments here seem that you are willing to edit this page to address this issue. I don't know if the anonymous user will concur. --- Vroo (talk) 06:30, 5 April 2015 (UTC)

Not sure what you haven't understood. In the article the private keys are a and b. The public keys are g^a mod p and g^b mod p. Possibly the article doesn't state this clearly enough. Anyway, another reference that clearly states that the Diffie-Hellman protocol is a public key protocol is the paper "New Directions in Cryptography" itself. Diffie and Hellman define in section III, "Public key cryptography" what a public key cryptosystem and what a public key distribution system is and then introduce DH as an example. If the term "public key cryptography" was narrowed since the publication of this paper, then surely it should be possible to give a citation for this. 2A02:120B:2C4F:7900:2C92:4337:230B:F9F8 (talk) 14:33, 5 April 2015 (UTC)

To reply to a few points by Vroo above:

The quote from the Public-key cryptography page makes an incorrect statement, and should be fixed. It describes public-key encryption, a particular instance of public-key cryptography.
Forget the dictionary definition. Because confidentiality has historically been the first (and until comparatively recently, the only) application, and even today texts use this as an introductory example of cryptography, a misconception exists that this is the extent of the field. The second paragraph of the lead of Cryptography speaks of this change. Rather consider a more notable source than a dictionary, and remember that dictionaries are sometimes slow to track changes. Here is a quote from Menenzes et al:
Definition Cryptography is the study of mathematical techniques related to aspects of information security such as confidentiality, data integrity, entity authentication, and data origin authentication.
D–H key agreement is a technique for providing confidentiality – of the agreed result – but is not encryption because that result is not explicitly chosen by either party. It can be used as a building block in a larger protocol for encryption. In particular, it seems to fit the description of the techniques in Menenzes's definition (and incidentally, that list is not exhaustive). By your criterion (that no encryption or decryption occurs), you would presumably argue for exclusion of digital signatures, message authentication and many of the other facets regarded to be part of cryptography.
And finally, with reference to your frustration, it is easy to understand it; we've all experienced the same, I'm sure, as it is natural in collaborative efforts such as WP. Yet, we are not here to frustrate each other, but rather to work towards a shared goal, and learning to manage your own frustration is essential. It might help to review WP:EQ and WP:ACM#Taking it too seriously.

—Quondum 16:54, 5 April 2015 (UTC)

A nice quote from Menendes et al: "A concise and elegant way to describe cryptography was given by Rivest [1054]: Cryptography is about communication in the presence of adversaries." —Quondum 17:03, 5 April 2015 (UTC)

I agree with Vroo that no communication is possible by DH alone, and that it is merely a way for exchanging keys. But the question is: Is DH public-key cryptography, or not? It can only be used to exchange symmetric keys, and cannot be used to encrypt/decrypt data. Why is it considered public-key cryptography? The only case it is used in public-key crypto is when it is combined with RSA (such as DHE-RSA used in TLS) so that one party can verify the identity of the other party and prevent MITM attacks. Tony Tan⁹⁸ · talk 17:18, 5 April 2015 (UTC)

Interestingly, Diffie–Hellman_key_exchange#Public_key states that DH actually can be used to encrypt/decrypt messages. We may have been wrong. Tony Tan⁹⁸ · talk 17:22, 5 April 2015 (UTC)

You too seem to be confusing the meaning of "cryptography". It includes many techniques that have nothing to do with encryption, for example digital signatures. It would help if you read the points being made.

The example you refer to that presents D–H being used for encryption is misleading. Here, D–H is still only used for key agreement; the only difference is that instead of an ephemeral key, Alice uses her static identity key. —Quondum 17:59, 5 April 2015 (UTC)

Quondum: I agree that cryptography is more than just encryption. But you seem to be confused on what the word public means in public-key crypto. Suppose Alice and Bob use DH to agree on a secret key. Then they proceed to use that secret key to encrypt their communication. They do this by XORing the key into the contents of their messages. Admittedly the XOR cipher isn't a very good one, but I choose it because no one would ever claim it is an instance of public-key encryption. Yet you claim this system constitutes public-key cryptography because each party has some secrets not known to the other. But in fact, the DH algorithm doesn't depend on a and b remaining private. It only requires that they be temporarily secret from the other party and that they be permanently secret from adversaries. Conversely, what you call public keys in DH must be shared with the other party and must not be shared with an adversary. If an adversary acquires both parties' public keys, then the game is over. In true PK crypto, the private keys must remain private and the public keys can be shared with anyone, even adversaries.

For comparison, consider the following algorithm for generating a new shared secret between two parties that already have a shared key (k1). We want to generate a new key that neither party can choose unilaterally yet is in no way dependent on our existing key. Here's the algorithm: Alice generates two secret values a1 and a2. She encrypts a1 using a2 as the key. Sending E_a1(k1, now, a2) to Bob. Likewise, Bob generates b1 and b2 and sends E_b1(k1, now, b2) to Alice. Once Alice receives this from Bob, she sends Bob back a1, and Bob likewise sends Alice b1. Each can decrypt, verify that the first part of the encrypted data is the old shared key, the time value is sufficiently recent that this is not a replay and derive a2 and b2 respectively. They then generate k2 = a2 XOR b2. Is this also public-key crypto? It relies on the fact that a1 and b1 are initially private (just as a and b in DH) but they must be exposed for the algorithm to work.

(Yes, I glossed over details here, like requirements on the encryption algorithm and size of k, a1, a2, b1, b2 that make it infeasible for Alice to generate a post-hoc a1 value in order to choose a particular value of a2 after decrypting b1. I'm sure you can fill in the blanks.) --- Vroo (talk) 01:34, 16 April 2015 (UTC)

To repeat what I said above:

Perhaps the choice of names is part of what causes confusion. The terms public-key cryptography and asymmetric cryptography are synonyms, and the latter is possibly the better one to avoid confusion, though the former is more widely used.

The fact that the term "public" is used in one version of the term should not mislead you; your arguments here seem intrinsically linked to an inappropriate interpretation of the meaning of the phrase based on the words. What elements of the system are or become public or private has little to do with the meaning. Your statement "Yet you claim this system constitutes public-key cryptography because each party has some secrets not known to the other" confuses me: I do not see such a claim by me. And now, please consider WP:TALK#USE – I think that this has gone far beyond discussing corrections to the content of the article, and has veered into a debate of your beliefs about the meaning of how the terminology is (or perhaps should be) applied. I'd suggest that you familiarize yourself with appropriate texts on the subject in a way that allows you to substantiate or modify these beliefs for encyclopaedic use before changing the interpretation in the article. —Quondum 03:50, 16 April 2015 (UTC)

justification for (g^a mod p)^b mod p = (g^a)^b mod p)

The equality:

 (g^a mod p)^b mod p = (g^a)^b mod p)

was given on the page, but no justification was given. I've googled many places, but found no justification.

It was repeated here:

http://security.stackexchange.com/questions/45963/diffie-hellman-key-exchange-in-plain-english

but that also failed to provide justification.

The, maybe closest, to a justification was here:

   http://math.stackexchange.com/questions/360248/does-ga-mod-pb-equiv-gab-mod-p-hold-true

but that just gave a hint on how to derive the equality, but not a strong enough hint for me.

Could someone please provide a link to a justification of provide a justification?

TIA.

Cppljevans (talk) 18:32, 5 May 2015 (UTC)

I don’t have a citable source for it, but it’s a well-known property of modular arithmetic that addition and multiplication commute with modulus-taking. Given that multiplication commutes, it’s pretty easy to convince yourself that exponentiation commutes too:

((A\mod M)\times (B\mod M))\mod M=(A\times B)\mod M

, therefore

((A\mod M)\times (A\mod M))=A^{2}\mod M

, so

(A\mod M)^{2}\mod M=A^{2}\mod M

, and then you can carry that forward to other exponents. You might find some more information, or even citable sources, on this page. Hawk777 (talk) 05:01, 6 May 2015 (UTC)

Hawk777 (talk) 05:01, 6 May 2015 (UTC)

Thanks very much Hawk777. To be more specific, the

following table shows the correspondence between your:

((A\mod M)\times (A\mod M))=A^{2}\mod M

and my:

(g^a mod p)^b mod p = (g^a)^b mod p)

Correspondence table:

Cppljevans	Hawk777
g^a	A
p	M
b	2
(g^a)^b	$A^{2}$

Cppljevans (talk) 19:03, 6 May 2015 (UTC)

Yes, that is roughly what I was thinking of. Obviously it’s not a full proof since

b\not =2

, but it was a rough sketch of some of the pieces of the puzzle. I’m not a mathematician so it would take me far more time than I have available to turn this into anything formal. Hawk777 (talk) 04:48, 9 May 2015 (UTC)

No, I'd say the table looks wrong. Start with g = A. As Hawk777 indicates, multipication and taking the modulus commute. (A more formal approach might treat g as the set of all values that are equal to some given value plus a multiple of p, but let's stick to reducing values modulo p.) We need the identity (g ⋅ h) mod p = ((g mod p) ⋅ (h mod p)) mod p. If you write g and h as say g = g′ + m ⋅ p and h = h′ + n ⋅ p, you should be able to convince yourself of this pretty quickly (see Modular arithmetic). Using the normal property of (g^a)^b = g^a⋅b, the required identity on the respective mod p values follows pretty directly. —Quondum 13:25, 9 May 2015 (UTC)

New Vulnerability (Logjam) Found In DHE_EXPORT Ciphersuites

A new vulnerability, called Logjam, has been found allowing an attacker to downgrade an HTTPS connection (and possibly SSH and VPN) to 512 bit encryption. From there, the connection can be compromised further.

Links: ArsTechnica Article Research Paper — Preceding unsigned comment added by Sacredsocks (talk • contribs) 22:53, 20 May 2015 (UTC)

logjam isn't just a vulnerability in export suites. it's the combination of a downgrade attack similar to FREAK with vulnerability in DH itself, and the small size of export DH parameters just makes the vulnerability easier to exploit. the vulnerability is still there even if larger parameters are used. hotaru2k3 (talk) 06:16, 21 May 2015 (UTC)

The logjam paper also points out that the use of a few well known prime groups enables precomputation. SOme of these well known primes are even embedded in standards documents. The article should point out that all primes should be choosen at random (plus some restraints fo weak primes ?) to void such precomputation. 78.54.73.38 (talk) 13:48, 21 May 2015 (UTC)

precomputation still works if servers use unique random primes. if a server uses the same prime for millions of connections, an attacker only has to expend the effort of breaking a single key to break all of them. the only way to maintain forward secrecy is to choose a new prime for every connection, and even ephemeral RSA is faster than that. hotaru2k3 (talk) 15:08, 21 May 2015 (UTC)

External links modified

Hello fellow Wikipedians,

I have just added archive links to one external link on Diffie–Hellman key exchange. Please take a moment to review my edit. If necessary, add {{cbignore}} after the link to keep me from modifying it. Alternatively, you can add {{nobots|deny=InternetArchiveBot}} to keep me off the page altogether. I made the following changes:

Added archive https://web.archive.org/20121018132414/http://www.comsoc.org/livepubs/ci1/public/anniv/pdfs/hellman.pdf to http://www.comsoc.org/livepubs/ci1/public/anniv/pdfs/hellman.pdf

When you have finished reviewing my changes, please set the checked parameter below to true to let others know.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers. —^{cyberbot II}_{Talk to my owner:Online} 22:17, 25 August 2015 (UTC)

External links modified

Hello fellow Wikipedians,

I have just added archive links to 2 external links on Diffie–Hellman key exchange. Please take a moment to review my edit. If necessary, add {{cbignore}} after the link to keep me from modifying it. Alternatively, you can add {{nobots|deny=InternetArchiveBot}} to keep me off the page altogether. I made the following changes:

When you have finished reviewing my changes, please set the checked parameter below to true to let others know.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—^{cyberbot II}_{Talk to my owner:Online} 08:42, 27 February 2016 (UTC)

DH vs RSA

Hello fellow Wikipedians,

As far as I know, what Clifford Cocks described in the '70 was a cryptosystem similar to RSA, not a DH key exchange. Am I right? — Preceding unsigned comment added by 87.220.154.159 (talk) 06:07, 4 September 2016 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified 2 external links on Diffie–Hellman key exchange. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

Y An editor has reviewed this edit and fixed any errors that were found.

If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 00:18, 13 December 2016 (UTC)

More elaborate example

This uses the 2048 bit prime suggested in rfc3526 :

p = FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74 020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F1437 4FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF05 98DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB 9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF695581718 3995497CEA956AE515D2261898FA051015728E5A8AACAA68FFFFFFFFFFFFFFFF

a = (secretly chosen by A, should also be 2048 bit, but shorter here)
19283746AABBCCDDEEFF00112233445598765432
b = (secretly chosen by B, should also be 2048 bit, but shorter here)
A91B25C68FE7A6D8998877661928332219345678

x = 2^a mod p = (calculated and transmitted by A)
D9487989280A9B0FC49A58CB4DCC73340C6828967D90AFE352BF6E61670FC94BEC37 DB07F6DAE2233EFB9D597314CEE442C14C3E22483E84A8110C6E02FE7519A1A583CC 2EA9FC650B0C89D57EFA46DCB6934F0DB6DC3BADC43E41BC895D4498F813BAEFA97D 2D8B75B7D6C5C05930F2D7C599238060AD23C9E0DED20E843699A8F8F092C74816D9 1D37DB11CE78A9DD9BD8D352691708CD7E6E7E2B076D43A46E87C5F46C79A3BE0011 3BC47AD1569641FB92001D7F0A1FBFEC2FDD9A23F62786DE02A387A9FC781C682E42 866B4BC98239C7F5F3ABDD40AA30E68F0A44C91858F9C063BE7FEB76FAD6E2B9B384 97C0F135EE78C761C641BCEB34855BA5CAF2
y = 2^b mod p = (calculated and transmitted by B)
C4EE2EF71F72CC5CF4FDE2CA0BE64D4FBD65552DD0D644615A064CC35E40E17A18D6 DF56F72DACF6424FFD8CAEA7B23DE82E3A7DD586668AFE51B0AD3E08DF85F899E6D3 B6B8AAEEDEB91FAFCDC5E104E10284E270B22B902304457031E754980E348F709549 4CC520D3A860BCA205884A64540BF6ED5C19ECF6A0AFB21A10911C423CB1C5D993B0 7FE85E84F086896D987A2D029A4E30B0E1FBAD8BDC4E4DAA560CE183E1AD0D0A3FB7 2CF1279D9175E8CEA4B0E0736DCAA5D8590C1071A9212F2CC54B0630843EF428F88B 29655E88CA8C3AF31C42B2E023C485A32D3C2352CC394A7425FD1994F93B78F353B3 0C07480F3DB6FCF756824A204F59C7E9E354
KeyA = y^a mod p = 2^(b*a) mod p (calculated by A)
485FFE50D43480DD431DC03F26BC91055D4B1159DBD0AB760E1070661761E54E2B84 F62AD290DA2023319F580CB594AD013331B676C5BBC273C75703096C3B919CCB14B9 1F09F1E78356D592D3AD3DB124D650139BA58FE1C782E6A17BA877175054D3206A65 C09EC6AF3DE2605C419FE266FD7D6B1BBC0868FE8E93302DE7708B78488CB5674BD4 86FE36FBBC84FFC4F80F7BF4E8739B9DC9B7385DB05087876C3F8F0032A281ED3464 BF0154C782611FB68251BBD2AE6829F73B4F3CC53AFD8B82B3B4CC9955591D5F8151 84DDAF80E8B7F977E0CBD2E3FE175120F3199E32F3A02EA42B241D1DFCCFF61BB679 A25E0802C0FDE59E531545FF3B97DD5236CD
KeyB = x^b mod p = 2^(a*b) mod p (calculated by B)
485FFE50D43480DD431DC03F26BC91055D4B1159DBD0AB760E1070661761E54E2B84 F62AD290DA2023319F580CB594AD013331B676C5BBC273C75703096C3B919CCB14B9 1F09F1E78356D592D3AD3DB124D650139BA58FE1C782E6A17BA877175054D3206A65 C09EC6AF3DE2605C419FE266FD7D6B1BBC0868FE8E93302DE7708B78488CB5674BD4 86FE36FBBC84FFC4F80F7BF4E8739B9DC9B7385DB05087876C3F8F0032A281ED3464 BF0154C782611FB68251BBD2AE6829F73B4F3CC53AFD8B82B3B4CC9955591D5F8151 84DDAF80E8B7F977E0CBD2E3FE175120F3199E32F3A02EA42B241D1DFCCFF61BB679 A25E0802C0FDE59E531545FF3B97DD5236CD

Maybe someone wants to reformat this and include it in the main page. 18:00, 18 February 2016 (UTC) — Preceding unsigned comment added by 194.25.174.98 (talk)

This is brilliant. Many thanks to the person who contributed this. There are many explanations on how Diffie–Hellman works but when it comes to actually implementing something, it is unclear what p, g and q are and where they come from. This examples clarifies that and should be included on the main page.203.118.131.249 (talk) 04:11, 5 July 2017 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified 2 external links on Diffie–Hellman key exchange. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

Added archive https://web.archive.org/web/20141030210530/https://cryptocellar.web.cern.ch/cryptocellar/cesg/possnse.pdf to http://cryptocellar.web.cern.ch/cryptocellar/cesg/possnse.pdf
Corrected formatting/usage for http://www.rsasecurity.com/rsalabs/node.asp?id=2306

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 14:11, 10 September 2017 (UTC)

Examples in Sections "explanation" and "Secrecy" using different private numbers

The former section uses a=3 and b=4 while the latter one is using a=6 and b=15 as private numbers. I could not guess any reason for that. Do you agree that it is better to change the latter to use the same private numbers (a=3 and b=4)? Alfa80 (talk) 16:09, 5 November 2017 (UTC)

Needs a section for Elliptic-curve Diffie–Hellman

Needs a section for cryptographic explanation of Elliptic-curve Diffie–Hellman and difference between ECDH and DH. 117.195.57.218 (talk) 08:24, 19 November 2017 (UTC)

The "General overview" subsection has misleading colours

Bob should mix yellow with blue, getting green. Now, he is mixing yellow with green-blue, getting light-blue, which is absurd. This issue concerns both the text and the illustration. Thank you for your attention. MCiura (talk) 17:14, 10 May 2018 (UTC)

Please, evaluate to correct the name of the page for issues when citing url which includes "en dashes" in the name.

As some more explained here https://productforums.google.com/forum/#!msg/webmasters/oPsAZ5Dc2hg/sa7I8YCOvxwJ citing this page gives some issues as when copying the url and pasting it, depending where one were working on (e.g. an editor or notepad app) it performs the following url link "https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange" (note the "%E2%80%93" extra for coding the "en dash" (U+2013, –, e2 80 93, EN DASH). Perhaps it helped to change the name including a more standard joining sign in the page name. — Preceding unsigned comment added by 86.30.159.160 (talk) 12:42, 7 January 2018 (UTC)

Done. You can now reference this Wikipedia article with the url: " https://en.wikipedia.org/wiki/Diffie-Hellman_key_exchange " (using the easier-to-type minus sign on most keyboards (ASCII 0x2D, -, U+002D - HYPHEN-MINUS ). To avoid breaking links that use the percent-encoded form of the URL, that URL will also continue to work. Two different URLs (one easy-to-type, the other "typographically correct") are common for a Wikipedia article, in accordance with the Wikipedia MOS:DASH guideline. --DavidCary (talk) 18:51, 5 April 2021 (UTC)

I propose a possible improvement to the algorithm explanation graphic, but lack the skills to deliver it

I've experimented with reworking the DH algorithm graphics to add a temporal dimension, but I lack the skills and wikipedia experience to turn my ideas into something usable; rather than pollute this page with excessive discussion, I wrote up the concepts at https://alecmuffett.com/article/14750 and would be interested to chat with anyone regarding whether this is actually a better proposal than the extant diagrams. Alecmuffett (talk) 21:14, 30 May 2021 (UTC)

DH is not vulnerable to MITM per se

the Diffie–Hellman exchange by itself does not provide authentication of the communicating parties and is thus vulnerable to a man-in-the-middle attack.

Given that Diffie–Hellman key exchange is anonymous, the example of a MITM attack between Alice, Bob and Mallory doesn't make sense, because Alice doesn't know who she is talking to!

The example makes sense to me: Alice may think she's talking to Bob (for some reason, for example because either the content or the context of the communication gives that impression), and the fact that with DH she doesn't actually know this is what makes Mallory able to masquerade as Bob. I could agree perhaps "vulnerable" is too strong: since DH isn't intended to protect against this, it seems unfair to classify this lack of protection as a "vulnerability". Perhaps it should be worded "thus does not protect against" instead of "is thus vulnerable to". I think the example is helpful, though. --Raboof (talk) 08:21, 17 January 2023 (UTC)