logo
pub struct EdwardsBasepointTable(_);
Expand description

A precomputed table of multiples of a basepoint, for accelerating fixed-base scalar multiplication. One table, for the Ed25519 basepoint, is provided in the constants module.

The basepoint tables are reasonably large, so they should probably be boxed.

The sizes for the tables and the number of additions required for one scalar multiplication are as follows:

Why 33 additions for radix-256?

Normally, the radix-256 tables would allow for only 32 additions per scalar multiplication. However, due to the fact that standardised definitions of legacy protocols—such as x25519—require allowing unreduced 255-bit scalar invariants, when converting such an unreduced scalar’s representation to radix-\(2^{8}\), we cannot guarantee the carry bit will fit in the last coefficient (the coefficients are i8s). When, \(w\), the power-of-2 of the radix, is \(w < 8\), we can fold the final carry onto the last coefficient, \(d\), because \(d < 2^{w/2}\), so $$ d + carry \cdot 2^{w} = d + 1 \cdot 2^{w} < 2^{w+1} < 2^{8} $$ When \(w = 8\), we can’t fit \(carry \cdot 2^{w}\) into an i8, so we add the carry bit onto an additional coefficient.

Implementations

Create a table of precomputed multiples of basepoint.

The computation uses Pippenger’s algorithm, as described on page 13 of the Ed25519 paper. Write the scalar \(a\) in radix \(16\) with coefficients in \([-8,8)\), i.e., $$ a = a_0 + a_1 16^1 + \cdots + a_{63} 16^{63}, $$ with \(-8 \leq a_i < 8\), \(-8 \leq a_{63} \leq 8\). Then $$ a B = a_0 B + a_1 16^1 B + \cdots + a_{63} 16^{63} B. $$ Grouping even and odd coefficients gives $$ \begin{aligned} a B = \quad a_0 16^0 B +& a_2 16^2 B + \cdots + a_{62} 16^{62} B \\ + a_1 16^1 B +& a_3 16^3 B + \cdots + a_{63} 16^{63} B \\ = \quad(a_0 16^0 B +& a_2 16^2 B + \cdots + a_{62} 16^{62} B) \\ + 16(a_1 16^0 B +& a_3 16^2 B + \cdots + a_{63} 16^{62} B). \\ \end{aligned} $$ For each \(i = 0 \ldots 31\), we create a lookup table of $$ [16^{2i} B, \ldots, 8\cdot16^{2i} B], $$ and use it to select \( x \cdot 16^{2i} \cdot B \) in constant time.

The radix-\(16\) representation requires that the scalar is bounded by \(2^{255}\), which is always the case.

Get the basepoint for this table as an EdwardsPoint.

Trait Implementations

Returns a copy of the value. Read more

Performs copy-assignment from source. Read more

Construct an EdwardsPoint from a Scalar \(a\) by computing the multiple \(aB\) of this basepoint \(B\).

The resulting type after applying the * operator.

Construct an EdwardsPoint from a Scalar \(a\) by computing the multiple \(aB\) of this basepoint \(B\).

The resulting type after applying the * operator.

Auto Trait Implementations

Blanket Implementations

Gets the TypeId of self. Read more

Immutably borrows from an owned value. Read more

Mutably borrows from an owned value. Read more

Returns the argument unchanged.

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Should always be Self

The resulting type after obtaining ownership.

Creates owned data from borrowed data, usually by cloning. Read more

🔬 This is a nightly-only experimental API. (toowned_clone_into)

Uses borrowed data to replace owned data, usually by cloning. Read more

The type returned in the event of a conversion error.

Performs the conversion.

The type returned in the event of a conversion error.

Performs the conversion.