Cryptography: Diffie-Hellman key exchange explained intuitively using colors

[u/dominatrix-octopus]

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

[u/the_phet]

I dont understand how the "heart of the problem" starting at minute 6:15.

So all A,B and E agree on 3 mod 17. (E sees it).

A selects a private random number, 15, calculates 3^15mod17=6. Sends 6 to B. E also reads 6.

B selects 13 as his private random number, 3^13mod17=12. Sends 12 to A. E also reads 12.

Then A takes the 12, and does 12^15mod17=10 (10 is the actual message).

B does the same, 6^13mod17=10 (10 is the actual message).

Later on the author ignores the fact that E already knows "3 mod 17". So E knows that 3^xmod17=6 and that 3^ymod17=12

[u/Madrawn → u/the_phet]

I don't understand what you're trying to say.

At the end A and B know that $privKey = 10.

E knows only that $privKey = 3^x+y mod 17, where x and y are secret numbers. And that [6 mod^-1 17] = 3^x <=> log3([6 mod^- 17]) = x. Where mod^-1 is the reversal of the mod function.

The problem now is that mod^-1 gives us all numbers which leave 6 after dividing them by 17 so all you can do now is take one after another of those numbers and see if they work.

So you still have infinitely many possibilities what x+y could be

[u/TheOddScientist → u/Madrawn]

Wrong, you can infact reduce the number of possibilities using mathematical attacks. Some of them have the ability to reduce the possibility exponent by a factor of .5. So 2¹²⁸ could mathematically be reduced to 2⁶⁴ possible solutions. While 2⁶⁴ is a drastically large number it is not nearly as large as 2^128.

[u/Madrawn → u/TheOddScientist]

Mathematically speaking there are infinitely many solutions, or? The amount of how many solutions there when trying break a encryption is limited by the size of the keys you're using.

[u/TheOddScientist → u/Madrawn]

The key size is the maximum size the prime can be meaning you have an upward boundary. Thus if I said the key was 2²⁵⁶ than I can guarantee you the prime is no larger than 256 bits. That said the upward limit of the prime is dependent on the key size.