Botan 3.1.1
Crypto and TLS for C&
mp_monty.cpp
Go to the documentation of this file.
1/*
2* Montgomery Reduction
3* (C) 1999-2011 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#include <botan/internal/mp_core.h>
11
12#include <botan/assert.h>
13#include <botan/exceptn.h>
14#include <botan/mem_ops.h>
15#include <botan/internal/ct_utils.h>
16
17namespace Botan {
18
19/*
20* Montgomery reduction - product scanning form
21*
22* Algorithm 5 from "Energy-Efficient Software Implementation of Long
23* Integer Modular Arithmetic"
24* (https://www.iacr.org/archive/ches2005/006.pdf)
25*
26* See also
27*
28* https://eprint.iacr.org/2013/882.pdf
29* https://www.microsoft.com/en-us/research/wp-content/uploads/1996/01/j37acmon.pdf
30*/
31void bigint_monty_redc_generic(word z[], size_t z_size, const word p[], size_t p_size, word p_dash, word ws[]) {
32 BOTAN_ARG_CHECK(z_size >= 2 * p_size && p_size > 0, "Invalid sizes for bigint_monty_redc_generic");
33
34 word w2 = 0, w1 = 0, w0 = 0;
35
36 w0 = z[0];
37
38 ws[0] = w0 * p_dash;
39
40 word3_muladd(&w2, &w1, &w0, ws[0], p[0]);
41
42 w0 = w1;
43 w1 = w2;
44 w2 = 0;
45
46 for(size_t i = 1; i != p_size; ++i) {
47 for(size_t j = 0; j < i; ++j) {
48 word3_muladd(&w2, &w1, &w0, ws[j], p[i - j]);
49 }
50
51 word3_add(&w2, &w1, &w0, z[i]);
52
53 ws[i] = w0 * p_dash;
54
55 word3_muladd(&w2, &w1, &w0, ws[i], p[0]);
56
57 w0 = w1;
58 w1 = w2;
59 w2 = 0;
60 }
61
62 for(size_t i = 0; i != p_size - 1; ++i) {
63 for(size_t j = i + 1; j != p_size; ++j) {
64 word3_muladd(&w2, &w1, &w0, ws[j], p[p_size + i - j]);
65 }
66
67 word3_add(&w2, &w1, &w0, z[p_size + i]);
68
69 ws[i] = w0;
70
71 w0 = w1;
72 w1 = w2;
73 w2 = 0;
74 }
75
76 word3_add(&w2, &w1, &w0, z[2 * p_size - 1]);
77
78 ws[p_size - 1] = w0;
79 ws[p_size] = w1;
80
81 /*
82 * The result might need to be reduced mod p. To avoid a timing
83 * channel, always perform the subtraction. If in the compution
84 * of x - p a borrow is required then x was already < p.
85 *
86 * x starts at ws[0] and is p_size+1 bytes long.
87 * x - p starts at z[0] and is also p_size+1 bytes log
88 *
89 * If borrow was set then x was already < p and the subtraction
90 * was not needed. In that case overwrite z[0:p_size] with the
91 * original x in ws[0:p_size].
92 *
93 * We only copy out p_size in the final step because we know
94 * the Montgomery result is < P
95 */
96
97 word borrow = bigint_sub3(z, ws, p_size + 1, p, p_size);
98
99 BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1);
100
101 CT::conditional_assign_mem(borrow, z, ws, p_size);
102 clear_mem(z + p_size, z_size - p_size);
103}
104
105} // namespace Botan
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:98
#define BOTAN_ARG_CHECK(expr, msg)
Definition: assert.h:29
Mask< T > conditional_assign_mem(T cnd, T *sink, const T *src, size_t elems)
Definition: ct_utils.h:292
Definition: alg_id.cpp:13
void word3_muladd(word *w2, word *w1, word *w0, word x, word y)
Definition: mp_asmi.h:528
void word3_add(word *w2, word *w1, word *w0, word x)
Definition: mp_asmi.h:569
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
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