Botan 3.14.1
Crypto and TLS for C&
mp_monty.cpp
Go to the documentation of this file.
1/*
2* Montgomery Reduction
3* (C) 1999-2011,2025 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
14#if defined(BOTAN_HAS_MP_MULX)
15 #include <botan/internal/mp_mulx.h>
16#endif
17
18namespace Botan {
19
20namespace {
21
22BOTAN_FORCE_INLINE void mul_rev_range(word3<word>& accum, const word ws[], const word p[], size_t bound) {
23 /*
24 Unrolled version of:
25
26 for(size_t i = 0; i < bound; ++i) {
27 accum.mul(ws[i], p[bound - i]);
28 }
29 */
30
31 size_t lower = 0;
32 while(lower < bound) {
33 const size_t upper = bound - lower;
34
35 if(upper >= 16) {
36 accum.mul(ws[lower], p[upper]);
37 accum.mul(ws[lower + 1], p[upper - 1]);
38 accum.mul(ws[lower + 2], p[upper - 2]);
39 accum.mul(ws[lower + 3], p[upper - 3]);
40 accum.mul(ws[lower + 4], p[upper - 4]);
41 accum.mul(ws[lower + 5], p[upper - 5]);
42 accum.mul(ws[lower + 6], p[upper - 6]);
43 accum.mul(ws[lower + 7], p[upper - 7]);
44 accum.mul(ws[lower + 8], p[upper - 8]);
45 accum.mul(ws[lower + 9], p[upper - 9]);
46 accum.mul(ws[lower + 10], p[upper - 10]);
47 accum.mul(ws[lower + 11], p[upper - 11]);
48 accum.mul(ws[lower + 12], p[upper - 12]);
49 accum.mul(ws[lower + 13], p[upper - 13]);
50 accum.mul(ws[lower + 14], p[upper - 14]);
51 accum.mul(ws[lower + 15], p[upper - 15]);
52 lower += 16;
53 } else if(upper >= 8) {
54 accum.mul(ws[lower], p[upper]);
55 accum.mul(ws[lower + 1], p[upper - 1]);
56 accum.mul(ws[lower + 2], p[upper - 2]);
57 accum.mul(ws[lower + 3], p[upper - 3]);
58 accum.mul(ws[lower + 4], p[upper - 4]);
59 accum.mul(ws[lower + 5], p[upper - 5]);
60 accum.mul(ws[lower + 6], p[upper - 6]);
61 accum.mul(ws[lower + 7], p[upper - 7]);
62 lower += 8;
63 } else if(upper >= 4) {
64 accum.mul(ws[lower], p[upper]);
65 accum.mul(ws[lower + 1], p[upper - 1]);
66 accum.mul(ws[lower + 2], p[upper - 2]);
67 accum.mul(ws[lower + 3], p[upper - 3]);
68 lower += 4;
69 } else if(upper >= 2) {
70 accum.mul(ws[lower], p[upper]);
71 accum.mul(ws[lower + 1], p[upper - 1]);
72 lower += 2;
73 } else {
74 accum.mul(ws[lower], p[upper]);
75 lower += 1;
76 }
77 }
78}
79
80} // namespace
81
82/*
83* Montgomery reduction - product scanning form
84*
85* Algorithm 5 from "Energy-Efficient Software Implementation of Long
86* Integer Modular Arithmetic"
87* (https://www.iacr.org/archive/ches2005/006.pdf)
88*
89* See also
90*
91* https://eprint.iacr.org/2013/882.pdf
92* https://www.microsoft.com/en-us/research/wp-content/uploads/1996/01/j37acmon.pdf
93*/
95 word r[], const word z[], size_t z_size, const word p[], size_t p_size, word p_dash, word ws[]) {
96 BOTAN_ARG_CHECK(z_size >= 2 * p_size && p_size > 0, "Invalid sizes for bigint_monty_redc_generic");
97
98 word3<word> accum;
99
100 accum.add(z[0]);
101
102 ws[0] = accum.monty_step(p[0], p_dash);
103
104 for(size_t i = 1; i != p_size; ++i) {
105 mul_rev_range(accum, ws, p, i);
106 accum.add(z[i]);
107 ws[i] = accum.monty_step(p[0], p_dash);
108 }
109
110 for(size_t i = 0; i != p_size - 1; ++i) {
111 mul_rev_range(accum, &ws[i + 1], &p[i], p_size - (i + 1));
112 accum.add(z[p_size + i]);
113 ws[i] = accum.extract();
114 }
115
116 accum.add(z[2 * p_size - 1]);
117
118 ws[p_size - 1] = accum.extract();
119 // w1 is the final part, which is not stored in the workspace
120 const word w1 = accum.extract();
121
122 /*
123 * The result might need to be reduced mod p. To avoid a timing
124 * channel, always perform the subtraction. If in the computation
125 * of x - p a borrow is required then x was already < p.
126 *
127 * x starts at ws[0] and is p_size bytes long plus a possible high
128 * digit left over in w1.
129 *
130 * x - p starts at z[0] and is also p_size bytes long
131 *
132 * If borrow was set after the subtraction, then x was already less
133 * than p and the subtraction was not needed. In that case overwrite
134 * z[0:p_size] with the original x in ws[0:p_size].
135 *
136 * We only copy out p_size in the final step because we know
137 * the Montgomery result is < P
138 */
139
140 bigint_monty_maybe_sub(p_size, r, w1, ws, p);
141}
142
144 word z[], const word x[], const word y[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size) {
145 BOTAN_ARG_CHECK(ws_size >= 4 * p_size && p_size > 0, "Invalid workspace for Montgomery multiplication");
146
147#if defined(BOTAN_HAS_MP_MULX)
148 if(use_mulx_monty(p_size)) {
149 return bigint_mulx_monty_mul(z, x, y, p, p_size, p_dash, ws);
150 }
151#endif
152
153 word* prod = ws;
154 word* mul_ws = ws + 2 * p_size;
155 bigint_mul(prod, 2 * p_size, x, p_size, p_size, y, p_size, p_size, mul_ws, 2 * p_size);
156 bigint_monty_redc(z, prod, p, p_size, p_dash, mul_ws, 2 * p_size);
157}
158
159void bigint_monty_sqr(word z[], const word x[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size) {
160 BOTAN_ARG_CHECK(ws_size >= 4 * p_size && p_size > 0, "Invalid workspace for Montgomery squaring");
161
162 word* prod = ws;
163
164#if defined(BOTAN_HAS_MP_MULX)
165 if(use_mulx_monty(p_size)) {
166 return bigint_mulx_monty_sqr(z, x, p, p_size, p_dash, ws);
167 }
168#endif
169
170 word* mul_ws = ws + 2 * p_size;
171 bigint_sqr(prod, 2 * p_size, x, p_size, p_size, mul_ws, 2 * p_size);
172 bigint_monty_redc(z, prod, p, p_size, p_dash, mul_ws, 2 * p_size);
173}
174
175} // namespace Botan
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
constexpr void add(W x)
Definition mp_asmi.h:656
constexpr W monty_step(W p0, W p_dash)
Definition mp_asmi.h:673
constexpr W extract()
Definition mp_asmi.h:665
#define BOTAN_FORCE_INLINE
Definition compiler.h:86
BOTAN_TEST_API void bigint_monty_mul(word z[], const word x[], const word y[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_monty.cpp:143
void bigint_mulx_monty_mul(word z[], const word x[], const word y[], const word p[], size_t N, word p_dash, word ws[])
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:327
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:94
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:283
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:1086
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
Definition mp_core.h:229
BOTAN_TEST_API void bigint_monty_sqr(word z[], const word x[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_monty.cpp:159
void bigint_mulx_monty_sqr(word z[], const word x[], const word p[], size_t N, word p_dash, word ws[])
bool use_mulx_monty(size_t p_size)
Definition mp_mulx.h:33
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131