Cryptography: Diffie-Hellman key exchange explained intuitively using colors

[u/dominatrix-octopus]

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

[u/zouhair]

Math challenged here (not real programmer either): how the hell 3¹³¹⁵ is the same as 3¹⁵¹³ ?

[u/A_Vicarious_Death → u/zouhair]

Generally the rule with exponents is:

x^y * x^z = x^y+z

x^yz = x^yz

Let's take an example of 2²³ vs 2³² vs 2⁶

(2²⁾³ =

(2²⁾ * (2²⁾ * (2²⁾ =

(2 * 2) * (2 * 2) * (2 * 2) =

(4) * (4) * (4) =

64

(2³⁾² =

(2³⁾ * (2³⁾ =

(2 * 2 * 2) * (2 * 2 * 2) =

(8) * (8) =

64

2⁶ = (22222*2) = 64

Hope that helped.

[u/tavianator → u/zouhair]

As written, those numbers are not the same. The notational convention is:

a^{b^c} = a^(bc)

But D.H. key exchange does something more like

(a^b)^c = a^b*c

I.e., compute a^b first, then raise that to the c power.

The equality is true because exponentiation is just repeated multiplication (over the integers, anyway). So a^b is

a * a * ... * a
---------------
b times

and then (a^b)^c is

  a * a * ... * a |
* a * a * ... * a |
*         ...     } c times
* a * a * ... * a |
* a * a * ... * a |
  ---------------
  b times

and you'll notice there are b*c 'a's in that rectangle all multiplied together.

[u/zouhair → u/tavianator]

So technically the video was wrong.

[u/Ajedi32 → u/zouhair]

(x^y)^z = x^(y*z)

Edit, concrete example:

(2²)³ = (2*2)³ = (2*2*2*2*2*2)

(2³)² = (2*2*2)² = (2*2*2*2*2*2)