In the past 5 years I've seen maybe a dozen "how elliptic curves work", but this is the first to actually illustrate how they work on a small field. I think that's key to understanding, seeing it in a small enough field that you can literally see all of the points. Nicely done.
If you want to keep going, as an advanced beginner I'd like to see:
Arbitrary bigint math - how do you do Exp/Sqrt with arbitrary sized ints? (I'm familiar with two crypto libs that do this, and MPIs & branches confuse me).
Second: why is C25519 faster than SecP256R1 or BrainPool? maybe some insight there? (Isn't Ed25519 the signature name? and X25519 the ECDH name?)
> this is the first to actually illustrate how they work on a small field
That means a lot, thanks! That was my design goal with the page: figuring out the best way to get the idea across _without_ the user having to read a lot of text and stare at the wall until they got it.
I've been casting around for the next idea to do a visualization of, adding yours to the list.
(as for a partial answer your second question: the answer is going to be that Montgomery curves like Curve25519 have a method [Montgomery ladder] to quickly and timing-safely calculate only the x values of point multiplication. Faster _and_ more likely to be implemented securely than NIST curves, by design. Unfortunately I don't know the details of BrainPool, yet?)
Yes, Curve25519 is the curve itself (and associate params), Ed25519 is the signature system implemented on top of C25519, and X25519 is the ECDHE mechanism implemented on top of C25519. This page talks mostly about the C and a little of the X, and doesn't go into Ed.
I noticed this problem with other images too. Sometimes animations change too fast, you see points moving, you look at them, but at the same time the formula changes, and you miss it. Especially bad when the formula is written under the image, far away from moving points.
Basically, you should not have several things changing in different places at the same time because human can only focus at one point. Maybe it would be better to add pauses in the sequence, animate one thing, wait a little, then animate other thing. Let the user stop and think a bit about what he/she have seen.
For example, in the image "Repeated addition of a point P" the points and lines are constantly moving, and I don't have time to look at the formula. I see that it is changing, but I cannot read it while looking at the animation. Maybe it would be better if the points stopped moving for a while, then the formula would change, then you give some time to read and comprehend it and then points continue moving.
Or maybe you could write all the formulas on the side, and have a box or selection moving over them. This way the viewer can see how the formulas are related to each other and doesn't have to remember previous ones.
Also, in the image "Point addition is associative and commutative" formulas seem to be random and do not illustrate anything. For example, I see 5P + P = 6P, then 2P + P = 3P, then 6P + P = 7P. So what it should mean?
Maybe a better way to illustrate these laws would be to have two images that produce the same result, for example P + 6P = 7P and 3P + 4P = 7P. It is easier to compare images side-by-side.
Instead of percent sign it might be better to use "mod" as percent sign is understood only by programmers but not by people familiar with mathematical notation.
To illustrate addition you might use a circle (or an ellipse, or even a square, why not) instead of a straight line. This way the wrapping behaviour would be more obvious. To illustrate multiplication, you could draw several sequential arcs (so that the multiplication is represented as several additions). And for negation, two arcs extending in the opposite direction from zero.
I don't understand how to illustrate inverse numbers though. Maybe several arcs that start at zero, end at 1 and number of them is the inverse value?
For the last illustration it definitely would help if it had some key points on the side, showing what we have done and what we are doing now.
I can imagine that play/pause/step buttons could help a lot (for all of the animations), so each reader could "slow it down" manually and take all the time they need.
Ah, hmm. Every animation on the page does have a play/pause _except_ the exchange demo (laugh). I’ll play around with having it pause itself at key points and/or giving it a step button.
> Arbitrary bigint math - how do you do Exp/Sqrt with arbitrary sized ints? (I'm familiar with two crypto libs that do this, and MPIs & branches confuse me).
I solve that problem by using Common Lisp. Because arbitrary bigints are built-in, that's a big chunk of the problem you don't need to worry about. You still need to write a Montgomery multiplier (because otherwise you'd fill available RAM or the divisions would slow everything to a crawl) but that's straightforward. Common Lisp makes exploring crypto algorithms easy.
Note that it's not usually safe to use a language's built-in bigint for crypto like this because it's not time constant - for performance reasons smaller numbers will compute more quickly than larger numbers.
Instead you'll need a fixed-size bigint lib with constant time guarantees.
Completely agree. For deployment I'd strongly prefer a well-tested library with good side-channel protection rather than rolling my own. I use Common Lisp for researching and understanding algorithms.
Very nice page BTW. I've written C25519 code and I now understand my own code better because of your logical, step-by-step presentation.
Great, but that's not an explanation that adds knowledge to the discussion. I mean, Python and JavaScript both have BigInt libraries and are trivial to use.
I want to know HOW they work, especially in C, since that's what the majority of popular crypto libraries are written in.
I've cobbled together a few. It's half interesting, and half boring.
The boring half is all carry-the-one manual operations that are very much like the addition, multi-digit multiplication, and long division that you learned at a classroom chalkboard.
The more interesting is things like modular exponentiation: there's a trick to computing n^e%p for large values, https://en.wikipedia.org/wiki/Modular_exponentiation goes into some detail. It's an operation used in both RSA and public curve cryptography.
I once emailed Grant from 3b1b and asked if he could explain convolution. Not neural-net convolution, but transfer convolution you learn in linear systems: e.g. f * g where you flip and slide g over f.
His short response: "That's too boring." I was a little miffed. Well, yeah, ECC is boring too, until someone like you makes cool graphics.
My broken record take on this stuff is that whatever value there is in visualizing elliptic curves, there's more intuition to build just by playing with the curve formulae directly (it's pretty basic math) and seeing how the operations work in code. I don't have the math background to back this up but my understanding of the group rules is that they're --- at least for the application we're using them in --- a little arbitrary.
For what it’s worth, in the math context (not thinking about applications), the group law is extremely natural. Every variety has an associated group called the Picard group tells you something about geometry of the variety. But for elliptic curves, it turns out there is a bijection between the complex points on the curve and the elements of (the degree 0 subgroup of) its Picard group, so it inherits the group structure this way. This is the same group structure as the usual one defined explicitly. I might write more about this when I get home.
To expand a little on top of that, you can think of Picard group of a variety as a group of linear combinations of codimension 1 subvarieties. For a 9-dimensional variety, these will be a dimension 8 subvarieties. To connect this huge free group to geometry of the original variety, we introduce certain constraint equations, i.e. we set certain linear combinations to equal to zero. These zero combinations are set to be those combinations that are obtained by intersecting the variety with a (codimension 1) hyperplane: if you take an embedded n-variety, and intersect it with n-1 dimensional plane, you typically get a result that’s a finite union of n-1 subvarieties. One can specify assignment of intersection numbers to each of these varieties, so that eg if a hyperplane intersects a variety “cleanly across” (transversally), the intersection number (and so the coefficient in the constrain equation) is 1, whereas if the intersecting hyperplane is tangent along the intersection, the intersection number will correspond to the degree of tangency (eg. the line y = 0 intersects the parabola y = x^2 at the origin with the intersection number (tangency degree) equal to 2).
Now, if the variety in question is a curve, the codimension 1 subvarieties will be of dimension 0, that is, finite sets of points. Moreover, if the curve is of degree 3, then hyperplanes (lines) will intersect it in exactly 3 points (counting the tangent intersections properly). Thus, we will get a bunch of constraints of the form:
P + Q + R = 0
This makes our huge group of linear combinations into rather simple group of points: take two points, P and Q. Run line across them, take third point of intersection: this is the negative of the sum P + Q. This is the procedure shown on the animations of the OP.
The point of this is that none of this is arbitrary: it’s just a lucky coincidence that happens only in dimension 1 and degree 3. One can introduce group structure on some other complex curves (which will actually look to us like surfaces), but it is not nearly as straightforward.
That's true for people whose verbal intelligence exceeds their spatial intelligence but might not be true for everybody. As for the importance of understanding eliptic curves... perhaps people would be best served by thinking of them as a black box discrete logarithm problem.
This is really great! I was fortunate enough to do my master's under a professor who included these visual representations in his lectures. I loved enough to write my thesis on the next step generalization, hyperelliptic curves.
As an algebraic geometer, I have a minor correction: The graphic "examples of elliptic curves" features the singular curve y^2 = x^3. This is not an elliptic curves, because by definition elliptic curves are smooth.
Good spotting. I actually based that animation on the grid of sample curves at https://en.wikipedia.org/wiki/Elliptic_curve , which includes A=B=0 in the illustration but makes the point it's not a valid curve.
I didn't think anyone would notice/care, but I'll tweak it to skip over that example.
Ah, I tried to trim the page down as much as possible, but there's a million tangents like this I could have gone down.
Each point that you pick is going to have a different number of times it can be added to itself before it lands on a point that has the same x-value but different y-value, and then the "point addition" operation draws a vertical line and the point goes to infinity. The number of times you can add a point to itself before it happens and the cycle resets is called the point's "order".
Most of the points on the graph will repeat themselves after less than a dozen times. The one I picked repeats itself after 72 points, which is great because that's every point on the curve. I chose it by writing a little program that tried each point and returned the best one.
Compare that to a "real" curve like Curve25519: it has the base point at x=9 and can repeat itself over 2^252 times before repeating. The author of that curve used a different technique to find the point's order (obviously he didn't try adding the point to itself a trillion^6 times) but the idea's the same.
That's also where had to scroll up again; where do Alice and Bob know P from?
That's pre defined public knowledge, right? It belongs to the curve they use.
Many many thanks for this brilliantly depicted explanation!
Ot: I also looked up ulfheim after I realized your first name is Michael, not Ulf.
"ulfheim" is an old domain name that I've had for decades; there's a little explanation on my home page but the short version is that it's from an old BBS handle.
Unfortunately a few years ago a racist hate group also started using the name for their own purposes. Today I've started the process of moving all my hosts to a new domain name, xargs.org .
Thank you so much for creating this! Under the Curve61 point addition example, I was trying to follow the formula for adding two points: P:(x1, y1) + Q(x2, y2) = R(x3=l^2-x1-x2, y3=l(x1-x3)-y1) where l=(y2-y1)/(x2-x1). I tried to use the example P:(5, 7) + 23P:(2, 24) = (226/9, 2888/7) != 24P:(59, 55) and was wondering where I've gone wrong? Appreciate your response!
After a few missteps where I transcribed the vars wrong (laugh) I wrote out the calcs and was able to reach the correct result. Here's my step-by-step process, hope this helps!
It's great! Minor correction: "In real numbers there are two square roots for EVERY non-zero number. The same is true in Fp...." "...only half the non-zero members of Fp have square roots"
could you correct anything wrong in my understanding?
so we can create an isomorphism(?) between the field (Z_61, +, *) and points on a modular elliptic curve with a base point P using function g:= g(k) = k * P
g(k) is fast to compute with the doubling method, but the inverse requires brute force. Even if you know k_a * P and k_b * P, computing k_a * k_b * P is hard.
However, if you know k_a or k_b (either private key) you can easily find k_a * g(k_b) = k_b * g(k_a) = k_a * k_b * P.
a mitm could just completely impersonate both parties decrypting and re-encrypting in both directions... unless at least one of the public keys was published through a secure channel like a certificate authority.
Hi, I like it, but one thing I have some trouble with is the transition from the eliptic curve to the eliptic curve with finite fields. Specifically, I see the curve, as some function y = f(x), but then in the next plots it looks like a scatter plot and I do see the points of the field, being the output of the curve, but I can not really see what happended to the curve itself. Did the curve become the field?
I worked a few months during my PhD on Seiberb-Witten theory, a specific supersymmetric quantum field theory that undergoes symmetry breaking (Higgs like, due to the scalar field) and the resulting moduli space (space of parameters) can be understood with elliptic curves!
A monument of theoretical physics and mathematics!
This visualization is incredible. In ten seconds, it gave me a stronger intuition for why cyclic groups are so important than when I took abstract algebra and cryptography in college. Thank you!
What is the reason for using elliptic curve groups in crypto? Are they just the best known groups with efficient computation and not-known-broken security, or is there a deeper reason?
Very compact public keys and private keys, reasonably fast operations, less reliance on very good random number generation/bad keypair rejection than RSA, especially for signing where you can have deterministic signatures. I'm not sure constant time implementation is "easier" (probably don't try it still), but it's still somewhat nicer than the bignum and blinding stuff needed for RSA.
One nice thing about X25519 in particular is that if your math operations are constant time (not always a given in bignum libraries...), then the easiest implementation (a montgomery ladder) does happen to be constant time. This was the reason for choosing a Montgomery curve for Curve25519 instead of the more usual Weierstrass curve form.
The ladder procedure is spelled out in https://datatracker.ietf.org/doc/html/rfc7748, though you'll also need to provide your own constant-time conditional variable swap (they give the xor swap trick as an example).
But why elliptic curve groups instead of, I don't know, some subgroup of GL(n, F_p) or something. Is it just that they happen to be the best known groups right now?
I think a lot of the rain might just be that the proof of Fermat's last theorem led to the development of a lot of theory for elliptic curves which happened to show that they work well for crypto.
Since there's been another thread here tonight about Mac OS tools (screenshot utility), I feel somebody needs to mention Mac OS ships with "Grapher", which is a great little tool for doing graphs/equations (and animating them!). Classic Apple stuff. I'm surprised it doesn't get more HN love... Maybe we all forgot it even exists... I must admit, I had until tonight...
If you want to keep going, as an advanced beginner I'd like to see:
Arbitrary bigint math - how do you do Exp/Sqrt with arbitrary sized ints? (I'm familiar with two crypto libs that do this, and MPIs & branches confuse me).
Second: why is C25519 faster than SecP256R1 or BrainPool? maybe some insight there? (Isn't Ed25519 the signature name? and X25519 the ECDH name?)
Greedy of me, but thanks!