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

[Mike Hamburg]

Here’s a quick and slightly sleepy try on curve shapes.  Please correct any errors you see.

Some of the curve shapes have multiple parameters; usually all but one of the parameters are fixed to a small number like +-1 or -3.

I’ll focus on curves over large-characteristic fields.  I will not describe binary curves (F(2^n)) or ternary ones (F(3^n)).  While I don’t believe any attacks are known against such curves, they are regarded as slightly sketchier due to progress on the classical discrete log problem in small-characteristic fields.

A formula for addition on an elliptic curves is *complete* if it has no corner cases that result in the wrong answer.  In general, that wrong answer will be 0/0.  Any algebraic addition formula must have a corner case in some extension field, but for complete formulas there aren’t any in the base field.

I won’t discuss pairings here, or other fancy techniques.  I won’t make a distinction between multiplication and squaring, even though usually squaring is slightly faster.




Short Weierstrass: y^2 = x^3 + ax + b.  Most often a=-3.

Minimum cofactor: 1.

Identity point: (0 : 1 : 0), i.e. infinity in the vertical direction.

This is the classic shape for elliptic curves, used by the likes of NIST and Brainpool.  For fields of characteristic >3, any elliptic curve can be put into this shape by a change of variables.  Most often used with Jacobian coordinates, where y is scaled by z^3 and x by z^2, i.e. y^2 = x^3 + axz^4 + bz^6.  Usually chosen with a=-3, which makes the point doubling formula more efficient.

Short Weierstrass curves are universal, and can have prime order.  Their main downsides are efficiency and completeness.  In particular, complete formulas for short Weierstrass curves are complicated and not very efficient.  The efficiency of point operations are so-so: Jacobian doubles are ~8M, and additions are ~16M.  Projective doubles are ~11M and additions are ~14M, which is usually but not always worse than Jacobian.  However, if the algorithm can be arranged so that the points you’re adding have the same Z-coordinate (“co-Z”), then they become more efficient, on the order of ~6-7M for addition.

When doing a scalar multiply of a single point, an efficient family of algorithms is the co-Z ladder (https://eprint.iacr.org/2010/309.pdf <https://eprint.iacr.org/2010/309.pdf>), which costs 14M/bit if you only want an x-coordinate out at the end, or 16M/bit if you want the y-coordinate too.  These algorithms are very memory-efficient and reasonably side-channel resistant.  So for all DJB likes to badmouth this curve shape, they’re not terrible.  You just have to be really careful to avoid the incompleteness problems.




Montgomery: by^2 = x(x^2+Ax+1).  Almost always b=1.

Minimum cofactor: 4.

The point of order 2 has (x,y)=(0,0).  A point of order 4 has x = +- 1.

The famous Curve25519 has this form.  The main point of Montgomery curves is that for a single scalar-multiply, there is a very simple, fast, memory-efficient and mostly-side-channel-resistant “Montgomery ladder” which computes the scalar multiply in 9M/bit.  Usually, this ladder is only used to compute the x coordinate, but there is an efficient way to recover y as well if you really want to, assuming you know y of the input point.  The Montgomery ladder is relatively easy to implement securely, at least compared to other algorithms.

Usually, Montgomery curves are chosen so that their twist — where b is multiplied by a nonsquare value — is also cryptographically secure.  This is because when implementing the Montgomery ladder, if you take a point on the twist (or rather, an x-coordinate corresponding to a point on the twist, since you don’t usually take y as input) you will get the correct output (but still on the twist).  So if the twist is secure, implementations can still be secure for most purposes even if they don’t check whether a point is on the curve or on the twist.

The main disadvantages are that these curves can’t have prime order, and operations other than the Montgomery ladder aren’t particularly efficient.  Not having prime order is annoying because of standards, and because lots of papers assume that the group has prime order and you have to check whether you need a workaround.

The cofactor is almost always arranged so that there are points of order 4.   IIRC when the underlying field has order 1 mod 4, it is possible to instead have a full complement of points of order 2 (i.e. 3 points of order 2, plus the identity) and no points of order 4, but nobody does this for some reason.  Let’s call this 2x2 torsion, because it makes the group structure look like 2*2*q instead of 4*q.

Note that a curve with 2*2*q torsion is *not a cyclic group*.  This usually doesn’t matter in practice.  Maybe it messes with a couple PAKE schemes if you’re not careful.  It’s annoying for the same reason that cofactor is annoying: there are so many crypto papers that assume G is cyclic, and you have to check whether it matters.





Twisted Edwards: ax^2 + y^2 = 1 + dx^2y^2.  The curve is “untwisted” if a=1.

Reference: https://eprint.iacr.org/2008/013.pdf <https://eprint.iacr.org/2008/013.pdf>
http://iacr.org/archive/asiacrypt2008/53500329/53500329.pdf <http://iacr.org/archive/asiacrypt2008/53500329/53500329.pdf>

Minimum cofactor: 4.  As with Montgomery curves, with twisted (but not untwisted) Edwards curves and p = 1 mod 4, it is possible to have 2x2 torsion instead of 1x4.  As with Montgomery curves, nobody does this.

Identity point (0,1).  For some reason, the identity point is at (0,1) and not (1,0), meaning that the y-coordinate is the more significant one instead of the x-coordinate.

When the terms (d,ad) are both nonsquare in the field, this curve has no points at infinity.  Otherwise, there are points of small order (2 or 4 IIRC) at infinity.  Furthermore, the curve supports fast addition laws that are complete when they don’t involve points at infinity.  This means that if (d,ad) aren’t square, those formulas are complete for any points on the curve.  Otherwise, the addition laws are still complete if you’ve doubled enough times to avoid the points of small order.  There are also slightly faster addition laws that aren’t complete.

Most often Edwards curves are chosen with a = 1 or -1.  The fastest coordinates in this case are “extended” (X:Y:Z:T) coordinates, where ZT = XY.  This makes the curve equation aX^2 + Y^2 = Z^2 + dT^2, which is nicely homogeneous and symmetrical.  When a=-1, the formulas cost ~8M for addition and ~8M for doubling, and they’re super pretty/simple/symmetric.  When a=+1, it’s 9M for addition.  Usually T isn’t used on doubling, which means that it can be computed only when necessary; this usually effectively saves 1M on doubling.  With this optimization, twisted Edwards curves with a=-1 are the fastest elliptic curves for almost every operation, except maybe when they’re beaten by the Montgomery ladder.

When the underlying field has order 3 mod 4, then a=-1 wouldn’t be square.  This means that either d or ad must be square, so the formulas are not complete.  This problem can be worked around in various ways.  The easiest thing to do is to set a=+1 and take the small performance hit, but there are other options.

When running on a non-tiny device, sometimes precomputed points are stored in “Niels” form, which is ((y+x)/2,(y-x)/2,dxy) or similar.  This makes the addition formula slightly faster at the cost of a bigger table.

Every Montgomery curve is birationally equivalent to a twisted Edwards curve, and vice versa.  This makes Edwards curves a great complement to Montgomery curves for operations other than the Montgomery ladder, such as signatures.

Additionally, there are *isogenies* between Montgomery and Edwards curves, and between Edwards and Twisted Edwards curves.  In particular, there are 4-isogenies between Ed(1,d), Ed(-1,d-1), and Mont(A = 2-4d).  This is used for the Ed448-Goldilocks curve is RFC 7748.  The isogenies are another way to work around the a=-1 problems to make implementations faster.




Jacobi intersections, Jacobi quartics and Huff curves

Jacobi intersections: s^2+c^2=1, a*s^2+d^2=1; neutral point (0,1,1).  Here s,c,d are coordinates, and a is a parameter.
https://eprint.iacr.org/2009/597.pdf <https://eprint.iacr.org/2009/597.pdf>

Jacobi quartics: y^2 = x^4 + ax^2 + 1, sometimes written 2ax^2 instead of ax^2.  Identity point (0,1).
https://eprint.iacr.org/2009/312.pdf <https://eprint.iacr.org/2009/312.pdf>

Huff curves: x(dy^2 + 1) = cy(ax^2+1).  Here a,c,d are parameters, and x,y are coordinates.  Neutral point (0,0).
https://eprint.iacr.org/2010/383.pdf <https://eprint.iacr.org/2010/383.pdf>

Minimum cofactor: 4, but (depending on whether you add in twisting parameters) generally with 2x2 torsion.  It might be that with some extra twisting parameters you can get the cofactor down to 2, but the formulas get less efficient.

These curve shapes are less common, because arithmetic isn’t quite as fast on them as Edwards, and they otherwise have the same advantages and disadvantages.  At least Huff curves and Jacobi quartics have a fast Montgomery “odd-ladder”.  This is almost exactly like the Montgomery ladder, has almost the same code, has the same speed, but for technical reasons works better or exclusively with an odd scalar.  I’m brewing a post on odd ladders… maybe in a week or two.

IIRC, at least most of these curve shapes or maybe all of them have reasonably efficient complete addition formulas.

IIRC these curves are birationally equivalent to each other, and are isogenous to Edwards curves.  For example, if you take a twisted Edwards curve

ax^2 + y^2 = 1 + dx^2y^2

and set (p = xy, r = x/y) then you get

p(ar + 1/r) = 1 + dp^2    <====>    p(ar^2+1) = r(1+dp^2)

which is a Huff curve that’s 2-isogenous to the twisted Edwards one.  This means that if for some reason you’re using a Huff curve for something, you can convert your points to Edwards and vice-versa for operations that one model doesn’t support as well.




Hessian curves:
x^3 + y^3 + 1 = 3dxy; homogenized to x^3 + y^3 + 1 = 3dxyz.

https://cr.yp.to/newelliptic/hessian-20150804.pdf <https://cr.yp.to/newelliptic/hessian-20150804.pdf>

Identity point is (1:-1:0), i.e. the point at infinity.

Minimum cofactor: 3.

Supports complete addition laws, I think.

IIRC these are pretty much eclipsed by Edwards curves, but if for some reason you want cofactor 3, then this is the shape for you.



Doche–Icart–Kohel curves: y^2 = x(x^2 + ax + 16a) and y^2=x^3+3*a*(x+1)^2.

I haven’t seen these used before.  I’m guessing they’re also eclipsed by Edwards, but maybe there is a niche use.


I hope this is helpful!
— Mike




> On Nov 6, 2016, at 3:51 PM, Trevor Perrin <trevp at trevp.net> wrote:
> 
> On Thu, Nov 3, 2016 at 7:01 PM, Andy Isaacson <adi at hexapodia.org> wrote:
>> As far as I can tell there's a quite remarkable
>> pile of specialized knowledge necessary to be able to effectively work with
>> elliptic curve cryptography, and this list is mostly for folks who already
>> have the knowledge to discuss things.
> 
> 
> I think it helps a lot to think of layers built on top of each other,
> from high-level to low:
> - Protocols (Signatures, Diffie-Hellman, MQV, etc.)
> - Groups (where discrete log is hard)
> - Elliptic Curves (where points form groups)
> - Fields (the coordinates of elliptic-curve points are field
> elements, e.g in GF(2^255-19))
> 
> 
> Here's a (rambling) tour of a couple layers, I'll try to connect it to
> recent discussion:
> 
> Groups
> -------
> At the level of DH or signatures, elliptic curve crypto is mostly just
> "discrete log" crypto, i.e. it deals with (cyclic) groups where
> calculating discrete logs is hard.  Constructs like DH, DSA, etc apply
> whether the group elements are points on an elliptic curve or integers
> modulo some prime.
> 
> In either case you'll have some element (elliptic curve point; or
> integer mod prime) that generates a group with large prime order q
> (number of elements), which is where you want to do crypto.  But this
> group is often part of a larger group, with order = cofactor * q.
> 
> If cofactor=1 then things are simpler, but cofactor > 1 means there's
> other groups co-existing with the "main subgroup", and there can be
> weird interactions.
> 
> "Small subgroup attacks" on DH with reused keys is the classic case:
> Someone gives you a DH public value A, you raise it to your reusable
> DH private value b to get a shared key and encrypt something with that
> key.
> 
> However!  Instead of A generating the main subgroup, it was
> maliciously chosen to generate some small-order subgroup with j
> elements.  The attacker can trial-decrypt your encrypted data to
> determine which of the j keys was chosen, thus learning your private
> key b mod j.  By repeating this with different A_i of order j_i the
> attacker can calculate b via the Chinese Remainder Theorem.
> 
> With traditional "mod p" or "finite field" Diffie-Hellman, you can
> choose a "safe prime" p=2q+1 to get a cofactor of 2 and a main
> subgroup order of q.  This prevents the attack because the 2-element
> subgroup containing (1,-1) is easy to test for, and because leaking a
> single bit of your key (mod 2) doesn't matter much.
> 
> For traditional Schnorr or DSA signatures you have to send a value
> (mod q) as part of the signature, so you want a prime p = cofactor*q +
> 1, where cofactor is large (instead of cofactor=2).  Thus, using
> DSA-style primes for DH would introduce a risk of small-subgroup
> attacks against re-used keys, requiring an expensive validation check
> (exponentiation by q) to ensure received public values are in the
> correct subgroup.
> 
> (To make this topical:  A recent paper points out that NIST recommends
> DSA-style primes for DH in SP800-56A [0,1].  RFC 5114 also recommends
> specific DSA-style primes for "IKE, TLS, SSH, and SMIME", without
> mentioning the need for validation checks [2].  The paper analyzes the
> "fragility" of the implementation landscape that has resulted, though
> various complications mostly seem to prevent devastating attacks, in
> the implementations looked at.)
> 
> So note that group structure and cofactor/subgroup questions are
> complicated even in "regular" DH, without getting to EC.
> With EC, cofactors are typically small enough (e.g. 1 for NIST
> P-curves, 8 for Curve25519) that the above attack isn't that relevant,
> though sending invalid points (not on the curve) can lead to a similar
> attack.
> 
> However, cofactor>1 can still have subtle and unexpected effects, e.g.
> see security considerations about "equivalent" public keys in RFC
> 7748, which is relevant to the cofactor multiplication "cV" in
> VXEdDSA, or including DH public keys into "AD" in Signal's (recently
> published) X3DH [3].
> 
> 
> Signatures
> -----------
> Discrete-log signatures (El Gamal, Schnorr, DSA, EC-DSA, EdDSA) build
> on top of the group structure, so can be considered without too much
> EC detail.
> 
> Academic intro to crypto books usually cover the basics well, the
> typical reference points are:
> * Schnorr's identification protocol
> * Fiat-Shamir transform
> * Security proof via Random Oracle Model and oracle rewinding
> 
> From there, DJB has a great writeup on concrete design details [4], as
> well as the Ed25519 and "More curves for EdDSA" papers.
> 
> It's also worth understanding these signatures as instances of
> "zero-knowledge proofs" which can do fancier things.  E.g. see
> Camenisch-Stadler [5] examples 2 and 3 on "equality of two discrete
> logarithms" (relevant to VRF), and "or" proofs (relevant to signature
> variants like "designated verifier" signatures).
> 
> 
> Curves
> -------
> This is harder math, and I'm not sure Montgomery / Edwards curves have
> made it into good textbooks and overviews yet.  I think people lean on
> DJB's Curve25519 and Ed25519 papers, "Twisted Edwards Curves" [6], and
> their references.  The authors have a "gentle introduction" to EC as
> well [7].
> 
> I'm not the person to do it, but if anyone wants to try an overview of
> modern curve equations / coordinate systems / algorithms, I'm sure it
> would be widely appreciated (there's about 600 people on this list,
> probably most here to learn things like that).
> 
> Trevor
> 
> 
> [0] https://eprint.iacr.org/2016/995
> [1] http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar2.pdf
> [2] https://tools.ietf.org/html/rfc5114
> [3] https://whispersystems.org/docs/specifications/x3dh/
> [4] https://blog.cr.yp.to/20140323-ecdsa.html
> [5] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.1208
> [6] https://eprint.iacr.org/2008/013
> [7] http://ecchacks.cr.yp.to/
> _______________________________________________
> 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/20161106/d22f6c5e/attachment.html>
-------------- 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/20161106/d22f6c5e/attachment.bin>