21–30 of 62 posts
A monument of theoretical physics and mathematics!
Earlier quoted context omitted.
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 struct…
Yes please.
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 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.
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?
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?…
> 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…
I want to know HOW they work, especially in C, since that's what the majority of popular crypto libraries are written in.
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?…
> 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…
Instead you'll need a fixed-size bigint lib with constant time guarantees.
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.
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…
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.
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.