4

The following image attempts to explain the diffie-hellman key exchange for people not strong in maths such as myself:

Diffie-Hellman key exchange

I do understand how the colour/paint example illustrates the idea. But I'm a bit confused about how it maps to the use of very large numbers as is the case with the real protocol.

In particular the last stages of the image above,

Receiving each other's mixture of paint, they add their secret colour and end up with a common secret. This secret is the same colour in the picture. But what if some other secret colours were used, I mean that wouldn't guarantee ending up with the same colour would it?

How does that relate to the use of large numbers. Do they end up with the same number as the common secret?

1 Answer 1

9

With big numbers, Diffie-Hellman looks like this: we work modulo a big prime p, and we start with a conventional big integer g (in the 2..p-2 range). Each integer modulo p represents an achieved colour; g itself is the starting point, i.e. "yellow" in your picture.

Each paint is an integer; the range of possible paint tones is large (at least 2160). Mixing a new paint x with the current mixture v is modular exponentiation: the new mixture becomes vx mod p (you raise v to the power x, working modulo p, so you get back to an integer in the 1..p-1 range). Mixing no paint at all is equivalent to mixing the paint "1", because v1 = v mod p.

Diffie-Hellman works thanks to two characteristics:

  1. One-wayness: given v and vx, it is hard to recompute x. In the paint analogy, anybody can mix paints, but nobody can "un-mix" that which was mixed.

  2. Commutativity: mixing paint x, then paint y, yields the same result as mixing y then x. With numbers: (gx)y = gxy = (gy)x mod p. With paints, this means that putting yellow in blue yields the same green as putting blue in yellow. This is why Alice and Bob end up with the same colour.

In the picture, Alice and Bob start with yellow. Alice mixes orange in, while Bob uses cyan on his own paper. Then Alice and Bob swap their papers; Alice gets the yellow+cyan paper, while Bob now has the yellow+orange paper. Alice does not know that what she has at that point is yellow+cyan; she only knows that she has a mix of yellow and "whatever secret colour Bob uses". She then mixes in her own secret colour (the same that she used initially on her own sheet, now in the hands of Bob), and this gives yellow+cyan+orange. Similarly, Bob adds cyan to the sheet he got from Alice, and obtains yellow+orange+cyan, i.e. the same final tone. This works because each sheet was splashed with the secret colours of both Alice and Bob (orange and cyan), and the order of mixing does not matter for the final tone. This is secure because what travelled "on the wire" (in reach of eavesdroppers) is only mixed sheets: a spy would see a yellow+orange sheet, and even knowing that it is a mix of yellow and the secret colour of Alice, then working out that the secret colour of Alice is orange is hard.

Where the paint analogy breaks down: As all analogies, it is not perfect. There are two features of modular arithmetics that are crucial to security, and don't translate to paints:

  1. Modular integers "wrap around". You can, at least theoretically, mix in a lot of distinct paints, and get back to the initial yellow. These number-paints can cancel each other; this is as if there were "negative paints" which remove pigments instead of adding new ones. With actual paints, extensive mixing can only reach some dark grey goo state.

  2. Tones can be similar to each other, not integers. If a spy (let's call him Charles) observes the yellow+orange sheet from Alice, he can make experiments with yellow and his own stock of paints. For instance, if Charles mixes yellow with red, he will get something close to the sheet he observed, much closer than if he mixes yellow with blue. Charles could then try again with several shades of pink and ochre and orange, until he pinpoints Alice's secret colour. This would work with physical paints, but not with modular integers, where you have no way to guess whether you are "close" or "not close".

    This illustrates a fundamental point: all of this protocol is about information. What Charles want is to "un-mix" the paints, but not necessarily to do so destructively; indeed, Charles' best interest is to let Alice's sheet reach Bob unscathed (there is no point in breaking a key exchange protocol if the victims don't actually complete the key exchange, and thus don't use the exchanged key). What Charles wants to do is to obtain a copy of Alice's secret colour (or at least a copy of the final tone), using his own stock of paints.

1
  • Nice! We could move the analogy to the way humans see color, where negative colors do exist. This could mitigate the 1st problem.
    – Artjom B.
    Commented May 24, 2014 at 14:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .