# Elliptic Curves of different forms

Looking at http://safecurves.cr.yp.to/ to find a safe curve, I find that most curves described here are of a different form from that generally used.

In Bouncy Castle, for example, FpCurves take curves of the form $y^2 = x^3+ax+b$ (Weierstrass), whereas the (safe) curves found on the above linked have different forms, such as $y^2 = x^3+ax^2+x$ (Montgomery) - how do I translate between the two? How do I use the second form of curve with, for example, Bouncy Castle?

(Or do I simply have to accept that no safe curves of the Fp form exist?)

What else have I tried? Guide to Elliptic Curve Cryptography (Hankerson et.al.) covers curves of the forms $y^2 = x^3+ax+b$ for fields with characteristic > 3, and only offer alternatives (that are not interchangable with the safe curves, either) for lower characteristics, that are not very useable in my situation. Even then, some curves on the safe curves website are of forms that I cannot immediately find explained anywhere.

-
Why do you want to use a montgomery/edwards curve if you then proceed to perform weierstrass form operations on them? To take advantage of montgomery form you need to use differential addition with an appropriate ladder. The whole point of supporting montgomery ladders is that you use them. – CodesInChaos Mar 16 '14 at 13:20
@CodesInChaos I understand this is the reason for the existence of the Montgomery form, however my question is about how to use "safe" curves in the likes of BouncyCastle that do not support Montgomery curves. – Niels Abildgaard Mar 18 '14 at 16:16

The idea of "safe curve" is somewhat overrated. What you really want is a safe implementation which won't leak secret information when employed in some practical context. Leakage may occur in a variety of ways; some examples include timing attacks and implementation behaviour when encountering anomalous input. This is not an exhaustive list, and, depending on the context, such leakages may or may not apply.

The so-called "safe curves" are curves with equations which, supposedly, make it easier to implement them safely. Note the operational term: easier. A "safe curve" does not automatically imply that any implementation will be sound and safe (a prime example is how OpenSSL botched at least twice their code for binary curves, while using the "safe" Montgomery ladder as adapted by López and Dahab to binary curves). Conversely, an "unsafe curve" can still be implemented safely. It would be wrong to place some anathema on "unsafe curves", as DJB's site seems to imply with its "safe/unsafe" terminology and conspicuous green and red labels (but only seems, mind you).

For an elliptic curve user, e.g. the designer of some protocol which relies on some elliptic curve cryptography implemented by a third-party library, the important matter is that the library is good, which is only loosely correlated with whether the base curve is called "safe" or "unsafe".

As for translation between curve equations, this may or may not be feasible, depending on the actual curves. For instance, proponents of "safe curves" usually mean using Montgomery curves whose equation is: $$By^2 = x^3 + Ax^2 + x$$ for two constants $A$ and $B$. A curve which follows this equation necessarily accepts the point $(0,0)$ which has order $2$ (that point, when doubled, yields the "point at infinity"). It follows that the order of a Montgomery curve must be even. Therefore, standard curves like P-256 with a prime order (thus odd) cannot be converted to a Montgomery equation. Other curves might be convertible, or not.

The Handbook of Elliptic and Hyperelliptic Curve Cryptography describes Montgomery curves in section 13.2.3. It discusses the conversions from Weierstraß to Montgomery equations and back, when that is possible at all. Notably, while Montgomery curves allow for a point multiplication algorithm which is both efficient and relatively easily amenable to "safe" implementation (the famous "ladder"), section 13.2.3.b points to an article from Brier and Joye who showed how a ladder algorithm can be applied to the generic case of the Weierstraß equation $$y^2 = x^3 + ax + b$$ albeit with a somewhat higher computational cost -- but nothing critical in most usages. This would make P-256 a "safe curve" as well, if we want to cling to that terminology (there are other criteria for a curve to be called "safe" but the main point remains: "safety" is ultimately a property of the implementation, not of the curve).

Indeed, if a basic PC or even a smartphone is implied, then the hardware can do thousands of point multiplications per second. For most if not all applications running on that kind of hardware, it makes no detectable difference whether a given ECC implementation can do 3000 or 30000 signatures or decryptions per second (if it did a difference for you, you would not even contemplate using a Java-based implementation like BouncyCastle; you would have gone straight to optimized assembly code).

-
The emphasis placed on "easy" is justified. People have an amazing ability to screw things up. Making it easier not to screw up is worthwhile. This is why we now have AEAD schemes instead of just encryption+MAC, etc., etc. – K.G. Mar 16 '14 at 20:21
Actually, I believe P-256 cannot be made into a "safe curve" (at least, not without help from whoever selected the curve) because one of the requirements is "rigidity", that there are no unexplained constants involved, and P-256 (and the other NIST curves) have the constant $b$ that has not been explained. – poncho Mar 16 '14 at 21:54
In your openssl example you use "binary curve" twice. Is that intended or a typo? – Maarten Bodewes Mar 17 '14 at 13:04
It is intended. In all the rest of the message, we talk about curves in $\mathbb{F}_p$ for some prime $p$. However, the Montgomery ladder has also been adapted to curves in $\mathbb{F}_{2^m}$ ("binary curves") with the same expected characteristics (efficient AND side-channel resistant), and yet the OpenSSL implementation of that ladder on binary curves turned out to leak information. This highlights the idea that having a curve amenable to leak-free implementations does not preclude the existence of an implementation which still leaks heavily. – Thomas Pornin Mar 17 '14 at 14:51
I just realized that SafeCurves (although fairly well-hidden) explains how to move from Montgomery to Weierstrass curves (which would make the curves usable, albeit not necessarily feasible performance-wise): "Substituting x = Bu-A/3 and y = Bv produces the short Weierstrass equation v^2 = u^3 + au + b" (safecurves.cr.yp.to/equation.html). What properties, pertaining to "safety", are lost with this transformation, assuming the Weierstrass implementation used is safe? It will involve bigger numbers, but will this impact the safety? – Niels Abildgaard Mar 18 '14 at 16:26

The curve equation $Y^2=X^3+AX+B$ is traditional because it greatly simplifies a lot of theory. I like to use it for teaching. But all of these curve equations are in a sense equivalent, and for any smooth cubic curve, you can usually find an isomorphic curve of desired form.

However, a long time ago, people realized that different curve equations have different formulae for point addition/doubling, and that these formulae have different costs and different properties. One early example is choosing $A=-3$ (or something like that).

Unfortunately, this means that it is not the curve that is interesting, but its curve equation. If you take one curve from safecurves and find an isomorphic curve equation of the form $Y^2=X^3+AX+B$, you will probably lose almost all the nice properties of the original curve equation. In which case you may as well not bother and use the NIST curves instead.

In other words, you cannot simply take a modern curve equation and "adapt" it for use with older cryptographic libraries. Sorry.

-
With "nice properties" do you mean "what makes it safe" or "what makes it fast for computations"? – Niels Abildgaard Mar 16 '14 at 10:40
Also, can you recommend any libraries that implement more modern curves? – Niels Abildgaard Mar 16 '14 at 10:41
Both. Modern curves are easier to implement correctly, and implementations are faster. No, I have no idea about implementations. Dan Bernstein probably has something sensible, but it may not be suitable for you. – K.G. Mar 16 '14 at 12:58
I just realized that SafeCurves (although fairly well-hidden) explains how to move from Montgomery to Weierstrass curves (which would make the curves usable, albeit not necessarily feasible performance-wise): "Substituting x = Bu-A/3 and y = Bv produces the short Weierstrass equation v^2 = u^3 + au + b" (safecurves.cr.yp.to/equation.html). What properties, pertaining to "safety", are lost with this transformation, assuming the Weierstrass implementation used is safe? – Niels Abildgaard Mar 18 '14 at 16:24
If you assume that the weierstrass implementation is safe, you only lose performance. Rigidness is the only property that directly relates to the security of the curve, all the other safety properties are about making it easier to write a fast and secure implementation. For example BouncyCastle C# is neither fast nor secure. – CodesInChaos Mar 18 '14 at 16:42

Montgomery curves have cofactor 4

Nist curves have cofactor 1

then you cannot convert from Montgomery curves to NIST curves, or reversely.

The reason NIST used curves with cofactor 1 is unknown. would NIST have chosen cofactor 4, then the mapping would have been possible, and the corresponding speed up too. Lobbying and licensing is probably behind the technical choices.

Safety is a matter of technical implementation, not about curve formula. Some implementations are better than other.

Security levels is about feeling and crypto guru egos. Never argue about that.

-
This is not really an answer. The question is about curves of the Weierstrass simple form rather than NIST curves specifically. secp256k1 is another example of a curve following the formula $y^2=x^3+ax+b$. – Niels Abildgaard Jun 13 '14 at 9:27
Your first question is "how do I translate between the two ?" Have a look to http : //en.wikipedia.org/wiki/Montgomery_curve#Equivalence_with_Weierstrass_curves , and you will find a simple conversion method from one curve to another. – Pierre Jun 15 '14 at 22:04
Your seqcond question is about "safe". If you accept that the two representations are birationally equivalent, then you have to consider they are equally "safe". I still don't know what your definition of "safe" is. – Pierre Jun 15 '14 at 22:08
Right, you answered the second part. My comment was directed at the first part. As you only talk about NIST curves you don't answer my question (but a different one: Is it possible to convert between different cofactors? No.). – Niels Abildgaard Jun 16 '14 at 8:36