Botan 3.0.0-alpha0
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 31 of file point_mul.cpp.

32 :
33 m_base_point(base),
34 m_mod_order(mod_order),
35 m_p_words(base.get_curve().get_p().sig_words())
36 {
37 std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
38
39 const size_t p_bits = base.get_curve().get_p().bits();
40
41 /*
42 * Some of the curves (eg secp160k1) have an order slightly larger than
43 * the size of the prime modulus. In all cases they are at most 1 bit
44 * longer. The +1 compensates for this.
45 */
46 const size_t T_bits = round_up(p_bits + blinding_size(mod_order.get_modulus()) + 1, WINDOW_BITS) / WINDOW_BITS;
47
48 std::vector<PointGFp> T(WINDOW_SIZE*T_bits);
49
50 PointGFp g = base;
51 PointGFp g2, g4;
52
53 for(size_t i = 0; i != T_bits; i++)
54 {
55 g2 = g;
56 g2.mult2(ws);
57 g4 = g2;
58 g4.mult2(ws);
59
60 T[7*i+0] = g;
61 T[7*i+1] = std::move(g2);
62 T[7*i+2] = T[7*i+1].plus(T[7*i+0], ws); // g2+g
63 T[7*i+3] = g4;
64 T[7*i+4] = T[7*i+3].plus(T[7*i+0], ws); // g4+g
65 T[7*i+5] = T[7*i+3].plus(T[7*i+1], ws); // g4+g2
66 T[7*i+6] = T[7*i+3].plus(T[7*i+2], ws); // g4+g2+g
67
68 g.swap(g4);
69 g.mult2(ws);
70 }
71
72 PointGFp::force_all_affine(T, ws[0].get_word_vector());
73
74 m_W.resize(T.size() * 2 * m_p_words);
75
76 word* p = &m_W[0];
77 for(size_t i = 0; i != T.size(); ++i)
78 {
79 T[i].get_x().encode_words(p, m_p_words);
80 p += m_p_words;
81 T[i].get_y().encode_words(p, m_p_words);
82 p += m_p_words;
83 }
84 }
static void force_all_affine(std::vector< PointGFp > &points, secure_vector< word > &ws)
Definition: point_gfp.cpp:419
fe T
Definition: ge.cpp:36
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 86 of file point_mul.cpp.

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

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: