#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)

Detailed Description

template<typename C, size_t W>
class Botan::WindowedMul2Table< C, W >

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.

Member Typedef Documentation

◆ AffinePoint

template<typename C , size_t W>

typedef C::AffinePoint Botan::WindowedMul2Table< C, W >::AffinePoint

Definition at line 1276 of file pcurves_impl.h.

◆ ProjectivePoint

template<typename C , size_t W>

typedef C::ProjectivePoint Botan::WindowedMul2Table< C, W >::ProjectivePoint

Definition at line 1277 of file pcurves_impl.h.

◆ Scalar

template<typename C , size_t W>

typedef C::Scalar Botan::WindowedMul2Table< C, W >::Scalar

Definition at line 1275 of file pcurves_impl.h.

Constructor & Destructor Documentation

◆ WindowedMul2Table()

template<typename C , size_t W>

Botan::WindowedMul2Table< C, W >::WindowedMul2Table	(	const AffinePoint &	x,
		const AffinePoint &	y )

inline

Definition at line 1288 of file pcurves_impl.h.

                                                                    {
         std::vector<ProjectivePoint> table;
         table.reserve(TableSize);
 
         for(size_t i = 0; i != TableSize; ++i) {
            const size_t t_i = (i + 1);
            const size_t x_i = t_i % WindowSize;
            const size_t y_i = (t_i >> WindowBits) % WindowSize;
 
            // Returns x_i * x + y_i * y
            auto next_tbl_e = [&]() {
               if(x_i % 2 == 0 && y_i % 2 == 0) {
                  // Where possible using doubling (eg indices 1, 7, 9 in
                  // the table above)
                  return table[(t_i / 2) - 1].dbl();
               } else if(x_i > 0 && y_i > 0) {
                  // A combination of x and y
                  return table[x_i - 1] + table[(y_i << WindowBits) - 1];
               } else if(x_i > 0 && y_i == 0) {
                  // A multiple of x without a y component
                  if(x_i == 1) {
                     // Just x
                     return ProjectivePoint::from_affine(x);
                  } else {
                     // x * x_{i-1}
                     return x + table[x_i - 1 - 1];
                  }
               } else if(x_i == 0 && y_i > 0) {
                  if(y_i == 1) {
                     // Just y
                     return ProjectivePoint::from_affine(y);
                  } else {
                     // y * y_{i-1}
                     return y + table[((y_i - 1) << WindowBits) - 1];
                  }
               } else {
                  BOTAN_ASSERT_UNREACHABLE();
               }
            };
 
            table.emplace_back(next_tbl_e());
         }
 
         m_table = ProjectivePoint::to_affine_batch(table);
      }

References BOTAN_ASSERT_UNREACHABLE, Botan::WindowedMul2Table< C, W >::TableSize, Botan::WindowedMul2Table< C, W >::WindowBits, and Botan::WindowedMul2Table< C, W >::WindowSize.

Member Function Documentation

◆ mul2_vartime()

template<typename C , size_t W>

ProjectivePoint Botan::WindowedMul2Table< C, W >::mul2_vartime	(	const Scalar &	s1,
		const Scalar &	s2 ) const

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.

                                                                             {
         const UnblindedScalarBits<C, W> bits1(s1);
         const UnblindedScalarBits<C, W> bits2(s2);
 
         auto accum = ProjectivePoint::identity();
 
         for(size_t i = 0; i != Windows; ++i) {
            if(i > 0) {
               accum = accum.dbl_n(WindowBits);
            }
 
            const size_t w_1 = bits1.get_window((Windows - i - 1) * WindowBits);
            const size_t w_2 = bits2.get_window((Windows - i - 1) * WindowBits);
 
            const size_t window = w_1 + (w_2 << WindowBits);
 
            if(window > 0) {
               accum += m_table[window - 1];
            }
         }
 
         return accum;
      }

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().

Member Data Documentation

◆ TableSize

template<typename C , size_t W>

size_t Botan::WindowedMul2Table< C, W >::TableSize = (1 << (2 * WindowBits)) - 1

staticconstexpr

Definition at line 1286 of file pcurves_impl.h.

Referenced by Botan::WindowedMul2Table< C, W >::WindowedMul2Table().

◆ WindowBits

template<typename C , size_t W>

size_t Botan::WindowedMul2Table< C, W >::WindowBits = W

staticconstexpr

Definition at line 1279 of file pcurves_impl.h.

Referenced by Botan::WindowedMul2Table< C, W >::mul2_vartime(), and Botan::WindowedMul2Table< C, W >::WindowedMul2Table().

◆ Windows

template<typename C , size_t W>

size_t Botan::WindowedMul2Table< C, W >::Windows = (Scalar::BITS + WindowBits - 1) / WindowBits

staticconstexpr

Definition at line 1281 of file pcurves_impl.h.

Referenced by Botan::WindowedMul2Table< C, W >::mul2_vartime().

◆ WindowSize

template<typename C , size_t W>

size_t Botan::WindowedMul2Table< C, W >::WindowSize = (1 << WindowBits)

staticconstexpr

Definition at line 1283 of file pcurves_impl.h.

Referenced by Botan::WindowedMul2Table< C, W >::WindowedMul2Table().

The documentation for this class was generated from the following file:

src/lib/math/pcurves/pcurves_impl.h

Public Types

Public Member Functions

Static Public Attributes

Detailed Description

Member Typedef Documentation

◆ AffinePoint

◆ ProjectivePoint

◆ Scalar

Constructor & Destructor Documentation

◆ WindowedMul2Table()

Member Function Documentation

◆ mul2_vartime()

Member Data Documentation

◆ TableSize

◆ WindowBits

◆ Windows

◆ WindowSize