Mike, I'm saving this forever, this is gold. Thank you! On Wed, Nov 9, 2016 at 3:35 AM Mike Hamburg <m...@shiftleft.org> wrote:
> > > On Nov 8, 2016, at 5:23 PM, Ron Garret <r...@flownet.com> wrote: > > > > > > On Nov 8, 2016, at 4:00 PM, Trevor Perrin <tr...@trevp.net> wrote: > > > >> On Mon, Nov 7, 2016 at 12:51 AM, Ben Smith <hyperellip...@gmail.com> > wrote: > >>> > >>> Here's a rather longish explanation that might be helpful (I hope). > >>> It's sort of a geometric complement to Mike's reply on curve shapes. > >>> It should really be a link to a blog post, I suppose---but in the > >>> absence of a blog, I'm posting it here. > >>> > >>> What I'm aiming to do here is > >>> * Connect the Edwards equation with a Weierstrass equation (actually a > >>> Montgomery curve); > >>> * Show how the usual magic birational map appears in a more natural > way; > >>> * Resolve Ron's apparent degree-3-vs-degree-4 incompatibility; and > >>> * Explain how we can ignore the whole resolution-of-singularities > >>> issue by simply never having singularities in the first place. > >>> > >>> (If the geometric language goes over your head, don't worry; there > >>> will be variables and equations the whole time to to show what I mean. > >> > >> > >> Thanks to you and Mike, that's awesome! > >> > >> I wonder what the easiest path is to *learn* the geometric language > >> that you and Mike are using, to the point of following along here? > >> > >> A lot of crypto-interested people can roughly understand RSA and DH, > >> and would like to understand ECC, but get lost with terms like > >> (skimming recent mails): > > I honestly don’t know! But, glossary: > > >> twist > > A twist TC of some curve C looks different over whatever field F you’re > working with, but the same over an algebraically closed field. That is, C > and TC are equivalent under a change of variables, but that change of > variables uses a value like sqrt(-1) that’s not actually in the field (but > is in some extension field). > > Therefore TC and C (considered over F) have different sizes and different > cryptographic properties. > > >> torsion > > An n-torsion point is a point P where nP = 0. For example, Curve25519 has > a 2-torsion point at (0,0). > > >> homogenous > > A polynomial or equation is homogeneous if every term has the same > degree. So x^2+1 isn’t homogeneous, but x^2+z^2 is. > > >> birational > > A birational map is a 1:1 change of variables. More specifically it’s a > rational function f :: (x,y) -> (x’,y’) where both f and its inverse are > (pairs of) ratios of polynomials in x and y. > > >> isogenies > > Isogenies are substitutions or changes of variables that aren’t 1:1, but > are still defined by ratios of polynomials. > > For example, if you take any point P on Curve25519, then the x-coordinate > of 2P is necessarily square. Call its square root “s”. Then there is a > curve (a Jacobi quartic) > > J : t^2 = s^4 + As^2 + 1, > > where (s,t) -> (x,y) by the map (x=s^2, y=ts). This is almost an isogeny > from J to Curve25519, but not quite, because (at least as traditionally > defined) J would have its neutral point at (0,1), and that doesn’t map to > Curve25519’s neutral point. The actual isogeny is basically the same but > with an inversion somewhere. > > Every isogeny \phi has a “dual isogeny” \psi, such that \phi(\psi(P)) = > n*P for some fixed n. Roughly, that n is the “degree" of the isogeny. The > above isogeny is a 2-isogeny, once you fix up the problem with the base > point. > > >> singularities / nonsingular > > A singularity is a point where the derivative of the curve is not > defined. For example, the graph y^2 = x^3 has a “cusp" at (0,0). This is > why that curve is not considered elliptic. > > >> affine > > Not projective. > > Affine function: a linear function with an offset, eg x,y -> x+3y+7. > > >> projective (plane, closure, line) > > Projective line: say you’re talking about the slope of a line. It could > be a real number, or it could be infinity (and +infinity and -infinity are > the same: they both mean a vertical line). The set of possible slopes is > the projective line. More formally, it’s ratios x:z where x and z aren’t > both zero, and x:z = x’:z’ if and only if xz’ = x’z. That is, scaling x > and z by the same value gives the same ratio. > > Projective plane: x:y:z, not all zero, kind of like the projective line. > > Projective closure: given a curve, add a z-coordinate to make it > homogeneous. Eg y^2 = x^3 + ax + b ==> y^2 z = x^3 + axz^2 + bz^3. This > lets you extend the domain of the curve from the affine plane to the > projective plane: it’s now the set of ratios x:y:z (not all zero) where y^2 > z = x^3 + axz^2 + bz^3. It’s important that you made it homogeneous, so > that scaling x,y, and z by the same factor won’t change whether the > equation holds (it will scale the LHS and RHS by the cube or whatever of > the factor). > > It’s usually more natural to talk about geometric objects like elliptic > curves in a projective setting. Conveniently, it’s also faster to > implement them this way. > > >> genus > > Ben can explain this one better than I can. It’s sort of a measure of how > complicated a curve is, with genus 0 being a circle or line, genus 1 an > elliptic curve, genus 2+ hyperelliptic. > > Genus is pretty complicated to explain and compute. For example, the > not-quite-elliptic curve y^2 = x^3 has genus 0. > > >> embedding > > A function from a smaller object into a larger one that preserves the > structure of the smaller object. For example, a line can be embedded into > a plane by mapping it to some line in that plane. > > > order > > For groups, and for elliptic curves, the order is the number of elements. > > But the order of a group element G is the least positive integer n such > that nG = 0. (Written as multiplication, such that G^n = 1.) Blarg. > > > cofactor > > Usually we want to use a group with large prime order q. If it instead > has a composite order h*q, where q is the part we’re using for crypto, then > h is the cofactor. > > > characteristic > > Of a field: the number of times you have to add 1 to itself to get 0. For > F(p) where p is prime, this is just p. But there are also eg binary fields > GF(2^n), which have characteristic 2, and GF(3^n) etc. (GF stands for > Galois Field; sometimes just written F(2^n).) > > > trace of frobenius > > This is just p+1-#E, where #E is the order of the curve and p is the order > of the underlying field. It’s called that because in algebraic geometry > it’s the “trace" of a map called the Frobenius map. The reason behind the > name isn’t important for most purposes, but it becomes clear when you try > to compute #E. > > > Another thing that has been driving me nuts for years is Theorem 2.1 in > the Curve25519 paper. I understand what it *says* but I still don’t > understand what it *means*. > > It means that Curve25519 is symmetric with a reflection across the > x-axis. The scalarmul map P -> nP preserves the symmetry. Also, the trick > of representing infinity by 0 works, because any scalar times either of > those points is still 0 or infinity. This means that x-only scalar > multiplication is well-defined. > > > rg > > Cheers, > — Mike_______________________________________________ > Curves mailing list > Curves@moderncrypto.org > https://moderncrypto.org/mailman/listinfo/curves >
_______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves