Botan::WindowedMulTable< C, W > Class Template Reference

#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
	WindowedMulTable (const AffinePoint &p)

Static Public Attributes
static constexpr size_t	TableSize = (1 << WindowBits) - 1
static constexpr size_t	WindowBits = W
static constexpr size_t	Windows = (BlindedScalar::Bits + WindowBits - 1) / WindowBits

Detailed Description

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

Precomputed point multiplication table

This is a standard fixed window multiplication using W-bit wide window.

Definition at line 1158 of file pcurves_impl.h.

Member Typedef Documentation

AffinePoint

template<typename C , size_t W>

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

Definition at line 1161 of file pcurves_impl.h.

BlindedScalar

template<typename C , size_t W>

using Botan::WindowedMulTable< C, W >::BlindedScalar = BlindedScalarBits<C, WindowBits>

Definition at line 1167 of file pcurves_impl.h.

ProjectivePoint

template<typename C , size_t W>

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

Definition at line 1162 of file pcurves_impl.h.

Scalar

template<typename C , size_t W>

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

Definition at line 1160 of file pcurves_impl.h.

Constructor & Destructor Documentation

WindowedMulTable()

template<typename C , size_t W>

Botan::WindowedMulTable< C, W >::WindowedMulTable ( const AffinePoint & p )

inline

Definition at line 1176 of file pcurves_impl.h.

                                             : m_table{} {
         std::vector<ProjectivePoint> table;
         table.reserve(TableSize);
 
         table.push_back(ProjectivePoint::from_affine(p));
         for(size_t i = 1; i != TableSize; ++i) {
            if(i % 2 == 1) {
               table.push_back(table[i / 2].dbl());
            } else {
               table.push_back(table[i - 1] + table[0]);
            }
         }
 
         m_table = ProjectivePoint::to_affine_batch(table);
      }

References Botan::WindowedMulTable< C, W >::TableSize.

Member Function Documentation

mul()

template<typename C , size_t W>

ProjectivePoint Botan::WindowedMulTable< C, W >::mul ( const Scalar & s, RandomNumberGenerator & rng ) const

inline

Definition at line 1192 of file pcurves_impl.h.

                                                                             {
         const BlindedScalar bits(s, rng);
 
         auto accum = [&]() {
            const size_t w_0 = bits.get_window((Windows - 1) * WindowBits);
            // Guaranteed because we set the high bit of the randomizer
            BOTAN_DEBUG_ASSERT(w_0 != 0);
            auto pt = ProjectivePoint::from_affine(AffinePoint::ct_select(m_table, w_0));
            pt.ct_poison();
            pt.randomize_rep(rng);
            return pt;
         }();
 
         for(size_t i = 1; i != Windows; ++i) {
            accum = accum.dbl_n(WindowBits);
            const size_t w_i = bits.get_window((Windows - i - 1) * WindowBits);
 
            /*
            This point addition cannot be a doubling (except once)
 
            Consider the sequence of points that are operated on, and specifically
            their discrete logarithms. We start out at the point at infinity
            (dlog 0) and then add the initial window which is precisely P*w_0
 
            We then perform WindowBits doublings, so accum's dlog at the point
            of the addition in the first iteration of the loop (when i == 1) is
            at least 2^W * w_0.
 
            Since we know w_0 > 0, then in every iteration of the loop, accums
            dlog will always be greater than the dlog of the table element we
            just looked up (something between 0 and 2^W-1), and thus the
            addition into accum cannot be a doubling.
 
            However due to blinding this argument fails, since we perform
            multiplications using a scalar that is larger than the group
            order. In this case it's possible that the dlog of accum becomes
            `order + x` (or, effectively, `x`) and `x` is smaller than 2^W.
            In this case, a doubling may occur. Future iterations of the loop
            cannot be doublings by the same argument above. Since the blinding
            factor is always less than the group order (substantially so),
            it is not possible for the dlog of accum to overflow a second time.
            */
            accum += AffinePoint::ct_select(m_table, w_i);
 
            if(i <= 3) {
               accum.randomize_rep(rng);
            }
         }
 
         accum.ct_unpoison();
         return accum;
      }

References BOTAN_DEBUG_ASSERT, Botan::BlindedScalarBits< C, WindowBits >::get_window(), Botan::WindowedMulTable< C, W >::WindowBits, and Botan::WindowedMulTable< C, W >::Windows.

Member Data Documentation

TableSize

template<typename C , size_t W>

size_t Botan::WindowedMulTable< C, W >::TableSize = (1 << WindowBits) - 1

staticconstexpr

Definition at line 1174 of file pcurves_impl.h.

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

WindowBits

template<typename C , size_t W>

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

staticconstexpr

Definition at line 1164 of file pcurves_impl.h.

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

Windows

template<typename C , size_t W>

size_t Botan::WindowedMulTable< C, W >::Windows = (BlindedScalar::Bits + WindowBits - 1) / WindowBits

staticconstexpr

Definition at line 1169 of file pcurves_impl.h.

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

---

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

• src/lib/math/pcurves/pcurves_impl.h