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