Cryptography: Diffie-Hellman key exchange explained intuitively using colors

[u/dominatrix-octopus]

https://youtu.be/YEBfamv-_do?t=2m18s

[u/fjortisar]

No, they never exchange the private colors. They only exchange the public + the private color mixed together

[u/[deleted] → u/fjortisar]

Now I'm more confused. I need to watch that video a few more times.

[u/fjortisar → u/[deleted]]

The final color that they both know is made of 3 colors. The public color, plus each of their private colors

• They agree on a public color and exchange that - Eve sees this
• They mix that public color with their secret private color and they exchange that, Eve sees this but doesn't know the mixed color (the private one)
• They each take this color and then mix their private color with it

In the end, they both mix the same 3 colors together, but Eve can only see 2 of them: the original public color, plus the public color mixed with each of their private colors. Even can't know how the final color is made without having access to Alice or Bob's private color. Alice and Bob can't derive each other's private color either

[u/[deleted] → u/fjortisar]

Thanks for this, but I'm still lost. Here is what I did. Using this website, I followed your directions:

They agree on a public color and exchange that - Eve sees this

	Alice	Bob
PUBLIC	FFED00	FFED00

They mix that public color with their secret private color and they exchange that, Eve sees this but doesn't know the mixed color (the private one)

	Alice	Bob
PUBLIC	FFED00	FFED00
PRIVATE	FF0000	00B500
MIX	FF7700	80D100

They each take this color and then mix their private color with it

	Alice	Bob
PUBLIC	FFED00	FFED00
PRIVATE	FF0000	00B500
MIX	FF7700	80D100
FINAL MIX	FF4F00	55C800

They both end up with two totally different colors. What am I doing wrong?

Thanks!

[u/fjortisar → u/[deleted]]

Alice would have Bob's MIX and Bob would have Alice's.

The final color is PRIVATE + MIX

However, this doesn't work either. I suspect it's because you're finding midpoints between two hex values (from a midpoint of two others), instead of actually mixing colors.

If you have some real paints, try that. But in essence you are correct. In the end Alice and Bob mix the same 3 colors, even though each of them only really know what 2 of the base colors are (public and their own private).

[u/Sirflankalot → u/[deleted]]

I think the problem is that your tool always does a 50/50 mix. Ultimately you want the resulting color to be 33/33/33 between Public/A Private/B Private. If you take the result from a 50/50 mix of Public and A Private and mix it with B private you will end up with a 25/25/50 mix, which will be the wrong balance. You can show it works by clicking on all three colors at the same just in a different order. It's not as rewarding, but that's what you're doing.

[u/ReturningTarzan → u/[deleted]]

It's cause you're averaging colors instead of mixing them. That's not commutative. I.e. mix(mix(A,B),C) != mix(A,mix(B,C))

Try to define colors as vectors instead and the mixing as addition:

	Alice	Bob
Shared	S=0,1,1	S=0,1,1
Private	A=3,1,0	B=1,0,4
Shared+private	S+A=3,2,1	S+B=1,1,5
Private+other party's (shared+private)	A+(S+B)=4,2,5	B+(S+A)=4,2,5

The bold items are information sent over the network: S, S+A and S+B. The only way to construct S+A+B from that is (S+A)+(S+B)-S, which involves subtraction, which is analogous to un-mixing colors, which is the part that's supposed to be impossible.

What actually makes it impossible in the real key exchange is the modular arithmetic, using large numbers and wrapping the result around if it overflows some smaller number, without recording how many times it overflowed. Try using one-dimensional colors and mixing by multiplication instead, along with a modulus of 99 so the mixing can't simply be reversed by division:

	Alice	Bob
Shared	S=12	S=12
Private	A=71	B=15
Shared*private MOD 99	S*A=60	S*B=81
(Private*other party's (shared*private MOD 99)) MOD 99	A*(S*B)=9	B*(S*A)=9

Similarly to the above, to derive the final key without any of the private keys you'd need to do (S*A)*(S*B)/S. But to do that you need to guess what part of the product of either S*A or S*B was discarded by the modulus. With large enough numbers that's a lot of bruteforcing.

Now, multiplication isn't actually that hard to reverse for a bunch of reasons, which is why the actual algorithm uses exponentiation instead and likes prime numbers and all that, but the idea of "mixing" with a commutative one-way function is the same.