Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The animated elliptic curve

curves.ulfheim.net

Post reply on HN
Print view View original

31–40 of 62 posts

Re: The animated elliptic curve

#31

Post by edflsafoiewq »

Vecr wrote: post #26
edflsafoiewq wrote: post #24

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.

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?

Re: The animated elliptic curve

#32

Post by max_likelihood »

syncsynchalt wrote: post #2

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

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!

Re: The animated elliptic curve

#33

Post by dreamcompiler »

syncsynchalt wrote: post #28
dreamcompiler wrote: post #25

Earlier quoted context omitted.

> 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…

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.

Re: The animated elliptic curve

#34

Post by edflsafoiewq »

max_likelihood wrote: post #32
syncsynchalt wrote: post #2

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

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!

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

Re: The animated elliptic curve

#35

Post by christoph »

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

Re: The animated elliptic curve

#36

Post by [deleted] »

max_likelihood wrote: post #32
syncsynchalt wrote: post #2

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

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!

[deleted]

Re: The animated elliptic curve

#37

Post by syncsynchalt »

Vecr wrote: post #26
edflsafoiewq wrote: post #24

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

Re: The animated elliptic curve

#38

Post by syncsynchalt »

max_likelihood wrote: post #32
syncsynchalt wrote: post #2

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

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!

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), which is 34, and multiply by that instead. This is explained at 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

Re: The animated elliptic curve

#40

Post by adgjlsfhk1 »

edflsafoiewq wrote: post #31
Vecr wrote: post #26

Earlier quoted context omitted.

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.

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.
Post reply on HN