Hacker News Reader

The above argument might feel slightly wrong to people because it relies on the property that (g^a mod p) ^ b mod p == (g^ab mod p). The fact that this holds isn't too hard to figure out, but requires knowledge that pq mod r == ((p mod r) * (q mod r)) mod r, which again isn't too hard to figure out. However, at this point you're asking people to derive two basic number theory properties in a row, and notably "using modulus to write fizz buzz" (which is the level most non-math-major programmers are at wrt to modulus) is not the same thing as knowing how to do basic number theory, and proficiency in the former doesn't imply proficiency in the latter.

>pq mod r == ((p mod r) * (q mod r)) mod r

that's just multiplication in Z_r...?

edit: alright i guess technically it uses homomorphism from Z to Z_r but you don't need to be able to write out the proof to intuit/believe it

This is elitist. The whole point of the OP is to describe it for the "layman", and you've curtly declared yours suitable "for anyone" - an even broader term - and yet now you're claiming it's supposed to be only for programmers, when reality is still further from your claim: That it is for programmers with a certain level of math knowledge (when in fact, ironically, anybody can understand diffie-hellman without needing to know the mathematical terms and notation).

Even allowing that you meant "programmers" originally, "programming" covers a massive field of knowledge sets. For example, I know what exponentiation and modular arithmetic are, but I can't derive the practical implications from your example without further research. I also have no idea what "g" is.

I guess eighth grade arithmetic is elitest now <shrug>

Was feeling briefly superior the purpose of your little half-baked discourse, or did you actually intend to demonstrate something useful as a learning tool? Hard to tell.

Perhaps a simpler way of explaining:

DH relies on the discrete logarithm problem. That means that if I give you g + g + .. + g, where g is added to itself n times, it will be difficult for you to find out what n is.

Both parties share the same prime p, and the same base point g. Then each of them select a random, secret point. Say Alice's secret is a and Bob's is b. Now each of them create their "public key", which is just g + g + g .. a times, and g + ... b times to create A and B, respectively. The (mod p) simply means divide the result by p and take the remainder as the answer.

Now if I am Alice, my secret is a, my public key is A. Bob sends me B = g^b (mod p). I exponentiate this with my own secret key to get shared secret = (B)^a = (g^b)^a = (g^a)^b = g^(ab) (mod p)

(mod can be deferred to the end of the calculation or done at each step, without changing the answer)

So you can see that, since the order of exponentiation doesn't matter, when Bob does the same calculation (multiplying his private b with alice's public key g^a) he gets the same shared secret.

I'm using Elliptic Curve variant. There's no "mod". But you got the general idea. Also, all the math is built-in and done natively by the browser.

I have no idea what this means, personally. I did understand the math and its practical implications long ago: I started with the paint-mixing example, which helped a lot, and went from there.

Note that I'm using the Elliptic Curve Diffie-Hellman (ECDH) exchaneg, which is an additive group. That's how I can get the shared keys down to a small size.

A group is a group. Doesn't matter whether you call it additive or multiplicative. So DH doesn't change since either way g^a and a*g are both defined as repeated action of g on g via the group operation.

ECDH has smaller keys because the attacks are (until now) weaker and not because you're using an additive cyclic group.

Yes, just do not write (mod p), as it can be misleading to the reader. A mathematician doesn't care, but in RFCs they call the (mod p) groups a "prime group" to differentiate it from the Elliptic Curve group. (In fact, I think they call them "prime fields", not merely groups).

I think the keys can be smaller because every random coordinate is a valid value (valid key), but in the case of RSA, valid values are more sparse.

I think it should also explain why this is secure. It may not be obvious that why you can't just compute the logarithm and get the shared key.

I'm the author. If you are referring to my page, the Developer notes provide all the info you need, and the source code is trivial. I've placed all the encryption stuff in a barebones open source library that you can read on GitHub. This makes the remaining source code in the page trivial.

I don't think I can explain to a layman without math backround why it is secure. So I have kept it simple.

What is g here?

Unfortunately I had to check it as well, and g seems to be a generating element of a finite cyclic group G

https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exc...

Diffie Hellman Key Exchange is performed over a cyclic group. That's just a large set of elements that wrap back around to each other. So for example the integers mod 7 is {0, 1, 2, 3, 4, 5, 6}. A generator for this group is any element that you can continuously add to generate the whole group, for example: 1.

In the case of DH, g is some such element.

p needs to be prime because...?

Reply on news.ycombinator.com