Botan 3.6.0
Crypto and TLS for C&
Public Member Functions | List of all members
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 29 of file point_mul.cpp.

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

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