/src/botan/src/lib/math/numbertheory/monty.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * (C) 2018 Jack Lloyd |
3 | | * |
4 | | * Botan is released under the Simplified BSD License (see license.txt) |
5 | | */ |
6 | | |
7 | | #include <botan/monty.h> |
8 | | #include <botan/reducer.h> |
9 | | #include <botan/internal/mp_core.h> |
10 | | |
11 | | namespace Botan { |
12 | | |
13 | | Montgomery_Params::Montgomery_Params(const BigInt& p, |
14 | | const Modular_Reducer& mod_p) |
15 | 84.2k | { |
16 | 84.2k | if(p.is_even() || p < 3) |
17 | 24 | throw Invalid_Argument("Montgomery_Params invalid modulus"); |
18 | 84.1k | |
19 | 84.1k | m_p = p; |
20 | 84.1k | m_p_words = m_p.sig_words(); |
21 | 84.1k | m_p_dash = monty_inverse(m_p.word_at(0)); |
22 | 84.1k | |
23 | 84.1k | const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS); |
24 | 84.1k | |
25 | 84.1k | m_r1 = mod_p.reduce(r); |
26 | 84.1k | m_r2 = mod_p.square(m_r1); |
27 | 84.1k | m_r3 = mod_p.multiply(m_r1, m_r2); |
28 | 84.1k | } |
29 | | |
30 | | Montgomery_Params::Montgomery_Params(const BigInt& p) |
31 | 6.53k | { |
32 | 6.53k | |
33 | 6.53k | if(p.is_negative() || p.is_even()) |
34 | 0 | throw Invalid_Argument("Montgomery_Params invalid modulus"); |
35 | 6.53k | |
36 | 6.53k | m_p = p; |
37 | 6.53k | m_p_words = m_p.sig_words(); |
38 | 6.53k | m_p_dash = monty_inverse(m_p.word_at(0)); |
39 | 6.53k | |
40 | 6.53k | const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS); |
41 | 6.53k | |
42 | | // It might be faster to use ct_modulo here vs setting up Barrett reduction? |
43 | 6.53k | Modular_Reducer mod_p(p); |
44 | 6.53k | |
45 | 6.53k | m_r1 = mod_p.reduce(r); |
46 | 6.53k | m_r2 = mod_p.square(m_r1); |
47 | 6.53k | m_r3 = mod_p.multiply(m_r1, m_r2); |
48 | 6.53k | } |
49 | | |
50 | | BigInt Montgomery_Params::inv_mod_p(const BigInt& x) const |
51 | 0 | { |
52 | | // TODO use Montgomery inverse here? |
53 | 0 | return inverse_mod(x, p()); |
54 | 0 | } |
55 | | |
56 | | BigInt Montgomery_Params::redc(const BigInt& x, secure_vector<word>& ws) const |
57 | 95.1k | { |
58 | 95.1k | const size_t output_size = 2*m_p_words + 2; |
59 | 95.1k | |
60 | 95.1k | if(ws.size() < output_size) |
61 | 95.1k | ws.resize(output_size); |
62 | 95.1k | |
63 | 95.1k | BigInt z = x; |
64 | 95.1k | z.grow_to(output_size); |
65 | 95.1k | |
66 | 95.1k | bigint_monty_redc(z.mutable_data(), |
67 | 95.1k | m_p.data(), m_p_words, m_p_dash, |
68 | 95.1k | ws.data(), ws.size()); |
69 | 95.1k | |
70 | 95.1k | return z; |
71 | 95.1k | } |
72 | | |
73 | | BigInt Montgomery_Params::mul(const BigInt& x, const BigInt& y, |
74 | | secure_vector<word>& ws) const |
75 | 1.34M | { |
76 | 1.34M | const size_t output_size = 2*m_p_words + 2; |
77 | 1.34M | |
78 | 1.34M | if(ws.size() < output_size) |
79 | 1.34M | ws.resize(output_size); |
80 | 1.34M | |
81 | 1.34M | BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words); |
82 | 1.34M | BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words); |
83 | 1.34M | |
84 | 1.34M | BigInt z(BigInt::Positive, output_size); |
85 | 1.34M | bigint_mul(z.mutable_data(), z.size(), |
86 | 1.34M | x.data(), x.size(), std::min(m_p_words, x.size()), |
87 | 1.34M | y.data(), y.size(), std::min(m_p_words, y.size()), |
88 | 1.34M | ws.data(), ws.size()); |
89 | 1.34M | |
90 | 1.34M | bigint_monty_redc(z.mutable_data(), |
91 | 1.34M | m_p.data(), m_p_words, m_p_dash, |
92 | 1.34M | ws.data(), ws.size()); |
93 | 1.34M | |
94 | 1.34M | return z; |
95 | 1.34M | } |
96 | | |
97 | | BigInt Montgomery_Params::mul(const BigInt& x, |
98 | | const secure_vector<word>& y, |
99 | | secure_vector<word>& ws) const |
100 | 0 | { |
101 | 0 | const size_t output_size = 2*m_p_words + 2; |
102 | 0 | if(ws.size() < output_size) |
103 | 0 | ws.resize(output_size); |
104 | 0 | BigInt z(BigInt::Positive, output_size); |
105 | 0 |
|
106 | 0 | BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words); |
107 | 0 |
|
108 | 0 | bigint_mul(z.mutable_data(), z.size(), |
109 | 0 | x.data(), x.size(), std::min(m_p_words, x.size()), |
110 | 0 | y.data(), y.size(), std::min(m_p_words, y.size()), |
111 | 0 | ws.data(), ws.size()); |
112 | 0 |
|
113 | 0 | bigint_monty_redc(z.mutable_data(), |
114 | 0 | m_p.data(), m_p_words, m_p_dash, |
115 | 0 | ws.data(), ws.size()); |
116 | 0 |
|
117 | 0 | return z; |
118 | 0 | } |
119 | | |
120 | | void Montgomery_Params::mul_by(BigInt& x, |
121 | | const secure_vector<word>& y, |
122 | | secure_vector<word>& ws) const |
123 | 2.78M | { |
124 | 2.78M | const size_t output_size = 2*m_p_words + 2; |
125 | 2.78M | |
126 | 2.78M | if(ws.size() < 2*output_size) |
127 | 0 | ws.resize(2*output_size); |
128 | 2.78M | |
129 | 2.78M | word* z_data = &ws[0]; |
130 | 2.78M | word* ws_data = &ws[output_size]; |
131 | 2.78M | |
132 | 2.78M | BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words); |
133 | 2.78M | |
134 | 2.78M | bigint_mul(z_data, output_size, |
135 | 2.78M | x.data(), x.size(), std::min(m_p_words, x.size()), |
136 | 2.78M | y.data(), y.size(), std::min(m_p_words, y.size()), |
137 | 2.78M | ws_data, output_size); |
138 | 2.78M | |
139 | 2.78M | bigint_monty_redc(z_data, |
140 | 2.78M | m_p.data(), m_p_words, m_p_dash, |
141 | 2.78M | ws_data, output_size); |
142 | 2.78M | |
143 | 2.78M | if(x.size() < output_size) |
144 | 0 | x.grow_to(output_size); |
145 | 2.78M | copy_mem(x.mutable_data(), z_data, output_size); |
146 | 2.78M | } |
147 | | |
148 | | void Montgomery_Params::mul_by(BigInt& x, |
149 | | const BigInt& y, |
150 | | secure_vector<word>& ws) const |
151 | 105k | { |
152 | 105k | const size_t output_size = 2*m_p_words + 2; |
153 | 105k | |
154 | 105k | if(ws.size() < 2*output_size) |
155 | 79 | ws.resize(2*output_size); |
156 | 105k | |
157 | 105k | word* z_data = &ws[0]; |
158 | 105k | word* ws_data = &ws[output_size]; |
159 | 105k | |
160 | 105k | BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words); |
161 | 105k | |
162 | 105k | bigint_mul(z_data, output_size, |
163 | 105k | x.data(), x.size(), std::min(m_p_words, x.size()), |
164 | 105k | y.data(), y.size(), std::min(m_p_words, y.size()), |
165 | 105k | ws_data, output_size); |
166 | 105k | |
167 | 105k | bigint_monty_redc(z_data, |
168 | 105k | m_p.data(), m_p_words, m_p_dash, |
169 | 105k | ws_data, output_size); |
170 | 105k | |
171 | 105k | if(x.size() < output_size) |
172 | 61 | x.grow_to(output_size); |
173 | 105k | copy_mem(x.mutable_data(), z_data, output_size); |
174 | 105k | } |
175 | | |
176 | | BigInt Montgomery_Params::sqr(const BigInt& x, secure_vector<word>& ws) const |
177 | 188 | { |
178 | 188 | const size_t output_size = 2*m_p_words + 2; |
179 | 188 | |
180 | 188 | if(ws.size() < output_size) |
181 | 94 | ws.resize(output_size); |
182 | 188 | |
183 | 188 | BigInt z(BigInt::Positive, output_size); |
184 | 188 | |
185 | 188 | BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words); |
186 | 188 | |
187 | 188 | bigint_sqr(z.mutable_data(), z.size(), |
188 | 188 | x.data(), x.size(), std::min(m_p_words, x.size()), |
189 | 188 | ws.data(), ws.size()); |
190 | 188 | |
191 | 188 | bigint_monty_redc(z.mutable_data(), |
192 | 188 | m_p.data(), m_p_words, m_p_dash, |
193 | 188 | ws.data(), ws.size()); |
194 | 188 | |
195 | 188 | return z; |
196 | 188 | } |
197 | | |
198 | | void Montgomery_Params::square_this(BigInt& x, |
199 | | secure_vector<word>& ws) const |
200 | 11.5M | { |
201 | 11.5M | const size_t output_size = 2*m_p_words + 2; |
202 | 11.5M | |
203 | 11.5M | if(ws.size() < 2*output_size) |
204 | 40.9k | ws.resize(2*output_size); |
205 | 11.5M | |
206 | 11.5M | word* z_data = &ws[0]; |
207 | 11.5M | word* ws_data = &ws[output_size]; |
208 | 11.5M | |
209 | 11.5M | BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words); |
210 | 11.5M | |
211 | 11.5M | bigint_sqr(z_data, output_size, |
212 | 11.5M | x.data(), x.size(), std::min(m_p_words, x.size()), |
213 | 11.5M | ws_data, output_size); |
214 | 11.5M | |
215 | 11.5M | bigint_monty_redc(z_data, |
216 | 11.5M | m_p.data(), m_p_words, m_p_dash, |
217 | 11.5M | ws_data, output_size); |
218 | 11.5M | |
219 | 11.5M | if(x.size() < output_size) |
220 | 34.6k | x.grow_to(output_size); |
221 | 11.5M | copy_mem(x.mutable_data(), z_data, output_size); |
222 | 11.5M | } |
223 | | |
224 | | Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params> params, |
225 | | const BigInt& v, |
226 | | bool redc_needed) : |
227 | | m_params(params) |
228 | 1.43M | { |
229 | 1.43M | if(redc_needed == false) |
230 | 1.34M | { |
231 | 1.34M | m_v = v; |
232 | 1.34M | } |
233 | 95.6k | else |
234 | 95.6k | { |
235 | 95.6k | BOTAN_ASSERT_NOMSG(m_v < m_params->p()); |
236 | 95.6k | secure_vector<word> ws; |
237 | 95.6k | m_v = m_params->mul(v, m_params->R2(), ws); |
238 | 95.6k | } |
239 | 1.43M | } |
240 | | |
241 | | Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params, |
242 | | const uint8_t bits[], size_t len, |
243 | | bool redc_needed) : |
244 | | m_params(params), |
245 | | m_v(bits, len) |
246 | 0 | { |
247 | 0 | if(redc_needed) |
248 | 0 | { |
249 | 0 | BOTAN_ASSERT_NOMSG(m_v < m_params->p()); |
250 | 0 | secure_vector<word> ws; |
251 | 0 | m_v = m_params->mul(m_v, m_params->R2(), ws); |
252 | 0 | } |
253 | 0 | } |
254 | | |
255 | | Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params, |
256 | | const word words[], size_t len, |
257 | | bool redc_needed) : |
258 | | m_params(params), |
259 | | m_v(words, len) |
260 | 88.7k | { |
261 | 88.7k | if(redc_needed) |
262 | 0 | { |
263 | 0 | BOTAN_ASSERT_NOMSG(m_v < m_params->p()); |
264 | 0 | secure_vector<word> ws; |
265 | 0 | m_v = m_params->mul(m_v, m_params->R2(), ws); |
266 | 0 | } |
267 | 88.7k | } |
268 | | |
269 | | void Montgomery_Int::fix_size() |
270 | 1.43M | { |
271 | 1.43M | const size_t p_words = m_params->p_words(); |
272 | 1.43M | |
273 | 1.43M | if(m_v.sig_words() > p_words) |
274 | 2 | throw Internal_Error("Montgomery_Int::fix_size v too large"); |
275 | 1.43M | |
276 | 1.43M | m_v.grow_to(p_words); |
277 | 1.43M | } |
278 | | |
279 | | bool Montgomery_Int::operator==(const Montgomery_Int& other) const |
280 | 0 | { |
281 | 0 | return m_v == other.m_v && m_params->p() == other.m_params->p(); |
282 | 0 | } |
283 | | |
284 | | std::vector<uint8_t> Montgomery_Int::serialize() const |
285 | 0 | { |
286 | 0 | std::vector<uint8_t> v(size()); |
287 | 0 | BigInt::encode_1363(v.data(), v.size(), value()); |
288 | 0 | return v; |
289 | 0 | } |
290 | | |
291 | | size_t Montgomery_Int::size() const |
292 | 0 | { |
293 | 0 | return m_params->p().bytes(); |
294 | 0 | } |
295 | | |
296 | | bool Montgomery_Int::is_one() const |
297 | 0 | { |
298 | 0 | return m_v == m_params->R1(); |
299 | 0 | } |
300 | | |
301 | | bool Montgomery_Int::is_zero() const |
302 | 0 | { |
303 | 0 | return m_v.is_zero(); |
304 | 0 | } |
305 | | |
306 | | BigInt Montgomery_Int::value() const |
307 | 95.1k | { |
308 | 95.1k | secure_vector<word> ws; |
309 | 95.1k | return m_params->redc(m_v, ws); |
310 | 95.1k | } |
311 | | |
312 | | Montgomery_Int Montgomery_Int::operator+(const Montgomery_Int& other) const |
313 | 0 | { |
314 | 0 | secure_vector<word> ws; |
315 | 0 | BigInt z = m_v; |
316 | 0 | z.mod_add(other.m_v, m_params->p(), ws); |
317 | 0 | return Montgomery_Int(m_params, z, false); |
318 | 0 | } |
319 | | |
320 | | Montgomery_Int Montgomery_Int::operator-(const Montgomery_Int& other) const |
321 | 0 | { |
322 | 0 | secure_vector<word> ws; |
323 | 0 | BigInt z = m_v; |
324 | 0 | z.mod_sub(other.m_v, m_params->p(), ws); |
325 | 0 | return Montgomery_Int(m_params, z, false); |
326 | 0 | } |
327 | | |
328 | | Montgomery_Int& Montgomery_Int::operator+=(const Montgomery_Int& other) |
329 | 0 | { |
330 | 0 | secure_vector<word> ws; |
331 | 0 | return this->add(other, ws); |
332 | 0 | } |
333 | | |
334 | | Montgomery_Int& Montgomery_Int::add(const Montgomery_Int& other, secure_vector<word>& ws) |
335 | 0 | { |
336 | 0 | m_v.mod_add(other.m_v, m_params->p(), ws); |
337 | 0 | return (*this); |
338 | 0 | } |
339 | | |
340 | | Montgomery_Int& Montgomery_Int::operator-=(const Montgomery_Int& other) |
341 | 0 | { |
342 | 0 | secure_vector<word> ws; |
343 | 0 | return this->sub(other, ws); |
344 | 0 | } |
345 | | |
346 | | Montgomery_Int& Montgomery_Int::sub(const Montgomery_Int& other, secure_vector<word>& ws) |
347 | 0 | { |
348 | 0 | m_v.mod_sub(other.m_v, m_params->p(), ws); |
349 | 0 | return (*this); |
350 | 0 | } |
351 | | |
352 | | Montgomery_Int Montgomery_Int::operator*(const Montgomery_Int& other) const |
353 | 1.24M | { |
354 | 1.24M | secure_vector<word> ws; |
355 | 1.24M | return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false); |
356 | 1.24M | } |
357 | | |
358 | | Montgomery_Int Montgomery_Int::mul(const Montgomery_Int& other, |
359 | | secure_vector<word>& ws) const |
360 | 1.03k | { |
361 | 1.03k | return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false); |
362 | 1.03k | } |
363 | | |
364 | | Montgomery_Int& Montgomery_Int::mul_by(const Montgomery_Int& other, |
365 | | secure_vector<word>& ws) |
366 | 105k | { |
367 | 105k | m_params->mul_by(m_v, other.m_v, ws); |
368 | 105k | return (*this); |
369 | 105k | } |
370 | | |
371 | | Montgomery_Int& Montgomery_Int::mul_by(const secure_vector<word>& other, |
372 | | secure_vector<word>& ws) |
373 | 2.78M | { |
374 | 2.78M | m_params->mul_by(m_v, other, ws); |
375 | 2.78M | return (*this); |
376 | 2.78M | } |
377 | | |
378 | | Montgomery_Int& Montgomery_Int::operator*=(const Montgomery_Int& other) |
379 | 0 | { |
380 | 0 | secure_vector<word> ws; |
381 | 0 | return mul_by(other, ws); |
382 | 0 | } |
383 | | |
384 | | Montgomery_Int& Montgomery_Int::operator*=(const secure_vector<word>& other) |
385 | 0 | { |
386 | 0 | secure_vector<word> ws; |
387 | 0 | return mul_by(other, ws); |
388 | 0 | } |
389 | | |
390 | | Montgomery_Int& Montgomery_Int::square_this_n_times(secure_vector<word>& ws, size_t n) |
391 | 3.11M | { |
392 | 14.6M | for(size_t i = 0; i != n; ++i) |
393 | 11.4M | m_params->square_this(m_v, ws); |
394 | 3.11M | return (*this); |
395 | 3.11M | } |
396 | | |
397 | | Montgomery_Int& Montgomery_Int::square_this(secure_vector<word>& ws) |
398 | 63.2k | { |
399 | 63.2k | m_params->square_this(m_v, ws); |
400 | 63.2k | return (*this); |
401 | 63.2k | } |
402 | | |
403 | | Montgomery_Int Montgomery_Int::square(secure_vector<word>& ws) const |
404 | 188 | { |
405 | 188 | return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false); |
406 | 188 | } |
407 | | |
408 | | Montgomery_Int Montgomery_Int::multiplicative_inverse() const |
409 | 0 | { |
410 | 0 | secure_vector<word> ws; |
411 | 0 | const BigInt iv = m_params->mul(m_params->inv_mod_p(m_v), m_params->R3(), ws); |
412 | 0 | return Montgomery_Int(m_params, iv, false); |
413 | 0 | } |
414 | | |
415 | | Montgomery_Int Montgomery_Int::additive_inverse() const |
416 | 0 | { |
417 | 0 | return Montgomery_Int(m_params, m_params->p()) - (*this); |
418 | 0 | } |
419 | | |
420 | | Montgomery_Int& Montgomery_Int::mul_by_2(secure_vector<word>& ws) |
421 | 0 | { |
422 | 0 | m_v.mod_mul(2, m_params->p(), ws); |
423 | 0 | return (*this); |
424 | 0 | } |
425 | | |
426 | | Montgomery_Int& Montgomery_Int::mul_by_3(secure_vector<word>& ws) |
427 | 0 | { |
428 | 0 | m_v.mod_mul(3, m_params->p(), ws); |
429 | 0 | return (*this); |
430 | 0 | } |
431 | | |
432 | | Montgomery_Int& Montgomery_Int::mul_by_4(secure_vector<word>& ws) |
433 | 0 | { |
434 | 0 | m_v.mod_mul(4, m_params->p(), ws); |
435 | 0 | return (*this); |
436 | 0 | } |
437 | | |
438 | | Montgomery_Int& Montgomery_Int::mul_by_8(secure_vector<word>& ws) |
439 | 0 | { |
440 | 0 | m_v.mod_mul(8, m_params->p(), ws); |
441 | 0 | return (*this); |
442 | 0 | } |
443 | | |
444 | | } |