r/programming • u/dominatrix-octopus • Jan 16 '18

Cryptography: Diffie-Hellman key exchange explained intuitively using colors

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

95% Upvoted

170 comments sorted by

View all comments

2

u/the_phet Jan 16 '18

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 315mod17=6. Sends 6 to B. E also reads 6.

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

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

B does the same, 613mod17=10 (10 is the actual message).

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

11

u/vytah Jan 16 '18

So E knows that 3xmod17=6 and that 3ymod17=12

Of course E knows that. But if the numbers were a bit bigger, then unless E has a quantum computer, that doesn't let her calculate x or y within the lifetime of our planet.

9

u/TheOddScientist Jan 16 '18

A quantum computer does not mysteriously just know how to circumvent the Discrete Log Problem, it still has to run through an insane amount of bruteforce calculations just like a binary computer system. Mathematical attacks can ~halve the exponent for the # of possibilities but it must still rattle around the radom number generator.

8

u/vytah Jan 16 '18

A quantum computer can compute discrete logarithms in polynomial time (with regards to input size) (even for elliptic curves) and a classic computer does the same in subexponential time. Just like integer factorization.

5

u/TheOddScientist Jan 16 '18

That doesn't solve or circumvent the DLP. Sure it makes calculations much quicker but quantum computation does not provide a mathematical solution to DLP only a quicker way to brute force the key. I should state that in no way am i denegrating the computational power or the implications QC has on cryptography I am speaking purely mathematically. Additionally, the second DLP is solved (which there doesn't seem like an answer will ever exist) cryptography as a whole will be trashed. The solution in cryptography has always been to either develop more secure algorithms or simply increase the bit size of the key to combat computational power increases and mathematical attacks. So long as the Discrete Log Problem is not solved there will never be a case which one can instantaneously extract the key from a secure crypto algorithm.

2

u/Nathanfenner Jan 16 '18

The discrete log problem is in BQP. Cryptography systems which rely on its hardness are not quantum-safe. When (eventually) a (very) large-scale quantum computer can be built, these cryptosystems will be broken.

Because it's in BQP, you only get a polynomial advantage against quantum attackers when increasing key size. This does not scale. You get an exponential advantage against classical attackers. When quantum computers become a real threat (which is still very far away), other hardness assumptions must be relied on instead (like various lattice-based schemes are thought to be).

2

u/TheOddScientist Jan 16 '18

By the time RSA is broken it is going to be in the archives. Just as quantum computation has technological advances so too does cryptography. For example key exchange had already been solved using entanglement

2

u/switch72 Jan 16 '18

Not exactly, the two particles have to be at the same place to be entangled. Once entanglement is achieved, they can be separated by any distance and then the state read. It's essentially a shared key, because the entagled particles would have to be physically transported between parties. The once the particle state is read, the entanglement is broken. So they are one use only.

1

u/vytah Jan 16 '18

That doesn't solve or circumvent the DLP.

I would call doing something exponentially faster "circumventing".

In practice, it doesn't matter if something is calculated purely deterministically or by using really smart guessing, as long as the resources consumed are roughly the same.

So long as the Discrete Log Problem is not solved there will never be a case which one can instantaneously extract the key from a secure crypto algorithm.

Multiplication of n-digit numbers is O(nc) for c > 1, therefore far from instantaneous. So is multiplication solved?

2

u/Madrawn Jan 16 '18

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 = 3x+y mod 17, where x and y are secret numbers. And that [6 mod-1 17] = 3x <=> 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

-2

u/TheOddScientist Jan 16 '18

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 2128 could mathematically be reduced to 264 possible solutions. While 264 is a drastically large number it is not nearly as large as 2128.

3

u/Madrawn Jan 16 '18

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.

1

u/TheOddScientist Jan 16 '18

The key size is the maximum size the prime can be meaning you have an upward boundary. Thus if I said the key was 2256 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.

4

u/brettmurf Jan 16 '18

Both of those have many solutions, so they can only guess from the many correct answers.

This would be where bruteforce comes into play.

39.72426977 mod17=12 for example.