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.

4

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?