Botan 2.19.5 Crypto and TLS for C&

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