Talk:Diffie–Hellman key exchange

Template:CryptographyReader

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)

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)

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)

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)

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!

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)