Botan 3.5.0
Crypto and TLS for C&
|
#include <pcurves_impl.h>
Public Types | |
typedef C::AffinePoint | AffinePoint |
using | BlindedScalar = BlindedScalarBits<C, WindowBits> |
typedef C::ProjectivePoint | ProjectivePoint |
typedef C::Scalar | Scalar |
Public Member Functions | |
ProjectivePoint | mul (const Scalar &s, RandomNumberGenerator &rng) const |
PrecomputedBaseMulTable (const AffinePoint &p) | |
Static Public Attributes | |
static constexpr size_t | TableSize = Windows * WindowElements |
static constexpr size_t | WindowBits = W |
static constexpr size_t | WindowElements = (1 << WindowBits) - 1 |
static constexpr size_t | Windows = (BlindedScalar::Bits + WindowBits - 1) / WindowBits |
Base point precomputation table
This algorithm works by precomputing a set of points such that the online phase of the point multiplication can be effected by a sequence of point additions.
The tables, even for W = 1, are large and costly to precompute, so this is only used for the base point.
The online phase of the algorithm uess ceil(SB/W)
additions, and no point doublings. The table is of size ceil(SB + W - 1)/W * ((1 << W) - 1)
where SB is the bit length of the (blinded) scalar.
Each window of the scalar is associated with a window in the table. The table windows are unique to that offset within the scalar.
The simplest version to understand is when W = 1. There the table consists of [P, 2*P, 4*P, ..., 2^N*P] where N is the bit length of the group order. The online phase consists of conditionally adding table[i] depending on if bit i of the scalar is set or not.
When W = 2, the scalar is examined 2 bits at a time, and the table for a window index I
is [(2^I)*P, (2^(I+1))*P, (2^I+2^(I+1))*P].
This extends similarly for larger W
At a certain point, the side channel silent table lookup becomes the dominating cost
For all W, each window in the table has an implicit element of the identity element which is used if the scalar bits were all zero. This is omitted to save space; AffinePoint::ct_select is designed to assist in this by returning the identity element if its index argument is zero, or otherwise it returns table[idx - 1]
Definition at line 1070 of file pcurves_impl.h.
typedef C::AffinePoint Botan::PrecomputedBaseMulTable< C, W >::AffinePoint |
Definition at line 1073 of file pcurves_impl.h.
using Botan::PrecomputedBaseMulTable< C, W >::BlindedScalar = BlindedScalarBits<C, WindowBits> |
Definition at line 1079 of file pcurves_impl.h.
typedef C::ProjectivePoint Botan::PrecomputedBaseMulTable< C, W >::ProjectivePoint |
Definition at line 1074 of file pcurves_impl.h.
typedef C::Scalar Botan::PrecomputedBaseMulTable< C, W >::Scalar |
Definition at line 1072 of file pcurves_impl.h.
|
inline |
Definition at line 1090 of file pcurves_impl.h.
References Botan::PrecomputedBaseMulTable< C, W >::TableSize, and Botan::PrecomputedBaseMulTable< C, W >::WindowElements.
|
inline |
Definition at line 1113 of file pcurves_impl.h.
References Botan::BlindedScalarBits< C, WindowBits >::get_window(), Botan::PrecomputedBaseMulTable< C, W >::WindowBits, Botan::PrecomputedBaseMulTable< C, W >::WindowElements, and Botan::PrecomputedBaseMulTable< C, W >::Windows.
Referenced by Botan::PCurve::PrimeOrderCurveImpl< C >::base_point_mul_x_mod_order(), and Botan::PCurve::PrimeOrderCurveImpl< C >::mul_by_g().
|
staticconstexpr |
Definition at line 1088 of file pcurves_impl.h.
Referenced by Botan::PrecomputedBaseMulTable< C, W >::PrecomputedBaseMulTable().
|
staticconstexpr |
Definition at line 1076 of file pcurves_impl.h.
Referenced by Botan::PrecomputedBaseMulTable< C, W >::mul().
|
staticconstexpr |
Definition at line 1086 of file pcurves_impl.h.
Referenced by Botan::PrecomputedBaseMulTable< C, W >::mul(), and Botan::PrecomputedBaseMulTable< C, W >::PrecomputedBaseMulTable().
|
staticconstexpr |
Definition at line 1081 of file pcurves_impl.h.
Referenced by Botan::PrecomputedBaseMulTable< C, W >::mul().