pub struct EdwardsBasepointTableRadix128(/* 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:
EdwardsBasepointTableRadix16
: 30KB, 64A (this is the default size, and is used forconstants::ED25519_BASEPOINT_TABLE
)EdwardsBasepointTableRadix64
: 120KB, 43AEdwardsBasepointTableRadix128
: 240KB, 37AEdwardsBasepointTableRadix256
: 480KB, 33A
§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 i8
s). 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 EdwardsBasepointTableRadix128
impl BasepointTable for EdwardsBasepointTableRadix128
source§fn create(basepoint: &EdwardsPoint) -> EdwardsBasepointTableRadix128
fn create(basepoint: &EdwardsPoint) -> EdwardsBasepointTableRadix128
Create a table of precomputed multiples of basepoint
.
source§fn basepoint(&self) -> EdwardsPoint
fn basepoint(&self) -> EdwardsPoint
Get the basepoint for this table as an EdwardsPoint
.
source§fn mul_base(&self, scalar: &Scalar) -> EdwardsPoint
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
type Point = EdwardsPoint
source§fn mul_base_clamped(&self, bytes: [u8; 32]) -> Self::Point
fn mul_base_clamped(&self, bytes: [u8; 32]) -> Self::Point
clamp_integer(bytes)
by this precomputed basepoint table, in constant time. For
a description of clamping, see clamp_integer
.source§impl Clone for EdwardsBasepointTableRadix128
impl Clone for EdwardsBasepointTableRadix128
source§fn clone(&self) -> EdwardsBasepointTableRadix128
fn clone(&self) -> EdwardsBasepointTableRadix128
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moresource§impl<'a> From<&'a EdwardsBasepointTable> for EdwardsBasepointTableRadix128
impl<'a> From<&'a EdwardsBasepointTable> for EdwardsBasepointTableRadix128
source§fn from(
table: &'a EdwardsBasepointTableRadix16,
) -> EdwardsBasepointTableRadix128
fn from( table: &'a EdwardsBasepointTableRadix16, ) -> EdwardsBasepointTableRadix128
source§impl<'a> From<&'a EdwardsBasepointTableRadix128> for EdwardsBasepointTableRadix16
impl<'a> From<&'a EdwardsBasepointTableRadix128> for EdwardsBasepointTableRadix16
source§fn from(
table: &'a EdwardsBasepointTableRadix128,
) -> EdwardsBasepointTableRadix16
fn from( table: &'a EdwardsBasepointTableRadix128, ) -> EdwardsBasepointTableRadix16
source§impl<'a> From<&'a EdwardsBasepointTableRadix128> for EdwardsBasepointTableRadix256
impl<'a> From<&'a EdwardsBasepointTableRadix128> for EdwardsBasepointTableRadix256
source§fn from(
table: &'a EdwardsBasepointTableRadix128,
) -> EdwardsBasepointTableRadix256
fn from( table: &'a EdwardsBasepointTableRadix128, ) -> EdwardsBasepointTableRadix256
source§impl<'a> From<&'a EdwardsBasepointTableRadix128> for EdwardsBasepointTableRadix32
impl<'a> From<&'a EdwardsBasepointTableRadix128> for EdwardsBasepointTableRadix32
source§fn from(
table: &'a EdwardsBasepointTableRadix128,
) -> EdwardsBasepointTableRadix32
fn from( table: &'a EdwardsBasepointTableRadix128, ) -> EdwardsBasepointTableRadix32
source§impl<'a> From<&'a EdwardsBasepointTableRadix128> for EdwardsBasepointTableRadix64
impl<'a> From<&'a EdwardsBasepointTableRadix128> for EdwardsBasepointTableRadix64
source§fn from(
table: &'a EdwardsBasepointTableRadix128,
) -> EdwardsBasepointTableRadix64
fn from( table: &'a EdwardsBasepointTableRadix128, ) -> EdwardsBasepointTableRadix64
source§impl<'a> From<&'a EdwardsBasepointTableRadix256> for EdwardsBasepointTableRadix128
impl<'a> From<&'a EdwardsBasepointTableRadix256> for EdwardsBasepointTableRadix128
source§fn from(
table: &'a EdwardsBasepointTableRadix256,
) -> EdwardsBasepointTableRadix128
fn from( table: &'a EdwardsBasepointTableRadix256, ) -> EdwardsBasepointTableRadix128
source§impl<'a> From<&'a EdwardsBasepointTableRadix32> for EdwardsBasepointTableRadix128
impl<'a> From<&'a EdwardsBasepointTableRadix32> for EdwardsBasepointTableRadix128
source§fn from(
table: &'a EdwardsBasepointTableRadix32,
) -> EdwardsBasepointTableRadix128
fn from( table: &'a EdwardsBasepointTableRadix32, ) -> EdwardsBasepointTableRadix128
source§impl<'a> From<&'a EdwardsBasepointTableRadix64> for EdwardsBasepointTableRadix128
impl<'a> From<&'a EdwardsBasepointTableRadix64> for EdwardsBasepointTableRadix128
source§fn from(
table: &'a EdwardsBasepointTableRadix64,
) -> EdwardsBasepointTableRadix128
fn from( table: &'a EdwardsBasepointTableRadix64, ) -> EdwardsBasepointTableRadix128
source§impl<'a, 'b> Mul<&'a EdwardsBasepointTableRadix128> for &'b Scalar
impl<'a, 'b> Mul<&'a EdwardsBasepointTableRadix128> for &'b Scalar
source§fn mul(self, basepoint_table: &'a EdwardsBasepointTableRadix128) -> EdwardsPoint
fn mul(self, basepoint_table: &'a EdwardsBasepointTableRadix128) -> EdwardsPoint
Construct an EdwardsPoint
from a Scalar
\(a\) by
computing the multiple \(aB\) of this basepoint \(B\).
§type Output = EdwardsPoint
type Output = EdwardsPoint
*
operator.source§impl<'a, 'b> Mul<&'b Scalar> for &'a EdwardsBasepointTableRadix128
impl<'a, 'b> Mul<&'b Scalar> for &'a EdwardsBasepointTableRadix128
source§fn mul(self, scalar: &'b Scalar) -> EdwardsPoint
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
type Output = EdwardsPoint
*
operator.Auto Trait Implementations§
impl Freeze for EdwardsBasepointTableRadix128
impl RefUnwindSafe for EdwardsBasepointTableRadix128
impl Send for EdwardsBasepointTableRadix128
impl Sync for EdwardsBasepointTableRadix128
impl Unpin for EdwardsBasepointTableRadix128
impl UnwindSafe for EdwardsBasepointTableRadix128
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> FmtForward for T
impl<T> FmtForward for T
source§fn fmt_binary(self) -> FmtBinary<Self>where
Self: Binary,
fn fmt_binary(self) -> FmtBinary<Self>where
Self: Binary,
self
to use its Binary
implementation when Debug
-formatted.source§fn fmt_display(self) -> FmtDisplay<Self>where
Self: Display,
fn fmt_display(self) -> FmtDisplay<Self>where
Self: Display,
self
to use its Display
implementation when
Debug
-formatted.source§fn fmt_lower_exp(self) -> FmtLowerExp<Self>where
Self: LowerExp,
fn fmt_lower_exp(self) -> FmtLowerExp<Self>where
Self: LowerExp,
self
to use its LowerExp
implementation when
Debug
-formatted.source§fn fmt_lower_hex(self) -> FmtLowerHex<Self>where
Self: LowerHex,
fn fmt_lower_hex(self) -> FmtLowerHex<Self>where
Self: LowerHex,
self
to use its LowerHex
implementation when
Debug
-formatted.source§fn fmt_octal(self) -> FmtOctal<Self>where
Self: Octal,
fn fmt_octal(self) -> FmtOctal<Self>where
Self: Octal,
self
to use its Octal
implementation when Debug
-formatted.source§fn fmt_pointer(self) -> FmtPointer<Self>where
Self: Pointer,
fn fmt_pointer(self) -> FmtPointer<Self>where
Self: Pointer,
self
to use its Pointer
implementation when
Debug
-formatted.source§fn fmt_upper_exp(self) -> FmtUpperExp<Self>where
Self: UpperExp,
fn fmt_upper_exp(self) -> FmtUpperExp<Self>where
Self: UpperExp,
self
to use its UpperExp
implementation when
Debug
-formatted.source§fn fmt_upper_hex(self) -> FmtUpperHex<Self>where
Self: UpperHex,
fn fmt_upper_hex(self) -> FmtUpperHex<Self>where
Self: UpperHex,
self
to use its UpperHex
implementation when
Debug
-formatted.source§impl<T> Pipe for Twhere
T: ?Sized,
impl<T> Pipe for Twhere
T: ?Sized,
source§fn pipe<R>(self, func: impl FnOnce(Self) -> R) -> Rwhere
Self: Sized,
fn pipe<R>(self, func: impl FnOnce(Self) -> R) -> Rwhere
Self: Sized,
source§fn pipe_ref<'a, R>(&'a self, func: impl FnOnce(&'a Self) -> R) -> Rwhere
R: 'a,
fn pipe_ref<'a, R>(&'a self, func: impl FnOnce(&'a Self) -> R) -> Rwhere
R: 'a,
self
and passes that borrow into the pipe function. Read moresource§fn pipe_ref_mut<'a, R>(&'a mut self, func: impl FnOnce(&'a mut Self) -> R) -> Rwhere
R: 'a,
fn pipe_ref_mut<'a, R>(&'a mut self, func: impl FnOnce(&'a mut Self) -> R) -> Rwhere
R: 'a,
self
and passes that borrow into the pipe function. Read moresource§fn pipe_borrow<'a, B, R>(&'a self, func: impl FnOnce(&'a B) -> R) -> R
fn pipe_borrow<'a, B, R>(&'a self, func: impl FnOnce(&'a B) -> R) -> R
source§fn pipe_borrow_mut<'a, B, R>(
&'a mut self,
func: impl FnOnce(&'a mut B) -> R,
) -> R
fn pipe_borrow_mut<'a, B, R>( &'a mut self, func: impl FnOnce(&'a mut B) -> R, ) -> R
source§fn pipe_as_ref<'a, U, R>(&'a self, func: impl FnOnce(&'a U) -> R) -> R
fn pipe_as_ref<'a, U, R>(&'a self, func: impl FnOnce(&'a U) -> R) -> R
self
, then passes self.as_ref()
into the pipe function.source§fn pipe_as_mut<'a, U, R>(&'a mut self, func: impl FnOnce(&'a mut U) -> R) -> R
fn pipe_as_mut<'a, U, R>(&'a mut self, func: impl FnOnce(&'a mut U) -> R) -> R
self
, then passes self.as_mut()
into the pipe
function.source§fn pipe_deref<'a, T, R>(&'a self, func: impl FnOnce(&'a T) -> R) -> R
fn pipe_deref<'a, T, R>(&'a self, func: impl FnOnce(&'a T) -> R) -> R
self
, then passes self.deref()
into the pipe function.source§impl<T> Tap for T
impl<T> Tap for T
source§fn tap_borrow<B>(self, func: impl FnOnce(&B)) -> Self
fn tap_borrow<B>(self, func: impl FnOnce(&B)) -> Self
Borrow<B>
of a value. Read moresource§fn tap_borrow_mut<B>(self, func: impl FnOnce(&mut B)) -> Self
fn tap_borrow_mut<B>(self, func: impl FnOnce(&mut B)) -> Self
BorrowMut<B>
of a value. Read moresource§fn tap_ref<R>(self, func: impl FnOnce(&R)) -> Self
fn tap_ref<R>(self, func: impl FnOnce(&R)) -> Self
AsRef<R>
view of a value. Read moresource§fn tap_ref_mut<R>(self, func: impl FnOnce(&mut R)) -> Self
fn tap_ref_mut<R>(self, func: impl FnOnce(&mut R)) -> Self
AsMut<R>
view of a value. Read moresource§fn tap_deref<T>(self, func: impl FnOnce(&T)) -> Self
fn tap_deref<T>(self, func: impl FnOnce(&T)) -> Self
Deref::Target
of a value. Read moresource§fn tap_deref_mut<T>(self, func: impl FnOnce(&mut T)) -> Self
fn tap_deref_mut<T>(self, func: impl FnOnce(&mut T)) -> Self
Deref::Target
of a value. Read moresource§fn tap_dbg(self, func: impl FnOnce(&Self)) -> Self
fn tap_dbg(self, func: impl FnOnce(&Self)) -> Self
.tap()
only in debug builds, and is erased in release builds.source§fn tap_mut_dbg(self, func: impl FnOnce(&mut Self)) -> Self
fn tap_mut_dbg(self, func: impl FnOnce(&mut Self)) -> Self
.tap_mut()
only in debug builds, and is erased in release
builds.source§fn tap_borrow_dbg<B>(self, func: impl FnOnce(&B)) -> Self
fn tap_borrow_dbg<B>(self, func: impl FnOnce(&B)) -> Self
.tap_borrow()
only in debug builds, and is erased in release
builds.source§fn tap_borrow_mut_dbg<B>(self, func: impl FnOnce(&mut B)) -> Self
fn tap_borrow_mut_dbg<B>(self, func: impl FnOnce(&mut B)) -> Self
.tap_borrow_mut()
only in debug builds, and is erased in release
builds.source§fn tap_ref_dbg<R>(self, func: impl FnOnce(&R)) -> Self
fn tap_ref_dbg<R>(self, func: impl FnOnce(&R)) -> Self
.tap_ref()
only in debug builds, and is erased in release
builds.source§fn tap_ref_mut_dbg<R>(self, func: impl FnOnce(&mut R)) -> Self
fn tap_ref_mut_dbg<R>(self, func: impl FnOnce(&mut R)) -> Self
.tap_ref_mut()
only in debug builds, and is erased in release
builds.source§fn tap_deref_dbg<T>(self, func: impl FnOnce(&T)) -> Self
fn tap_deref_dbg<T>(self, func: impl FnOnce(&T)) -> Self
.tap_deref()
only in debug builds, and is erased in release
builds.