In all textbooks I used the Diffie-Hellman key exchange is under "public key cryptography".

As far as I can see it is a method to exchange a key to be used with a symmetric cryptographic algorithm, so it falls very naturally in the area of symmetric key cryptography.

So where does DH stand in the split between symmetric and public key algorithms?

  • $\begingroup$ As per my reading diffie hellman is useful for symmetric key cryptography $\endgroup$ – user25776 Jul 24 '15 at 10:04

The Diffie-Hellman key exchange is a public-key technology. It is (by itself) not an encryption algorithm (or signature algorithm), though.

Here is the basic function: (All calculations here happen in a discrete group of sufficient size, where the Diffie-Hellman problem is considered hard, usually the multiplicative group modulo a big prime (for classical DH) or an elliptic curve group (for ECDH).)

  1. Each party choses a private key $x$ or $y$
  2. Each party calculates the corresponding public key $g^x$ or $g^y$.
  3. Each party sends the public key $g^x$ or $g^y$ to the other party.
  4. Each party uses the received public key together with its own private key to calculate the new shared secret $(g^y)^x = (g^x)^y$.

The result of this key exchange is a shared secret, which is usually then used with a key derivation function (using other input known to both parties, such as a session ID) to derive a set of keys for a symmetric encryption scheme and MAC keys, if we aren't using an encryption scheme with integrated authentication. If we are building a bidirectional channel (like in TLS/SSL or SSH), we derive different keys for both communication directions.

This might be what causes confusion: it is an asymmetric technology used to negotiate symmetric keys. But the same is valid for most other asymmetric technologies, like signature or encryption algorithms: At the core there is something asymmetric, but then we use a symmetric algorithm to do the bulk of the work. For example, with most asymmetric encryption algorithms we usually encrypt just a symmetric key for the actual message, with most signature algorithms we first hash a message, then asymmetrically sign the hash.

The values $g^y$ or $g^x$ are named public keys, because they can be transmitted in plain, so anyone listening on the connection knows it. The values $x$ and $y$ never leave the choosers computer, so they stay private. $(x, g^x)$ and $(y, g^y)$ are the private-public key pairs here. Incidentally, these are the same types of keys as in DSA or ElGamal.

One could have long-term key pairs (and then the public key could even already be in some address book, saving the transmission, or be signed with some certificate), but more usually these key pairs are created on the fly for each connection.

When combining the Diffie-Hellman key exchange (with a long term public key of the receiver) with a symmetric encryption scheme, we get a nice public-key encryption scheme – actually one of the first ones to be proposed at all. It works like this:

  1. The receiver has a private key $x$ and a corresponding public key $g^x$.
  2. The sender somehow securely obtains the public key $g^x$.
  3. The sender choses a temporary private key $y$ and calculates the corresponding public key $g^y$.
  4. The sender calculates $(g^x)^y$ and derives from this a symmetric key $K = f((g^x)^y)$.
  5. The sender encrypts his message: $C = E_K(P)$.
  6. The sender sends $(g^y, C)$ to the receiver.
  7. The receiver gets $(g^y, C)$.
  8. The receiver calculates $(g^y)^x$ and derives from this $K = f((g^y)^x)$. This is the same $K$ as before.
  9. The receiver decrypts the message: $P = D_K(C)$.

This is an asymmetric encryption scheme – to encrypt, the sender needs to know only $g^x$, while for decryption $x$ itself is needed.

  • $\begingroup$ Hmm - thanks. The symmetric key K = f((g^x)^y) part made me think that DF may be discussed in the realm of symmetric cryptography (I know it is not a cipher) - but your explanation clarifies why it is considered public key. See also the wikipedia article : Once Alice and Bob compute the shared secret they can use it as an encryption key, known only to them, for sending messages across the same open communications channel. Looks like symmetric - no ? Could be s (g^(xy)) be used as the key in AES for instance ? $\endgroup$ – Mr_and_Mrs_D Feb 10 '13 at 18:59
  • $\begingroup$ $g^{xy}$ itself is usually not in the right format for an AES key, so we normally apply a key derivation function (something like a hash) on it to get the actual cipher key. This also allows having different keys for both directions, and MAC keys, too. $\endgroup$ – Paŭlo Ebermann Feb 10 '13 at 19:12
  • 1
    $\begingroup$ Thanks - if we do apply we end up with a symmetric key - no ? So in this case DH is used to create and exchange the symmetric keys - or is never used like this ? $\endgroup$ – Mr_and_Mrs_D Feb 10 '13 at 19:24
  • $\begingroup$ Yes, DH is almost always used to finally exchange a symmetric key. In this respect, it is just like RSA or ElGamal encryption – here you usually don't encrypt your plain text, but a symmetric key (or something from which the key will be derived) to be sent to the partner. $\endgroup$ – Paŭlo Ebermann Feb 10 '13 at 19:27
  • $\begingroup$ OK - that is where the confusion lies - DH is usually discussed in the realm of public key cryptography while used in the realm of symmetric key cryptography. Duh $\endgroup$ – Mr_and_Mrs_D Feb 10 '13 at 19:34

I would like to explain this with an example, that why it lies in public key cryptography domain.

All the values used in this example (a = Private Key of Alice, b = Private Key of Bob, g, n, PKalice = Public key of Alice, and PKbob = Public key of Bob) are large, let say 2Kb or 4Kb, prime numbers.

Let Alice and Bob (who don't know each other) want to communicate. They both have generated their private keys (let say 'a' and 'b'). Similarly, they both have calculated their public keys (let PKalice = g^a mod n, and PKbob = g^b mod n).

The values g, n and public keys (PKalice and PKbob) are publically known and could be stored in a central repository. Now whenever the two users want to communicate, they can obtain the publically known and agreed upon values and can generate the session keys (symmetric key) and use that key for secure communication.

For Alice, the function to calculate session key is (PKbob ^ a mod n) and for Bob (PKalice ^ b mod n), that result in the same value for Alice and Bob, although they don't know each other private keys or values.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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