The Magic of Math in Modern Cryptography [video] | Hacker News Reader

The Magic of Math in Modern Cryptography [video]

youtube.com

137 pointsgcnaccount19 comments

I prepared this presentation to introduce others to the magical math that secures our digital lives. It is presented graphically so complex topics can be appreciated by the expert and layperson alike.

Presentation topics include:

How to achieve privacy when someone is always listening. (encryption)

How to decide on a secret when everyone is watching. (key agreement)

How to turn one random number into unlimited random numbers. (PRNGs)

How to speak in a way that's impossible to imitate. (digital signatures)

How to help protect data without possessing it. (secret sharing)

How to check proofs that you can't see. (zero knowledge proofs)

How to process data you don't have access to. (homomorphic encryption)

If anyone would like the slides for this presentation, they are available here:

https://docs.google.com/presentation/d/1uXTud6gZaIhJ3aLDuCup...

I loved the "clock-math" to explain away modulo operations. Gonna send this to friends interested in crypto, thanks.

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?

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.

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

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.

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.)

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").

[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.

Bigger question. Why is your username green?

That’s classified.

Taking this question at face value --- HN makes "new" accounts green for a few weeks. This presumably would make a flood of new accounts created to support some particular opinion or post more obviously manipulative (although I've never seen that occur here).

Hah. I always wondered why it was green. I always thought it was flagged or something.

Yeah there was no snark involved in the question. It was weird that it was turbo green.

I forgot this is stack overflow.

There's a search box at the bottom of most pages, and typing "green username" into it will answer your question.

Huh, I never noticed that search box was there. I've just been going to hn.algolia.com forever.

Cease your investigations.

Why do you need to know?

Who are you?

What is your method of proof for these?

Reply on news.ycombinator.com