Botan 3.5.0
Crypto and TLS for C&
|
#include <pcurves_impl.h>
Public Types | |
typedef C::AffinePoint | AffinePoint |
typedef C::ProjectivePoint | ProjectivePoint |
typedef C::Scalar | Scalar |
Public Member Functions | |
ProjectivePoint | mul2_vartime (const Scalar &s1, const Scalar &s2) const |
WindowedMul2Table (const AffinePoint &x, const AffinePoint &y) | |
Static Public Attributes | |
static constexpr size_t | TableSize = (1 << (2 * WindowBits)) - 1 |
static constexpr size_t | WindowBits = W |
static constexpr size_t | Windows = (Scalar::BITS + WindowBits - 1) / WindowBits |
static constexpr size_t | WindowSize = (1 << WindowBits) |
Effect 2-ary multiplication ie x*G + y*H
This is done using a windowed variant of what is usually called Shamir's trick.
The W = 1 case is simple; we precompute an extra point GH = G + H, and then examine 1 bit in each of x and y. If one or the other bits are set then add G or H resp. If both bits are set, add GH.
The example below is a precomputed table for W=2. The flattened table begins at (x_i,y_i) = (1,0), i.e. the identity element is omitted. The indices in each cell refer to the cell's location in m_table.
x-> 0 1 2 3 0 |/ (ident) |0 x |1 2x |2 3x | 1 |3 y |4 x+y |5 2x+y |6 3x+y | y = 2 |7 2y |8 x+2y |9 2(x+y) |10 3x+2y | 3 |11 3y |12 x+3y |13 2x+3y |14 3x+3y |
Definition at line 1270 of file pcurves_impl.h.
typedef C::AffinePoint Botan::WindowedMul2Table< C, W >::AffinePoint |
Definition at line 1276 of file pcurves_impl.h.
typedef C::ProjectivePoint Botan::WindowedMul2Table< C, W >::ProjectivePoint |
Definition at line 1277 of file pcurves_impl.h.
typedef C::Scalar Botan::WindowedMul2Table< C, W >::Scalar |
Definition at line 1275 of file pcurves_impl.h.
|
inline |
Definition at line 1288 of file pcurves_impl.h.
References BOTAN_ASSERT_UNREACHABLE, Botan::WindowedMul2Table< C, W >::TableSize, Botan::WindowedMul2Table< C, W >::WindowBits, and Botan::WindowedMul2Table< C, W >::WindowSize.
|
inline |
Variable time 2-ary multiplication
A common use of 2-ary multiplication is when verifying the commitments of an elliptic curve signature. Since in this case the inputs are all public, there is no problem with variable time computation.
It may be useful to offer a constant time (+blinded) variant of this in the future for handling secret inputs, for example when computing Pedersen commitments
TODO for variable time computation we could make use of a wNAF representation instead
Definition at line 1348 of file pcurves_impl.h.
References Botan::UnblindedScalarBits< C, WindowBits >::get_window(), Botan::WindowedMul2Table< C, W >::WindowBits, and Botan::WindowedMul2Table< C, W >::Windows.
Referenced by Botan::PCurve::PrimeOrderCurveImpl< C >::mul2_vartime(), and Botan::PCurve::PrimeOrderCurveImpl< C >::mul2_vartime_x_mod_order().
|
staticconstexpr |
Definition at line 1286 of file pcurves_impl.h.
Referenced by Botan::WindowedMul2Table< C, W >::WindowedMul2Table().
|
staticconstexpr |
Definition at line 1279 of file pcurves_impl.h.
Referenced by Botan::WindowedMul2Table< C, W >::mul2_vartime(), and Botan::WindowedMul2Table< C, W >::WindowedMul2Table().
|
staticconstexpr |
Definition at line 1281 of file pcurves_impl.h.
Referenced by Botan::WindowedMul2Table< C, W >::mul2_vartime().
|
staticconstexpr |
Definition at line 1283 of file pcurves_impl.h.
Referenced by Botan::WindowedMul2Table< C, W >::WindowedMul2Table().