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