Botan 3.8.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,2024 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/assert.h>
14#include <botan/exceptn.h>
15#include <botan/mem_ops.h>
16#include <botan/types.h>
17#include <botan/internal/ct_utils.h>
18#include <botan/internal/mp_asmi.h>
19#include <algorithm>
20#include <array>
21#include <span>
22
23namespace Botan {
24
25/*
26* If cond == 0, does nothing.
27* If cond > 0, swaps x[0:size] with y[0:size]
28* Runs in constant time
29*/
30template <WordType W>
31inline constexpr void bigint_cnd_swap(W cnd, W x[], W y[], size_t size) {
32 const auto mask = CT::Mask<W>::expand(cnd);
33
34 for(size_t i = 0; i != size; ++i) {
35 const W a = x[i];
36 const W b = y[i];
37 x[i] = mask.select(b, a);
38 y[i] = mask.select(a, b);
39 }
40}
41
42template <WordType W>
43inline constexpr W bigint_cnd_add(W cnd, W x[], size_t x_size, const W y[], size_t y_size) {
44 BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
45
46 const auto mask = CT::Mask<W>::expand(cnd).value();
47
48 W carry = 0;
49
50 for(size_t i = 0; i != y_size; ++i) {
51 x[i] = word_add(x[i], y[i] & mask, &carry);
52 }
53
54 for(size_t i = y_size; i != x_size; ++i) {
55 x[i] = word_add(x[i], static_cast<W>(0), &carry);
56 }
57
58 return (mask & carry);
59}
60
61/*
62* If cond > 0 adds x[0:size] and y[0:size] and returns carry
63* Runs in constant time
64*/
65template <WordType W>
66inline constexpr W bigint_cnd_add(W cnd, W x[], const W y[], size_t size) {
67 return bigint_cnd_add(cnd, x, size, y, size);
68}
69
70/*
71* If cond > 0 subtracts x[0:size] and y[0:size] and returns borrow
72* Runs in constant time
73*/
74template <WordType W>
75inline constexpr auto bigint_cnd_sub(W cnd, W x[], size_t x_size, const W y[], size_t y_size) -> W {
76 BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
77
78 const auto mask = CT::Mask<W>::expand(cnd).value();
79
80 W carry = 0;
81
82 for(size_t i = 0; i != y_size; ++i) {
83 x[i] = word_sub(x[i], y[i] & mask, &carry);
84 }
85
86 for(size_t i = y_size; i != x_size; ++i) {
87 x[i] = word_sub(x[i], static_cast<W>(0), &carry);
88 }
89
90 return (mask & carry);
91}
92
93/*
94* If cond > 0 adds x[0:size] and y[0:size] and returns carry
95* Runs in constant time
96*/
97template <WordType W>
98inline constexpr auto bigint_cnd_sub(W cnd, W x[], const W y[], size_t size) -> W {
99 return bigint_cnd_sub(cnd, x, size, y, size);
100}
101
102/*
103* Equivalent to
104* bigint_cnd_add( mask, x, y, size);
105* bigint_cnd_sub(~mask, x, y, size);
106*
107* Mask must be either 0 or all 1 bits
108*/
109template <WordType W>
110inline constexpr void bigint_cnd_add_or_sub(CT::Mask<W> mask, W x[], const W y[], size_t size) {
111 const size_t blocks = size - (size % 8);
112
113 W carry = 0;
114 W borrow = 0;
115
116 W t0[8] = {0};
117 W t1[8] = {0};
118
119 for(size_t i = 0; i != blocks; i += 8) {
120 carry = word8_add3(t0, x + i, y + i, carry);
121 borrow = word8_sub3(t1, x + i, y + i, borrow);
122 mask.select_n(x + i, t0, t1, 8);
123 }
124
125 for(size_t i = blocks; i != size; ++i) {
126 const W a = word_add(x[i], y[i], &carry);
127 const W s = word_sub(x[i], y[i], &borrow);
128
129 x[i] = mask.select(a, s);
130 }
131}
132
133/*
134* Equivalent to
135* bigint_cnd_add( mask, x, size, y, size);
136* bigint_cnd_sub(~mask, x, size, z, size);
137*
138* Mask must be either 0 or all 1 bits
139*
140* Returns the carry or borrow resp
141*/
142template <WordType W>
143inline constexpr auto bigint_cnd_addsub(CT::Mask<W> mask, W x[], const W y[], const W z[], size_t size) -> W {
144 const size_t blocks = size - (size % 8);
145
146 W carry = 0;
147 W borrow = 0;
148
149 W t0[8] = {0};
150 W t1[8] = {0};
151
152 for(size_t i = 0; i != blocks; i += 8) {
153 carry = word8_add3(t0, x + i, y + i, carry);
154 borrow = word8_sub3(t1, x + i, z + i, borrow);
155 mask.select_n(x + i, t0, t1, 8);
156 }
157
158 for(size_t i = blocks; i != size; ++i) {
159 t0[0] = word_add(x[i], y[i], &carry);
160 t1[0] = word_sub(x[i], z[i], &borrow);
161 x[i] = mask.select(t0[0], t1[0]);
162 }
163
164 return mask.select(carry, borrow);
165}
166
167/*
168* 2s complement absolute value
169* If cond > 0 sets x to ~x + 1
170* Runs in constant time
171*/
172template <WordType W>
173inline constexpr void bigint_cnd_abs(W cnd, W x[], size_t size) {
174 const auto mask = CT::Mask<W>::expand(cnd);
175
176 W carry = mask.if_set_return(1);
177 for(size_t i = 0; i != size; ++i) {
178 const W z = word_add(~x[i], static_cast<W>(0), &carry);
179 x[i] = mask.select(z, x[i]);
180 }
181}
182
183/**
184* Two operand addition with carry out
185*/
186template <WordType W>
187inline constexpr auto bigint_add2_nc(W x[], size_t x_size, const W y[], size_t y_size) -> W {
188 W carry = 0;
189
190 BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
191
192 const size_t blocks = y_size - (y_size % 8);
193
194 for(size_t i = 0; i != blocks; i += 8) {
195 carry = word8_add2(x + i, y + i, carry);
196 }
197
198 for(size_t i = blocks; i != y_size; ++i) {
199 x[i] = word_add(x[i], y[i], &carry);
200 }
201
202 for(size_t i = y_size; i != x_size; ++i) {
203 x[i] = word_add(x[i], static_cast<W>(0), &carry);
204 }
205
206 return carry;
207}
208
209/**
210* Three operand addition with carry out
211*/
212template <WordType W>
213inline constexpr auto bigint_add3_nc(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W {
214 if(x_size < y_size) {
215 return bigint_add3_nc(z, y, y_size, x, x_size);
216 }
217
218 W carry = 0;
219
220 const size_t blocks = y_size - (y_size % 8);
221
222 for(size_t i = 0; i != blocks; i += 8) {
223 carry = word8_add3(z + i, x + i, y + i, carry);
224 }
225
226 for(size_t i = blocks; i != y_size; ++i) {
227 z[i] = word_add(x[i], y[i], &carry);
228 }
229
230 for(size_t i = y_size; i != x_size; ++i) {
231 z[i] = word_add(x[i], static_cast<W>(0), &carry);
232 }
233
234 return carry;
235}
236
237/**
238* Two operand addition
239* @param x the first operand (and output)
240* @param x_size size of x
241* @param y the second operand
242* @param y_size size of y (must be <= x_size)
243*/
244template <WordType W>
245inline constexpr void bigint_add2(W x[], size_t x_size, const W y[], size_t y_size) {
246 x[x_size] += bigint_add2_nc(x, x_size, y, y_size);
247}
248
249/**
250* Three operand addition
251*/
252template <WordType W>
253inline constexpr void bigint_add3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) {
254 z[x_size > y_size ? x_size : y_size] += bigint_add3_nc(z, x, x_size, y, y_size);
255}
256
257/**
258* Two operand subtraction
259*/
260template <WordType W>
261inline constexpr auto bigint_sub2(W x[], size_t x_size, const W y[], size_t y_size) -> W {
262 W borrow = 0;
263
264 BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
265
266 const size_t blocks = y_size - (y_size % 8);
267
268 for(size_t i = 0; i != blocks; i += 8) {
269 borrow = word8_sub2(x + i, y + i, borrow);
270 }
271
272 for(size_t i = blocks; i != y_size; ++i) {
273 x[i] = word_sub(x[i], y[i], &borrow);
274 }
275
276 for(size_t i = y_size; i != x_size; ++i) {
277 x[i] = word_sub(x[i], static_cast<W>(0), &borrow);
278 }
279
280 return borrow;
281}
282
283/**
284* Two operand subtraction, x = y - x; assumes y >= x
285*/
286template <WordType W>
287inline constexpr void bigint_sub2_rev(W x[], const W y[], size_t y_size) {
288 W 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
296 for(size_t i = blocks; i != y_size; ++i) {
297 x[i] = word_sub(y[i], x[i], &borrow);
298 }
299
300 BOTAN_ASSERT(borrow == 0, "y must be greater than x");
301}
302
303/**
304* Three operand subtraction
305*
306* Expects that x_size >= y_size
307*
308* Writes to z[0:x_size] and returns borrow
309*/
310template <WordType W>
311inline constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W {
312 W borrow = 0;
313
314 BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
315
316 const size_t blocks = y_size - (y_size % 8);
317
318 for(size_t i = 0; i != blocks; i += 8) {
319 borrow = word8_sub3(z + i, x + i, y + i, borrow);
320 }
321
322 for(size_t i = blocks; i != y_size; ++i) {
323 z[i] = word_sub(x[i], y[i], &borrow);
324 }
325
326 for(size_t i = y_size; i != x_size; ++i) {
327 z[i] = word_sub(x[i], static_cast<W>(0), &borrow);
328 }
329
330 return borrow;
331}
332
333/**
334* Conditional subtraction for Montgomery reduction
335*
336* This function assumes that (x0 || x) is less than 2*p
337*
338* Computes z[0:N] = (x0 || x[0:N]) - p[0:N]
339*
340* If z would be positive, returns z[0:N]
341* Otherwise returns original input x
342*/
343template <WordType W>
344inline constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[]) {
345 W borrow = 0;
346
347 const size_t blocks = N - (N % 8);
348
349 for(size_t i = 0; i != blocks; i += 8) {
350 borrow = word8_sub3(z + i, x + i, p + i, borrow);
351 }
352
353 for(size_t i = blocks; i != N; ++i) {
354 z[i] = word_sub(x[i], p[i], &borrow);
355 }
356
357 borrow = (x0 - borrow) > x0;
358
359 CT::conditional_assign_mem(borrow, z, x, N);
360}
361
362/**
363* Conditional subtraction for Montgomery reduction
364*
365* This function assumes that (x0 || x) is less than 2*p
366*
367* Computes z[0:N] = (x0 || x[0:N]) - p[0:N]
368*
369* If z would be positive, returns z[0:N]
370* Otherwise returns original input x
371*/
372template <size_t N, WordType W>
373inline constexpr void bigint_monty_maybe_sub(W z[N], W x0, const W x[N], const W y[N]) {
374 W borrow = 0;
375
376 for(size_t i = 0; i != N; ++i) {
377 z[i] = word_sub(x[i], y[i], &borrow);
378 }
379
380 borrow = (x0 - borrow) > x0;
381
382 CT::conditional_assign_mem(borrow, z, x, N);
383}
384
385/**
386* Return abs(x-y), ie if x >= y, then compute z = x - y
387* Otherwise compute z = y - x
388* No borrow is possible since the result is always >= 0
389*
390* Returns ~0 if x >= y or 0 if x < y
391* @param z output array of at least N words
392* @param x input array of N words
393* @param y input array of N words
394* @param N length of x and y
395* @param ws array of at least 2*N words
396*/
397template <WordType W>
398inline constexpr auto bigint_sub_abs(W z[], const W x[], const W y[], size_t N, W ws[]) -> CT::Mask<W> {
399 // Subtract in both direction then conditional copy out the result
400
401 W* ws0 = ws;
402 W* ws1 = ws + N;
403
404 W borrow0 = 0;
405 W borrow1 = 0;
406
407 const size_t blocks = N - (N % 8);
408
409 for(size_t i = 0; i != blocks; i += 8) {
410 borrow0 = word8_sub3(ws0 + i, x + i, y + i, borrow0);
411 borrow1 = word8_sub3(ws1 + i, y + i, x + i, borrow1);
412 }
413
414 for(size_t i = blocks; i != N; ++i) {
415 ws0[i] = word_sub(x[i], y[i], &borrow0);
416 ws1[i] = word_sub(y[i], x[i], &borrow1);
417 }
418
419 return CT::conditional_copy_mem(borrow0, z, ws1, ws0, N);
420}
421
422/*
423* Shift Operations
424*/
425template <WordType W>
426inline constexpr void bigint_shl1(W x[], size_t x_size, size_t x_words, size_t shift) {
427 const size_t word_shift = shift / WordInfo<W>::bits;
428 const size_t bit_shift = shift % WordInfo<W>::bits;
429
430 copy_mem(x + word_shift, x, x_words);
431 clear_mem(x, word_shift);
432
433 const auto carry_mask = CT::Mask<W>::expand(bit_shift);
434 const W carry_shift = carry_mask.if_set_return(WordInfo<W>::bits - bit_shift);
435
436 W carry = 0;
437 for(size_t i = word_shift; i != x_size; ++i) {
438 const W w = x[i];
439 x[i] = (w << bit_shift) | carry;
440 carry = carry_mask.if_set_return(w >> carry_shift);
441 }
442}
443
444template <WordType W>
445inline constexpr void bigint_shr1(W x[], size_t x_size, size_t shift) {
446 const size_t word_shift = shift / WordInfo<W>::bits;
447 const size_t bit_shift = shift % WordInfo<W>::bits;
448
449 const size_t top = x_size >= word_shift ? (x_size - word_shift) : 0;
450
451 if(top > 0) {
452 copy_mem(x, x + word_shift, top);
453 }
454 clear_mem(x + top, std::min(word_shift, x_size));
455
456 const auto carry_mask = CT::Mask<W>::expand(bit_shift);
457 const W carry_shift = carry_mask.if_set_return(WordInfo<W>::bits - bit_shift);
458
459 W carry = 0;
460
461 for(size_t i = 0; i != top; ++i) {
462 const W w = x[top - i - 1];
463 x[top - i - 1] = (w >> bit_shift) | carry;
464 carry = carry_mask.if_set_return(w << carry_shift);
465 }
466}
467
468template <WordType W>
469inline constexpr void bigint_shl2(W y[], const W x[], size_t x_size, size_t shift) {
470 const size_t word_shift = shift / WordInfo<W>::bits;
471 const size_t bit_shift = shift % WordInfo<W>::bits;
472
473 copy_mem(y + word_shift, x, x_size);
474
475 const auto carry_mask = CT::Mask<W>::expand(bit_shift);
476 const W carry_shift = carry_mask.if_set_return(WordInfo<W>::bits - bit_shift);
477
478 W carry = 0;
479 for(size_t i = word_shift; i != x_size + word_shift + 1; ++i) {
480 const W w = y[i];
481 y[i] = (w << bit_shift) | carry;
482 carry = carry_mask.if_set_return(w >> carry_shift);
483 }
484}
485
486template <WordType W>
487inline constexpr void bigint_shr2(W y[], const W x[], size_t x_size, size_t shift) {
488 const size_t word_shift = shift / WordInfo<W>::bits;
489 const size_t bit_shift = shift % WordInfo<W>::bits;
490 const size_t new_size = x_size < word_shift ? 0 : (x_size - word_shift);
491
492 if(new_size > 0) {
493 copy_mem(y, x + word_shift, new_size);
494 }
495
496 const auto carry_mask = CT::Mask<W>::expand(bit_shift);
497 const W carry_shift = carry_mask.if_set_return(WordInfo<W>::bits - bit_shift);
498
499 W carry = 0;
500 for(size_t i = new_size; i > 0; --i) {
501 W w = y[i - 1];
502 y[i - 1] = (w >> bit_shift) | carry;
503 carry = carry_mask.if_set_return(w << carry_shift);
504 }
505}
506
507/*
508* Linear Multiply - returns the carry
509*/
510template <WordType W>
511[[nodiscard]] inline constexpr auto bigint_linmul2(W x[], size_t x_size, W y) -> W {
512 const size_t blocks = x_size - (x_size % 8);
513
514 W carry = 0;
515
516 for(size_t i = 0; i != blocks; i += 8) {
517 carry = word8_linmul2(x + i, y, carry);
518 }
519
520 for(size_t i = blocks; i != x_size; ++i) {
521 x[i] = word_madd2(x[i], y, &carry);
522 }
523
524 return carry;
525}
526
527template <WordType W>
528inline constexpr void bigint_linmul3(W z[], const W x[], size_t x_size, W y) {
529 const size_t blocks = x_size - (x_size % 8);
530
531 W carry = 0;
532
533 for(size_t i = 0; i != blocks; i += 8) {
534 carry = word8_linmul3(z + i, x + i, y, carry);
535 }
536
537 for(size_t i = blocks; i != x_size; ++i) {
538 z[i] = word_madd2(x[i], y, &carry);
539 }
540
541 z[x_size] = carry;
542}
543
544/**
545* Compare x and y
546* Return -1 if x < y
547* Return 0 if x == y
548* Return 1 if x > y
549*/
550template <WordType W>
551inline constexpr int32_t bigint_cmp(const W x[], size_t x_size, const W y[], size_t y_size) {
552 static_assert(sizeof(W) >= sizeof(uint32_t), "Size assumption");
553
554 const W LT = static_cast<W>(-1);
555 const W EQ = 0;
556 const W GT = 1;
557
558 const size_t common_elems = std::min(x_size, y_size);
559
560 W result = EQ; // until found otherwise
561
562 for(size_t i = 0; i != common_elems; i++) {
563 const auto is_eq = CT::Mask<W>::is_equal(x[i], y[i]);
564 const auto is_lt = CT::Mask<W>::is_lt(x[i], y[i]);
565
566 result = is_eq.select(result, is_lt.select(LT, GT));
567 }
568
569 if(x_size < y_size) {
570 W mask = 0;
571 for(size_t i = x_size; i != y_size; i++) {
572 mask |= y[i];
573 }
574
575 // If any bits were set in high part of y, then x < y
576 result = CT::Mask<W>::is_zero(mask).select(result, LT);
577 } else if(y_size < x_size) {
578 W mask = 0;
579 for(size_t i = y_size; i != x_size; i++) {
580 mask |= x[i];
581 }
582
583 // If any bits were set in high part of x, then x > y
584 result = CT::Mask<W>::is_zero(mask).select(result, GT);
585 }
586
587 CT::unpoison(result);
588 BOTAN_DEBUG_ASSERT(result == LT || result == GT || result == EQ);
589 return static_cast<int32_t>(result);
590}
591
592/**
593* Compare x and y
594* Return ~0 if x[0:x_size] < y[0:y_size] or 0 otherwise
595* If lt_or_equal is true, returns ~0 also for x == y
596*/
597template <WordType W>
598inline constexpr auto bigint_ct_is_lt(const W x[], size_t x_size, const W y[], size_t y_size, bool lt_or_equal = false)
599 -> CT::Mask<W> {
600 const size_t common_elems = std::min(x_size, y_size);
601
602 auto is_lt = CT::Mask<W>::expand(lt_or_equal);
603
604 for(size_t i = 0; i != common_elems; i++) {
605 const auto eq = CT::Mask<W>::is_equal(x[i], y[i]);
606 const auto lt = CT::Mask<W>::is_lt(x[i], y[i]);
607 is_lt = eq.select_mask(is_lt, lt);
608 }
609
610 if(x_size < y_size) {
611 W mask = 0;
612 for(size_t i = x_size; i != y_size; i++) {
613 mask |= y[i];
614 }
615 // If any bits were set in high part of y, then is_lt should be forced true
616 is_lt |= CT::Mask<W>::expand(mask);
617 } else if(y_size < x_size) {
618 W mask = 0;
619 for(size_t i = y_size; i != x_size; i++) {
620 mask |= x[i];
621 }
622
623 // If any bits were set in high part of x, then is_lt should be false
624 is_lt &= CT::Mask<W>::is_zero(mask);
625 }
626
627 return is_lt;
628}
629
630template <WordType W>
631inline constexpr auto bigint_ct_is_eq(const W x[], size_t x_size, const W y[], size_t y_size) -> CT::Mask<W> {
632 const size_t common_elems = std::min(x_size, y_size);
633
634 W diff = 0;
635
636 for(size_t i = 0; i != common_elems; i++) {
637 diff |= (x[i] ^ y[i]);
638 }
639
640 // If any bits were set in high part of x/y, then they are not equal
641 if(x_size < y_size) {
642 for(size_t i = x_size; i != y_size; i++) {
643 diff |= y[i];
644 }
645 } else if(y_size < x_size) {
646 for(size_t i = y_size; i != x_size; i++) {
647 diff |= x[i];
648 }
649 }
650
651 return CT::Mask<W>::is_zero(diff);
652}
653
654/**
655* Set z to abs(x-y), ie if x >= y, then compute z = x - y
656* Otherwise compute z = y - x
657* No borrow is possible since the result is always >= 0
658*
659* Return the relative size of x vs y (-1, 0, 1)
660*
661* @param z output array of max(x_size,y_size) words
662* @param x input param
663* @param x_size length of x
664* @param y input param
665* @param y_size length of y
666*/
667template <WordType W>
668inline constexpr int32_t bigint_sub_abs(W z[], const W x[], size_t x_size, const W y[], size_t y_size) {
669 const int32_t relative_size = bigint_cmp(x, x_size, y, y_size);
670
671 // Swap if relative_size == -1
672 const bool need_swap = relative_size < 0;
673 CT::conditional_swap_ptr(need_swap, x, y);
674 CT::conditional_swap(need_swap, x_size, y_size);
675
676 /*
677 * We know at this point that x >= y so if y_size is larger than
678 * x_size, we are guaranteed they are just leading zeros which can
679 * be ignored
680 */
681 y_size = std::min(x_size, y_size);
682
683 bigint_sub3(z, x, x_size, y, y_size);
684
685 return relative_size;
686}
687
688/**
689* Set t to t-s modulo mod
690*
691* @param t first integer
692* @param s second integer
693* @param mod the modulus
694* @param mod_sw size of t, s, and mod
695* @param ws workspace of size mod_sw
696*/
697template <WordType W>
698inline constexpr void bigint_mod_sub(W t[], const W s[], const W mod[], size_t mod_sw, W ws[]) {
699 // ws = t - s
700 const W borrow = bigint_sub3(ws, t, mod_sw, s, mod_sw);
701
702 // Conditionally add back the modulus
703 bigint_cnd_add(borrow, ws, mod, mod_sw);
704
705 copy_mem(t, ws, mod_sw);
706}
707
708/**
709* Compute ((n1<<bits) + n0) / d
710*/
711template <WordType W>
712inline constexpr auto bigint_divop_vartime(W n1, W n0, W d) -> W {
713 if(d == 0) {
714 throw Invalid_Argument("bigint_divop_vartime divide by zero");
715 }
716
717 if constexpr(WordInfo<W>::dword_is_native) {
718 typename WordInfo<W>::dword n = n1;
719 n <<= WordInfo<W>::bits;
720 n |= n0;
721 return static_cast<W>(n / d);
722 } else {
723 W high = n1 % d;
724 W quotient = 0;
725
726 for(size_t i = 0; i != WordInfo<W>::bits; ++i) {
727 const W high_top_bit = high >> (WordInfo<W>::bits - 1);
728
729 high <<= 1;
730 high |= (n0 >> (WordInfo<W>::bits - 1 - i)) & 1;
731 quotient <<= 1;
732
733 if(high_top_bit || high >= d) {
734 high -= d;
735 quotient |= 1;
736 }
737 }
738
739 return quotient;
740 }
741}
742
743/**
744* Compute ((n1<<bits) + n0) % d
745*/
746template <WordType W>
747inline constexpr auto bigint_modop_vartime(W n1, W n0, W d) -> W {
748 if(d == 0) {
749 throw Invalid_Argument("bigint_modop_vartime divide by zero");
750 }
751
752 W z = bigint_divop_vartime(n1, n0, d);
753 W carry = 0;
754 z = word_madd2(z, d, &carry);
755 return (n0 - z);
756}
757
758/*
759* Compute an integer x such that (a*x) == -1 (mod 2^n)
760*
761* Throws an exception if input is even, since in that case no inverse
762* exists. If input is odd, then input and 2^n are relatively prime and
763* the inverse exists.
764*/
765template <WordType W>
766inline constexpr auto monty_inverse(W a) -> W {
767 if(a % 2 == 0) {
768 throw Invalid_Argument("monty_inverse only valid for odd integers");
769 }
770
771 /*
772 * From "A New Algorithm for Inversion mod p^k" by Çetin Kaya Koç
773 * https://eprint.iacr.org/2017/411.pdf sections 5 and 7.
774 */
775
776 W b = 1;
777 W r = 0;
778
779 for(size_t i = 0; i != WordInfo<W>::bits; ++i) {
780 const W bi = b % 2;
781 r >>= 1;
782 r += bi << (WordInfo<W>::bits - 1);
783
784 b -= a * bi;
785 b >>= 1;
786 }
787
788 // Now invert in addition space
789 r = (WordInfo<W>::max - r) + 1;
790
791 return r;
792}
793
794template <size_t S, WordType W, size_t N>
795inline constexpr W shift_left(std::array<W, N>& x) {
796 static_assert(S < WordInfo<W>::bits, "Shift too large");
797
798 W carry = 0;
799 for(size_t i = 0; i != N; ++i) {
800 const W w = x[i];
801 x[i] = (w << S) | carry;
802 carry = w >> (WordInfo<W>::bits - S);
803 }
804
805 return carry;
806}
807
808template <size_t S, WordType W, size_t N>
809inline constexpr W shift_right(std::array<W, N>& x) {
810 static_assert(S < WordInfo<W>::bits, "Shift too large");
811
812 W carry = 0;
813 for(size_t i = 0; i != N; ++i) {
814 const W w = x[N - 1 - i];
815 x[N - 1 - i] = (w >> S) | carry;
816 carry = w << (WordInfo<W>::bits - S);
817 }
818
819 return carry;
820}
821
822// Should be consteval but this triggers a bug in Clang 14
823template <WordType W, size_t N>
824constexpr auto hex_to_words(const char (&s)[N]) {
825 // Char count includes null terminator which we ignore
826 const constexpr size_t C = N - 1;
827
828 // Number of nibbles that a word can hold
829 const constexpr size_t NPW = (WordInfo<W>::bits / 4);
830
831 // Round up to the next number of words that will fit the input
832 const constexpr size_t S = (C + NPW - 1) / NPW;
833
834 auto hex2int = [](char c) -> int8_t {
835 if(c >= '0' && c <= '9') {
836 return static_cast<int8_t>(c - '0');
837 } else if(c >= 'a' && c <= 'f') {
838 return static_cast<int8_t>(c - 'a' + 10);
839 } else if(c >= 'A' && c <= 'F') {
840 return static_cast<int8_t>(c - 'A' + 10);
841 } else {
842 return -1;
843 }
844 };
845
846 std::array<W, S> r = {0};
847
848 for(size_t i = 0; i != C; ++i) {
849 const int8_t c = hex2int(s[i]);
850 if(c >= 0) {
851 shift_left<4>(r);
852 r[0] += c;
853 }
854 }
855
856 return r;
857}
858
859/*
860* Comba Multiplication / Squaring
861*/
862BOTAN_FUZZER_API void bigint_comba_mul4(word z[8], const word x[4], const word y[4]);
863BOTAN_FUZZER_API void bigint_comba_mul6(word z[12], const word x[6], const word y[6]);
864BOTAN_FUZZER_API void bigint_comba_mul7(word z[14], const word x[7], const word y[7]);
865BOTAN_FUZZER_API void bigint_comba_mul8(word z[16], const word x[8], const word y[8]);
866BOTAN_FUZZER_API void bigint_comba_mul9(word z[18], const word x[9], const word y[9]);
867BOTAN_FUZZER_API void bigint_comba_mul16(word z[32], const word x[16], const word y[16]);
868BOTAN_FUZZER_API void bigint_comba_mul24(word z[48], const word x[24], const word y[24]);
869
870BOTAN_FUZZER_API void bigint_comba_sqr4(word out[8], const word in[4]);
871BOTAN_FUZZER_API void bigint_comba_sqr6(word out[12], const word in[6]);
872BOTAN_FUZZER_API void bigint_comba_sqr7(word out[14], const word x[7]);
873BOTAN_FUZZER_API void bigint_comba_sqr8(word out[16], const word in[8]);
874BOTAN_FUZZER_API void bigint_comba_sqr9(word out[18], const word in[9]);
875BOTAN_FUZZER_API void bigint_comba_sqr16(word out[32], const word in[16]);
876BOTAN_FUZZER_API void bigint_comba_sqr24(word out[48], const word in[24]);
877
878/*
879* Comba Fixed Length Multiplication
880*/
881template <size_t N, WordType W>
882constexpr inline void comba_mul(W z[2 * N], const W x[N], const W y[N]) {
883 if(!std::is_constant_evaluated()) {
884 if constexpr(std::same_as<W, word> && N == 4) {
885 return bigint_comba_mul4(z, x, y);
886 }
887 if constexpr(std::same_as<W, word> && N == 6) {
888 return bigint_comba_mul6(z, x, y);
889 }
890 if constexpr(std::same_as<W, word> && N == 7) {
891 return bigint_comba_mul7(z, x, y);
892 }
893 if constexpr(std::same_as<W, word> && N == 8) {
894 return bigint_comba_mul8(z, x, y);
895 }
896 if constexpr(std::same_as<W, word> && N == 9) {
897 return bigint_comba_mul9(z, x, y);
898 }
899 if constexpr(std::same_as<W, word> && N == 16) {
900 return bigint_comba_mul16(z, x, y);
901 }
902 }
903
904 word3<W> accum;
905
906 for(size_t i = 0; i != 2 * N; ++i) {
907 const size_t start = i + 1 < N ? 0 : i + 1 - N;
908 const size_t end = std::min(N, i + 1);
909
910 for(size_t j = start; j != end; ++j) {
911 accum.mul(x[j], y[i - j]);
912 }
913 z[i] = accum.extract();
914 }
915}
916
917template <size_t N, WordType W>
918constexpr inline void comba_sqr(W z[2 * N], const W x[N]) {
919 if(!std::is_constant_evaluated()) {
920 if constexpr(std::same_as<W, word> && N == 4) {
921 return bigint_comba_sqr4(z, x);
922 }
923 if constexpr(std::same_as<W, word> && N == 6) {
924 return bigint_comba_sqr6(z, x);
925 }
926 if constexpr(std::same_as<W, word> && N == 7) {
927 return bigint_comba_sqr7(z, x);
928 }
929 if constexpr(std::same_as<W, word> && N == 8) {
930 return bigint_comba_sqr8(z, x);
931 }
932 if constexpr(std::same_as<W, word> && N == 9) {
933 return bigint_comba_sqr9(z, x);
934 }
935 if constexpr(std::same_as<W, word> && N == 16) {
936 return bigint_comba_sqr16(z, x);
937 }
938 }
939
940 word3<W> accum;
941
942 for(size_t i = 0; i != 2 * N; ++i) {
943 const size_t start = i + 1 < N ? 0 : i + 1 - N;
944 const size_t end = std::min(N, i + 1);
945
946 for(size_t j = start; j != end; ++j) {
947 accum.mul(x[j], x[i - j]);
948 }
949 z[i] = accum.extract();
950 }
951}
952
953/*
954* Montgomery reduction
955*
956* Sets r to the Montgomery reduction of z using parameters p / p_dash
957*
958* The workspace should be of size equal to the prime
959*/
960BOTAN_FUZZER_API void bigint_monty_redc_4(word r[4], const word z[8], const word p[4], word p_dash, word ws[4]);
961BOTAN_FUZZER_API void bigint_monty_redc_6(word r[6], const word z[12], const word p[6], word p_dash, word ws[6]);
962BOTAN_FUZZER_API void bigint_monty_redc_8(word r[8], const word z[16], const word p[8], word p_dash, word ws[8]);
963BOTAN_FUZZER_API void bigint_monty_redc_12(word r[12], const word z[24], const word p[12], word p_dash, word ws[12]);
964BOTAN_FUZZER_API void bigint_monty_redc_16(word r[16], const word z[32], const word p[16], word p_dash, word ws[16]);
965BOTAN_FUZZER_API void bigint_monty_redc_24(word r[24], const word z[48], const word p[24], word p_dash, word ws[24]);
966BOTAN_FUZZER_API void bigint_monty_redc_32(word r[32], const word z[64], const word p[32], word p_dash, word ws[32]);
967
970 word r[], const word z[], size_t z_size, const word p[], size_t p_size, word p_dash, word ws[]);
971
972/**
973* Montgomery Reduction
974* @param r result of exactly p_size words
975* @param z integer to reduce, of size exactly 2*p_size.
976* @param p modulus
977* @param p_size size of p
978* @param p_dash Montgomery value
979* @param ws array of at least p_size words
980* @param ws_size size of ws in words
981*
982* It is allowed to set &r[0] == &z[0] however in this case note that only the
983* first p_size words of r will be written to and the high p_size words of r/z
984* will still hold the original inputs, these must be cleared after use.
985* See bigint_monty_redc_inplace
986*/
988 word r[], const word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size) {
989 const size_t z_size = 2 * p_size;
990
991 BOTAN_ARG_CHECK(ws_size >= p_size, "Montgomery reduction workspace too small");
992
993 if(p_size == 4) {
994 bigint_monty_redc_4(r, z, p, p_dash, ws);
995 } else if(p_size == 6) {
996 bigint_monty_redc_6(r, z, p, p_dash, ws);
997 } else if(p_size == 8) {
998 bigint_monty_redc_8(r, z, p, p_dash, ws);
999 } else if(p_size == 12) {
1000 bigint_monty_redc_12(r, z, p, p_dash, ws);
1001 } else if(p_size == 16) {
1002 bigint_monty_redc_16(r, z, p, p_dash, ws);
1003 } else if(p_size == 24) {
1004 bigint_monty_redc_24(r, z, p, p_dash, ws);
1005 } else if(p_size == 32) {
1006 bigint_monty_redc_32(r, z, p, p_dash, ws);
1007 } else {
1008 bigint_monty_redc_generic(r, z, z_size, p, p_size, p_dash, ws);
1009 }
1010}
1011
1012inline void bigint_monty_redc_inplace(word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size) {
1013 bigint_monty_redc(z, z, p, p_size, p_dash, ws, ws_size);
1014 clear_mem(z + p_size, p_size);
1015}
1016
1017/**
1018* Basecase O(N^2) multiplication
1019*/
1021void basecase_mul(word z[], size_t z_size, const word x[], size_t x_size, const word y[], size_t y_size);
1022
1023/**
1024* Basecase O(N^2) squaring
1025*/
1027void basecase_sqr(word z[], size_t z_size, const word x[], size_t x_size);
1028
1029/*
1030* High Level Multiplication/Squaring Interfaces
1031*/
1032void bigint_mul(word z[],
1033 size_t z_size,
1034 const word x[],
1035 size_t x_size,
1036 size_t x_sw,
1037 const word y[],
1038 size_t y_size,
1039 size_t y_sw,
1040 word workspace[],
1041 size_t ws_size);
1042
1043void 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);
1044
1045/**
1046* Reduce z modulo p = 2**B - C where C is small
1047*
1048* z is assumed to be at most (p-1)**2
1049*
1050* For details on the algorithm see
1051* - Handbook of Applied Cryptography, Algorithm 14.47
1052* - Guide to Elliptic Curve Cryptography, Algorithm 2.54 and Note 2.55
1053*
1054*/
1055template <WordType W, size_t N, W C>
1056constexpr std::array<W, N> redc_crandall(std::span<const W, 2 * N> z) {
1057 static_assert(N >= 2);
1058
1059 std::array<W, N> hi = {};
1060
1061 // hi = hi * c + lo
1062
1063 W carry = 0;
1064 for(size_t i = 0; i != N; ++i) {
1065 hi[i] = word_madd3(z[i + N], C, z[i], &carry);
1066 }
1067
1068 // hi += carry * C
1069 word carry_c[2] = {0};
1070 carry_c[0] = word_madd2(carry, C, &carry_c[1]);
1071
1072 carry = bigint_add2_nc(hi.data(), N, carry_c, 2);
1073
1074 constexpr W P0 = WordInfo<W>::max - (C - 1);
1075
1076 std::array<W, N> r = {};
1077
1078 W borrow = 0;
1079
1080 /*
1081 * For undetermined reasons, on GCC (only) removing this asm block causes
1082 * massive (up to 20%) performance regressions in secp256k1.
1083 *
1084 * The generated code without the asm seems quite reasonable, and timing
1085 * repeated calls to redc_crandall with the cycle counter show that GCC
1086 * computes it in about the same number of cycles with or without the asm.
1087 *
1088 * So the cause of the regression is unclear. But it is reproducible across
1089 * machines and GCC versions.
1090 */
1091#if defined(BOTAN_MP_USE_X86_64_ASM) && defined(__GNUC__) && !defined(__clang__)
1092 if constexpr(N == 4 && std::same_as<W, uint64_t>) {
1093 if(!std::is_constant_evaluated()) {
1094 asm volatile(R"(
1095 movq 0(%[x]), %[borrow]
1096 subq %[p0], %[borrow]
1097 movq %[borrow], 0(%[r])
1098 movq 16(%[x]), %[borrow]
1099 sbbq $-1, %[borrow]
1100 movq %[borrow], 8(%[r])
1101 movq 16(%[x]), %[borrow]
1102 sbbq $-1, %[borrow]
1103 movq %[borrow], 16(%[r])
1104 movq 24(%[x]), %[borrow]
1105 sbbq $-1, %[borrow]
1106 movq %[borrow], 24(%[r])
1107 sbbq %[borrow],%[borrow]
1108 negq %[borrow]
1109 )"
1110 : [borrow] "=r"(borrow)
1111 : [x] "r"(hi.data()), [p0] "r"(P0), [r] "r"(r.data()), "0"(borrow)
1112 : "cc", "memory");
1113 }
1114
1115 borrow = (carry - borrow) > carry;
1116 CT::conditional_assign_mem(borrow, r.data(), hi.data(), N);
1117 return r;
1118 }
1119#endif
1120
1121 r[0] = word_sub(hi[0], P0, &borrow);
1122 for(size_t i = 1; i != N; ++i) {
1123 r[i] = word_sub(hi[i], WordInfo<W>::max, &borrow);
1124 }
1125
1126 borrow = (carry - borrow) > carry;
1127
1128 CT::conditional_assign_mem(borrow, r.data(), hi.data(), N);
1129
1130 return r;
1131}
1132
1133/**
1134* Set r to r - C. Then if r < 0, add P to r
1135*/
1136template <size_t N, WordType W>
1137constexpr inline void bigint_correct_redc(std::array<W, N>& r, const std::array<W, N>& P, const std::array<W, N>& C) {
1138 // TODO look into combining the two operations for important values of N
1139 W borrow = bigint_sub2(r.data(), N, C.data(), N);
1140 bigint_cnd_add(borrow, r.data(), N, P.data(), N);
1141}
1142
1143// Extract a WindowBits sized window out of s, depending on offset.
1144template <size_t WindowBits, typename W, size_t N>
1145constexpr size_t read_window_bits(std::span<const W, N> words, size_t offset) {
1146 static_assert(WindowBits >= 1 && WindowBits <= 7);
1147
1148 constexpr uint8_t WindowMask = static_cast<uint8_t>(1 << WindowBits) - 1;
1149
1150 constexpr size_t W_bits = sizeof(W) * 8;
1151 const auto bit_shift = offset % W_bits;
1152 const auto word_offset = words.size() - 1 - (offset / W_bits);
1153
1154 const bool single_byte_window = bit_shift <= (W_bits - WindowBits) || word_offset == 0;
1155
1156 const auto w0 = words[word_offset];
1157
1158 if(single_byte_window) {
1159 return (w0 >> bit_shift) & WindowMask;
1160 } else {
1161 // Otherwise we must join two words and extract the result
1162 const auto w1 = words[word_offset - 1];
1163 const auto combined = ((w0 >> bit_shift) | (w1 << (W_bits - bit_shift)));
1164 return combined & WindowMask;
1165 }
1166}
1167
1168} // namespace Botan
1169
1170#endif
#define BOTAN_FUZZER_API
Definition api.h:51
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:100
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:31
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:52
constexpr void select_n(T output[], const T x[], const T y[], size_t len) const
Definition ct_utils.h:577
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:409
constexpr T select(T x, T y) const
Definition ct_utils.h:560
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:454
static constexpr Mask< T > is_lt(T x, T y)
Definition ct_utils.h:462
static constexpr Mask< T > is_zero(T x)
Definition ct_utils.h:449
constexpr W extract()
Definition mp_asmi.h:583
constexpr void mul(W x, W y)
Definition mp_asmi.h:509
constexpr void conditional_swap_ptr(bool cnd, T &x, T &y)
Definition ct_utils.h:765
constexpr void conditional_swap(bool cnd, T &x, T &y)
Definition ct_utils.h:759
constexpr Mask< T > conditional_assign_mem(T cnd, T *sink, const T *src, size_t elems)
Definition ct_utils.h:745
constexpr Mask< T > conditional_copy_mem(Mask< T > mask, T *to, const T *from0, const T *from1, size_t elems)
Definition ct_utils.h:733
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:65
constexpr void bigint_cnd_abs(W cnd, W x[], size_t size)
Definition mp_core.h:173
constexpr void bigint_linmul3(W z[], const W x[], size_t x_size, W y)
Definition mp_core.h:528
constexpr void bigint_cnd_swap(W cnd, W x[], W y[], size_t size)
Definition mp_core.h:31
constexpr auto word8_sub3(W z[8], const W x[8], const W y[8], W carry) -> W
Definition mp_asmi.h:355
constexpr W shift_left(std::array< W, N > &x)
Definition mp_core.h:795
constexpr auto word_sub(W x, W y, W *carry) -> W
Definition mp_asmi.h:278
constexpr auto word_add(W x, W y, W *carry) -> W
Definition mp_asmi.h:189
constexpr void comba_sqr(W z[2 *N], const W x[N])
Definition mp_core.h:918
constexpr uint64_t carry_shift(const donna128 &a, size_t shift)
Definition donna128.h:133
constexpr void bigint_shr2(W y[], const W x[], size_t x_size, size_t shift)
Definition mp_core.h:487
BOTAN_FUZZER_API void basecase_sqr(word z[], size_t z_size, const word x[], size_t x_size)
Definition mp_karat.cpp:46
constexpr size_t read_window_bits(std::span< const W, N > words, size_t offset)
Definition mp_core.h:1145
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:74
constexpr void bigint_shr1(W x[], size_t x_size, size_t shift)
Definition mp_core.h:445
constexpr auto word8_add3(W z[8], const W x[8], const W y[8], W carry) -> W
Definition mp_asmi.h:252
BOTAN_FUZZER_API void bigint_monty_redc_6(word r[6], const word z[12], const word p[6], word p_dash, word ws[6])
constexpr void comba_mul(W z[2 *N], const W x[N], const W y[N])
Definition mp_core.h:882
constexpr auto word8_sub2(W x[8], const W y[8], W carry) -> W
Definition mp_asmi.h:303
void bigint_comba_sqr7(word z[14], const word x[7])
Definition mp_comba.cpp:171
void bigint_comba_mul4(word z[8], const word x[4], const word y[4])
Definition mp_comba.cpp:42
constexpr auto word_madd2(W a, W b, W *c) -> W
Definition mp_asmi.h:84
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:794
constexpr auto word8_sub2_rev(W x[8], const W y[8], W carry) -> W
Definition mp_asmi.h:329
BOTAN_FUZZER_API void bigint_monty_redc_24(word r[24], const word z[48], const word p[24], word p_dash, word ws[24])
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:311
constexpr auto monty_inverse(W a) -> W
Definition mp_core.h:766
BOTAN_FUZZER_API void bigint_monty_redc_generic(word r[], const 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_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
constexpr auto bigint_cnd_addsub(CT::Mask< W > mask, W x[], const W y[], const W z[], size_t size) -> W
Definition mp_core.h:143
void bigint_comba_mul6(word z[12], const word x[6], const word y[6])
Definition mp_comba.cpp:115
constexpr void bigint_shl1(W x[], size_t x_size, size_t x_words, size_t shift)
Definition mp_core.h:426
constexpr auto bigint_ct_is_eq(const W x[], size_t x_size, const W y[], size_t y_size) -> CT::Mask< W >
Definition mp_core.h:631
constexpr int32_t bigint_cmp(const W x[], size_t x_size, const W y[], size_t y_size)
Definition mp_core.h:551
BOTAN_FUZZER_API void bigint_monty_redc_4(word r[4], const word z[8], const word p[4], word p_dash, word ws[4])
void bigint_monty_redc_inplace(word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_core.h:1012
void bigint_monty_redc(word r[], const word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_core.h:987
void bigint_comba_mul7(word z[14], const word x[7], const word y[7])
Definition mp_comba.cpp:221
constexpr auto bigint_cnd_sub(W cnd, W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:75
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
Definition mp_core.h:344
constexpr void bigint_shl2(W y[], const W x[], size_t x_size, size_t shift)
Definition mp_core.h:469
void bigint_comba_mul9(word z[18], const word x[9], const word y[9])
Definition mp_comba.cpp:511
BOTAN_FUZZER_API void bigint_monty_redc_12(word r[12], const word z[24], const word p[12], word p_dash, word ws[12])
constexpr W bigint_cnd_add(W cnd, W x[], size_t x_size, const W y[], size_t y_size)
Definition mp_core.h:43
void carry(int64_t &h0, int64_t &h1)
constexpr auto word8_linmul2(W x[8], W y, W carry) -> W
Definition mp_asmi.h:381
BOTAN_FUZZER_API void bigint_monty_redc_16(word r[16], const word z[32], const word p[16], word p_dash, word ws[16])
void bigint_comba_mul24(word z[48], const word x[24], const word y[24])
constexpr auto bigint_modop_vartime(W n1, W n0, W d) -> W
Definition mp_core.h:747
constexpr auto bigint_sub_abs(W z[], const W x[], const W y[], size_t N, W ws[]) -> CT::Mask< W >
Definition mp_core.h:398
constexpr void bigint_add2(W x[], size_t x_size, const W y[], size_t y_size)
Definition mp_core.h:245
constexpr auto bigint_ct_is_lt(const W x[], size_t x_size, const W y[], size_t y_size, bool lt_or_equal=false) -> CT::Mask< W >
Definition mp_core.h:598
constexpr std::array< W, N > redc_crandall(std::span< const W, 2 *N > z)
Definition mp_core.h:1056
constexpr void bigint_correct_redc(std::array< W, N > &r, const std::array< W, N > &P, const std::array< W, N > &C)
Definition mp_core.h:1137
constexpr auto word8_add2(W x[8], const W y[8], W carry) -> W
Definition mp_asmi.h:226
constexpr auto bigint_sub2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:261
void bigint_comba_sqr8(word z[16], const word x[8])
Definition mp_comba.cpp:292
constexpr auto hex_to_words(const char(&s)[N])
Definition mp_core.h:824
void bigint_comba_sqr16(word z[32], const word x[16])
Definition mp_comba.cpp:618
constexpr void bigint_cnd_add_or_sub(CT::Mask< W > mask, W x[], const W y[], size_t size)
Definition mp_core.h:110
constexpr void bigint_sub2_rev(W x[], const W y[], size_t y_size)
Definition mp_core.h:287
void bigint_comba_sqr9(word z[18], const word x[9])
Definition mp_comba.cpp:440
constexpr auto bigint_add2_nc(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:187
constexpr auto word8_linmul3(W z[8], const W x[8], W y, W carry) -> W
Definition mp_asmi.h:407
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
constexpr void bigint_add3(W z[], const W x[], size_t x_size, const W y[], size_t y_size)
Definition mp_core.h:253
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
Definition types.h:119
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:149
void bigint_comba_mul8(word z[16], const word x[8], const word y[8])
Definition mp_comba.cpp:352
BOTAN_FUZZER_API void bigint_monty_redc_8(word r[8], const word z[16], const word p[8], word p_dash, word ws[8])
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:123
constexpr auto bigint_divop_vartime(W n1, W n0, W d) -> W
Definition mp_core.h:712
constexpr W shift_right(std::array< W, N > &x)
Definition mp_core.h:809
constexpr void bigint_mod_sub(W t[], const W s[], const W mod[], size_t mod_sw, W ws[])
Definition mp_core.h:698
BOTAN_FUZZER_API void bigint_monty_redc_32(word r[32], const word z[64], const word p[32], word p_dash, word ws[32])
constexpr auto word_madd3(W a, W b, W c, W *d) -> W
Definition mp_asmi.h:110
constexpr auto bigint_add3_nc(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:213
constexpr auto bigint_linmul2(W x[], size_t x_size, W y) -> W
Definition mp_core.h:511