Selecting Elliptic Curves for Cryptography: an Efficiency and Security Analysis

We select a set of elliptic curves for cryptography and analyze our selection from a performance and security perspective. This analysis complements recent curve proposals that suggest (twisted) Edwards curves by also considering the Weierstrass model. Working with both Montgomery-friendly and pseudo-Mersenne primes allows us to consider more possibilities which help to improve the overall efficiency of base field arithmetic. Our Weierstrass curves are backwards compatible with current implementations of prime order NIST curves, while providing improved efficiency and stronger security properties. We choose algorithms and explicit formulas to demonstrate that our curves support constant-time, exception-free scalar multiplications, thereby offering high practical security in cryptographic applications. Our implementation shows that variable-base scalar multiplication on the new Weierstrass curves at the 128-bit security level is about 1.4 times faster than the recent implementation record on the corresponding NIST curve. For practitioners who are willing to use a different curve model and sacrifice a few bits of security, we present a collection of twisted Edwards curves with particularly efficient arithmetic that are up to 1.42, 1.26 and 1.24 times faster than the new Weierstrass curves at the 128-, 192- and 256-bit security levels, respectively. Finally, we discuss how these curves behave in a real-world protocol by considering different scalar multiplication scenarios in the transport layer security (TLS) protocol. The proposed curves and the results of the analysis are intended to contribute to the recent efforts towards recommending new elliptic curves for Internet standards. Recently, part of the cryptographic community has been looking for alternatives to the currently deployed elliptic curves that may offer better performance and provide stronger overall security (see for example an evaluation of recent curve candidates in [12]). Most notably, the TLS working group has issued a formal request to the Crypto Forum Research Group (CFRG) asking for recommendations for new elliptic curves. The urge to change curves has been fueled by the recently leaked NSA documents, which suggest the existence of a back door in the Dual Elliptic Curve Deterministic Random Bit Generator [56]. Although cryptographers have suspected this at least as early as in 2007 [53], these recent revelations have accelerated a controversy on whether the widely deployed NIST curves [58] should be replaced by curves with a verifiably deterministic generation. Besides such security concerns, there has been significant progress related to both efficiency and security since the initial standardization of elliptic curve