Botan 3.4.0 Crypto and TLS for C&
monty.cpp
Go to the documentation of this file.
1/*
2* (C) 2018 Jack Lloyd
3*
5*/
6
7#include <botan/internal/monty.h>
8
9#include <botan/reducer.h>
10#include <botan/internal/mp_core.h>
11
12#include <utility>
13
14namespace Botan {
15
17 if(p.is_even() || p < 3) {
18 throw Invalid_Argument("Montgomery_Params invalid modulus");
19 }
20
21 m_p = p;
22 m_p_words = m_p.sig_words();
23 m_p_dash = monty_inverse(m_p.word_at(0));
24
25 const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
26
27 m_r1 = mod_p.reduce(r);
28 m_r2 = mod_p.square(m_r1);
29 m_r3 = mod_p.multiply(m_r1, m_r2);
30}
31
33 if(p.is_even() || p < 3) {
34 throw Invalid_Argument("Montgomery_Params invalid modulus");
35 }
36
37 m_p = p;
38 m_p_words = m_p.sig_words();
39 m_p_dash = monty_inverse(m_p.word_at(0));
40
41 const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
42
43 // It might be faster to use ct_modulo here vs setting up Barrett reduction?
44 Modular_Reducer mod_p(p);
45
46 m_r1 = mod_p.reduce(r);
47 m_r2 = mod_p.square(m_r1);
48 m_r3 = mod_p.multiply(m_r1, m_r2);
49}
50
52 // TODO use Montgomery inverse here?
53 return inverse_mod(x, p());
54}
55
57 const size_t output_size = m_p_words + 1;
58
59 if(ws.size() < output_size) {
60 ws.resize(output_size);
61 }
62
63 BigInt z = x;
64 z.grow_to(2 * m_p_words);
65
66 bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());
67
68 return z;
69}
70
72 const size_t output_size = 2 * m_p_words + 2;
73
74 if(ws.size() < output_size) {
75 ws.resize(output_size);
76 }
77
78 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
79 BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
80
81 BigInt z = BigInt::with_capacity(output_size);
83 z.size(),
84 x.data(),
85 x.size(),
86 std::min(m_p_words, x.size()),
87 y.data(),
88 y.size(),
89 std::min(m_p_words, y.size()),
90 ws.data(),
91 ws.size());
92
93 bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());
94
95 return z;
96}
97
99 const size_t output_size = 2 * m_p_words + 2;
100 if(ws.size() < output_size) {
101 ws.resize(output_size);
102 }
103 BigInt z = BigInt::with_capacity(output_size);
104
105 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
106
108 z.size(),
109 x.data(),
110 x.size(),
111 std::min(m_p_words, x.size()),
112 y.data(),
113 y.size(),
114 std::min(m_p_words, y.size()),
115 ws.data(),
116 ws.size());
117
118 bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());
119
120 return z;
121}
122
124 const size_t output_size = 2 * m_p_words;
125
126 if(ws.size() < 2 * output_size) {
127 ws.resize(2 * output_size);
128 }
129
130 word* z_data = &ws[0];
131 word* ws_data = &ws[output_size];
132
133 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
134
135 bigint_mul(z_data,
136 output_size,
137 x.data(),
138 x.size(),
139 std::min(m_p_words, x.size()),
140 y.data(),
141 y.size(),
142 std::min(m_p_words, y.size()),
143 ws_data,
144 output_size);
145
146 bigint_monty_redc(z_data, m_p.data(), m_p_words, m_p_dash, ws_data, output_size);
147
148 if(x.size() < output_size) {
149 x.grow_to(output_size);
150 }
151 copy_mem(x.mutable_data(), z_data, output_size);
152}
153
155 const size_t output_size = 2 * m_p_words;
156
157 if(ws.size() < 2 * output_size) {
158 ws.resize(2 * output_size);
159 }
160
161 word* z_data = &ws[0];
162 word* ws_data = &ws[output_size];
163
164 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
165
166 bigint_mul(z_data,
167 output_size,
168 x.data(),
169 x.size(),
170 std::min(m_p_words, x.size()),
171 y.data(),
172 y.size(),
173 std::min(m_p_words, y.size()),
174 ws_data,
175 output_size);
176
177 bigint_monty_redc(z_data, m_p.data(), m_p_words, m_p_dash, ws_data, output_size);
178
179 if(x.size() < output_size) {
180 x.grow_to(output_size);
181 }
182 copy_mem(x.mutable_data(), z_data, output_size);
183}
184
186 const size_t output_size = 2 * m_p_words;
187
188 if(ws.size() < output_size) {
189 ws.resize(output_size);
190 }
191
192 BigInt z = BigInt::with_capacity(output_size);
193
194 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
195
196 bigint_sqr(z.mutable_data(), z.size(), x.data(), x.size(), std::min(m_p_words, x.size()), ws.data(), ws.size());
197
198 bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());
199
200 return z;
201}
202
204 const size_t output_size = 2 * m_p_words;
205
206 if(ws.size() < 2 * output_size) {
207 ws.resize(2 * output_size);
208 }
209
210 word* z_data = &ws[0];
211 word* ws_data = &ws[output_size];
212
213 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
214
215 bigint_sqr(z_data, output_size, x.data(), x.size(), std::min(m_p_words, x.size()), ws_data, output_size);
216
217 bigint_monty_redc(z_data, m_p.data(), m_p_words, m_p_dash, ws_data, output_size);
218
219 if(x.size() < output_size) {
220 x.grow_to(output_size);
221 }
222 copy_mem(x.mutable_data(), z_data, output_size);
223}
224
225Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
226 const BigInt& v,
227 bool redc_needed) :
228 m_params(params) {
229 if(redc_needed == false) {
230 m_v = v;
231 } else {
232 BOTAN_ASSERT_NOMSG(m_v < m_params->p());
234 m_v = m_params->mul(v, m_params->R2(), ws);
235 }
236}
237
238Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
239 const uint8_t bits[],
240 size_t len,
241 bool redc_needed) :
242 m_params(params), m_v(bits, len) {
243 if(redc_needed) {
244 BOTAN_ASSERT_NOMSG(m_v < m_params->p());
246 m_v = m_params->mul(m_v, m_params->R2(), ws);
247 }
248}
249
250Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
251 const word words[],
252 size_t len,
253 bool redc_needed) :
254 m_params(std::move(params)) {
255 m_v.set_words(words, len);
256
257 if(redc_needed) {
258 BOTAN_ASSERT_NOMSG(m_v < m_params->p());
260 m_v = m_params->mul(m_v, m_params->R2(), ws);
261 }
262}
263
265 const size_t p_words = m_params->p_words();
266
267 if(m_v.sig_words() > p_words) {
268 throw Internal_Error("Montgomery_Int::fix_size v too large");
269 }
270
271 m_v.grow_to(p_words);
272}
273
275 return m_v == other.m_v && m_params->p() == other.m_params->p();
276}
277
278std::vector<uint8_t> Montgomery_Int::serialize() const {
279 std::vector<uint8_t> v(size());
280 BigInt::encode_1363(v.data(), v.size(), value());
281 return v;
282}
283
284size_t Montgomery_Int::size() const {
285 return m_params->p().bytes();
286}
287
289 return m_v == m_params->R1();
290}
291
293 return m_v.is_zero();
294}
295
298 return m_params->redc(m_v, ws);
299}
300
303 BigInt z = m_v;
305 return Montgomery_Int(m_params, z, false);
306}
307
310 BigInt z = m_v;
311 z.mod_sub(other.m_v, m_params->p(), ws);
312 return Montgomery_Int(m_params, z, false);
313}
314
318}
319
322 return (*this);
323}
324
327 return this->sub(other, ws);
328}
329
331 m_v.mod_sub(other.m_v, m_params->p(), ws);
332 return (*this);
333}
334
337 return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
338}
339
341 return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
342}
343
345 m_params->mul_by(m_v, other.m_v, ws);
346 return (*this);
347}
348
350 m_params->mul_by(m_v, other, ws);
351 return (*this);
352}
353
356 return mul_by(other, ws);
357}
358
363
365 for(size_t i = 0; i != n; ++i) {
366 m_params->square_this(m_v, ws);
367 }
368 return (*this);
369}
370
372 m_params->square_this(m_v, ws);
373 return (*this);
374}
375
377 return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
378}
379
381 return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
382}
383
386 const BigInt iv = m_params->mul(m_params->inv_mod_p(m_v), m_params->R3(), ws);
387 return Montgomery_Int(m_params, iv, false);
388}
389
391 return Montgomery_Int(m_params, m_params->p()) - (*this);
392}
393
395 m_v.mod_mul(2, m_params->p(), ws);
396 return (*this);
397}
398
400 m_v.mod_mul(3, m_params->p(), ws);
401 return (*this);
402}
403
405 m_v.mod_mul(4, m_params->p(), ws);
406 return (*this);
407}
408
410 m_v.mod_mul(8, m_params->p(), ws);
411 return (*this);
412}
413
414} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:98
BigInt & mod_mul(uint8_t y, const BigInt &mod, secure_vector< word > &ws)
Definition big_ops2.cpp:119
size_t sig_words() const
Definition bigint.h:584
word * mutable_data()
Definition bigint.h:609
size_t size() const
Definition bigint.h:578
void grow_to(size_t n) const
Definition bigint.h:631
void set_words(const word w[], size_t len)
Definition bigint.h:522
BigInt & mod_add(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition big_ops2.cpp:45
const word * data() const
Definition bigint.h:615
word word_at(size_t n) const
Definition bigint.h:518
BigInt & mod_sub(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition big_ops2.cpp:90
bool is_even() const
Definition bigint.h:410
static BigInt power_of_2(size_t n)
Definition bigint.h:739
static secure_vector< uint8_t > encode_1363(const BigInt &n, size_t bytes)
Definition big_code.cpp:105
bool is_zero() const
Definition bigint.h:428
static BigInt with_capacity(size_t n)
Definition bigint.cpp:58
BigInt square(const BigInt &x) const
Definition reducer.h:43
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition reducer.h:30
BigInt reduce(const BigInt &x) const
Definition reducer.cpp:37
size_t size() const
Definition monty.cpp:284
Montgomery_Int & operator*=(const Montgomery_Int &other)
Definition monty.cpp:354
Montgomery_Int(std::shared_ptr< const Montgomery_Params > params)
Definition monty.h:26
bool operator==(const Montgomery_Int &other) const
Definition monty.cpp:274
bool is_one() const
Definition monty.cpp:288
Montgomery_Int & add(const Montgomery_Int &other, secure_vector< word > &ws)
Definition monty.cpp:320
Montgomery_Int & operator+=(const Montgomery_Int &other)
Definition monty.cpp:315
Montgomery_Int & operator-=(const Montgomery_Int &other)
Definition monty.cpp:325
Montgomery_Int square(secure_vector< word > &ws) const
Definition monty.cpp:376
Montgomery_Int cube(secure_vector< word > &ws) const
Definition monty.cpp:380
Definition monty.cpp:390
Montgomery_Int operator*(const Montgomery_Int &other) const
Definition monty.cpp:335
Montgomery_Int & mul_by_3(secure_vector< word > &ws)
Definition monty.cpp:399
Montgomery_Int & mul_by_8(secure_vector< word > &ws)
Definition monty.cpp:409
Montgomery_Int & mul_by_2(secure_vector< word > &ws)
Definition monty.cpp:394
Montgomery_Int & sub(const Montgomery_Int &other, secure_vector< word > &ws)
Definition monty.cpp:330
Montgomery_Int operator-(const Montgomery_Int &other) const
Definition monty.cpp:308
Montgomery_Int operator+(const Montgomery_Int &other) const
Definition monty.cpp:301
bool is_zero() const
Definition monty.cpp:292
BigInt value() const
Definition monty.cpp:296
Montgomery_Int & square_this_n_times(secure_vector< word > &ws, size_t n)
Definition monty.cpp:364
Montgomery_Int & mul_by_4(secure_vector< word > &ws)
Definition monty.cpp:404
Montgomery_Int & square_this(secure_vector< word > &ws)
Definition monty.cpp:371
Montgomery_Int multiplicative_inverse() const
Definition monty.cpp:384
Montgomery_Int mul(const Montgomery_Int &other, secure_vector< word > &ws) const
Definition monty.cpp:340
Montgomery_Int & mul_by(const Montgomery_Int &other, secure_vector< word > &ws)
Definition monty.cpp:344
std::vector< uint8_t > serialize() const
Definition monty.cpp:278
BigInt redc(const BigInt &x, secure_vector< word > &ws) const
Definition monty.cpp:56
void mul_by(BigInt &x, const secure_vector< word > &y, secure_vector< word > &ws) const
Definition monty.cpp:123
BigInt mul(const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition monty.cpp:71
BigInt sqr(const BigInt &x, secure_vector< word > &ws) const
Definition monty.cpp:185
BigInt inv_mod_p(const BigInt &x) const
Definition monty.cpp:51
Montgomery_Params(const BigInt &p, const Modular_Reducer &mod_p)
Definition monty.cpp:16
void square_this(BigInt &x, secure_vector< word > &ws) const
Definition monty.cpp:203
const BigInt & p() const
Definition monty.h:141
#define BOTAN_MP_WORD_BITS
Definition build.h:50
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
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
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
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:146
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition mod_inv.cpp:178