Struct curve25519_dalek::edwards::EdwardsBasepointTable
source · [−]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:
EdwardsBasepointTableRadix16
: 30KB, 64A (this is the default size, and is used for [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 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 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.
Implementations
sourceimpl EdwardsBasepointTable
impl EdwardsBasepointTable
sourcepub fn create(basepoint: &EdwardsPoint) -> EdwardsBasepointTable
pub fn create(basepoint: &EdwardsPoint) -> EdwardsBasepointTable
Create a table of precomputed multiples of basepoint
.
sourcepub fn basepoint_mul(&self, scalar: &Scalar) -> EdwardsPoint
pub fn basepoint_mul(&self, scalar: &Scalar) -> EdwardsPoint
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.
sourcepub fn basepoint(&self) -> EdwardsPoint
pub fn basepoint(&self) -> EdwardsPoint
Get the basepoint for this table as an EdwardsPoint
.
Trait Implementations
sourceimpl Clone for EdwardsBasepointTable
impl Clone for EdwardsBasepointTable
sourcefn clone(&self) -> EdwardsBasepointTable
fn clone(&self) -> EdwardsBasepointTable
Returns a copy of the value. Read more
1.0.0 · sourcefn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from source
. Read more
sourceimpl<'a, 'b> Mul<&'a EdwardsBasepointTable> for &'b Scalar
impl<'a, 'b> Mul<&'a EdwardsBasepointTable> for &'b Scalar
sourcefn mul(self, basepoint_table: &'a EdwardsBasepointTable) -> EdwardsPoint
fn mul(self, basepoint_table: &'a EdwardsBasepointTable) -> EdwardsPoint
Construct an EdwardsPoint
from a Scalar
\(a\) by
computing the multiple \(aB\) of this basepoint \(B\).
type Output = EdwardsPoint
type Output = EdwardsPoint
The resulting type after applying the *
operator.
sourceimpl<'a, 'b> Mul<&'b Scalar> for &'a EdwardsBasepointTable
impl<'a, 'b> Mul<&'b Scalar> for &'a EdwardsBasepointTable
sourcefn 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
The resulting type after applying the *
operator.
Auto Trait Implementations
impl RefUnwindSafe for EdwardsBasepointTable
impl Send for EdwardsBasepointTable
impl Sync for EdwardsBasepointTable
impl Unpin for EdwardsBasepointTable
impl UnwindSafe for EdwardsBasepointTable
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcepub fn borrow_mut(&mut self) -> &mut T
pub fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more
sourceimpl<T> ToOwned for T where
T: Clone,
impl<T> ToOwned for T where
T: Clone,
type Owned = T
type Owned = T
The resulting type after obtaining ownership.
sourcepub fn to_owned(&self) -> T
pub fn to_owned(&self) -> T
Creates owned data from borrowed data, usually by cloning. Read more
sourcepub fn clone_into(&self, target: &mut T)
pub fn clone_into(&self, target: &mut T)
toowned_clone_into
)Uses borrowed data to replace owned data, usually by cloning. Read more