[curves] Climbing the elliptic learning curve (was: Re: Finalizing XEdDSA)

[Deirdre Connolly]

Mike, I'm saving this forever, this is gold. Thank you!

On Wed, Nov 9, 2016 at 3:35 AM Mike Hamburg <mike at shiftleft.org> wrote:

>
> > On Nov 8, 2016, at 5:23 PM, Ron Garret <ron at flownet.com> wrote:
> >
> >
> > On Nov 8, 2016, at 4:00 PM, Trevor Perrin <trevp at trevp.net> wrote:
> >
> >> On Mon, Nov 7, 2016 at 12:51 AM, Ben Smith <hyperelliptic at 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 at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20161110/f30ef110/attachment.html>