7 ms·
The animated elliptic curve
- nigma1337 4y agoI've spent quite some time on things like cryptohack, and speaking to my cryptography friends, but ECC has never actually stuck as well as this does. Brilliantly done!
- deleted 4y ago[deleted]
- syncsynchalt 4y agoAuthor here, let me know if there are any questions or comments!
- pvillano 4y agocould 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.
- pvillano 4y agoa 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.
- proofrock 4y agoVery nice work! Useful and informative. I’ll spread it at work.
- 2mol 4y agoThis 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. You might be interested in the fact that a variant of this visual representation still works: https://www.juricho.me/files/masterarbeit-hyperelliptic_curves-juri.pdf https://www.juricho.me/files/masterarbeit-hyperelliptic_curv...
- sadjad 4y agoGreat article and great visuals! One very minor missing detail is how the base point P is picked.
- syncsynchalt 4y agoAh, 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.
- yonrg 4y agoThat'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.
- syncsynchalt 4y ago"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 .
- 4y ago
- red_trumpet 4y agoNice work! 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.
- syncsynchalt 4y agoGood spotting. I actually based that animation on the grid of sample curves at https://en.wikipedia.org/wiki/Elliptic_curve 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.
- acer4666 4y agoIt'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"
- syncsynchalt 4y agoTook me a few re-reads to see what you mean. Will fix!
- mathgenius 4y ago> associative: addition of additions has the same result as adding the points individually You should mention the generic rule: P+(Q+R) = (P+Q)+R, even if it's much more tricky to show than P+(P+P)=(P+P)+P.
- syncsynchalt 4y agoGood idea, let me tweak that... (pushed)
- max_likelihood 4y agoThank 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!
- edflsafoiewq 4y agoYou haven't gone wrong, those are equal in F_61. 226 / 9 = (226*34) / (9*34) = 7684 / 306 = 7684 / 1 (since 306 = 1 mod 61) = 59 / 1 (since 7684 = 59 mod 61) I think y3=2888/7 is a typo for 2888/27, which also equals 55 by a similar calculation (1/27 = 52 mod 61).
- max_likelihood 4y agoThat was definitely a typo. Thanks for your response!
- deleted 4y ago[deleted]
- syncsynchalt 4y agoAfter 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! https://gist.github.com/syncsynchalt/ed02e39ad7adc8580b1086f6e34d8ab1 https://gist.github.com/syncsynchalt/ed02e39ad7adc8580b1086f... Looking at your comment the disconnect seems to be at the division step: when performing a division such as 226/9, look up or calculate the multiplicative inverse for 9 (you can use the table at https://curves.ulfheim.net/inverse61.html https://curves.ulfheim.net/inverse61.html), which is 34, and multiply by that instead. This is explained at https://curves.ulfheim.net/#division-multiplicative-inverse https://curves.ulfheim.net/#division-multiplicative-inverse In F61, 226/9 = 226*34 = 7684 % 61 = 59. In F61, 2888/27 = 2888*52 = 150176 % 61 = 55. (you can also proactively reduce those numerators and calculate with some smaller numbers): (226%61)/9 => 43/9 (2888%61)/27 => 21/27
- c-fe 4y agoHi, 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?
- sbf501 4y agoIn 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?) Greedy of me, but thanks!
- syncsynchalt 4y ago> 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.
- geoduck14 4y agoI'll agree with GP - this is the best I've seen, too. If I may offer a critique: the final example with Alice and Bob went too fast. I watched it 5 times and I'm a bit lost. I'll rewatch it again later
- syncsynchalt 4y agoThat’s good feedback. There’s a lot of steps, where should I slow it down? (“All” is an acceptable answer): - Alice computes A - Bob computes B - there’s a 3? second delay - Alice and Bob simultaneously compute the shared secret by multiplying their private key by the others’ public key
- tptacek 4y agoMy 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.
- whatshisface 4y agoThat'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.
- hutchisonc 4y agoFor 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.
- tptacek 4y agoYes please.
- jacobolus 4y agoIf elliptic curves seem tricky, you can follow the same idea with conics https://arxiv.org/pdf/math/0311306.pdf https://arxiv.org/pdf/math/0311306.pdf https://www.researchgate.net/profile/Shailesh-Shirali/publication/305987450_Groups_associated_with_conics/links/59ed232aa6fdccef8b0dc5ed/Groups-associated-with-conics.pdf https://www.researchgate.net/profile/Shailesh-Shirali/public...
- phailhaus 4y agoThis 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!
- alpineidyll3 4y agoBeautiful
- immmmmm 4y agoI 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!
- DesiLurker 4y agoSite is broken for me
- syncsynchalt 4y agoSorry to hear that, let me know what OS/browser you're seeing the problem on, and I'll see if I can figure it out.
- DesiLurker 4y agoits fixed now, likely it was hacker-news'd.
- edflsafoiewq 4y agoWhat 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?
- Vecr 4y agoVery 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.
- edflsafoiewq 4y agoBut 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?
- adgjlsfhk1 4y agoI 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.
- syncsynchalt 4y agoOne 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 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).
- christoph 4y agoSince 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...
- junon 4y agoThis is fantastic. Very well done.
- pieter_mj 4y agoAbsolutely awesome. I would also like to see an elliptic curve unsuited for cryptography and the reasons why.