Botan 3.7.1
Crypto and TLS for C&
monty.cpp
Go to the documentation of this file.
1/*
2* (C) 2018,2024 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#include <botan/internal/monty.h>
8
9#include <botan/numthry.h>
10#include <botan/reducer.h>
11#include <botan/internal/mp_core.h>
12
13#include <utility>
14
15namespace Botan {
16
18 if(p.is_even() || p < 3) {
19 throw Invalid_Argument("Montgomery_Params invalid modulus");
20 }
21
22 m_p = p;
23 m_p_words = m_p.sig_words();
24 m_p_dash = monty_inverse(m_p.word_at(0));
25
26 const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
27
28 m_r1 = mod_p.reduce(r);
29 m_r2 = mod_p.square(m_r1);
30 m_r3 = mod_p.multiply(m_r1, m_r2);
31}
32
34 if(p.is_even() || p < 3) {
35 throw Invalid_Argument("Montgomery_Params invalid modulus");
36 }
37
38 m_p = p;
39 m_p_words = m_p.sig_words();
40 m_p_dash = monty_inverse(m_p.word_at(0));
41
42 const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
43
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 const size_t output_size = m_p_words + 1;
53
54 if(ws.size() < output_size) {
55 ws.resize(output_size);
56 }
57
58 BigInt z = x;
59 z.grow_to(2 * m_p_words);
60
61 bigint_monty_redc(z.mutable_data(), m_p._data(), m_p_words, m_p_dash, ws.data(), ws.size());
62
63 return z;
64}
65
67 const size_t output_size = 2 * m_p_words;
68
69 if(ws.size() < output_size) {
70 ws.resize(output_size);
71 }
72
73 x.grow_to(output_size);
74
75 bigint_monty_redc(x.mutable_data(), m_p._data(), m_p_words, m_p_dash, ws.data(), ws.size());
76}
77
79 BigInt z = BigInt::with_capacity(2 * m_p_words);
80 this->mul(z, x, y, ws);
81 return z;
82}
83
84void Montgomery_Params::mul(BigInt& z, const BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
85 const size_t output_size = 2 * m_p_words;
86
87 if(ws.size() < output_size) {
88 ws.resize(output_size);
89 }
90
91 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
92 BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
93
94 if(z.size() < output_size) {
95 z.grow_to(output_size);
96 }
97
99 z.size(),
100 x._data(),
101 x.size(),
102 std::min(m_p_words, x.size()),
103 y._data(),
104 y.size(),
105 std::min(m_p_words, y.size()),
106 ws.data(),
107 ws.size());
108
109 bigint_monty_redc(z.mutable_data(), m_p._data(), m_p_words, m_p_dash, ws.data(), ws.size());
110}
111
112BigInt Montgomery_Params::mul(const BigInt& x, std::span<const word> y, secure_vector<word>& ws) const {
113 BigInt z = BigInt::with_capacity(2 * m_p_words);
114 this->mul(z, x, y, ws);
115 return z;
116}
117
118void Montgomery_Params::mul(BigInt& z, const BigInt& x, std::span<const word> y, secure_vector<word>& ws) const {
119 const size_t output_size = 2 * m_p_words;
120 if(ws.size() < output_size) {
121 ws.resize(output_size);
122 }
123 if(z.size() < output_size) {
124 z.grow_to(output_size);
125 }
126
127 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
128
130 z.size(),
131 x._data(),
132 x.size(),
133 std::min(m_p_words, x.size()),
134 y.data(),
135 y.size(),
136 std::min(m_p_words, y.size()),
137 ws.data(),
138 ws.size());
139
140 bigint_monty_redc(z.mutable_data(), m_p._data(), m_p_words, m_p_dash, ws.data(), ws.size());
141}
142
143void Montgomery_Params::mul_by(BigInt& x, std::span<const word> y, secure_vector<word>& ws) const {
144 const size_t output_size = 2 * m_p_words;
145
146 if(ws.size() < 2 * output_size) {
147 ws.resize(2 * output_size);
148 }
149
150 word* z_data = &ws[0];
151 word* ws_data = &ws[output_size];
152
153 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
154
155 bigint_mul(z_data,
156 output_size,
157 x._data(),
158 x.size(),
159 std::min(m_p_words, x.size()),
160 y.data(),
161 y.size(),
162 std::min(m_p_words, y.size()),
163 ws_data,
164 output_size);
165
166 bigint_monty_redc(z_data, m_p._data(), m_p_words, m_p_dash, ws_data, output_size);
167
168 if(x.size() < output_size) {
169 x.grow_to(output_size);
170 }
171 copy_mem(x.mutable_data(), z_data, output_size);
172}
173
175 const size_t output_size = 2 * m_p_words;
176
177 if(ws.size() < 2 * output_size) {
178 ws.resize(2 * output_size);
179 }
180
181 word* z_data = &ws[0];
182 word* ws_data = &ws[output_size];
183
184 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
185
186 bigint_mul(z_data,
187 output_size,
188 x._data(),
189 x.size(),
190 std::min(m_p_words, x.size()),
191 y._data(),
192 y.size(),
193 std::min(m_p_words, y.size()),
194 ws_data,
195 output_size);
196
197 bigint_monty_redc(z_data, m_p._data(), m_p_words, m_p_dash, ws_data, output_size);
198
199 if(x.size() < output_size) {
200 x.grow_to(output_size);
201 }
202 copy_mem(x.mutable_data(), z_data, output_size);
203}
204
206 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
207 return this->sqr(std::span{x._data(), x.size()}, ws);
208}
209
210BigInt Montgomery_Params::sqr(std::span<const word> x, secure_vector<word>& ws) const {
211 BigInt z = BigInt::with_capacity(2 * m_p_words);
212 this->sqr(z, x, ws);
213 return z;
214}
215
217 this->sqr(z, std::span{x._data(), x.size()}, ws);
218}
219
220void Montgomery_Params::sqr(BigInt& z, std::span<const word> x, secure_vector<word>& ws) const {
221 const size_t output_size = 2 * m_p_words;
222
223 if(ws.size() < output_size) {
224 ws.resize(output_size);
225 }
226
227 if(z.size() < output_size) {
228 z.grow_to(output_size);
229 }
230
231 bigint_sqr(z.mutable_data(), z.size(), x.data(), x.size(), std::min(m_p_words, x.size()), ws.data(), ws.size());
232
233 bigint_monty_redc(z.mutable_data(), m_p._data(), m_p_words, m_p_dash, ws.data(), ws.size());
234}
235
237 const size_t output_size = 2 * m_p_words;
238
239 if(ws.size() < 2 * output_size) {
240 ws.resize(2 * output_size);
241 }
242
243 word* z_data = &ws[0];
244 word* ws_data = &ws[output_size];
245
246 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
247
248 bigint_sqr(z_data, output_size, x._data(), x.size(), std::min(m_p_words, x.size()), ws_data, output_size);
249
250 bigint_monty_redc(z_data, m_p._data(), m_p_words, m_p_dash, ws_data, output_size);
251
252 if(x.size() < output_size) {
253 x.grow_to(output_size);
254 }
255 copy_mem(x.mutable_data(), z_data, output_size);
256}
257
258Montgomery_Int Montgomery_Int::one(const std::shared_ptr<const Montgomery_Params>& params) {
259 return Montgomery_Int(params, params->R1(), false);
260}
261
262Montgomery_Int Montgomery_Int::from_wide_int(const std::shared_ptr<const Montgomery_Params>& params, const BigInt& x) {
263 //BOTAN_ARG_CHECK(x < params->p() * params->p(), "Input too large");
264
266 auto redc_x = params->mul(params->redc(x, ws), params->R3(), ws);
267 return Montgomery_Int(params, redc_x, false);
268}
269
270Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
271 const BigInt& v,
272 bool redc_needed) :
273 m_params(params) {
274 if(redc_needed == false) {
275 m_v = v;
276 } else {
277 BOTAN_ASSERT_NOMSG(m_v < m_params->p());
279 m_v = m_params->mul(v, m_params->R2(), ws);
280 }
281}
282
283Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
284 const uint8_t bits[],
285 size_t len,
286 bool redc_needed) :
287 m_params(params), m_v(bits, len) {
288 if(redc_needed) {
289 BOTAN_ASSERT_NOMSG(m_v < m_params->p());
291 m_v = m_params->mul(m_v, m_params->R2(), ws);
292 }
293}
294
295Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
296 const word words[],
297 size_t len,
298 bool redc_needed) :
299 m_params(std::move(params)) {
300 m_v.set_words(words, len);
301
302 if(redc_needed) {
303 BOTAN_ASSERT_NOMSG(m_v < m_params->p());
305 m_v = m_params->mul(m_v, m_params->R2(), ws);
306 }
307}
308
310 const size_t p_words = m_params->p_words();
311 BOTAN_DEBUG_ASSERT(m_v.sig_words() <= p_words);
312 m_v.grow_to(p_words);
313}
314
316 return m_v == other.m_v && m_params->p() == other.m_params->p();
317}
318
319std::vector<uint8_t> Montgomery_Int::serialize() const {
320 return value().serialize();
321}
322
323size_t Montgomery_Int::size() const {
324 return m_params->p().bytes();
325}
326
328 return m_v == m_params->R1();
329}
330
332 return m_v.is_zero();
333}
334
337 return m_params->redc(m_v, ws);
338}
339
341 BOTAN_STATE_CHECK(other.m_params == m_params);
343 BigInt z = m_v;
344 z.mod_add(other.m_v, m_params->p(), ws);
345 return Montgomery_Int(m_params, z, false);
346}
347
349 BOTAN_STATE_CHECK(other.m_params == m_params);
351 BigInt z = m_v;
352 z.mod_sub(other.m_v, m_params->p(), ws);
353 return Montgomery_Int(m_params, z, false);
354}
355
357 BOTAN_STATE_CHECK(other.m_params == m_params);
359 return this->add(other, ws);
360}
361
363 BOTAN_STATE_CHECK(other.m_params == m_params);
364 m_v.mod_add(other.m_v, m_params->p(), ws);
365 return (*this);
366}
367
369 BOTAN_STATE_CHECK(other.m_params == m_params);
371 return this->sub(other, ws);
372}
373
375 BOTAN_STATE_CHECK(other.m_params == m_params);
376 m_v.mod_sub(other.m_v, m_params->p(), ws);
377 return (*this);
378}
379
381 BOTAN_STATE_CHECK(other.m_params == m_params);
383 return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
384}
385
387 BOTAN_STATE_CHECK(other.m_params == m_params);
388 return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
389}
390
392 BOTAN_STATE_CHECK(other.m_params == m_params);
393 m_params->mul_by(m_v, other.m_v, ws);
394 return (*this);
395}
396
398 m_params->mul_by(m_v, other, ws);
399 return (*this);
400}
401
403 BOTAN_STATE_CHECK(other.m_params == m_params);
405 return mul_by(other, ws);
406}
407
412
414 for(size_t i = 0; i != n; ++i) {
415 m_params->square_this(m_v, ws);
416 }
417 return (*this);
418}
419
421 m_params->square_this(m_v, ws);
422 return (*this);
423}
424
426 return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
427}
428
430 return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
431}
432
434 return Montgomery_Int(m_params, m_params->p()) - (*this);
435}
436
438 m_v.mod_mul(2, m_params->p(), ws);
439 return (*this);
440}
441
443 m_v.mod_mul(3, m_params->p(), ws);
444 return (*this);
445}
446
448 m_v.mod_mul(4, m_params->p(), ws);
449 return (*this);
450}
451
453 m_v.mod_mul(8, m_params->p(), ws);
454 return (*this);
455}
456
457} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:98
#define BOTAN_STATE_CHECK(expr)
Definition assert.h:41
BigInt & mod_mul(uint8_t y, const BigInt &mod, secure_vector< word > &ws)
Definition big_ops2.cpp:113
size_t sig_words() const
Definition bigint.h:616
word * mutable_data()
Definition bigint.h:641
size_t size() const
Definition bigint.h:610
void grow_to(size_t n) const
Definition bigint.h:667
void set_words(const word w[], size_t len)
Definition bigint.h:552
BigInt & mod_add(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition big_ops2.cpp:45
word word_at(size_t n) const
Definition bigint.h:548
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:440
static BigInt power_of_2(size_t n)
Definition bigint.h:830
const word * _data() const
Definition bigint.h:936
bool is_zero() const
Definition bigint.h:458
BigInt & square(secure_vector< word > &ws)
Definition big_ops2.cpp:177
T serialize(size_t len) const
Definition bigint.h:712
static BigInt with_capacity(size_t n)
Definition bigint.cpp:58
BigInt square(const BigInt &x) const
Definition reducer.cpp:61
static Modular_Reducer for_secret_modulus(const BigInt &m)
Definition reducer.cpp:32
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition reducer.h:32
BigInt reduce(const BigInt &x) const
Definition reducer.cpp:54
size_t size() const
Definition monty.cpp:323
Montgomery_Int & operator*=(const Montgomery_Int &other)
Definition monty.cpp:402
static Montgomery_Int one(const std::shared_ptr< const Montgomery_Params > &params)
Definition monty.cpp:258
Montgomery_Int(std::shared_ptr< const Montgomery_Params > params)
Definition monty.h:28
bool operator==(const Montgomery_Int &other) const
Definition monty.cpp:315
bool is_one() const
Definition monty.cpp:327
Montgomery_Int & add(const Montgomery_Int &other, secure_vector< word > &ws)
Definition monty.cpp:362
Montgomery_Int & operator+=(const Montgomery_Int &other)
Definition monty.cpp:356
Montgomery_Int & operator-=(const Montgomery_Int &other)
Definition monty.cpp:368
Montgomery_Int square(secure_vector< word > &ws) const
Definition monty.cpp:425
Montgomery_Int cube(secure_vector< word > &ws) const
Definition monty.cpp:429
Montgomery_Int additive_inverse() const
Definition monty.cpp:433
Montgomery_Int operator*(const Montgomery_Int &other) const
Definition monty.cpp:380
Montgomery_Int & mul_by_3(secure_vector< word > &ws)
Definition monty.cpp:442
Montgomery_Int & mul_by_8(secure_vector< word > &ws)
Definition monty.cpp:452
Montgomery_Int & mul_by_2(secure_vector< word > &ws)
Definition monty.cpp:437
Montgomery_Int & sub(const Montgomery_Int &other, secure_vector< word > &ws)
Definition monty.cpp:374
Montgomery_Int operator-(const Montgomery_Int &other) const
Definition monty.cpp:348
Montgomery_Int operator+(const Montgomery_Int &other) const
Definition monty.cpp:340
bool is_zero() const
Definition monty.cpp:331
BigInt value() const
Definition monty.cpp:335
Montgomery_Int & square_this_n_times(secure_vector< word > &ws, size_t n)
Definition monty.cpp:413
Montgomery_Int & mul_by_4(secure_vector< word > &ws)
Definition monty.cpp:447
Montgomery_Int & square_this(secure_vector< word > &ws)
Definition monty.cpp:420
static Montgomery_Int from_wide_int(const std::shared_ptr< const Montgomery_Params > &params, const BigInt &x)
Definition monty.cpp:262
Montgomery_Int mul(const Montgomery_Int &other, secure_vector< word > &ws) const
Definition monty.cpp:386
Montgomery_Int & mul_by(const Montgomery_Int &other, secure_vector< word > &ws)
Definition monty.cpp:391
std::vector< uint8_t > serialize() const
Definition monty.cpp:319
BigInt redc(const BigInt &x, secure_vector< word > &ws) const
Definition monty.cpp:51
BigInt sqr(const BigInt &x, secure_vector< word > &ws) const
Definition monty.cpp:205
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition monty.cpp:84
void redc_in_place(BigInt &x, secure_vector< word > &ws) const
Definition monty.cpp:66
Montgomery_Params(const BigInt &p, const Modular_Reducer &mod_p)
Definition monty.cpp:17
void mul_by(BigInt &x, std::span< const word > y, secure_vector< word > &ws) const
Definition monty.cpp:143
void square_this(BigInt &x, secure_vector< word > &ws) const
Definition monty.cpp:236
const BigInt & p() const
Definition monty.h:150
#define BOTAN_MP_WORD_BITS
Definition build.h:71
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:1003
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:788
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:147