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

[Mike Hamburg]

> 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3693 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20161109/f3cc1824/attachment.bin>