<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">Here’s a quick and slightly sleepy try on curve shapes. Please correct any errors you see.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Short Weierstrass: y^2 = x^3 + ax + b. Most often a=-3.</div><div class=""><br class=""></div><div class="">Minimum cofactor: 1.</div><div class=""><br class=""></div><div class="">Identity point: (0 : 1 : 0), i.e. infinity in the vertical direction.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">When doing a scalar multiply of a single point, an efficient family of algorithms is the co-Z ladder (<a href="https://eprint.iacr.org/2010/309.pdf" class="">https://eprint.iacr.org/2010/309.pdf</a>), 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.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Montgomery: by^2 = x(x^2+Ax+1). Almost always b=1.</div><div class=""><br class=""></div><div class="">Minimum cofactor: 4.</div><div class=""><br class=""></div><div class="">The point of order 2 has (x,y)=(0,0). A point of order 4 has x = +- 1.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><div class="">Twisted Edwards: ax^2 + y^2 = 1 + dx^2y^2. The curve is “untwisted” if a=1.</div><div class=""><br class=""></div><div class="">Reference: <a href="https://eprint.iacr.org/2008/013.pdf" class="">https://eprint.iacr.org/2008/013.pdf</a></div><div class=""><a href="http://iacr.org/archive/asiacrypt2008/53500329/53500329.pdf" class="">http://iacr.org/archive/asiacrypt2008/53500329/53500329.pdf</a></div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div></div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Jacobi intersections, Jacobi quartics and Huff curves</div><div class=""><br class=""></div><div class="">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.</div><div class=""><a href="https://eprint.iacr.org/2009/597.pdf" class="">https://eprint.iacr.org/2009/597.pdf</a></div><div class=""><br class=""></div><div class="">Jacobi quartics: y^2 = x^4 + ax^2 + 1, sometimes written 2ax^2 instead of ax^2. Identity point (0,1).</div><div class=""><a href="https://eprint.iacr.org/2009/312.pdf" class="">https://eprint.iacr.org/2009/312.pdf</a></div><div class=""><br class=""></div><div class="">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).</div><div class=""><a href="https://eprint.iacr.org/2010/383.pdf" class="">https://eprint.iacr.org/2010/383.pdf</a></div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">IIRC, at least most of these curve shapes or maybe all of them have reasonably efficient complete addition formulas.</div><div class=""><br class=""></div><div class="">IIRC these curves are birationally equivalent to each other, and are isogenous to Edwards curves. For example, if you take a twisted Edwards curve</div><div class=""><br class=""></div><div class="">ax^2 + y^2 = 1 + dx^2y^2</div><div class=""><br class=""></div><div class="">and set (p = xy, r = x/y) then you get</div><div class=""><br class=""></div><div class="">p(ar + 1/r) = 1 + dp^2 <====> p(ar^2+1) = r(1+dp^2)</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Hessian curves:</div><div class="">x^3 + y^3 + 1 = 3dxy; homogenized to x^3 + y^3 + 1 = 3dxyz.</div><div class=""><br class=""></div><div class=""><a href="https://cr.yp.to/newelliptic/hessian-20150804.pdf" class="">https://cr.yp.to/newelliptic/hessian-20150804.pdf</a></div><div class=""><br class=""></div><div class="">Identity point is (1:-1:0), i.e. the point at infinity.</div><div class=""><br class=""></div><div class="">Minimum cofactor: 3.</div><div class=""><br class=""></div><div class="">Supports complete addition laws, I think.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Doche–Icart–Kohel curves: y^2 = x(x^2 + ax + 16a) and y^2=x^3+3*a*(x+1)^2.</div><div class=""><br class=""></div><div class="">I haven’t seen these used before. I’m guessing they’re also eclipsed by Edwards, but maybe there is a niche use.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">I hope this is helpful!</div><div class="">— Mike</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><br class=""><div><blockquote type="cite" class=""><div class="">On Nov 6, 2016, at 3:51 PM, Trevor Perrin <<a href="mailto:trevp@trevp.net" class="">trevp@trevp.net</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class="">On Thu, Nov 3, 2016 at 7:01 PM, Andy Isaacson <<a href="mailto:adi@hexapodia.org" class="">adi@hexapodia.org</a>> wrote:<br class=""><blockquote type="cite" class="">As far as I can tell there's a quite remarkable<br class="">pile of specialized knowledge necessary to be able to effectively work with<br class="">elliptic curve cryptography, and this list is mostly for folks who already<br class="">have the knowledge to discuss things.<br class=""></blockquote><br class=""><br class="">I think it helps a lot to think of layers built on top of each other,<br class="">from high-level to low:<br class=""> - Protocols (Signatures, Diffie-Hellman, MQV, etc.)<br class=""> - Groups (where discrete log is hard)<br class=""> - Elliptic Curves (where points form groups)<br class=""> - Fields (the coordinates of elliptic-curve points are field<br class="">elements, e.g in GF(2^255-19))<br class=""><br class=""><br class="">Here's a (rambling) tour of a couple layers, I'll try to connect it to<br class="">recent discussion:<br class=""><br class="">Groups<br class="">-------<br class="">At the level of DH or signatures, elliptic curve crypto is mostly just<br class="">"discrete log" crypto, i.e. it deals with (cyclic) groups where<br class="">calculating discrete logs is hard. Constructs like DH, DSA, etc apply<br class="">whether the group elements are points on an elliptic curve or integers<br class="">modulo some prime.<br class=""><br class="">In either case you'll have some element (elliptic curve point; or<br class="">integer mod prime) that generates a group with large prime order q<br class="">(number of elements), which is where you want to do crypto. But this<br class="">group is often part of a larger group, with order = cofactor * q.<br class=""><br class="">If cofactor=1 then things are simpler, but cofactor > 1 means there's<br class="">other groups co-existing with the "main subgroup", and there can be<br class="">weird interactions.<br class=""><br class="">"Small subgroup attacks" on DH with reused keys is the classic case:<br class="">Someone gives you a DH public value A, you raise it to your reusable<br class="">DH private value b to get a shared key and encrypt something with that<br class="">key.<br class=""><br class="">However! Instead of A generating the main subgroup, it was<br class="">maliciously chosen to generate some small-order subgroup with j<br class="">elements. The attacker can trial-decrypt your encrypted data to<br class="">determine which of the j keys was chosen, thus learning your private<br class="">key b mod j. By repeating this with different A_i of order j_i the<br class="">attacker can calculate b via the Chinese Remainder Theorem.<br class=""><br class="">With traditional "mod p" or "finite field" Diffie-Hellman, you can<br class="">choose a "safe prime" p=2q+1 to get a cofactor of 2 and a main<br class="">subgroup order of q. This prevents the attack because the 2-element<br class="">subgroup containing (1,-1) is easy to test for, and because leaking a<br class="">single bit of your key (mod 2) doesn't matter much.<br class=""><br class="">For traditional Schnorr or DSA signatures you have to send a value<br class="">(mod q) as part of the signature, so you want a prime p = cofactor*q +<br class="">1, where cofactor is large (instead of cofactor=2). Thus, using<br class="">DSA-style primes for DH would introduce a risk of small-subgroup<br class="">attacks against re-used keys, requiring an expensive validation check<br class="">(exponentiation by q) to ensure received public values are in the<br class="">correct subgroup.<br class=""><br class="">(To make this topical: A recent paper points out that NIST recommends<br class="">DSA-style primes for DH in SP800-56A [0,1]. RFC 5114 also recommends<br class="">specific DSA-style primes for "IKE, TLS, SSH, and SMIME", without<br class="">mentioning the need for validation checks [2]. The paper analyzes the<br class="">"fragility" of the implementation landscape that has resulted, though<br class="">various complications mostly seem to prevent devastating attacks, in<br class="">the implementations looked at.)<br class=""><br class="">So note that group structure and cofactor/subgroup questions are<br class="">complicated even in "regular" DH, without getting to EC.<br class="">With EC, cofactors are typically small enough (e.g. 1 for NIST<br class="">P-curves, 8 for Curve25519) that the above attack isn't that relevant,<br class="">though sending invalid points (not on the curve) can lead to a similar<br class="">attack.<br class=""><br class="">However, cofactor>1 can still have subtle and unexpected effects, e.g.<br class="">see security considerations about "equivalent" public keys in RFC<br class="">7748, which is relevant to the cofactor multiplication "cV" in<br class="">VXEdDSA, or including DH public keys into "AD" in Signal's (recently<br class="">published) X3DH [3].<br class=""><br class=""><br class="">Signatures<br class="">-----------<br class="">Discrete-log signatures (El Gamal, Schnorr, DSA, EC-DSA, EdDSA) build<br class="">on top of the group structure, so can be considered without too much<br class="">EC detail.<br class=""><br class="">Academic intro to crypto books usually cover the basics well, the<br class="">typical reference points are:<br class=""> * Schnorr's identification protocol<br class=""> * Fiat-Shamir transform<br class=""> * Security proof via Random Oracle Model and oracle rewinding<br class=""><br class="">From there, DJB has a great writeup on concrete design details [4], as<br class="">well as the Ed25519 and "More curves for EdDSA" papers.<br class=""><br class="">It's also worth understanding these signatures as instances of<br class="">"zero-knowledge proofs" which can do fancier things. E.g. see<br class="">Camenisch-Stadler [5] examples 2 and 3 on "equality of two discrete<br class="">logarithms" (relevant to VRF), and "or" proofs (relevant to signature<br class="">variants like "designated verifier" signatures).<br class=""><br class=""><br class="">Curves<br class="">-------<br class="">This is harder math, and I'm not sure Montgomery / Edwards curves have<br class="">made it into good textbooks and overviews yet. I think people lean on<br class="">DJB's Curve25519 and Ed25519 papers, "Twisted Edwards Curves" [6], and<br class="">their references. The authors have a "gentle introduction" to EC as<br class="">well [7].<br class=""><br class="">I'm not the person to do it, but if anyone wants to try an overview of<br class="">modern curve equations / coordinate systems / algorithms, I'm sure it<br class="">would be widely appreciated (there's about 600 people on this list,<br class="">probably most here to learn things like that).<br class=""><br class="">Trevor<br class=""><br class=""><br class="">[0] <a href="https://eprint.iacr.org/2016/995" class="">https://eprint.iacr.org/2016/995</a><br class="">[1] <a href="http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar2.pdf" class="">http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar2.pdf</a><br class="">[2] <a href="https://tools.ietf.org/html/rfc5114" class="">https://tools.ietf.org/html/rfc5114</a><br class="">[3] <a href="https://whispersystems.org/docs/specifications/x3dh/" class="">https://whispersystems.org/docs/specifications/x3dh/</a><br class="">[4] <a href="https://blog.cr.yp.to/20140323-ecdsa.html" class="">https://blog.cr.yp.to/20140323-ecdsa.html</a><br class="">[5] <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.1208" class="">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.1208</a><br class="">[6] <a href="https://eprint.iacr.org/2008/013" class="">https://eprint.iacr.org/2008/013</a><br class="">[7] <a href="http://ecchacks.cr.yp.to/" class="">http://ecchacks.cr.yp.to/</a><br class="">_______________________________________________<br class="">Curves mailing list<br class=""><a href="mailto:Curves@moderncrypto.org" class="">Curves@moderncrypto.org</a><br class="">https://moderncrypto.org/mailman/listinfo/curves<br class=""></div></div></blockquote></div><br class=""></body></html>