1
$\begingroup$

I'm tired of going online looking for a simple explanation of how the Diffie-Hellman Key Exchange works. Many guides I've found attempt to explain it using anything from "paint" to massive holes in the explanation such as "g is usually 2" which infuriates me. If you can't explain it simply, you don't understand it well enough. I get that encryption is not often a simple subject but come on now; Paint? Are you kidding me?

Below is a guide I have created which attempts to explain the what, the how and the why. I really don't believe you need to be a mathematician to understand all that is required.

All I need to know is if I got it correctly with your feedback.

For example:

Why is g = 2 in RFC 3526?

  • Answer: Because having a generator that produces a distinct group ensures that the shared secret space is as large as possible, maximizing the pool of shared secrets to choose from.
  • Not Answer: Because it is usually 2.

The Guide

The Safe Prime (p = 11)

A safe prime is used as the modulus for modular arithmetic in the Diffie-Hellman Key Exchange.
It is a prime number of the form 2·p+1, where p is also a prime. Safe primes ensure a subgroup of a prime order, enhancing the security of the exchange.

The Finite Field & Euler's Totient Function

Euler's totient function, denoted as ϕ(n), counts the positive integers up to n that are relatively prime to n. For a safe prime number p, ϕ(p) = p−1, as all integers from 1 to p−1 are relatively prime to p.

The Primitive Root (Generator, g = 2)

A primitive root modulo p is an integer g such that every number coprime to p is congruent to a power of g modulo p. Using g = 2 as a generator produces a distinct group (where each member of the group can be generated by raising the generator to an exponent modulo p) ensuring that the shared secret space is as large as possible, thus maximizing security.

2 ^ 1   mod 11 = 2
2 ^ 2   mod 11 = 4
2 ^ 3   mod 11 = 8
2 ^ 4   mod 11 = 5
2 ^ 5   mod 11 = 10
2 ^ 6   mod 11 = 9
2 ^ 7   mod 11 = 7
2 ^ 8   mod 11 = 3
2 ^ 9   mod 11 = 6
2 ^ 10  mod 11 = 1

The Diffie-Hellman Key Exchange

  1. Alice and Bob publicly agree to use a modulus p = 11 & base g = 2

  2. Alice chooses private integer a = 5

  3. Alice derives public integer A = g^a mod p then sends it to Bob

  4. Bob chooses private integer b = 7

  5. Bob derives public integer B = g^b mod p then sends it to Alice

  6. Alice computes the shared secret sA = B^a mod p

  7. Bob computes the shared secret sB = A^b mod p

  8. Alice and Bob now share a secret (the number 10)

$\endgroup$
4
  • $\begingroup$ When it comes to explaining a thing, it would be fair to judge an explanation based on what is assumed from the reader and the goals. Otherwise, an explanation either lacks details or is too boring. When I read "I really don't believe you need to be a mathematician..." and "Because having a generator". To me, there's a bit of a disconnect and unclarity as to what is being achieved here. A non math persons gets a sense of what is happening with paint. $\endgroup$ Mar 18 at 13:09
  • $\begingroup$ Furthermore, cryptography is a field that lends itself well to abstraction (mostly). One of my cryptography teachers would make proofs but drawing tons of box on the blackboard week after week. Even in that case, because the abstractions boundaries were clear, there was no need to always lay it all out there. So I would suggest figuring out your target audience and provide them with the best quality you can. $\endgroup$ Mar 18 at 13:12
  • $\begingroup$ Sure. Target audience: People who like their teacher because they explain things like this. I'm a programmer. When I want to know something, whatever I look for, is explained with a what, a how and a why. And in the shortest form possible. And with examples. And completely. All guides you find for Diffie-Hellman Key Exchange cover the what and the how, NEVER the why. Example: This is a car and it moves forward. But why? Because it usually does. Just find a good manufacturer(the encryption library) and you don't need to know why. You can just trust they are smarter than you. $\endgroup$
    – suchislife
    Mar 18 at 15:40
  • $\begingroup$ As for the EC part of ECDH, now that's something you probably need to be a mathematician in order to understand. Naturally you find graphs online describing the curve and then when you want to implement an example in code, you discover it has nothing to do with curves on a graph but rather dots! Argh! You gotta love it.. $\endgroup$
    – suchislife
    Mar 18 at 15:54

1 Answer 1

1
$\begingroup$

One of the most important requirement is missing: for security, $p$ must be large, in the thousands bits. That's a necessary (not sufficient) condition for the Discrete Logarithm Problem modulo $p$ to be hard. Current wisdom is to use a 2560-bit prime, give or take 512, for 128-bit security. $p=11$ used as example has is only 4-bit!

Safe primes are not necessary to get a subgroup of prime order. They allow the largest possible subgroup of prime order. And while it's required for security to have a subgroup of large prime order, having the largest possible is not a requirement for security: a subgroup of 256-bit prime order $q$ allows 128-bit security, thus is ample when $p$ is 2048-bit and $g$ of order multiple of $q$.

For these reasons, it's not necessary for security of Diffie-Hellman modulo $p$ to have $p$ a safe prime. Some Schnorr groups are fine, too. One advantage of having $p$ a safe prime in Diffie-Hellman modulo $p$ is that it's a sufficient condition to insure that no precaution is required against the small subgroup attack.

$\varphi(p)=p-1$ is valid for any prime (not just safe primes), because the reason stated (all integers from $1$ to $p−1$ are relatively prime to $p$) applies for any prime.

Using $g=2$ and a safe prime $p$ does not insure $g$ is a generator. One counterexample is $p=23$, where the subgroup generated by $g=2$ has order $q=11$. For some safe primes $p$ (about half), $g=2$ is of prime order $q=(p-1)/2$, and for the others $g=2$ is a generator.

$\endgroup$
3
  • $\begingroup$ Certainly. I used p = 11 to keep the example less than astronomical for the average viewer. And thank you! You have really made the distinction between largest and secure clear to understand. I've read that choosing a large enough p and an appropriate g also protects against specific attacks, such as the small subgroup attack, by ensuring that the subgroup generated by g has a DISTINCT prime order and is large enough to resist brute-force attacks. $\endgroup$
    – suchislife
    Mar 18 at 16:44
  • $\begingroup$ Thinking about it, using a Schnorr group for DHKE might be tricky. I made it a question. @suchislife $\endgroup$
    – fgrieu
    Mar 18 at 17:37
  • $\begingroup$ I believe there in lies the choice of a safe prime. $\endgroup$
    – suchislife
    Mar 18 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.