5 ms·

Author here, let me know if there are any questions or comments!

pvillano 4y ago
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.
- pvillano 4y ago
  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.
proofrock 4y ago
Very nice work! Useful and informative. I’ll spread it at work.
2mol 4y ago
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. 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 ago
Great article and great visuals! One very minor missing detail is how the base point P is picked.
- syncsynchalt 4y ago
  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.
- yonrg 4y ago
  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.
  - 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 .
    - krapp 4y ago
      Yeah, unfortunately Nazis and neo-Nazis have ruined Norse mythology for everyone else.
red_trumpet 4y ago
Nice 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 ago
  Good 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 ago
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"
- syncsynchalt 4y ago
  Took 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 ago
  Good idea, let me tweak that... (pushed)
max_likelihood 4y ago
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!
- edflsafoiewq 4y ago
  You 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 ago
    That was definitely a typo. Thanks for your response!
- deleted 4y ago
  [deleted]
- syncsynchalt 4y ago
  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! 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 ago
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?

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.

pvillano 4y ago
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.

proofrock 4y ago

Very nice work! Useful and informative. I’ll spread it at work.

2mol 4y ago

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. 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 ago

Great article and great visuals! One very minor missing detail is how the base point P is picked.

syncsynchalt 4y ago
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.
yonrg 4y ago
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.
- 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 .
  - krapp 4y ago
    Yeah, unfortunately Nazis and neo-Nazis have ruined Norse mythology for everyone else.

red_trumpet 4y ago

Nice 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 ago
Good 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 ago

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"

syncsynchalt 4y ago
Took 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 ago
Good idea, let me tweak that... (pushed)

max_likelihood 4y ago

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!

edflsafoiewq 4y ago
You 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 ago
  That was definitely a typo. Thanks for your response!
deleted 4y ago
[deleted]
syncsynchalt 4y ago
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! 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 ago

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?