Talk:Diffie-Hellman key exchange

From Wikipedia, the free encyclopedia

WikiProject on Cryptography This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography on 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.
WikiReader Cryptography It is intended that this article be included in WikiReader Cryptography, a WikiReader on the topic of cryptography. Help and comments for improving this article would be especially welcome. A tool for coordinating the editing and review of these articles is the daily article box.
To-do list for Diffie-Hellman key exchange: edit · history · watch · refresh

Here are some tasks you can do:

    Contents

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

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

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

    [edit] 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 (gx)y = (gy)x = gxy 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

    [edit] 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 gab from g, ga and gb. 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

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

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

    [edit] 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 gab 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)

    [edit] 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 ga 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)

    [edit] "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)

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

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

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

    [edit] 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?

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

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