Botan 3.9.0
Crypto and TLS for C&
Botan::EC_Point_Base_Point_Precompute Class Referencefinal

#include <point_mul.h>

Public Member Functions

 EC_Point_Base_Point_Precompute (const EC_Point &base_point, const Barrett_Reduction &mod_order)
EC_Point mul (const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const

Detailed Description

Definition at line 16 of file point_mul.h.

Constructor & Destructor Documentation

◆ EC_Point_Base_Point_Precompute()

Botan::EC_Point_Base_Point_Precompute::EC_Point_Base_Point_Precompute ( const EC_Point & base_point,
const Barrett_Reduction & mod_order )

Definition at line 40 of file point_mul.cpp.

41 :
42 m_base_point(base), m_mod_order(mod_order), m_p_words(base.get_curve().get_p_words()) {
43 std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE);
44
45 const size_t order_bits = mod_order.modulus_bits();
46
47 const size_t T_bits = round_up(order_bits + blinding_size(order_bits), WindowBits) / WindowBits;
48
49 std::vector<EC_Point> T(WindowSize * T_bits);
50
51 EC_Point g = base;
52 EC_Point g2;
53 EC_Point g4;
54
55 for(size_t i = 0; i != T_bits; i++) {
56 g2 = g;
57 g2.mult2(ws);
58 g4 = g2;
59 g4.mult2(ws);
60
61 T[7 * i + 0] = g;
62 T[7 * i + 1] = std::move(g2);
63 T[7 * i + 2] = T[7 * i + 1].plus(T[7 * i + 0], ws); // g2+g
64 T[7 * i + 3] = g4;
65 T[7 * i + 4] = T[7 * i + 3].plus(T[7 * i + 0], ws); // g4+g
66 T[7 * i + 5] = T[7 * i + 3].plus(T[7 * i + 1], ws); // g4+g2
67 T[7 * i + 6] = T[7 * i + 3].plus(T[7 * i + 2], ws); // g4+g2+g
68
69 g.swap(g4);
70 g.mult2(ws);
71 }
72
73 EC_Point::force_all_affine(T, ws[0].get_word_vector());
74
75 m_W.resize(T.size() * 2 * m_p_words);
76
77 word* p = m_W.data();
78 for(const auto& pt : T) {
79 pt.get_x().encode_words(p, m_p_words);
80 p += m_p_words;
81 pt.get_y().encode_words(p, m_p_words);
82 p += m_p_words;
83 }
84}
static void force_all_affine(std::span< EC_Point > points, secure_vector< word > &ws)
Definition ec_point.cpp:520
constexpr size_t round_up(size_t n, size_t align_to)
Definition rounding.h:26
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
Definition types.h:119

References Botan::EC_Point::force_all_affine(), Botan::Barrett_Reduction::modulus_bits(), Botan::EC_Point::mult2(), Botan::EC_Point::plus(), Botan::round_up(), Botan::EC_Point::swap(), and Botan::EC_Point::WORKSPACE_SIZE.

Member Function Documentation

◆ mul()

EC_Point Botan::EC_Point_Base_Point_Precompute::mul ( const BigInt & k,
RandomNumberGenerator & rng,
const BigInt & group_order,
std::vector< BigInt > & ws ) const

Definition at line 86 of file point_mul.cpp.

89 {
90 if(k.is_negative()) {
91 throw Invalid_Argument("EC_Point_Base_Point_Precompute scalar must be positive");
92 }
93
94 // Instead of reducing k mod group order should we alter the mask size??
95 BigInt scalar = m_mod_order.reduce(k);
96
97 if(rng.is_seeded()) {
98 // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
99 scalar += group_order * blinding_mask(group_order, rng);
100 } else {
101 /*
102 When we don't have an RNG we cannot do scalar blinding. Instead use the
103 same trick as OpenSSL and add one or two copies of the order to normalize
104 the length of the scalar at order.bits()+1. This at least ensures the loop
105 bound does not leak information about the high bits of the scalar.
106 */
107 scalar += group_order;
108 if(scalar.bits() == group_order.bits()) {
109 scalar += group_order;
110 }
111 BOTAN_DEBUG_ASSERT(scalar.bits() == group_order.bits() + 1);
112 }
113
114 const size_t windows = round_up(scalar.bits(), WindowBits) / WindowBits;
115
116 const size_t elem_size = 2 * m_p_words;
117
118 BOTAN_ASSERT(windows <= m_W.size() / (3 * elem_size), "Precomputed sufficient values for scalar mult");
119
120 EC_Point R = m_base_point.zero();
121
122 if(ws.size() < EC_Point::WORKSPACE_SIZE) {
123 ws.resize(EC_Point::WORKSPACE_SIZE);
124 }
125
126 // the precomputed multiples are not secret so use std::vector
127 std::vector<word> Wt(elem_size);
128
129 for(size_t i = 0; i != windows; ++i) {
130 const size_t window = windows - i - 1;
131 const size_t base_addr = (WindowSize * window) * elem_size;
132
133 const word w = scalar.get_substring(WindowBits * window, WindowBits);
134
135 const auto w_is_1 = CT::Mask<word>::is_equal(w, 1);
136 const auto w_is_2 = CT::Mask<word>::is_equal(w, 2);
137 const auto w_is_3 = CT::Mask<word>::is_equal(w, 3);
138 const auto w_is_4 = CT::Mask<word>::is_equal(w, 4);
139 const auto w_is_5 = CT::Mask<word>::is_equal(w, 5);
140 const auto w_is_6 = CT::Mask<word>::is_equal(w, 6);
141 const auto w_is_7 = CT::Mask<word>::is_equal(w, 7);
142
143 for(size_t j = 0; j != elem_size; ++j) {
144 const word w1 = w_is_1.if_set_return(m_W[base_addr + 0 * elem_size + j]);
145 const word w2 = w_is_2.if_set_return(m_W[base_addr + 1 * elem_size + j]);
146 const word w3 = w_is_3.if_set_return(m_W[base_addr + 2 * elem_size + j]);
147 const word w4 = w_is_4.if_set_return(m_W[base_addr + 3 * elem_size + j]);
148 const word w5 = w_is_5.if_set_return(m_W[base_addr + 4 * elem_size + j]);
149 const word w6 = w_is_6.if_set_return(m_W[base_addr + 5 * elem_size + j]);
150 const word w7 = w_is_7.if_set_return(m_W[base_addr + 6 * elem_size + j]);
151
152 Wt[j] = w1 | w2 | w3 | w4 | w5 | w6 | w7;
153 }
154
155 R.add_affine(Wt.data(), m_p_words, &Wt[m_p_words], m_p_words, ws);
156
157 if(i == 0 && rng.is_seeded()) {
158 /*
159 * Since we start with the top bit of the exponent we know the
160 * first window must have a non-zero element, and thus R is
161 * now a point other than the point at infinity.
162 */
163 BOTAN_DEBUG_ASSERT(w != 0);
164 R.randomize_repr(rng, ws[0].get_word_vector());
165 }
166 }
167
168 BOTAN_DEBUG_ASSERT(R.on_the_curve());
169
170 return R;
171}
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:129
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:62
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:470

References Botan::EC_Point::add_affine(), Botan::BigInt::bits(), BOTAN_ASSERT, BOTAN_DEBUG_ASSERT, Botan::BigInt::get_substring(), Botan::CT::Mask< T >::is_equal(), Botan::BigInt::is_negative(), Botan::RandomNumberGenerator::is_seeded(), Botan::EC_Point::on_the_curve(), Botan::EC_Point::randomize_repr(), Botan::round_up(), Botan::EC_Point::WORKSPACE_SIZE, and Botan::EC_Point::zero().


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