Talk:Diffie-Hellman key exchange

Missing image Key-crypto-sideways.png WikiProject on Cryptography

This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography in the Wikipedia. If you would like to participate, you can choose to edit the article attached to this page, or visit the project page, where you can join the project and see a list of open tasks.

Template:CryptographyReader

	Pending tasks for [[Template:Articlespace:Diffie-Hellman key exchange]]: (https://academickids.com:443/encyclopedia/index.php?title=Talk:Diffie-Hellman_key_exchange&action=purge)	edit (https://academickids.com:443/encyclopedia/index.php?title=Talk:Diffie-Hellman_key_exchange/to_do&action=edit) - watch (https://academickids.com:443/encyclopedia/index.php?title=Talk:Diffie-Hellman_key_exchange/to_do&action=watch) - purge (https://academickids.com:443/encyclopedia/index.php?title=Talk:Diffie-Hellman_key_exchange&action=purge)
	Talk:Diffie-Hellman key exchange/to do

Contents

1 Attributing the system 2 but what about precedent? 3 key exchange -> key agreement? 4 Abelian requirement 5 I may be wrong, but isn't this article .. wrong?

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 Jul 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 Jul 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 Aug 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 <math>(g^x)^y = (g^y)^x = g^{xy}<math> 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 (http://cacr.math.uwaterloo.ca/hac) (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

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:

1. 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.
2. Alice picks a random natural number a and sends g^a to Bob.
3. Bob picks a random natural number b and sends g^b to Alice.
4. Alice computes (g^b)^a.
5. 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