Trait curve25519_dalek::traits::BasepointTable[−][src]

pub trait BasepointTable {
    type Point;
    fn create(basepoint: &Self::Point) -> Self;

    fn basepoint(&self) -> Self::Point;

    fn basepoint_mul(&self, scalar: &Scalar) -> Self::Point;
}
Expand description

A precomputed table of basepoints, for optimising scalar multiplications.

Associated Types

The type of point contained within this table.

Required methods

Generate a new precomputed basepoint table from the given basepoint.

Retrieve the original basepoint from this table.

Multiply a scalar by this precomputed basepoint table, in constant time.

Implementors

Create a table of precomputed multiples of basepoint.

Get the basepoint for this table as an EdwardsPoint.

The computation uses Pippeneger’s algorithm, as described for the specific case of radix-16 on page 13 of the Ed25519 paper.

Piggenger’s Algorithm Generalised

Write the scalar \(a\) in radix-\(w\), where \(w\) is a power of 2, with coefficients in \([\frac{-w}{2},\frac{w}{2})\), i.e., $$ a = a_0 + a_1 w^1 + \cdots + a_{x} w^{x}, $$ with $$ \frac{-w}{2} \leq a_i < \frac{w}{2}, \cdots, \frac{-w}{2} \leq a_{x} \leq \frac{w}{2} $$ and the number of additions, \(x\), is given by \(x = \lceil \frac{256}{w} \rceil\). Then $$ a B = a_0 B + a_1 w^1 B + \cdots + a_{x-1} w^{x-1} B. $$ Grouping even and odd coefficients gives $$ \begin{aligned} a B = \quad a_0 w^0 B +& a_2 w^2 B + \cdots + a_{x-2} w^{x-2} B \\ + a_1 w^1 B +& a_3 w^3 B + \cdots + a_{x-1} w^{x-1} B \\ = \quad(a_0 w^0 B +& a_2 w^2 B + \cdots + a_{x-2} w^{x-2} B) \\ + w(a_1 w^0 B +& a_3 w^2 B + \cdots + a_{x-1} w^{x-2} B). \\ \end{aligned} $$ For each \(i = 0 \ldots 31\), we create a lookup table of $$ [w^{2i} B, \ldots, \frac{w}{2}\cdotw^{2i} B], $$ and use it to select \( y \cdot w^{2i} \cdot B \) in constant time.

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

The above algorithm is trivially generalised to other powers-of-2 radices.

Create a table of precomputed multiples of basepoint.

Get the basepoint for this table as an EdwardsPoint.

The computation uses Pippeneger’s algorithm, as described for the specific case of radix-16 on page 13 of the Ed25519 paper.

Piggenger’s Algorithm Generalised

Write the scalar \(a\) in radix-\(w\), where \(w\) is a power of 2, with coefficients in \([\frac{-w}{2},\frac{w}{2})\), i.e., $$ a = a_0 + a_1 w^1 + \cdots + a_{x} w^{x}, $$ with $$ \frac{-w}{2} \leq a_i < \frac{w}{2}, \cdots, \frac{-w}{2} \leq a_{x} \leq \frac{w}{2} $$ and the number of additions, \(x\), is given by \(x = \lceil \frac{256}{w} \rceil\). Then $$ a B = a_0 B + a_1 w^1 B + \cdots + a_{x-1} w^{x-1} B. $$ Grouping even and odd coefficients gives $$ \begin{aligned} a B = \quad a_0 w^0 B +& a_2 w^2 B + \cdots + a_{x-2} w^{x-2} B \\ + a_1 w^1 B +& a_3 w^3 B + \cdots + a_{x-1} w^{x-1} B \\ = \quad(a_0 w^0 B +& a_2 w^2 B + \cdots + a_{x-2} w^{x-2} B) \\ + w(a_1 w^0 B +& a_3 w^2 B + \cdots + a_{x-1} w^{x-2} B). \\ \end{aligned} $$ For each \(i = 0 \ldots 31\), we create a lookup table of $$ [w^{2i} B, \ldots, \frac{w}{2}\cdotw^{2i} B], $$ and use it to select \( y \cdot w^{2i} \cdot B \) in constant time.

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

The above algorithm is trivially generalised to other powers-of-2 radices.

Create a table of precomputed multiples of basepoint.

Get the basepoint for this table as an EdwardsPoint.

The computation uses Pippeneger’s algorithm, as described for the specific case of radix-16 on page 13 of the Ed25519 paper.

Piggenger’s Algorithm Generalised

Write the scalar \(a\) in radix-\(w\), where \(w\) is a power of 2, with coefficients in \([\frac{-w}{2},\frac{w}{2})\), i.e., $$ a = a_0 + a_1 w^1 + \cdots + a_{x} w^{x}, $$ with $$ \frac{-w}{2} \leq a_i < \frac{w}{2}, \cdots, \frac{-w}{2} \leq a_{x} \leq \frac{w}{2} $$ and the number of additions, \(x\), is given by \(x = \lceil \frac{256}{w} \rceil\). Then $$ a B = a_0 B + a_1 w^1 B + \cdots + a_{x-1} w^{x-1} B. $$ Grouping even and odd coefficients gives $$ \begin{aligned} a B = \quad a_0 w^0 B +& a_2 w^2 B + \cdots + a_{x-2} w^{x-2} B \\ + a_1 w^1 B +& a_3 w^3 B + \cdots + a_{x-1} w^{x-1} B \\ = \quad(a_0 w^0 B +& a_2 w^2 B + \cdots + a_{x-2} w^{x-2} B) \\ + w(a_1 w^0 B +& a_3 w^2 B + \cdots + a_{x-1} w^{x-2} B). \\ \end{aligned} $$ For each \(i = 0 \ldots 31\), we create a lookup table of $$ [w^{2i} B, \ldots, \frac{w}{2}\cdotw^{2i} B], $$ and use it to select \( y \cdot w^{2i} \cdot B \) in constant time.

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

The above algorithm is trivially generalised to other powers-of-2 radices.

Create a table of precomputed multiples of basepoint.

Get the basepoint for this table as an EdwardsPoint.

The computation uses Pippeneger’s algorithm, as described for the specific case of radix-16 on page 13 of the Ed25519 paper.

Piggenger’s Algorithm Generalised

Write the scalar \(a\) in radix-\(w\), where \(w\) is a power of 2, with coefficients in \([\frac{-w}{2},\frac{w}{2})\), i.e., $$ a = a_0 + a_1 w^1 + \cdots + a_{x} w^{x}, $$ with $$ \frac{-w}{2} \leq a_i < \frac{w}{2}, \cdots, \frac{-w}{2} \leq a_{x} \leq \frac{w}{2} $$ and the number of additions, \(x\), is given by \(x = \lceil \frac{256}{w} \rceil\). Then $$ a B = a_0 B + a_1 w^1 B + \cdots + a_{x-1} w^{x-1} B. $$ Grouping even and odd coefficients gives $$ \begin{aligned} a B = \quad a_0 w^0 B +& a_2 w^2 B + \cdots + a_{x-2} w^{x-2} B \\ + a_1 w^1 B +& a_3 w^3 B + \cdots + a_{x-1} w^{x-1} B \\ = \quad(a_0 w^0 B +& a_2 w^2 B + \cdots + a_{x-2} w^{x-2} B) \\ + w(a_1 w^0 B +& a_3 w^2 B + \cdots + a_{x-1} w^{x-2} B). \\ \end{aligned} $$ For each \(i = 0 \ldots 31\), we create a lookup table of $$ [w^{2i} B, \ldots, \frac{w}{2}\cdotw^{2i} B], $$ and use it to select \( y \cdot w^{2i} \cdot B \) in constant time.

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

The above algorithm is trivially generalised to other powers-of-2 radices.

Create a table of precomputed multiples of basepoint.

Get the basepoint for this table as an EdwardsPoint.

The computation uses Pippeneger’s algorithm, as described for the specific case of radix-16 on page 13 of the Ed25519 paper.

Piggenger’s Algorithm Generalised

Write the scalar \(a\) in radix-\(w\), where \(w\) is a power of 2, with coefficients in \([\frac{-w}{2},\frac{w}{2})\), i.e., $$ a = a_0 + a_1 w^1 + \cdots + a_{x} w^{x}, $$ with $$ \frac{-w}{2} \leq a_i < \frac{w}{2}, \cdots, \frac{-w}{2} \leq a_{x} \leq \frac{w}{2} $$ and the number of additions, \(x\), is given by \(x = \lceil \frac{256}{w} \rceil\). Then $$ a B = a_0 B + a_1 w^1 B + \cdots + a_{x-1} w^{x-1} B. $$ Grouping even and odd coefficients gives $$ \begin{aligned} a B = \quad a_0 w^0 B +& a_2 w^2 B + \cdots + a_{x-2} w^{x-2} B \\ + a_1 w^1 B +& a_3 w^3 B + \cdots + a_{x-1} w^{x-1} B \\ = \quad(a_0 w^0 B +& a_2 w^2 B + \cdots + a_{x-2} w^{x-2} B) \\ + w(a_1 w^0 B +& a_3 w^2 B + \cdots + a_{x-1} w^{x-2} B). \\ \end{aligned} $$ For each \(i = 0 \ldots 31\), we create a lookup table of $$ [w^{2i} B, \ldots, \frac{w}{2}\cdotw^{2i} B], $$ and use it to select \( y \cdot w^{2i} \cdot B \) in constant time.

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

The above algorithm is trivially generalised to other powers-of-2 radices.