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