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