Hacker News new | past | comments | ask | show | jobs | submit login
Elliptic Curves as Python Objects (jeremykun.com)
95 points by ColinWright on May 28, 2017 | hide | past | favorite | 10 comments



This post is part of a series of 8 posts on ECC and its applications, and for those interested you can find all the posts in the series under "Cryptography" here: https://jeremykun.com/main-content/


I really enjoy your blog. When are you going to publish a math book for programmers, covering a broad selection of programming-related math topics? I think you mentioned this possibility in a past blog post. I'd buy it.

I'll also make note of your Patreon:

https://www.patreon.com/user?u=615882


250 pages in, and slowly chugging along. Join the mailing list, if you want updates and a preview (when it's ready): http://jeremykun.us11.list-manage.com/subscribe?u=99aa071e97...


If you like this you may possibly enjoy my blog post about creating an elliptic curve for cryptographic use (for fun): http://blog.bjrn.se/2015/07/lets-construct-elliptic-curve.ht...

I also have a lot of elliptic curve code for Python here: https://github.com/bjornedstrom/elliptic-curve-chemistry-set



this inspired me to write similar code for julia.

https://gist.github.com/ityonemo/2eca5fe5854ca6ef1154c896d79...

One of the really nice things about the julia is (I think) that it should allow you to seamlessly use the same code to transition to finite fields by overloading the / operation.

Also, each time you build a new EC, the typesystem will JIT the A & B constants, so instead of a lookup, it's an immediate constant in the machine code.

The tradeoff with julia is that all concrete types must be leaf types, so you can't overload the standard EC point with the ideal (zero point). On the one hand, that does make your code a bit convoluted - you're effectively unrolling the type checking that python is doing behind the scenes. On the other hand, the performance implications for not having to muck around with complicated type graph traversals should be fairly obvious.

edit: indeed it's fairly easy with a trivial prime field implementation.

https://gist.github.com/ityonemo/c74ebd8a968e5fc7826762bf6a4...


Notice that there is a RosettaCode entry about it:

http://rosettacode.org/wiki/Elliptic_curve_arithmetic


Wouldn't it make more sense to make `point` a factory method on instances of curves?


Personally, I have always found these patterns make more sense in a large-scale engineering context (to avoid others misusing a library) than a primer whose goal is to teach one about math. I don't think anyone would realistically use this code for a production application (it's quite slow, and vulnerable to certain timing attacks anyway)


While dkarapetyan used the term factory, which awakes deep rooted emotions in anyone who learned Java at university, the point is not really one of using a pattern or not (even though the pattern may make sense here).

If you have a curve already, it makes sense to get one of its points. Having a method on the curve class that gives you a point would be just as easy, if not easier, than creating the point and passing in a reference to the curve.

The reason you might use a factory is because we have different kinds of points being returned (Point and Ideal) - why not use a factory do return the correct one? The reason of course, which may not be obvious, is that these are points in a projective space and the ideal point doesn't have an (x,y) representation. (x,y) really means [x:y:1] and the ideal point is [0:1:0].

So using a `factory` is not necessary, as you know when you are creating the point what type it will be (either Point or Ideal) - there is no case where you would get the Ideal and not already know that it is the Ideal (at the point of object creation, that is).




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: