Struct curve25519_dalek::edwards::EdwardsBasepointTableRadix16 [−][src]
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.
Trait Implementations
impl BasepointTable for EdwardsBasepointTableRadix16
[src]
type Point = EdwardsPoint
The type of point contained within this table.
fn create(basepoint: &EdwardsPoint) -> EdwardsBasepointTableRadix16
[src]
Create a table of precomputed multiples of basepoint
.
fn basepoint(&self) -> EdwardsPoint
[src]
Get the basepoint for this table as an EdwardsPoint
.
fn basepoint_mul(&self, scalar: &Scalar) -> EdwardsPoint
[src]
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.
impl Clone for EdwardsBasepointTableRadix16
[src]
fn clone(&self) -> EdwardsBasepointTableRadix16
[src]
pub fn clone_from(&mut self, source: &Self)
1.0.0[src]
impl Debug for EdwardsBasepointTableRadix16
[src]
impl<'a> From<&'a EdwardsBasepointTableRadix128> for EdwardsBasepointTableRadix16
[src]
fn from(
table: &'a EdwardsBasepointTableRadix128
) -> EdwardsBasepointTableRadix16
[src]
table: &'a EdwardsBasepointTableRadix128
) -> EdwardsBasepointTableRadix16
impl<'a> From<&'a EdwardsBasepointTableRadix16> for EdwardsBasepointTableRadix32
[src]
fn from(table: &'a EdwardsBasepointTableRadix16) -> EdwardsBasepointTableRadix32
[src]
impl<'a> From<&'a EdwardsBasepointTableRadix16> for EdwardsBasepointTableRadix64
[src]
fn from(table: &'a EdwardsBasepointTableRadix16) -> EdwardsBasepointTableRadix64
[src]
impl<'a> From<&'a EdwardsBasepointTableRadix16> for EdwardsBasepointTableRadix128
[src]
fn from(
table: &'a EdwardsBasepointTableRadix16
) -> EdwardsBasepointTableRadix128
[src]
table: &'a EdwardsBasepointTableRadix16
) -> EdwardsBasepointTableRadix128
impl<'a> From<&'a EdwardsBasepointTableRadix16> for EdwardsBasepointTableRadix256
[src]
fn from(
table: &'a EdwardsBasepointTableRadix16
) -> EdwardsBasepointTableRadix256
[src]
table: &'a EdwardsBasepointTableRadix16
) -> EdwardsBasepointTableRadix256
impl<'a> From<&'a EdwardsBasepointTableRadix256> for EdwardsBasepointTableRadix16
[src]
fn from(
table: &'a EdwardsBasepointTableRadix256
) -> EdwardsBasepointTableRadix16
[src]
table: &'a EdwardsBasepointTableRadix256
) -> EdwardsBasepointTableRadix16
impl<'a> From<&'a EdwardsBasepointTableRadix32> for EdwardsBasepointTableRadix16
[src]
fn from(table: &'a EdwardsBasepointTableRadix32) -> EdwardsBasepointTableRadix16
[src]
impl<'a> From<&'a EdwardsBasepointTableRadix64> for EdwardsBasepointTableRadix16
[src]
fn from(table: &'a EdwardsBasepointTableRadix64) -> EdwardsBasepointTableRadix16
[src]
impl<'a, 'b> Mul<&'a EdwardsBasepointTableRadix16> for &'b Scalar
[src]
type Output = EdwardsPoint
The resulting type after applying the *
operator.
fn mul(self, basepoint_table: &'a EdwardsBasepointTableRadix16) -> EdwardsPoint
[src]
Construct an EdwardsPoint
from a Scalar
\(a\) by
computing the multiple \(aB\) of this basepoint \(B\).
impl<'a, 'b> Mul<&'b Scalar> for &'a EdwardsBasepointTableRadix16
[src]
type Output = EdwardsPoint
The resulting type after applying the *
operator.
fn mul(self, scalar: &'b Scalar) -> EdwardsPoint
[src]
Construct an EdwardsPoint
from a Scalar
\(a\) by
computing the multiple \(aB\) of this basepoint \(B\).
Auto Trait Implementations
impl RefUnwindSafe for EdwardsBasepointTableRadix16
impl Send for EdwardsBasepointTableRadix16
impl Sync for EdwardsBasepointTableRadix16
impl Unpin for EdwardsBasepointTableRadix16
impl UnwindSafe for EdwardsBasepointTableRadix16
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
pub fn borrow_mut(&mut self) -> &mut T
[src]
impl<T, U> Cast<U> for T where
U: FromCast<T>,
[src]
U: FromCast<T>,
impl<T> From<T> for T
[src]
impl<T> FromBits<T> for T
[src]
impl<T> FromCast<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T, U> IntoBits<U> for T where
U: FromBits<T>,
[src]
U: FromBits<T>,
impl<T> Same<T> for T
type Output = T
Should always be Self
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
pub fn to_owned(&self) -> T
[src]
pub fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,