Botan 3.6.1
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 Modular_Reducer &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 Modular_Reducer & mod_order )

Definition at line 35 of file point_mul.cpp.

35 :
36 m_base_point(base), m_mod_order(mod_order), m_p_words(base.get_curve().get_p_words()) {
37 std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE);
38
39 const size_t order_bits = mod_order.get_modulus().bits();
40
41 const size_t T_bits = round_up(order_bits + blinding_size(mod_order.get_modulus()), WINDOW_BITS) / WINDOW_BITS;
42
43 std::vector<EC_Point> T(WINDOW_SIZE * T_bits);
44
45 EC_Point g = base;
46 EC_Point g2, g4;
47
48 for(size_t i = 0; i != T_bits; i++) {
49 g2 = g;
50 g2.mult2(ws);
51 g4 = g2;
52 g4.mult2(ws);
53
54 T[7 * i + 0] = g;
55 T[7 * i + 1] = std::move(g2);
56 T[7 * i + 2] = T[7 * i + 1].plus(T[7 * i + 0], ws); // g2+g
57 T[7 * i + 3] = g4;
58 T[7 * i + 4] = T[7 * i + 3].plus(T[7 * i + 0], ws); // g4+g
59 T[7 * i + 5] = T[7 * i + 3].plus(T[7 * i + 1], ws); // g4+g2
60 T[7 * i + 6] = T[7 * i + 3].plus(T[7 * i + 2], ws); // g4+g2+g
61
62 g.swap(g4);
63 g.mult2(ws);
64 }
65
66 EC_Point::force_all_affine(T, ws[0].get_word_vector());
67
68 m_W.resize(T.size() * 2 * m_p_words);
69
70 word* p = &m_W[0];
71 for(size_t i = 0; i != T.size(); ++i) {
72 T[i].get_x().encode_words(p, m_p_words);
73 p += m_p_words;
74 T[i].get_y().encode_words(p, m_p_words);
75 p += m_p_words;
76 }
77}
static void force_all_affine(std::span< EC_Point > points, secure_vector< word > &ws)
Definition ec_point.cpp:387
FE_25519 T
Definition ge.cpp:34
constexpr size_t round_up(size_t n, size_t align_to)
Definition rounding.h:25

References Botan::BigInt::bits(), Botan::EC_Point::force_all_affine(), Botan::Modular_Reducer::get_modulus(), Botan::EC_Point::mult2(), Botan::EC_Point::plus(), Botan::round_up(), Botan::EC_Point::swap(), T, 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 79 of file point_mul.cpp.

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

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::Modular_Reducer::reduce(), Botan::round_up(), Botan::EC_Point::WORKSPACE_SIZE, and Botan::EC_Point::zero().


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