4 ms·

The public key is like a math answer that is easy to compute if you have the whole equation, but really hard if you only have the answer. Kind of like "what ar

The public key is like a math answer that is easy to compute if you have the whole equation, but really hard if you only have the answer. Kind of like "what are the divisors of 93036637?" You can figure it out, but it requires testing lots of numbers (a brute force apporoach) to figure out that it's only 9391 and 9907. Say Adam sends the public key of 93036637 to Bob. (Note that the public key was chosen to be the product of two primes). Bob chooses a new prime number - say 8867 - and multiplies it in there, too, and the sends it back to Adam. Now we have 93036637 x 8867 => 824955860279 When Adam gets that public key back, he can divide out one of the original two prime numbers (824955860279 ÷ 9907 => 83,269,997) and then send it back to Bob. Bob KNOWS that his secret key was 8867, so he divides that back out to get the shared secret: 9391 (the other half of the original public key). Even though Eve listened to every single number being transmitted: Adam: "93,036,637" Bob: "copy. 824,955,860,279" Adam: "copy. 83,269,997" Only Adam and Bob can know the three prime factors of 8867, 9391, and 9907 without doing brute force division. Brute force division is easy for prime numbers less than 10k, but a sender can choose a prime number that's long enough to satisfy their privacy needs, based on their estimate of Eve's resources. So the bottom line is that the public key is easy to compute if you have the inputs, but incredibly time consuming (brute force) if you don't.

ta8645 3y ago
If Eve is listening in to the data stream you've outlined, it's trivial for her to decode. Adam: (A)93,036,637 Bob: (B)824,955,860,279 Eve: (B)824955860279 / (A)93036637 = Bob's secret of (S3)8867 Adam: (C)83,269,997 Eve: (C)83269997 / (S3)8867 = (S1)9391 Eve: (A)93036637 / (S1)9391 = (S2)9907 Eve doesn't need anything but A, B, and C to easily calculate the rest.
- a1369209993 3y ago
  Yeah, I'm not sure why they used a blatantly broken example, but here: >>> The public key is like a math answer that is easy to compute if you have the whole equation, but really hard if you only have the answer. Kind of like "if 2^x mod 32749 = 29640, what is x?" You can figure it out, but it requires testing lots of numbers (a brute force apporoach) to figure out that it's 12345. Say Adam sends the public key of 29640 to Bob. (Note that the public key was chosen to be two to some known power, modulo a shared and public prime number). Bob chooses a new number - say 22222 - and computes 2^22222 mod 32749, too, and the sends it back to Adam. Now we have 2^22222 mod 32749 => 12883. When Adam gets that public key back, he can raise it to his own private key, 12345, and get (2^b)^a = 2^(b*a) (mod 32749) = 31458. Meanwhile, Bob can do the computation (2^a)^b = 2^(a*b = b*a) (mod 32749) = 31458. Even though Eve listened to both numbers being transmitted: Adam: "29640" Bob: "copy. 12883" Only Adam and Bob can know the result 31458 without doing brute force exponentiation. Brute force exponentiation is easy for prime numbers less than 33k, but a sender can choose a prime number that's long enough to satisfy their privacy needs, based on their estimate of Eve's resources. So the bottom line is that the secret is easy to compute if you have one of the private keys, but incredibly time consuming (brute force) if you don't. <<< There are still some problems with this (really, Finite-Field Diffie-Hellman just generally kind of sucks, even without quantum attacks), but it's basically the right idea.
- dclowd9901 3y ago
  Having now understood how this all works from the Khan Academy explanation, the real magic of all of this are these two things: 1) math that’s hard to do backwards 2) the transitive property of mathematics. Given #1 is basically arbitrary, I think it can be hand-waved in service of explaining the process, which only works because of that transitive property, which I think the person you replied to did a decent job of relating. In these explanations, people are getting hung up on the literal nuts and bolts steps, but simply understanding that we can send parts of a complete equation to each other and let the rules of math sort it out really clarifies the point.
mnahkies 3y ago
This is a good explanation but thought it might additionally be useful to link to https://en.m.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange https://en.m.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_e... as an example of creating a secure channel from an insecure one

ta8645 3y ago

If Eve is listening in to the data stream you've outlined, it's trivial for her to decode. Adam: (A)93,036,637 Bob: (B)824,955,860,279 Eve: (B)824955860279 / (A)93036637 = Bob's secret of (S3)8867 Adam: (C)83,269,997 Eve: (C)83269997 / (S3)8867 = (S1)9391 Eve: (A)93036637 / (S1)9391 = (S2)9907 Eve doesn't need anything but A, B, and C to easily calculate the rest.

a1369209993 3y ago
Yeah, I'm not sure why they used a blatantly broken example, but here: >>> The public key is like a math answer that is easy to compute if you have the whole equation, but really hard if you only have the answer. Kind of like "if 2^x mod 32749 = 29640, what is x?" You can figure it out, but it requires testing lots of numbers (a brute force apporoach) to figure out that it's 12345. Say Adam sends the public key of 29640 to Bob. (Note that the public key was chosen to be two to some known power, modulo a shared and public prime number). Bob chooses a new number - say 22222 - and computes 2^22222 mod 32749, too, and the sends it back to Adam. Now we have 2^22222 mod 32749 => 12883. When Adam gets that public key back, he can raise it to his own private key, 12345, and get (2^b)^a = 2^(b*a) (mod 32749) = 31458. Meanwhile, Bob can do the computation (2^a)^b = 2^(a*b = b*a) (mod 32749) = 31458. Even though Eve listened to both numbers being transmitted: Adam: "29640" Bob: "copy. 12883" Only Adam and Bob can know the result 31458 without doing brute force exponentiation. Brute force exponentiation is easy for prime numbers less than 33k, but a sender can choose a prime number that's long enough to satisfy their privacy needs, based on their estimate of Eve's resources. So the bottom line is that the secret is easy to compute if you have one of the private keys, but incredibly time consuming (brute force) if you don't. <<< There are still some problems with this (really, Finite-Field Diffie-Hellman just generally kind of sucks, even without quantum attacks), but it's basically the right idea.
dclowd9901 3y ago
Having now understood how this all works from the Khan Academy explanation, the real magic of all of this are these two things: 1) math that’s hard to do backwards 2) the transitive property of mathematics. Given #1 is basically arbitrary, I think it can be hand-waved in service of explaining the process, which only works because of that transitive property, which I think the person you replied to did a decent job of relating. In these explanations, people are getting hung up on the literal nuts and bolts steps, but simply understanding that we can send parts of a complete equation to each other and let the rules of math sort it out really clarifies the point.

mnahkies 3y ago

This is a good explanation but thought it might additionally be useful to link to https://en.m.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange https://en.m.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_e... as an example of creating a secure channel from an insecure one