Module curve25519_dalek::ristretto
[−]
[src]
An implementation of Ristretto, which provides a primeorder group.
The Ristretto Group
Ristretto is a modification of Mike Hamburg's Decaf scheme to work with cofactor\(8\) curves, such as Curve25519.
The introduction of the Decaf paper, Decaf: Eliminating cofactors through point compression, notes that while most cryptographic systems require a group of prime order, most concrete implementations using elliptic curve groups fall short – they either provide a group of prime order, but with incomplete or variabletime addition formulae (for instance, most Weierstrass models), or else they provide a fast and safe implementation of a group whose order is not quite a prime \(q\), but \(hq\) for a small cofactor \(h\) (for instance, Edwards curves, which have cofactor at least \(4\)).
This abstraction mismatch is commonly “handled” by pushing the complexity upwards, adding adhoc protocol modifications. But these modifications require careful analysis and are a recurring source of vulnerabilities and design complications.
Instead, Decaf (and Ristretto) use a quotient group to implement a primeorder group using a nonprimeorder curve. This provides the correct abstraction for cryptographic systems, while retaining the speed and safety benefits of an Edwards curve.
Decaf is named “after the procedure which divides the effect of coffee by \(4\)”. However, Curve25519 has a cofactor of \(8\). To eliminate its cofactor, Ristretto restricts further; this additional restriction gives the Ristretto encoding.
More details
are described in the Implementation section below. Ristretto
points are provided in curve25519dalek
by the RistrettoPoint
struct.
Encoding and Decoding
Encoding is done by converting to and from a CompressedRistretto
struct, which is a typed wrapper around [u8; 32]
.
The encoding is not batchable, but it is possible to
doubleandencode in a batch using
RistrettoPoint::double_and_compress_batch
.
Equality Testing
Testing equality of points on an Edwards curve in projective coordinates requires an expensive inversion. By contrast, equality checking in the Ristretto group can be done in projective coordinates without requiring an inversion, so it is much faster.
The RistrettoPoint
struct implements the
subtle::ConstantTimeEq
trait for constanttime equality
checking, and the Rust Eq
trait for variabletime equality
checking.
Scalars
Scalars are represented by the Scalar
struct. Each scalar has a
canonical representative mod the group order. To attempt to load
a supposedlycanonical scalar, use
Scalar::from_canonical_bytes()
. To check whether a
representative is canonical, use Scalar::is_canonical()
.
Scalar Multiplication
Scalar multiplication on Ristretto points is provided by:

the
*
operator between aScalar
and aRistrettoPoint
, which performs constanttime variablebase scalar multiplication; 
the
*
operator between aScalar
and aRistrettoBasepointTable
, which performs constanttime fixedbase scalar multiplication; 
the
ristretto::multiscalar_mul
function, which performs constanttime variablebase multiscalar multiplication; 
the
ristretto::vartime::multiscalar_mul
function, which performs variabletime variablebase multiscalar multiplication.
Random Points and Hashing to Ristretto
The Ristretto group comes equipped with an Elligator map. This is used to implement

RistrettoPoint::random()
, which generates random points from an RNG; 
RistrettoPoint::from_hash()
andRistrettoPoint::hash_from_bytes()
, which perform hashing to the group.
The Elligator map itself is not currently exposed.
Implementation
The Decaf suggestion is to use a quotient group, such as \(\mathcal E / \mathcal E[4]\) or \(2 \mathcal E / \mathcal E[2] \), to implement a primeorder group using a nonprimeorder curve.
This requires only changing
 the function for equality checking (so that two representatives of the same coset are considered equal);
 the function for encoding (so that two representatives of the same coset are encoded as identical bitstrings);
 the function for decoding (so that only the canonical encoding of a coset is accepted).
Internally, each coset is represented by a curve point; two points \( P, Q \) may represent the same coset in the same way that two points with different \(X,Y,Z\) coordinates may represent the same point. The group operations are carried out with no overhead using Edwards formulas.
Notes on the details of the encoding can be found in the
ristretto::notes
submodule of the internal curve25519dalek
documentation.
Modules
vartime 
Variabletime operations on ristretto points, useful for nonsecret data. 
Structs
CompressedRistretto 
A Ristretto point, in compressed wire format. 
RistrettoBasepointTable 
A precomputed table of multiples of a basepoint, used to accelerate scalar multiplication. 
RistrettoPoint 
A 
Functions
multiscalar_mul 
Given an iterator of (possibly secret) scalars and an iterator of (possibly secret) points, compute $$ Q = c_1 P_1 + \cdots + c_n P_n. $$ 