Struct curve25519_dalek::edwards::EdwardsBasepointTable

pub struct EdwardsBasepointTable(pub(crate) [LookupTable<AffineNielsPoint>; 32]);

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 (30KB), so they should probably be boxed.

Methods

impl EdwardsBasepointTable

fn basepoint_mul(&self, scalar: &Scalar) -> EdwardsPoint

The computation uses Pippeneger'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.

impl EdwardsBasepointTable

pub fn create(basepoint: &EdwardsPoint) -> EdwardsBasepointTable

Create a table of precomputed multiples of basepoint.

pub fn basepoint(&self) -> EdwardsPoint

Get the basepoint for this table as an EdwardsPoint.

Trait Implementations

impl Clone for EdwardsBasepointTable

fn clone(&self) -> EdwardsBasepointTable

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for EdwardsBasepointTable

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<'a, 'b> Mul<&'a EdwardsBasepointTable> for &'b Scalar

type Output = EdwardsPoint

The resulting type after applying the * operator.

fn mul(self, basepoint_table: &'a EdwardsBasepointTable) -> EdwardsPoint

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

impl<'a, 'b> Mul<&'b Scalar> for &'a EdwardsBasepointTable

type Output = EdwardsPoint

The resulting type after applying the * operator.

fn mul(self, scalar: &'b Scalar) -> EdwardsPoint

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