.png)
2 hours ago
1
CurveForge: generic, constant-time elliptic curves by construction in Rust. Or: how we implemented Montgomery curves in a few hours instead of a few weeks.
Traditionally, engineering elliptic curve implementations is rather painful. For the best performance, a given elliptic curve needs bespoke optimizations, which depend on the exact (mathematical) parameters and the architecture of the platform on which it will run. Care has to be taken that operations run in constant time (i.e., the time that an operation takes is independent of the secrets).
For the past few years, we have worked on CurveForge. CurveForge is a framework for prototyping, researching and engineering elliptic curve implementations in Rust. The resulting code is constant-time by construction, it is designed to be easily extensible to new curves and elliptic curve models, and allows to generically implement optimizations.
Demo: Curve25519 in 21 lines
The above code snippet defines Curve25519 in the Montgomery model. Apart from the birational mapping to Ed25519, this is the actual source code for Curve25519 in CurveForge. The macro call generates a full-featured implementation of Curve25519, including point addition, point doubling, scalar multiplication, and serialization/deserialization. CurveForge then generates a set of types:
- Curve25519
- Curve25519Point
- Curve25519ScalarElement
- Curve25519FieldElement
These behave mostly as you would expect:
We also implemented Curve448, along with several other curves in different models.
Elliptic curves can be represented in different models, which are roughly the mathematical equation that define the elliptic curve. Depending on the model and on the curve’s coefficients, different operations are more or less efficient, or representations in certain models may not exist. For example, Curve25519 has its parameters chosen such that the Montgomery ladder is very efficient, when represented as a Montgomery curve:
$$Bv^2 = u^3 + Au^2 + u.$$
This is why Curve25519 can be so fast for Diffie-Hellman key exchange. Contrary, Ed25519 is represented as a twisted Edwards curve, $ax^2 + y^2 = 1 + dx^2 y^2.$ In the twisted Edwards model, operations for digital signatures (among others) are very efficient, hence the Ed25519 signature scheme. Not every curve is a twisted Edwards curve, and not all twisted Edwards curves can be optimized the same way.
Currently, we have implementations for short Weierstrass, Montgomery, extended twisted Edwards and double-odd curves. All models use some form of projective coordinates to avoid inversions in the group operations; see the specific model documentation and source code for details.
CurveForge is designed to be easily extensible to new models, which are implemented through a macro. This elliptic_curve_model! macro features a small domain specific language (DSL) to describe operations in the model.
Here is a partial implementation of the Montgomery model (x-only, projective), with implementations for point serialization, deserialization, equality check and point doubling.
This fragment leaves out the double-and-add algorithm for scalar multiplication for brevity, but feel free to consult the complete implementation.
The DSL is designed to be as close as possible to the mathematical notation found in the literature; it is inspired by the notation used in the EFD (Explicit Formulas Database), by Daniel J. Bernstein and Tanja Lange. The curveforge-macro crate’s README documents the DSL in more detail.
The main point of the DSL is to disallow any non-constant-time operations. It allows “branching” through a ternary operator, which is implemented in constant-time (through subtle’s ConditionallySelectable trait); both branches are always evaluated, and the result is selected based on the condition. The following is the implementation of point serialization for (extended) twisted Edwards curves, as an example of the C-style ternary in use:
The DSL captures the semantics of the arithmetic that backs the elliptic curve implementation. This means that the transpiler that generates Rust code based on the DSL, can make decisions based on these semantics.
For example: the double method of the Montgomery implementation above contains the fragment (A + 2) * 4.inv(). Any ordinary elliptic curve implementation will hard-code this constant, and will specifically avoid computing 4.inv() because of the cost of inversion. CurveForge, on the other hand, will automatically precompute this constant. In case $A = 2$, CurveForge knows that $(A + 2)/4 = 1$, and it will eliminate the multiplication altogether. If the result of $(A+2)/4$ is a “small” number (like 2, i.e. $A=6$) instead, CurveForge can optimize for the specific case.
In the future, we foresee more optimizations, such as operation reordering (which could for example detect cases where inverse square roots can be used), or common subexpression elimination (such that $Ax^3 +Bx^2 + x$ can be computed with one square and one multiplication of $x$). Low level optimizations, such as Montgomery representation for field elements, will benefit all curve implementations at the same time.
CurveForge is designed with speed, safety, and extensibility in mind. Currently, the performance is not on par with hand-optimized implementations such as the famous curve25519-dalek. However, the generated code is still reasonably fast, and because the DSL understands the high-level mathematical semantics, it is possible to implement both high-level and low-level optimizations.
Being written in Rust, CurveForge benefits from Rust’s strong type system, memory safety guarantees, and compilation targets. We have not played with it yet, but it should be perfectly viable to run the generated code in no_std environments.
CurveForge does not use any unsafe code. This might change if at some point we will generate optimized assembly for vector operations. CurveForge currently also uses generic_array, because we use some operations on consts that would require generic constant expressions.
There are quite a few great elliptic curve libraries out there, many of them written in Rust. This section briefly summarizes how CurveForge differs from these other libraries.
Dalek’s Curve25519 is probably the fastest elliptic curve library out there, but it specializes in Curve25519 and Ed25519 arithmetic. We see this as the baseline for raw speed.
Arkworks implements a generic interface for elliptic curves, although not through a DSL. Implementing new models and curves requires imperative Rust code, which makes e.g. specialization in constants quite awkward. For example, this pull request implements the double-odd model and the Jq255s curve in Arkworks in about 1160 lines. In comparison, the roughly equivalent double odd implementation of CurveForge is about 156 lines long, and the Jq255s implementation 22 lines. We are comparing apples to oranges here, so take these line counts with a pinch of salt.
RustCrypto is the Rust reference for elliptic curve cryptography for anything but Curve25519.
To track and compare performance, we ship curveforge-compat. This crate contains some criterion.rs benchmarks to track our progress.
This post is a first one in a series on CurveForge. In the next few posts, we plan to dive a bit deeper into the CurveForge design. We don’t really have a schedule for publishing the follow-ups, but expect the following topics:
- The inner workings of the domain-specific language (DSL)
- Our abuse of the Rust type system to optimize finite field reductions
- Implementation of constant-time arithmetic
- Use cases for CurveForge – we’ll keep that as a surprise for now 😉
This project is funded through NGI0 Entrust, a fund established by NLnet with financial support from the European Commission’s Next Generation Internet program. Learn more at the NLnet project page.
