pub struct EdwardsBasepointTableRadix256(/* private fields */);
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 scalars 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.

Trait Implementations§

source§

impl BasepointTable for EdwardsBasepointTableRadix256

source§

fn create(basepoint: &EdwardsPoint) -> EdwardsBasepointTableRadix256

Create a table of precomputed multiples of basepoint.

source§

fn basepoint(&self) -> EdwardsPoint

Get the basepoint for this table as an EdwardsPoint.

source§

fn mul_base(&self, scalar: &Scalar) -> 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 $$ \begin{aligned} \frac{-w}{2} \leq a_i < \frac{w}{2} &&\cdots&& \frac{-w}{2} \leq a_{x} \leq \frac{w}{2} \end{aligned} $$ 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}\cdot w^{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.

§

type Point = EdwardsPoint

The type of point contained within this table.
source§

fn mul_base_clamped(&self, bytes: [u8; 32]) -> Self::Point

Multiply clamp_integer(bytes) by this precomputed basepoint table, in constant time. For a description of clamping, see clamp_integer.
source§

impl Clone for EdwardsBasepointTableRadix256

source§

fn clone(&self) -> EdwardsBasepointTableRadix256

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

impl Debug for EdwardsBasepointTableRadix256

source§

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

Formats the value using the given formatter. Read more
source§

impl<'a> From<&'a EdwardsBasepointTable> for EdwardsBasepointTableRadix256

source§

fn from( table: &'a EdwardsBasepointTableRadix16, ) -> EdwardsBasepointTableRadix256

Converts to this type from the input type.
source§

impl<'a> From<&'a EdwardsBasepointTableRadix128> for EdwardsBasepointTableRadix256

source§

fn from( table: &'a EdwardsBasepointTableRadix128, ) -> EdwardsBasepointTableRadix256

Converts to this type from the input type.
source§

impl<'a> From<&'a EdwardsBasepointTableRadix256> for EdwardsBasepointTableRadix16

source§

fn from( table: &'a EdwardsBasepointTableRadix256, ) -> EdwardsBasepointTableRadix16

Converts to this type from the input type.
source§

impl<'a> From<&'a EdwardsBasepointTableRadix256> for EdwardsBasepointTableRadix128

source§

fn from( table: &'a EdwardsBasepointTableRadix256, ) -> EdwardsBasepointTableRadix128

Converts to this type from the input type.
source§

impl<'a> From<&'a EdwardsBasepointTableRadix256> for EdwardsBasepointTableRadix32

source§

fn from( table: &'a EdwardsBasepointTableRadix256, ) -> EdwardsBasepointTableRadix32

Converts to this type from the input type.
source§

impl<'a> From<&'a EdwardsBasepointTableRadix256> for EdwardsBasepointTableRadix64

source§

fn from( table: &'a EdwardsBasepointTableRadix256, ) -> EdwardsBasepointTableRadix64

Converts to this type from the input type.
source§

impl<'a> From<&'a EdwardsBasepointTableRadix32> for EdwardsBasepointTableRadix256

source§

fn from( table: &'a EdwardsBasepointTableRadix32, ) -> EdwardsBasepointTableRadix256

Converts to this type from the input type.
source§

impl<'a> From<&'a EdwardsBasepointTableRadix64> for EdwardsBasepointTableRadix256

source§

fn from( table: &'a EdwardsBasepointTableRadix64, ) -> EdwardsBasepointTableRadix256

Converts to this type from the input type.
source§

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

source§

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

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

§

type Output = EdwardsPoint

The resulting type after applying the * operator.
source§

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

source§

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

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

§

type Output = EdwardsPoint

The resulting type after applying the * operator.

Auto Trait Implementations§

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> CloneToUninit for T
where T: Clone,

source§

default unsafe fn clone_to_uninit(&self, dst: *mut T)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dst. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

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

source§

impl<T> Same for T

§

type Output = T

Should always be Self
source§

impl<T> ToOwned for T
where T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

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

fn clone_into(&self, target: &mut T)

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

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.