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