#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

Detailed Description

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

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.

Member Typedef Documentation

◆ AffinePoint

template<typename C , size_t W>

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

Definition at line 1073 of file pcurves_impl.h.

◆ BlindedScalar

template<typename C , size_t W>

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

Definition at line 1079 of file pcurves_impl.h.

◆ ProjectivePoint

template<typename C , size_t W>

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

Definition at line 1074 of file pcurves_impl.h.

◆ Scalar

template<typename C , size_t W>

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

Definition at line 1072 of file pcurves_impl.h.

Constructor & Destructor Documentation

◆ PrecomputedBaseMulTable()

template<typename C , size_t W>

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

inline

Definition at line 1090 of file pcurves_impl.h.

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

References Botan::PrecomputedBaseMulTable< C, W >::TableSize, and Botan::PrecomputedBaseMulTable< C, W >::WindowElements.

Member Function Documentation

◆ mul()

template<typename C , size_t W>

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

inline

Definition at line 1113 of file pcurves_impl.h.

                                                                             {
         const BlindedScalar bits(s, rng);
 
         // TODO: C++23 - use std::mdspan to access m_table
         auto table = std::span{m_table};
 
         auto accum = [&]() {
            const size_t w_0 = bits.get_window(0);
            const auto tbl_0 = table.first(WindowElements);
            auto pt = ProjectivePoint::from_affine(AffinePoint::ct_select(tbl_0, w_0));
            pt.ct_poison();
            pt.randomize_rep(rng);
            return pt;
         }();
 
         for(size_t i = 1; i != Windows; ++i) {
            const size_t w_i = bits.get_window(WindowBits * i);
            const auto tbl_i = table.subspan(WindowElements * i, WindowElements);
 
            /*
            None of these additions can be doublings, because in each iteration, the
            discrete logarithms of the points we're selecting out of the table are
            larger than the largest possible dlog of accum.
            */
            accum += AffinePoint::ct_select(tbl_i, w_i);
 
            if(i <= 3) {
               accum.randomize_rep(rng);
            }
         }
 
         accum.ct_unpoison();
         return accum;
      }