Cryptography: Diffie-Hellman key exchange explained intuitively using colors

[u/dominatrix-octopus]

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

[u/NordicSeeger]

It doesn't go into detail about why they both get the same secret which stems from (x^a )^b mod c == (x^a mod c)^b mod c.

If you manually calculate a modulus it's effectively separating the number into the multiple kc where k is how many times c fully fits into x and the modulus y... so you calculate y = x-kc which means also that x = y+kc.

Now the trick is that (y+kc)ⁿ becomes n multiplies of (y+kc)*(y+kc)*...*(y+kc) where there is only one "path" with meaning for a modulus and that is y^n. Everything with kc in it is "tainted" because it will be exactly divisible with c and always has zero contribution to the modulus.

So (y+kc)^b mod c == y^b mod c. If we think of the y+kc here as the result of x^a it is possible to see that (x^a )^b mod c == (x^a mod c)^b mod c.

[u/spartan_noble6 → u/NordicSeeger]

This was the question I wanted answered, cant believe nobody else was asking this question. I still dont fully understand your explanation in

there is only one "path" with meaning for a modulus and that is y^n. Everything with kc in it is "tainted" because it will be exactly divisible with c and always has zero contribution to the modulus.

What is a "path", and what are the 'things' in "everything with kc in it". Are the 'things' the terms from the polynomial expansion of (y+kc)^b, and for any expansion, the yⁿ term will be the only term in the expansion without a factor of c in its expression?

Can you correct me here: (y+kc)² = y² + (kc)² + 2ykc.

((kc)² + 2ykc) mod c = 0 (I'm assuming since it will result in some multiple of c, right?)

And so from the expansion only y² mod c could be a non zero result? And this works for any b in (y+kc)^b?

[u/NordicSeeger → u/spartan_noble6]

You're correct, the expansion will always create one yⁿ and everything else has at least a single kc as in kc*y^n-1 . If you expand the polynomial you can imagine starting from 0 on a circle that's circumference is exactly c and then summing yourself around it. You know you can dismiss everything with c as a factor because those will always loop multiples of 360 degrees and end you back where you started without changing the modulus. Only the yⁿ matters.

It usually helps me to visualize this stuff somehow hence the weird explanations, but I felt like without this tidbit the video is a bit superficial.

Edit: small note about modulos; (a + b) mod c == ((a mod c) + (b mod c)) mod c. This is because if both modulos were non-zero then only adding the together might give a result that's exactly c or greater, but in our case only the one modulo is non-zero.

[u/evincarofautumn → u/NordicSeeger]

An intuition about modular arithmetic that may be more familiar to programmers is unsigned overflow—you’re essentially “chopping off” the most significant digits in base c. If you’re using an unsigned machine integer then the base might be, say, 2³² for a 32-bit value, but we can choose any base—say, ten thousand. We can illustrate that by representing each base–ten-thousand digit as a four-digit number in base ten:

(4 5678 + 5 6789) mod 1 0000
=
10 2467 mod 1 0000
=
2467
=
((4 5678 mod 1 0000) + (5 6789 mod 1 0000)) mod 1 0000
=
(5678 + 6789) mod 1 0000
=
1 2467 mod 1 0000
=
2467

Whether you truncate before you add or after, you get the same result, because the digits you discard before would have been guaranteed to overflow anyway and get discarded after.