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.
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).