An interactive intro to Elliptic Curve Cryptography | Hacker News Reader

An interactive intro to Elliptic Curve Cryptography

growingswe.com

142 pointsvismit200020 comments

As someone with only the vaguest ideas of how cryptography works under the hood (and none at all about how elliptic curves might be useful) this turned out to be the primer I didn't know I needed! I found it really accessible and well-presented.

It's super nit-picky of me to point out: the double and add visualization is a meme among professional elliptic curve guys.

You are in fact drawing a hyperbola between points on an (almost) circular plane. However, you won't find this published anywhere idk why. It's just one of those things you get from spending 3 years in office hours with the 73 year old math professor who's worked on elliptic curves since they became mainstream in the 1980's.

TBH i needed this when i was working on my undergrad thesis with ECC and ECDHA but thanks author for making this. Helped me remember all the fundamentals.

I'm really not into math and got really lost in the second half of "Adding points on a curve". Just don't understand what the author wants to tell me with the grouping and the role of the identity element, which is called infinity but is zero?

However, after looking at the next section and playing with the chart I immediately got the idea where the whole article is heading. Interesting to see how this works.

There is a slight bug on the interaction. When you set P=Q or for example you can't get the one P at the top and Q at the bottom. The lines disappear.

Basically you need the "infinite/zero" point to compensate for a situation when you have two points completely perpendicular to the x-axis. AKA it is not intersecting a third point. So it intersects this special "infinite" point.

And conceptually why you need this "infinite" point is that without it you can't add points together properly.

Say for counter argument instead of doing this "flip or mirror" across the x-axis (in the interaction it is the red dot appearing). And instead the red dot just appears on the same side as the two points being added on the curve - without the flipping.

If P1+P2 = Q instead of this Q' that is flipped. And P2+Q = P1

If you try and add P1+P2+Q you would get either Q+Q or P1+P1 depending on if you did (P1+P2)+Q or adding up P1+(P2+Q) which are not equal.

so you need this red dot flipping thing happening in the interaction. However, if you have this flipping that means P1+P2 = Q' which is the mirror flip of Q.

So Q'+Q need to equal this special infinite/zero point to ensure associativity works.

Just to toss on some info you might already know, the mention about grouping is related to group theory. [0] If a set satisfies those 3 axioms, there's some assertions you can build off that are common to all group theory sets, and having an identity element is one of them. It's weird that it's NOT zero, but in this case, infinity behaves LIKE zero. (Imagine going infinitely along the curve on the x-axis towards the open part of the curve, so therefore going infinitely up/down the y-axis. At somepoint, you're essentially have a vertical line between the original point, and your infinitely far away point, which points at the exact opposite side of the curve, which reflects back to the original point.) For natural numbers, zero is the identity, since X + 0 = X, in the same way P + infintelyfarawaypoint = P in this set.

To use a dumb analogy, it's polymorphism where your interface is something like regular old natural numbers: as long as your class behaves like natural numbers in some key ways, you can pass them to any add()/subtract()/multiply() functions relying on that behaviour.

[0] https://en.wikipedia.org/wiki/Group_(mathematics)#Definition

Seeing the below error when visiting the site.

“This site can’t provide a secure connection

growingswe.com sent an invalid response.

ERR_SSL_PROTOCOL_ERROR”

I see more and more of these types of errors, not only for me but also people posting message like GP just did: not necessarily that precise message but they're typically related to the security of the connection to the HTTPS website.

Why is this getting more and more common?

My pet (conspiracy) theory is ISP middle boxes toying with degrading/MITMing SSL.

My pet theory is that:

1. many people use Letsencrypt for website certificates

2. letsencrypt recently stopped automatically sending "It is time to renew your certificate" emails.

3. People (like me) got used to those emails and did not set up their own reminders.

4. The certificates expire and the owner (again like me) does not notice for several days.

Yeah, that's usually what happens. But many of those errors are TLS protocol errors, not expired certs.

An expired certificate causes a different error.

there must be tons of functions that are easy to process one way but almost impossible the other.

i get the feeling there is more to it than finding such a function, but the article doesnt get into that

Would there not be an infinite number?

You can make as many slight variations as you want by creating a specific instantiation of a hard problem with different constants. But we don't know how many meaningfully different hard problems exist.

These are problems that have been studied for many years, that are more-or-less central to mathematics, and where we have good reason to think that an efficient solution would be extremely surprising.

If you have much lower standards, there's going to be infinely many that I can't personally solve. Or if you have impractically high standards, there could be zero hard problems, if they just so happen to all have efficient solutions that we haven't found yet. We can't formally prove any of these are hard.

I'd be very surprised if the number of meaningfully hard problems is capable of being bounded. As a proposition it feels opposite to almost everything else we believe about numbers. But, that's just my naieve view.

I think there's a weak claim that I'm happy to make and then a much stronger one. The set of hard problems in general is vastly larger than hard problems that are considered useful to cryptographers. The latter is very much finite, and hardness in cryptography is rarely a formal affair either. At best cryptographers can prove reductions to problems that they think are hard, but they can't prove the hardness of the problems themselves. We don't know that the ECDLP is hard, for example. And I'd be very surprised if complexity theorists were able to say anything about these kind of hard problem in my lifetime.

For the stronger claim, if you pick a complexity class like NP and assume P!=NP, I'm pretty confident you could find as many problems as you want in NP that aren't in P and that all look meaningfully different from each other. So the claim that these are bounded is probably false. But hard problems in the sense of NP-hardness isn't sufficient to make them useful to cryptographers.

You also need the group structure, ie. a(bG) = b(aG) = (ab)G.

But AFAICT, elliptic curve groups really are the best known groups where DH is hard. The "Why curves win" section talks about it terms of key size, but the reason other groups require larger keys is they have some kind of structure which can be exploited to attack the "hard" direction (eg. in a finite field, the ability to factor over primes can be used to solve discrete logs), so the group size has to go up to compensate.

Please use a variable-width typeface for readability

Reply on news.ycombinator.com