Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

mp_core.h
Go to the documentation of this file.
1 /*
2 * MPI Algorithms
3 * (C) 1999-2010,2018 Jack Lloyd
4 * 2006 Luca Piccarreta
5 * 2016 Matthias Gierlings
6 *
7 * Botan is released under the Simplified BSD License (see license.txt)
8 */
9
10 #ifndef BOTAN_MP_CORE_OPS_H_
11 #define BOTAN_MP_CORE_OPS_H_
12
13 #include <botan/types.h>
14 #include <botan/exceptn.h>
15 #include <botan/mem_ops.h>
16 #include <botan/internal/mp_asmi.h>
17 #include <botan/internal/ct_utils.h>
18 #include <algorithm>
19
20 namespace Botan {
21
22 const word MP_WORD_MAX = ~static_cast<word>(0);
23
24 /*
25 * If cond == 0, does nothing.
26 * If cond > 0, swaps x[0:size] with y[0:size]
27 * Runs in constant time
28 */
29 inline void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
30 {
31 const auto mask = CT::Mask<word>::expand(cnd);
32
33 for(size_t i = 0; i != size; ++i)
34 {
35 const word a = x[i];
36 const word b = y[i];
37 x[i] = mask.select(b, a);
38 y[i] = mask.select(a, b);
39 }
40 }
41
42 inline word bigint_cnd_add(word cnd, word x[], word x_size,
43 const word y[], size_t y_size)
44 {
45 BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
46
47 const auto mask = CT::Mask<word>::expand(cnd);
48
49 word carry = 0;
50
51 const size_t blocks = y_size - (y_size % 8);
52 word z[8] = { 0 };
53
54 for(size_t i = 0; i != blocks; i += 8)
55 {
56 carry = word8_add3(z, x + i, y + i, carry);
57 mask.select_n(x + i, z, x + i, 8);
58 }
59
60 for(size_t i = blocks; i != y_size; ++i)
61 {
62 z[0] = word_add(x[i], y[i], &carry);
63 x[i] = mask.select(z[0], x[i]);
64 }
65
66 for(size_t i = y_size; i != x_size; ++i)
67 {
68 z[0] = word_add(x[i], 0, &carry);
69 x[i] = mask.select(z[0], x[i]);
70 }
71
72 return mask.if_set_return(carry);
73 }
74
75 /*
76 * If cond > 0 adds x[0:size] and y[0:size] and returns carry
77 * Runs in constant time
78 */
79 inline word bigint_cnd_add(word cnd, word x[], const word y[], size_t size)
80 {
81 return bigint_cnd_add(cnd, x, size, y, size);
82 }
83
84 /*
85 * If cond > 0 subtracts x[0:size] and y[0:size] and returns borrow
86 * Runs in constant time
87 */
88 inline word bigint_cnd_sub(word cnd,
89 word x[], size_t x_size,
90 const word y[], size_t y_size)
91 {
92 BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
93
94 const auto mask = CT::Mask<word>::expand(cnd);
95
96 word carry = 0;
97
98 const size_t blocks = y_size - (y_size % 8);
99 word z[8] = { 0 };
100
101 for(size_t i = 0; i != blocks; i += 8)
102 {
103 carry = word8_sub3(z, x + i, y + i, carry);
104 mask.select_n(x + i, z, x + i, 8);
105 }
106
107 for(size_t i = blocks; i != y_size; ++i)
108 {
109 z[0] = word_sub(x[i], y[i], &carry);
110 x[i] = mask.select(z[0], x[i]);
111 }
112
113 for(size_t i = y_size; i != x_size; ++i)
114 {
115 z[0] = word_sub(x[i], 0, &carry);
116 x[i] = mask.select(z[0], x[i]);
117 }
118
119 return mask.if_set_return(carry);
120 }
121
122 /*
123 * If cond > 0 adds x[0:size] and y[0:size] and returns carry
124 * Runs in constant time
125 */
126 inline word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
127 {
128 return bigint_cnd_sub(cnd, x, size, y, size);
129 }
130
131
132 /*
133 * Equivalent to
134 * bigint_cnd_add( mask, x, y, size);
135 * bigint_cnd_sub(~mask, x, y, size);
136 *
137 * Mask must be either 0 or all 1 bits
138 */
139 inline void bigint_cnd_add_or_sub(CT::Mask<word> mask, word x[], const word y[], size_t size)
140 {
141 const size_t blocks = size - (size % 8);
142
143 word carry = 0;
144 word borrow = 0;
145
146 word t0[8] = { 0 };
147 word t1[8] = { 0 };
148
149 for(size_t i = 0; i != blocks; i += 8)
150 {
151 carry = word8_add3(t0, x + i, y + i, carry);
152 borrow = word8_sub3(t1, x + i, y + i, borrow);
153
154 for(size_t j = 0; j != 8; ++j)
155 x[i+j] = mask.select(t0[j], t1[j]);
156 }
157
158 for(size_t i = blocks; i != size; ++i)
159 {
160 const word a = word_add(x[i], y[i], &carry);
161 const word s = word_sub(x[i], y[i], &borrow);
162
163 x[i] = mask.select(a, s);
164 }
165 }
166
167 /*
168 * Equivalent to
169 * bigint_cnd_add( mask, x, size, y, size);
170 * bigint_cnd_sub(~mask, x, size, z, size);
171 *
172 * Mask must be either 0 or all 1 bits
173 *
174 * Returns the carry or borrow resp
175 */
176 inline word bigint_cnd_addsub(CT::Mask<word> mask, word x[],
177 const word y[], const word z[],
178 size_t size)
179 {
180 const size_t blocks = size - (size % 8);
181
182 word carry = 0;
183 word borrow = 0;
184
185 word t0[8] = { 0 };
186 word t1[8] = { 0 };
187
188 for(size_t i = 0; i != blocks; i += 8)
189 {
190 carry = word8_add3(t0, x + i, y + i, carry);
191 borrow = word8_sub3(t1, x + i, z + i, borrow);
192
193 for(size_t j = 0; j != 8; ++j)
194 x[i+j] = mask.select(t0[j], t1[j]);
195 }
196
197 for(size_t i = blocks; i != size; ++i)
198 {
199 t0[0] = word_add(x[i], y[i], &carry);
200 t1[0] = word_sub(x[i], z[i], &borrow);
201 x[i] = mask.select(t0[0], t1[0]);
202 }
203
204 return mask.select(carry, borrow);
205 }
206
207 /*
208 * 2s complement absolute value
209 * If cond > 0 sets x to ~x + 1
210 * Runs in constant time
211 */
212 inline void bigint_cnd_abs(word cnd, word x[], size_t size)
213 {
214 const auto mask = CT::Mask<word>::expand(cnd);
215
216 word carry = mask.if_set_return(1);
217 for(size_t i = 0; i != size; ++i)
218 {
219 const word z = word_add(~x[i], 0, &carry);
220 x[i] = mask.select(z, x[i]);
221 }
222 }
223
224 /**
225 * Two operand addition with carry out
226 */
227 inline word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
228 {
229 word carry = 0;
230
231 BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
232
233 const size_t blocks = y_size - (y_size % 8);
234
235 for(size_t i = 0; i != blocks; i += 8)
236 carry = word8_add2(x + i, y + i, carry);
237
238 for(size_t i = blocks; i != y_size; ++i)
239 x[i] = word_add(x[i], y[i], &carry);
240
241 for(size_t i = y_size; i != x_size; ++i)
242 x[i] = word_add(x[i], 0, &carry);
243
244 return carry;
245 }
246
247 /**
248 * Three operand addition with carry out
249 */
250 inline word bigint_add3_nc(word z[],
251 const word x[], size_t x_size,
252 const word y[], size_t y_size)
253 {
254 if(x_size < y_size)
255 { return bigint_add3_nc(z, y, y_size, x, x_size); }
256
257 word carry = 0;
258
259 const size_t blocks = y_size - (y_size % 8);
260
261 for(size_t i = 0; i != blocks; i += 8)
262 carry = word8_add3(z + i, x + i, y + i, carry);
263
264 for(size_t i = blocks; i != y_size; ++i)
265 z[i] = word_add(x[i], y[i], &carry);
266
267 for(size_t i = y_size; i != x_size; ++i)
268 z[i] = word_add(x[i], 0, &carry);
269
270 return carry;
271 }
272
273 /**
274 * Two operand addition
275 * @param x the first operand (and output)
276 * @param x_size size of x
277 * @param y the second operand
278 * @param y_size size of y (must be >= x_size)
279 */
280 inline void bigint_add2(word x[], size_t x_size,
281 const word y[], size_t y_size)
282 {
283 x[x_size] += bigint_add2_nc(x, x_size, y, y_size);
284 }
285
286 /**
287 * Three operand addition
288 */
289 inline void bigint_add3(word z[],
290 const word x[], size_t x_size,
291 const word y[], size_t y_size)
292 {
293 z[x_size > y_size ? x_size : y_size] +=
294 bigint_add3_nc(z, x, x_size, y, y_size);
295 }
296
297 /**
298 * Two operand subtraction
299 */
300 inline word bigint_sub2(word x[], size_t x_size,
301 const word y[], size_t y_size)
302 {
303 word borrow = 0;
304
305 BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
306
307 const size_t blocks = y_size - (y_size % 8);
308
309 for(size_t i = 0; i != blocks; i += 8)
310 borrow = word8_sub2(x + i, y + i, borrow);
311
312 for(size_t i = blocks; i != y_size; ++i)
313 x[i] = word_sub(x[i], y[i], &borrow);
314
315 for(size_t i = y_size; i != x_size; ++i)
316 x[i] = word_sub(x[i], 0, &borrow);
317
318 return borrow;
319 }
320
321 /**
322 * Two operand subtraction, x = y - x; assumes y >= x
323 */
324 inline void bigint_sub2_rev(word x[], const word y[], size_t y_size)
325 {
326 word borrow = 0;
327
328 const size_t blocks = y_size - (y_size % 8);
329
330 for(size_t i = 0; i != blocks; i += 8)
331 borrow = word8_sub2_rev(x + i, y + i, borrow);
332
333 for(size_t i = blocks; i != y_size; ++i)
334 x[i] = word_sub(y[i], x[i], &borrow);
335
336 BOTAN_ASSERT(borrow == 0, "y must be greater than x");
337 }
338
339 /**
340 * Three operand subtraction
341 */
342 inline word bigint_sub3(word z[],
343 const word x[], size_t x_size,
344 const word y[], size_t y_size)
345 {
346 word borrow = 0;
347
348 BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
349
350 const size_t blocks = y_size - (y_size % 8);
351
352 for(size_t i = 0; i != blocks; i += 8)
353 borrow = word8_sub3(z + i, x + i, y + i, borrow);
354
355 for(size_t i = blocks; i != y_size; ++i)
356 z[i] = word_sub(x[i], y[i], &borrow);
357
358 for(size_t i = y_size; i != x_size; ++i)
359 z[i] = word_sub(x[i], 0, &borrow);
360
361 return borrow;
362 }
363
364 /**
365 * Return abs(x-y), ie if x >= y, then compute z = x - y
366 * Otherwise compute z = y - x
367 * No borrow is possible since the result is always >= 0
368 *
369 * Returns ~0 if x >= y or 0 if x < y
370 * @param z output array of at least N words
371 * @param x input array of N words
372 * @param y input array of N words
373 * @param N length of x and y
374 * @param ws array of at least 2*N words
375 */
376 inline CT::Mask<word>
377 bigint_sub_abs(word z[],
378 const word x[], const word y[], size_t N,
379 word ws[])
380 {
381 // Subtract in both direction then conditional copy out the result
382
383 word* ws0 = ws;
384 word* ws1 = ws + N;
385
386 word borrow0 = 0;
387 word borrow1 = 0;
388
389 const size_t blocks = N - (N % 8);
390
391 for(size_t i = 0; i != blocks; i += 8)
392 {
393 borrow0 = word8_sub3(ws0 + i, x + i, y + i, borrow0);
394 borrow1 = word8_sub3(ws1 + i, y + i, x + i, borrow1);
395 }
396
397 for(size_t i = blocks; i != N; ++i)
398 {
399 ws0[i] = word_sub(x[i], y[i], &borrow0);
400 ws1[i] = word_sub(y[i], x[i], &borrow1);
401 }
402
403 return CT::conditional_copy_mem(borrow0, z, ws1, ws0, N);
404 }
405
406 /*
407 * Shift Operations
408 */
409 inline void bigint_shl1(word x[], size_t x_size, size_t x_words,
410 size_t word_shift, size_t bit_shift)
411 {
412 copy_mem(x + word_shift, x, x_words);
413 clear_mem(x, word_shift);
414
415 const auto carry_mask = CT::Mask<word>::expand(bit_shift);
416 const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
417
418 word carry = 0;
419 for(size_t i = word_shift; i != x_size; ++i)
420 {
421 const word w = x[i];
422 x[i] = (w << bit_shift) | carry;
423 carry = carry_mask.if_set_return(w >> carry_shift);
424 }
425 }
426
427 inline void bigint_shr1(word x[], size_t x_size,
428 size_t word_shift, size_t bit_shift)
429 {
430 const size_t top = x_size >= word_shift ? (x_size - word_shift) : 0;
431
432 copy_mem(x, x + word_shift, top);
433 clear_mem(x + top, std::min(word_shift, x_size));
434
435 const auto carry_mask = CT::Mask<word>::expand(bit_shift);
436 const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
437
438 word carry = 0;
439
440 for(size_t i = 0; i != top; ++i)
441 {
442 const word w = x[top - i - 1];
443 x[top-i-1] = (w >> bit_shift) | carry;
444 carry = carry_mask.if_set_return(w << carry_shift);
445 }
446 }
447
448 inline void bigint_shl2(word y[], const word x[], size_t x_size,
449 size_t word_shift, size_t bit_shift)
450 {
451 copy_mem(y + word_shift, x, x_size);
452
453 const auto carry_mask = CT::Mask<word>::expand(bit_shift);
454 const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
455
456 word carry = 0;
457 for(size_t i = word_shift; i != x_size + word_shift + 1; ++i)
458 {
459 const word w = y[i];
460 y[i] = (w << bit_shift) | carry;
461 carry = carry_mask.if_set_return(w >> carry_shift);
462 }
463 }
464
465 inline void bigint_shr2(word y[], const word x[], size_t x_size,
466 size_t word_shift, size_t bit_shift)
467 {
468 const size_t new_size = x_size < word_shift ? 0 : (x_size - word_shift);
469
470 copy_mem(y, x + word_shift, new_size);
471
472 const auto carry_mask = CT::Mask<word>::expand(bit_shift);
473 const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
474
475 word carry = 0;
476 for(size_t i = new_size; i > 0; --i)
477 {
478 word w = y[i-1];
479 y[i-1] = (w >> bit_shift) | carry;
480 carry = carry_mask.if_set_return(w << carry_shift);
481 }
482 }
483
484 /*
485 * Linear Multiply - returns the carry
486 */
487 inline word BOTAN_WARN_UNUSED_RESULT bigint_linmul2(word x[], size_t x_size, word y)
488 {
489 const size_t blocks = x_size - (x_size % 8);
490
491 word carry = 0;
492
493 for(size_t i = 0; i != blocks; i += 8)
494 carry = word8_linmul2(x + i, y, carry);
495
496 for(size_t i = blocks; i != x_size; ++i)
497 x[i] = word_madd2(x[i], y, &carry);
498
499 return carry;
500 }
501
502 inline void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
503 {
504 const size_t blocks = x_size - (x_size % 8);
505
506 word carry = 0;
507
508 for(size_t i = 0; i != blocks; i += 8)
509 carry = word8_linmul3(z + i, x + i, y, carry);
510
511 for(size_t i = blocks; i != x_size; ++i)
512 z[i] = word_madd2(x[i], y, &carry);
513
514 z[x_size] = carry;
515 }
516
517 /**
518 * Compare x and y
519 * Return -1 if x < y
520 * Return 0 if x == y
521 * Return 1 if x > y
522 */
523 inline int32_t bigint_cmp(const word x[], size_t x_size,
524 const word y[], size_t y_size)
525 {
526 static_assert(sizeof(word) >= sizeof(uint32_t), "Size assumption");
527
528 const word LT = static_cast<word>(-1);
529 const word EQ = 0;
530 const word GT = 1;
531
532 const size_t common_elems = std::min(x_size, y_size);
533
534 word result = EQ; // until found otherwise
535
536 for(size_t i = 0; i != common_elems; i++)
537 {
538 const auto is_eq = CT::Mask<word>::is_equal(x[i], y[i]);
539 const auto is_lt = CT::Mask<word>::is_lt(x[i], y[i]);
540
541 result = is_eq.select(result, is_lt.select(LT, GT));
542 }
543
544 if(x_size < y_size)
545 {
546 word mask = 0;
547 for(size_t i = x_size; i != y_size; i++)
548 mask |= y[i];
549
550 // If any bits were set in high part of y, then x < y
551 result = CT::Mask<word>::is_zero(mask).select(result, LT);
552 }
553 else if(y_size < x_size)
554 {
555 word mask = 0;
556 for(size_t i = y_size; i != x_size; i++)
557 mask |= x[i];
558
559 // If any bits were set in high part of x, then x > y
560 result = CT::Mask<word>::is_zero(mask).select(result, GT);
561 }
562
563 CT::unpoison(result);
564 BOTAN_DEBUG_ASSERT(result == LT || result == GT || result == EQ);
565 return static_cast<int32_t>(result);
566 }
567
568 /**
569 * Compare x and y
570 * Return ~0 if x[0:x_size] < y[0:y_size] or 0 otherwise
571 * If lt_or_equal is true, returns ~0 also for x == y
572 */
573 inline CT::Mask<word>
574 bigint_ct_is_lt(const word x[], size_t x_size,
575 const word y[], size_t y_size,
576 bool lt_or_equal = false)
577 {
578 const size_t common_elems = std::min(x_size, y_size);
579
580 auto is_lt = CT::Mask<word>::expand(lt_or_equal);
581
582 for(size_t i = 0; i != common_elems; i++)
583 {
584 const auto eq = CT::Mask<word>::is_equal(x[i], y[i]);
585 const auto lt = CT::Mask<word>::is_lt(x[i], y[i]);
586 is_lt = eq.select_mask(is_lt, lt);
587 }
588
589 if(x_size < y_size)
590 {
591 word mask = 0;
592 for(size_t i = x_size; i != y_size; i++)
593 mask |= y[i];
594 // If any bits were set in high part of y, then is_lt should be forced true
595 is_lt |= CT::Mask<word>::expand(mask);
596 }
597 else if(y_size < x_size)
598 {
599 word mask = 0;
600 for(size_t i = y_size; i != x_size; i++)
601 mask |= x[i];
602
603 // If any bits were set in high part of x, then is_lt should be false
604 is_lt &= CT::Mask<word>::is_zero(mask);
605 }
606
607 return is_lt;
608 }
609
610 inline CT::Mask<word>
611 bigint_ct_is_eq(const word x[], size_t x_size,
612 const word y[], size_t y_size)
613 {
614 const size_t common_elems = std::min(x_size, y_size);
615
616 word diff = 0;
617
618 for(size_t i = 0; i != common_elems; i++)
619 {
620 diff |= (x[i] ^ y[i]);
621 }
622
623 // If any bits were set in high part of x/y, then they are not equal
624 if(x_size < y_size)
625 {
626 for(size_t i = x_size; i != y_size; i++)
627 diff |= y[i];
628 }
629 else if(y_size < x_size)
630 {
631 for(size_t i = y_size; i != x_size; i++)
632 diff |= x[i];
633 }
634
635 return CT::Mask<word>::is_zero(diff);
636 }
637
638 /**
639 * Set z to abs(x-y), ie if x >= y, then compute z = x - y
640 * Otherwise compute z = y - x
641 * No borrow is possible since the result is always >= 0
642 *
643 * Return the relative size of x vs y (-1, 0, 1)
644 *
645 * @param z output array of max(x_size,y_size) words
646 * @param x input param
647 * @param x_size length of x
648 * @param y input param
649 * @param y_size length of y
650 */
651 inline int32_t
652 bigint_sub_abs(word z[],
653 const word x[], size_t x_size,
654 const word y[], size_t y_size)
655 {
656 const int32_t relative_size = bigint_cmp(x, x_size, y, y_size);
657
658 // Swap if relative_size == -1
659 const bool need_swap = relative_size < 0;
660 CT::conditional_swap_ptr(need_swap, x, y);
661 CT::conditional_swap(need_swap, x_size, y_size);
662
663 /*
664 * We know at this point that x >= y so if y_size is larger than
665 * x_size, we are guaranteed they are just leading zeros which can
666 * be ignored
667 */
668 y_size = std::min(x_size, y_size);
669
670 bigint_sub3(z, x, x_size, y, y_size);
671
672 return relative_size;
673 }
674
675 /**
676 * Set t to t-s modulo mod
677 *
678 * @param t first integer
679 * @param s second integer
680 * @param mod the modulus
681 * @param mod_sw size of t, s, and mod
682 * @param ws workspace of size mod_sw
683 */
684 inline void
685 bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[])
686 {
687 // is t < s or not?
688 const auto is_lt = bigint_ct_is_lt(t, mod_sw, s, mod_sw);
689
690 // ws = p - s
691 const word borrow = bigint_sub3(ws, mod, mod_sw, s, mod_sw);
692
693 // Compute either (t - s) or (t + (p - s)) depending on mask
694 const word carry = bigint_cnd_addsub(is_lt, t, ws, s, mod_sw);
695
696 BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0);
697 BOTAN_UNUSED(carry, borrow);
698 }
699
700 template<size_t N>
701 inline void bigint_mod_sub_n(word t[], const word s[], const word mod[], word ws[])
702 {
703 // is t < s or not?
704 const auto is_lt = bigint_ct_is_lt(t, N, s, N);
705
706 // ws = p - s
707 const word borrow = bigint_sub3(ws, mod, N, s, N);
708
709 // Compute either (t - s) or (t + (p - s)) depending on mask
710 const word carry = bigint_cnd_addsub(is_lt, t, ws, s, N);
711
712 BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0);
713 BOTAN_UNUSED(carry, borrow);
714 }
715
716 /**
717 * Compute ((n1<<bits) + n0) / d
718 */
719 inline word bigint_divop(word n1, word n0, word d)
720 {
721 if(d == 0)
722 throw Invalid_Argument("bigint_divop divide by zero");
723
724 #if defined(BOTAN_HAS_MP_DWORD)
725 return ((static_cast<dword>(n1) << BOTAN_MP_WORD_BITS) | n0) / d;
726 #else
727
728 word high = n1 % d;
729 word quotient = 0;
730
731 for(size_t i = 0; i != BOTAN_MP_WORD_BITS; ++i)
732 {
733 const word high_top_bit = high >> (BOTAN_MP_WORD_BITS-1);
734
735 high <<= 1;
736 high |= (n0 >> (BOTAN_MP_WORD_BITS-1-i)) & 1;
737 quotient <<= 1;
738
739 if(high_top_bit || high >= d)
740 {
741 high -= d;
742 quotient |= 1;
743 }
744 }
745
746 return quotient;
747 #endif
748 }
749
750 /**
751 * Compute ((n1<<bits) + n0) % d
752 */
753 inline word bigint_modop(word n1, word n0, word d)
754 {
755 if(d == 0)
756 throw Invalid_Argument("bigint_modop divide by zero");
757
758 #if defined(BOTAN_HAS_MP_DWORD)
759 return ((static_cast<dword>(n1) << BOTAN_MP_WORD_BITS) | n0) % d;
760 #else
761 word z = bigint_divop(n1, n0, d);
762 word dummy = 0;
763 z = word_madd2(z, d, &dummy);
764 return (n0-z);
765 #endif
766 }
767
768 /*
769 * Comba Multiplication / Squaring
770 */
771 void bigint_comba_mul4(word z[8], const word x[4], const word y[4]);
772 void bigint_comba_mul6(word z[12], const word x[6], const word y[6]);
773 void bigint_comba_mul8(word z[16], const word x[8], const word y[8]);
774 void bigint_comba_mul9(word z[18], const word x[9], const word y[9]);
775 void bigint_comba_mul16(word z[32], const word x[16], const word y[16]);
776 void bigint_comba_mul24(word z[48], const word x[24], const word y[24]);
777
778 void bigint_comba_sqr4(word out[8], const word in[4]);
779 void bigint_comba_sqr6(word out[12], const word in[6]);
780 void bigint_comba_sqr8(word out[16], const word in[8]);
781 void bigint_comba_sqr9(word out[18], const word in[9]);
782 void bigint_comba_sqr16(word out[32], const word in[16]);
783 void bigint_comba_sqr24(word out[48], const word in[24]);
784
785 /**
786 * Montgomery Reduction
787 * @param z integer to reduce, of size exactly 2*(p_size+1).
788 Output is in the first p_size+1 words, higher
789 words are set to zero.
790 * @param p modulus
791 * @param p_size size of p
792 * @param p_dash Montgomery value
793 * @param workspace array of at least 2*(p_size+1) words
794 * @param ws_size size of workspace in words
795 */
796 void bigint_monty_redc(word z[],
797 const word p[], size_t p_size,
798 word p_dash,
799 word workspace[],
800 size_t ws_size);
801
802 /*
803 * High Level Multiplication/Squaring Interfaces
804 */
805
806 void bigint_mul(word z[], size_t z_size,
807 const word x[], size_t x_size, size_t x_sw,
808 const word y[], size_t y_size, size_t y_sw,
809 word workspace[], size_t ws_size);
810
811 void bigint_sqr(word z[], size_t z_size,
812 const word x[], size_t x_size, size_t x_sw,
813 word workspace[], size_t ws_size);
814
815 }
816
817 #endif
Botan::bigint_shr1
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:427
Botan::bigint_sub2_rev
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition: mp_core.h:324
Botan::Invalid_Argument
Definition: exceptn.h:136
Botan::word8_sub2_rev
word word8_sub2_rev(word x[8], const word y[8], word carry)
Definition: mp_asmi.h:275
Botan::CT::conditional_swap_ptr
void conditional_swap_ptr(bool cnd, T &x, T &y)
Definition: ct_utils.h:362
Botan::word8_add2
word word8_add2(word x[8], const word y[8], word carry)
Definition: mp_asmi.h:138
Botan::word8_linmul3
word word8_linmul3(word z[8], const word x[8], word y, word carry)
Definition: mp_asmi.h:381
Botan::bigint_shr2
void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:465
Botan::carry
void carry(int64_t &h0, int64_t &h1)
Definition: ed25519_internal.h:32
Botan::bigint_linmul2
word BOTAN_WARN_UNUSED_RESULT bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_core.h:487
Botan::bigint_mod_sub_n
void bigint_mod_sub_n(word t[], const word s[], const word mod[], word ws[])
Definition: mp_core.h:701
Botan::bigint_cmp
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:523
Botan::clear_mem
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:112
Botan::bigint_sub2
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:300
Botan::bigint_add3_nc
word bigint_add3_nc(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:250
Botan::bigint_comba_mul4
void bigint_comba_mul4(word z[8], const word x[4], const word y[4])
Definition: mp_comba.cpp:50
Botan::CT::Mask
Definition: ct_utils.h:87
BOTAN_WARN_UNUSED_RESULT
#define BOTAN_WARN_UNUSED_RESULT
Definition: compiler.h:80
Botan::word8_sub2
word word8_sub2(word x[8], const word y[8], word carry)
Definition: mp_asmi.h:240
Botan::bigint_sub3
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:342
Botan::bigint_divop
word bigint_divop(word n1, word n0, word d)
Definition: mp_core.h:719
Botan::bigint_comba_mul9
void bigint_comba_mul9(word z[18], const word x[9], const word y[9])
Definition: mp_comba.cpp:474
Botan::bigint_sqr
void bigint_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, word workspace[], size_t ws_size)
Definition: mp_karat.cpp:357
Botan::carry_shift
uint64_t carry_shift(const donna128 &a, size_t shift)
Definition: donna128.h:116
Botan::bigint_cnd_addsub
word bigint_cnd_addsub(CT::Mask< word > mask, word x[], const word y[], const word z[], size_t size)
Definition: mp_core.h:176
Botan::CT::Mask::select
T select(T x, T y) const
Definition: ct_utils.h:264
Botan::bigint_comba_mul24
void bigint_comba_mul24(word z[48], const word x[24], const word y[24])
Definition: mp_comba.cpp:1535
Botan::word_madd2
word word_madd2(word a, word b, word *c)
Definition: mp_madd.h:46
BOTAN_ASSERT
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
Botan::bigint_linmul3
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.h:502
Botan::bigint_comba_sqr16
void bigint_comba_sqr16(word z[32], const word x[16])
Definition: mp_comba.cpp:598
Botan::CT::Mask::expand
static Mask< T > expand(T v)
Definition: ct_utils.h:123
Botan::bigint_cnd_sub
word bigint_cnd_sub(word cnd, word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:88
Botan::bigint_shl1
void bigint_shl1(word x[], size_t x_size, size_t x_words, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:409
BOTAN_DEBUG_ASSERT
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
Botan::bigint_sub_abs
CT::Mask< word > bigint_sub_abs(word z[], const word x[], const word y[], size_t N, word ws[])
Definition: mp_core.h:377
Botan::bigint_comba_sqr24
void bigint_comba_sqr24(word z[48], const word x[24])
Definition: mp_comba.cpp:1132
Botan::bigint_cnd_swap
void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
Definition: mp_core.h:29
Botan::word8_linmul2
word word8_linmul2(word x[8], word y, word carry)
Definition: mp_asmi.h:346
Botan::bigint_cnd_add
word bigint_cnd_add(word cnd, word x[], word x_size, const word y[], size_t y_size)
Definition: mp_core.h:42
Botan::bigint_ct_is_eq
CT::Mask< word > bigint_ct_is_eq(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:611
Botan::bigint_add2_nc
word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:227
Botan::bigint_cnd_add_or_sub
void bigint_cnd_add_or_sub(CT::Mask< word > mask, word x[], const word y[], size_t size)
Definition: mp_core.h:139
Botan::copy_mem
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:132
Botan
Definition: alg_id.cpp:13
Botan::CT::conditional_copy_mem
Mask< T > conditional_copy_mem(T cnd, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:339
Botan::bigint_comba_sqr9
void bigint_comba_sqr9(word z[18], const word x[9])
Definition: mp_comba.cpp:386
BOTAN_UNUSED
#define BOTAN_UNUSED(...)
Definition: assert.h:142
Botan::bigint_mul
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition: mp_karat.cpp:298
Botan::word8_add3
word word8_add3(word z[8], const word x[8], const word y[8], word carry)
Definition: mp_asmi.h:173
Botan::bigint_monty_redc
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word workspace[], size_t ws_size)
Definition: mp_monty.cpp:109
Botan::bigint_shl2
void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:448
Botan::bigint_comba_mul8
void bigint_comba_mul8(word z[16], const word x[8], const word y[8])
Definition: mp_comba.cpp:283
Botan::MP_WORD_MAX
const word MP_WORD_MAX
Definition: mp_core.h:22
Botan::word_sub
word word_sub(word x, word y, word *carry)
Definition: mp_asmi.h:209
Botan::bigint_ct_is_lt
CT::Mask< word > bigint_ct_is_lt(const word x[], size_t x_size, const word y[], size_t y_size, bool lt_or_equal=false)
Definition: mp_core.h:574
Botan::bigint_comba_sqr8
void bigint_comba_sqr8(word z[16], const word x[8])
Definition: mp_comba.cpp:208
Botan::bigint_add2
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:280
Botan::bigint_comba_mul16
void bigint_comba_mul16(word z[32], const word x[16], const word y[16])
Definition: mp_comba.cpp:805
Botan::word_add
word word_add(word x, word y, word *carry)
Definition: mp_asmi.h:107
Botan::CT::unpoison
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:59
Botan::bigint_comba_mul6
void bigint_comba_mul6(word z[12], const word x[6], const word y[6])
Definition: mp_comba.cpp:141
Botan::bigint_cnd_abs
void bigint_cnd_abs(word cnd, word x[], size_t size)
Definition: mp_core.h:212
Botan::CT::Mask::is_zero
static Mask< T > is_zero(T x)
Definition: ct_utils.h:141
Botan::word8_sub3
word word8_sub3(word z[8], const word x[8], const word y[8], word carry)
Definition: mp_asmi.h:310
Botan::CT::Mask::is_equal
static Mask< T > is_equal(T x, T y)
Definition: ct_utils.h:149
Botan::bigint_mod_sub
void bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[])
Definition: mp_core.h:685
Botan::bigint_comba_sqr4
void bigint_comba_sqr4(word z[8], const word x[4])
Definition: mp_comba.cpp:17
Botan::bigint_comba_sqr6
void bigint_comba_sqr6(word z[12], const word x[6])
Definition: mp_comba.cpp:89
Botan::bigint_add3
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:289
Botan::bigint_modop
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.h:753
Botan::CT::Mask::is_lt
static Mask< T > is_lt(T x, T y)
Definition: ct_utils.h:157
Botan::CT::conditional_swap
void conditional_swap(bool cnd, T &x, T &y)
Definition: ct_utils.h:351