[easymovet]

I tried out the math for key exchange, 2^y^x=B^x=R=A^y=2^x^y and have a few questions. If a 3rd person followed the same process and said a number out loud, say C, then wouldn't they be able to figure out both x and y? (Caveat I haven't finished the video, just got to slide 12 so far)

wouldn't 2^z^x=B^x=R=C^z=2^x^z and 2^y^z=C^z=R=A^y=2^z^y be true?

[zeroxfe]

Key exchange on its own is susceptible to an MITM attack, which is why you use it along with certs / digital signatures.

[tialaramex]

Yes, I suppose such an attack is either what easymovet was proposing or at least it's the only application.

In a powerful sense what you've got in this case is two secure key exchanges, Alice to Mallory and Mallory to Bob.

Why this distinction? This is what enables us to use digital signatures to solve the identity problem in modern protocols. You encrypt the channel first using this shared secret even though you've no idea who you're talking to, and only then you may bind proof of your identity to this encrypted channel and/or look for proof of the other participant's identity.

If Mallory sits between Alice and Bob, there's no use taking the binding of Bob's identity to the Mallory-Bob channel and showing it to Alice on the Alice-Mallory channel because it's clearly for the wrong encrypted channel and Alice will know she isn't really talking (directly) to Bob.

[ColinWright]

Firstly, this is all being done modulo a big prime, otherwise it's all reversible has no secrecy.

Secondly, it's not at all clear what you're actually proposing here ... you'll need to be a lot more precise about the exact sequence and the exact operations.

[gwillen]

As another commenter mentioned, this is all done modulo some large prime (or, apparently, in some cases, a carefully-chosen composite number with a large prime factor), so 2^y^x=B^x=R=A^y=2^x^y mod p. (Note that mathematicians use "mod" in a notation that is sometimes surprising to programmers. "x = y mod p" means that _both_ x and y are reduced mod p.) The security of this hinges on the difficulty of the "discrete logarithm problem" -- that is, given R = 2^a mod p, it is computationally intractable to find a = log_2(R) mod p (with appropriate parameter choices.)

[bawolff]

[I have not watched the video] Diffie-helman is extensible to 3 people. See https://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange#Op...

I'm not following your equations (you seem to have C=2^y and 2^x at the same time(?)). Generally the way 3 party works is just like 2 party except you do every operation with both other parties, and the resulting secret is 2^x^y^z.

[KMag]

Yes, it's invertible, but the thing is that we lie slightly when we write it like that. Instead of normal exponentiation, we chose an operation where Amdahl's Law screws you over. The simplest choice for this lie is that we perform all of the exponentiations modulo a large prime number.

The best known algorithms for performing the inverse of exponentiation modulo a large integer with at least one large prime factor (called a discrete logarithm) have some steps that parallelize well, but the steps that don't parallelize well still take thousands of years. (Remember that a large prime number has a large prime factor: itself.)

More generally, we can talk about the properties required of this operation we lie about. The two properties we need are quasi-commutativity and the inverse operation being insanely slow. Normal commutativity means f(a, b) = f(b, a), quasicommutativity means f( f( x, a ), b ) = f( f( x, b ), a ).

Another common choice for this quasicommutative operation is multiplication of a point in an elliptic curve by a scalar. Again, it's not the normal integer multiplication we're talking about, which can confuse people. It's called multiplication because it's defined in terms of another operation called addition of two points, and it does follow the normal algebraic rules, allowing you to re-use all of the algebra you learned in elementary school, except that you need to remember every time you write the division sign, you need to remember that that step takes thousands of years even on a multi-million-core supercomputer. With points on an elliptic curve, we usually write points with capital letters and scalars with lower-case letters. a * b * P = b * a * P is the quasicommutative operation with a slow inverse that we use for elliptic curve cryptography.

Remember that with normal integer exponentiation, x^a * x^b = x^(a+b), so all of the normal algebraic rules would still apply if we changed our notation to use logarithmic space and wrote x^a as aX and x^b as bX, and this is the notation usually used when talking about algebraic groups other than integers modulo large integers ("multiplicative groups modulo large integers").