Botan 2.19.1
Crypto and TLS for C&
Public Member Functions | List of all members
Botan::PointGFp_Base_Point_Precompute Class Referencefinal

#include <point_mul.h>

Public Member Functions

PointGFp mul (const BigInt &k, RandomNumberGenerator &rng, const BigInt &group_order, std::vector< BigInt > &ws) const
 
 PointGFp_Base_Point_Precompute (const PointGFp &base_point, const Modular_Reducer &mod_order)
 

Detailed Description

Definition at line 16 of file point_mul.h.

Constructor & Destructor Documentation

◆ PointGFp_Base_Point_Precompute()

Botan::PointGFp_Base_Point_Precompute::PointGFp_Base_Point_Precompute ( const PointGFp base_point,
const Modular_Reducer mod_order 
)

Definition at line 54 of file point_mul.cpp.

55 :
56 m_base_point(base),
57 m_mod_order(mod_order),
58 m_p_words(base.get_curve().get_p().sig_words())
59 {
60 std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
61
62 const size_t p_bits = base.get_curve().get_p().bits();
63
64 /*
65 * Some of the curves (eg secp160k1) have an order slightly larger than
66 * the size of the prime modulus. In all cases they are at most 1 bit
67 * longer. The +1 compensates for this.
68 */
69 const size_t T_bits = round_up(p_bits + blinding_size(mod_order.get_modulus()) + 1, WINDOW_BITS) / WINDOW_BITS;
70
71 std::vector<PointGFp> T(WINDOW_SIZE*T_bits);
72
73 PointGFp g = base;
74 PointGFp g2, g4;
75
76 for(size_t i = 0; i != T_bits; i++)
77 {
78 g2 = g;
79 g2.mult2(ws);
80 g4 = g2;
81 g4.mult2(ws);
82
83 T[7*i+0] = g;
84 T[7*i+1] = std::move(g2);
85 T[7*i+2] = T[7*i+1].plus(T[7*i+0], ws); // g2+g
86 T[7*i+3] = g4;
87 T[7*i+4] = T[7*i+3].plus(T[7*i+0], ws); // g4+g
88 T[7*i+5] = T[7*i+3].plus(T[7*i+1], ws); // g4+g2
89 T[7*i+6] = T[7*i+3].plus(T[7*i+2], ws); // g4+g2+g
90
91 g.swap(g4);
92 g.mult2(ws);
93 }
94
95 PointGFp::force_all_affine(T, ws[0].get_word_vector());
96
97 m_W.resize(T.size() * 2 * m_p_words);
98
99 word* p = &m_W[0];
100 for(size_t i = 0; i != T.size(); ++i)
101 {
102 T[i].get_x().encode_words(p, m_p_words);
103 p += m_p_words;
104 T[i].get_y().encode_words(p, m_p_words);
105 p += m_p_words;
106 }
107 }
static void force_all_affine(std::vector< PointGFp > &points, secure_vector< word > &ws)
Definition: point_gfp.cpp:420
fe T
Definition: ge.cpp:37
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21

Member Function Documentation

◆ mul()

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

Definition at line 109 of file point_mul.cpp.

113 {
114 if(k.is_negative())
115 throw Invalid_Argument("PointGFp_Base_Point_Precompute scalar must be positive");
116
117 // Instead of reducing k mod group order should we alter the mask size??
118 BigInt scalar = m_mod_order.reduce(k);
119
120 if(rng.is_seeded())
121 {
122 // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
123 const BigInt mask(rng, blinding_size(group_order));
124 scalar += group_order * mask;
125 }
126 else
127 {
128 /*
129 When we don't have an RNG we cannot do scalar blinding. Instead use the
130 same trick as OpenSSL and add one or two copies of the order to normalize
131 the length of the scalar at order.bits()+1. This at least ensures the loop
132 bound does not leak information about the high bits of the scalar.
133 */
134 scalar += group_order;
135 if(scalar.bits() == group_order.bits())
136 scalar += group_order;
137 BOTAN_DEBUG_ASSERT(scalar.bits() == group_order.bits() + 1);
138 }
139
140 const size_t windows = round_up(scalar.bits(), WINDOW_BITS) / WINDOW_BITS;
141
142 const size_t elem_size = 2*m_p_words;
143
144 BOTAN_ASSERT(windows <= m_W.size() / (3*elem_size),
145 "Precomputed sufficient values for scalar mult");
146
147 PointGFp R = m_base_point.zero();
148
149 if(ws.size() < PointGFp::WORKSPACE_SIZE)
150 ws.resize(PointGFp::WORKSPACE_SIZE);
151
152 // the precomputed multiples are not secret so use std::vector
153 std::vector<word> Wt(elem_size);
154
155 for(size_t i = 0; i != windows; ++i)
156 {
157 const size_t window = windows - i - 1;
158 const size_t base_addr = (WINDOW_SIZE*window)*elem_size;
159
160 const word w = scalar.get_substring(WINDOW_BITS*window, WINDOW_BITS);
161
162 const auto w_is_1 = CT::Mask<word>::is_equal(w, 1);
163 const auto w_is_2 = CT::Mask<word>::is_equal(w, 2);
164 const auto w_is_3 = CT::Mask<word>::is_equal(w, 3);
165 const auto w_is_4 = CT::Mask<word>::is_equal(w, 4);
166 const auto w_is_5 = CT::Mask<word>::is_equal(w, 5);
167 const auto w_is_6 = CT::Mask<word>::is_equal(w, 6);
168 const auto w_is_7 = CT::Mask<word>::is_equal(w, 7);
169
170 for(size_t j = 0; j != elem_size; ++j)
171 {
172 const word w1 = w_is_1.if_set_return(m_W[base_addr + 0*elem_size + j]);
173 const word w2 = w_is_2.if_set_return(m_W[base_addr + 1*elem_size + j]);
174 const word w3 = w_is_3.if_set_return(m_W[base_addr + 2*elem_size + j]);
175 const word w4 = w_is_4.if_set_return(m_W[base_addr + 3*elem_size + j]);
176 const word w5 = w_is_5.if_set_return(m_W[base_addr + 4*elem_size + j]);
177 const word w6 = w_is_6.if_set_return(m_W[base_addr + 5*elem_size + j]);
178 const word w7 = w_is_7.if_set_return(m_W[base_addr + 6*elem_size + j]);
179
180 Wt[j] = w1 | w2 | w3 | w4 | w5 | w6 | w7;
181 }
182
183 R.add_affine(&Wt[0], m_p_words, &Wt[m_p_words], m_p_words, ws);
184
185 if(i == 0 && rng.is_seeded())
186 {
187 /*
188 * Since we start with the top bit of the exponent we know the
189 * first window must have a non-zero element, and thus R is
190 * now a point other than the point at infinity.
191 */
192 BOTAN_DEBUG_ASSERT(w != 0);
193 R.randomize_repr(rng, ws[0].get_word_vector());
194 }
195 }
196
197 BOTAN_DEBUG_ASSERT(R.on_the_curve());
198
199 return R;
200 }
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
static Mask< T > is_equal(T x, T y)
Definition: ct_utils.h:149
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:37
PointGFp zero() const
Definition: point_gfp.h:319

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


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