What the hell is an elliptic curve?
onlynv.dev
onlynv.dev
Edit: The article has since been edited to disclaim "values are not encrypted realistically" - sure, use small numbers for demonstration purposes etc., but what is being demonstrated here? You've added scare-quotes to "encrypted" but what is the actual intended meaning?
The whole idea of an algebraic expression is to relate x and y (for 2D). What's the simplest relation?
y/x = r => we have a straight line with slope r. Let's add a bit more detail.
(y-b)/(x-a) = r => we shift the origin to (a,b) and check how the line looks.
These relations can also get "self-aware". This is similar to how a rate of change can be self-aware (ex: d/dx f(x) = x). The rate of water drain out from a tap at the bottom of the water tank would depend on the water height which itself affected by the drain out. Something like that.
(y-b)/(x-a) = x => That is a "self-aware" relation, because we replaced r (a constant) with the variable x. So we have a parabola now.
Let's change gears a bit. we will use higher degree for variables
y^2/x^2 = r => For positive values of r, we have a pair of straight lines.
Now, ((y-a)(y-b))/((x-c)(x-d)) = r => What happened? we get a conic.
Let's make it self-aware
((y-a)(y-b))/((x-c)(x-d)) = x => There it is. A cubic equation
Digging deeper, we see that the self-awareness makes the curve to bring the left-side parts to join at finite distance rather than at negative infinity. To understand this, consider the pair of straight lines (y^2/x^2 = r). You might see that it is a pair of straight lines crossing each other. But you can also look at two sharply bent lines touching each other at a point. a conic has a bit smoother turn.
> The ECDLP involves finding the integer k such that P=k⋅G, where P is a point on the curve, G is a known point (the generator point), and k is the ephemeral key. The difficulty of this problem is what makes ECC secure.
So uh. What is P? Why do I want to work it out? What’s G? Why do I know it, or not know it? Also k. I assume I know maybe one of these values, but maybe I know none.
Why does any of this make anything secure? I get, in general, that knowing numbers that someone else doesn’t know is good for me to be good at security with someone else, but is it?
… just not good.
It's not inscrutable, it's missing.
As an example, the function m => m^65537 is a completely useless encryption function over the reals because it's trivial to take 65537-th roots over R (even if the numbers are unwieldy in size), but it's a surprisingly strong encryption function when computed over certain finite groups (i.e. RSA).
Similarly, any ECC scheme defined over real numbers is pretty useless. It only gets interesting when you use a finite field. Unfortunately, the math is less simple that way.
https://media.ccc.de/v/31c3_-_6369_-_en_-_saal_1_-_201412272...
I doubt there has been a smartphone in history that had even the slightest issue with RSA. When thinking of devices with limited resources, we should probably think of smart cards and such.
https://blog.cloudflare.com/a-relatively-easy-to-understand-...
This is completely made up. The name comes from "elliptic integral". From the Wikipedia page on Elliptic Curves:
> An elliptic curve is not an ellipse in the sense of a projective conic, which has genus zero: see elliptic integral for the origin of the term.
https://www.reddit.com/r/puzzles/comments/azf0zo/im_stuck_on...
I feel like I'm missing something in the example below this statement. I can type in 'hello world' and there is no P on the curve in the graph if I zoom it out, just a bunch of points that seem disconnected from the curve itself.
Very roughly speaking, putting the complication of "point at infinity" problem under the rug, a characteristic feature of a EC is that a straight line passing through two points on the curve will pass through a third point on the curve (yes, unless you take a vertical line, point at infinity). So you can define an "addition of points on the curve" : take two points A and B, draw a straight line passing through them, name the third intersection point between the line and the curve C, declare A + B = C (actually there’s a symmetry around the x axis involved for the usual properties of addition to hold, another complication, let's sweep it under the rug too).
(for A = B, take the tangent of the curve at A ; in R you can see that it works because you can take the limit as B goes arbitrarily close to A : that gives you the tangent ; in a finite field that’s less obvious but the algebraic proof is the same)
So k*G is just G + G + ... + G, k times.
If you want more details, your favorite reasoning LLM can do a better job explaining what I’ve swept under the rug.
> The ECDLP involves finding the integer k such that P=k⋅G, where P is a point on the curve, G is a known point (the generator point), and k is the ephemeral key. The difficulty of this problem is what makes ECC secure.
I don't get it?
We're working on a certified course that will should be available at https://quantumformalism.academy/courses. It will cover post-quantum cryptography as well.
Superficial description of what an elliptic curve is, even less than superficial description of what a discrete logarithm is (including absolutely no mention of what it being discrete means) or how that applies to elliptic curves, and there is no mention of finite fields either.
But P on the image isn't on the curve it's at the origin.