Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- Class List
- Class Index
- Class Hierarchy
- Class Members

Public Member Functions | List of all members
Botan::Montgomery_Params Class Referencefinal

`#include <monty.h>`

## Public Member Functions
BigInt | inv_mod_p (const BigInt &x) const
| Montgomery_Params (const BigInt &p, const Modular_Reducer &mod_p)
| Montgomery_Params (const BigInt &p)
BigInt | mul (const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
BigInt | mul (const BigInt &x, const secure_vector< word > &y, secure_vector< word > &ws) const
void | mul_by (BigInt &x, const secure_vector< word > &y, secure_vector< word > &ws) const
void | mul_by (BigInt &x, const BigInt &y, secure_vector< word > &ws) const
const BigInt & | p () const
word | p_dash () const
size_t | p_words () const
const BigInt & | R1 () const
const BigInt & | R2 () const
const BigInt & | R3 () const
BigInt | redc (const BigInt &x, secure_vector< word > &ws) const
BigInt | sqr (const BigInt &x, secure_vector< word > &ws) const
void | square_this (BigInt &x, secure_vector< word > &ws) const

## Detailed Description

Parameters for Montgomery Reduction

Definition at line 129 of file monty.h.

## Constructor & Destructor Documentation

Botan::Montgomery_Params::Montgomery_Params | ( | const BigInt & | p,
|  | const Modular_Reducer & | mod_p
| ) |  |

Initialize a set of Montgomery reduction parameters. These values can be shared by all values in a specific Montgomery domain.

Definition at line 13 of file monty.cpp.

References Botan::BigInt::is_even(), Botan::monty_inverse(), Botan::Modular_Reducer::multiply(), p(), Botan::BigInt::power_of_2(), Botan::Modular_Reducer::reduce(), Botan::BigInt::sig_words(), Botan::Modular_Reducer::square(), and Botan::BigInt::word_at().

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 }
Botan::BigInt::word_at
word word_at(size_t n) const
Definition: bigint.h:506
Botan::BigInt::sig_words
size_t sig_words() const
Definition: bigint.h:584
Botan::BigInt::is_even
bool is_even() const
Definition: bigint.h:401
Botan::Montgomery_Params::p
const BigInt & p() const
Definition: monty.h:144
Botan::BigInt::power_of_2
static BigInt power_of_2(size_t n)
Definition: bigint.h:751
Botan::BigInt::square
BigInt & square(secure_vector< word > &ws)
Definition: big_ops2.cpp:216
Botan::monty_inverse
word monty_inverse(word a)
Definition: numthry.cpp:419

Botan::Montgomery_Params::Montgomery_Params | ( | const BigInt & | p | ) |

Initialize a set of Montgomery reduction parameters. These values can be shared by all values in a specific Montgomery domain.

Definition at line 30 of file monty.cpp.

References Botan::BigInt::is_even(), Botan::BigInt::is_negative(), Botan::monty_inverse(), Botan::Modular_Reducer::multiply(), p(), Botan::BigInt::power_of_2(), Botan::Modular_Reducer::reduce(), Botan::BigInt::sig_words(), Botan::Modular_Reducer::square(), and Botan::BigInt::word_at().

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 }
Botan::BigInt::word_at
word word_at(size_t n) const
Definition: bigint.h:506
Botan::BigInt::sig_words
size_t sig_words() const
Definition: bigint.h:584
Botan::BigInt::is_even
bool is_even() const
Definition: bigint.h:401
Botan::Montgomery_Params::p
const BigInt & p() const
Definition: monty.h:144
Botan::BigInt::is_negative
bool is_negative() const
Definition: bigint.h:525
Botan::BigInt::power_of_2
static BigInt power_of_2(size_t n)
Definition: bigint.h:751
Botan::BigInt::square
BigInt & square(secure_vector< word > &ws)
Definition: big_ops2.cpp:216
Botan::monty_inverse
word monty_inverse(word a)
Definition: numthry.cpp:419

## Member Function Documentation

BigInt Botan::Montgomery_Params::inv_mod_p | ( | const BigInt & | x | ) | const

Definition at line 50 of file monty.cpp.

References Botan::ct_inverse_mod_odd_modulus(), and p().

51 {
52 return ct_inverse_mod_odd_modulus(x, p());
53 }
Botan::Montgomery_Params::p
const BigInt & p() const
Definition: monty.h:144
Botan::ct_inverse_mod_odd_modulus
BigInt ct_inverse_mod_odd_modulus(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:200

BigInt Botan::Montgomery_Params::mul | ( | const BigInt & | x,
|  | const BigInt & | y,
|  | secure_vector< word > & | ws
| ) |  | const

Definition at line 72 of file monty.cpp.

References Botan::bigint_monty_redc(), Botan::bigint_mul(), BOTAN_DEBUG_ASSERT, Botan::BigInt::data(), Botan::BigInt::Positive, Botan::BigInt::sig_words(), and Botan::BigInt::size().

74 {
75 const size_t output_size = 2*m_p_words + 2;
76
77 if(ws.size() < output_size)
78 ws.resize(output_size);
79
80 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
81 BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
82
83 BigInt z(BigInt::Positive, output_size);
84 bigint_mul(z.mutable_data(), z.size(),
85 x.data(), x.size(), std::min(m_p_words, x.size()),
86 y.data(), y.size(), std::min(m_p_words, y.size()),
87 ws.data(), ws.size());
88
89 bigint_monty_redc(z.mutable_data(),
90 m_p.data(), m_p_words, m_p_dash,
91 ws.data(), ws.size());
92
93 return z;
94 }
Botan::BigInt::Positive
Definition: bigint.h:35
BOTAN_DEBUG_ASSERT
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
Botan::BigInt::data
const word * data() const
Definition: bigint.h:618
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::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

BigInt Botan::Montgomery_Params::mul | ( | const BigInt & | x,
|  | const secure_vector< word > & | y,
|  | secure_vector< word > & | ws
| ) |  | const

Definition at line 96 of file monty.cpp.

References Botan::bigint_monty_redc(), Botan::bigint_mul(), BOTAN_DEBUG_ASSERT, Botan::BigInt::data(), Botan::BigInt::mutable_data(), Botan::BigInt::Positive, Botan::BigInt::sig_words(), and Botan::BigInt::size().

99 {
100 const size_t output_size = 2*m_p_words + 2;
101 if(ws.size() < output_size)
102 ws.resize(output_size);
103 BigInt z(BigInt::Positive, output_size);
104
105 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
106
107 bigint_mul(z.mutable_data(), z.size(),
108 x.data(), x.size(), std::min(m_p_words, x.size()),
109 y.data(), y.size(), std::min(m_p_words, y.size()),
110 ws.data(), ws.size());
111
112 bigint_monty_redc(z.mutable_data(),
113 m_p.data(), m_p_words, m_p_dash,
114 ws.data(), ws.size());
115
116 return z;
117 }
Botan::BigInt::Positive
Definition: bigint.h:35
BOTAN_DEBUG_ASSERT
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
Botan::BigInt::data
const word * data() const
Definition: bigint.h:618
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::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

void Botan::Montgomery_Params::mul_by | ( | BigInt & | x,
|  | const secure_vector< word > & | y,
|  | secure_vector< word > & | ws
| ) |  | const

Definition at line 119 of file monty.cpp.

References Botan::bigint_monty_redc(), Botan::bigint_mul(), BOTAN_DEBUG_ASSERT, Botan::copy_mem(), Botan::BigInt::data(), Botan::BigInt::grow_to(), Botan::BigInt::mutable_data(), Botan::BigInt::sig_words(), and Botan::BigInt::size().

122 {
123 const size_t output_size = 2*m_p_words + 2;
124
125 if(ws.size() < 2*output_size)
126 ws.resize(2*output_size);
127
128 word* z_data = &ws[0];
129 word* ws_data = &ws[output_size];
130
131 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
132
133 bigint_mul(z_data, output_size,
134 x.data(), x.size(), std::min(m_p_words, x.size()),
135 y.data(), y.size(), std::min(m_p_words, y.size()),
136 ws_data, output_size);
137
138 bigint_monty_redc(z_data,
139 m_p.data(), m_p_words, m_p_dash,
140 ws_data, output_size);
141
142 if(x.size() < output_size)
143 x.grow_to(output_size);
144 copy_mem(x.mutable_data(), z_data, output_size);
145 }
BOTAN_DEBUG_ASSERT
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
Botan::BigInt::data
const word * data() const
Definition: bigint.h:618
Botan::copy_mem
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:132
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::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

void Botan::Montgomery_Params::mul_by | ( | BigInt & | x,
|  | const BigInt & | y,
|  | secure_vector< word > & | ws
| ) |  | const

Definition at line 147 of file monty.cpp.

References Botan::bigint_monty_redc(), Botan::bigint_mul(), BOTAN_DEBUG_ASSERT, Botan::copy_mem(), Botan::BigInt::data(), Botan::BigInt::grow_to(), Botan::BigInt::mutable_data(), Botan::BigInt::sig_words(), and Botan::BigInt::size().

150 {
151 const size_t output_size = 2*m_p_words + 2;
152
153 if(ws.size() < 2*output_size)
154 ws.resize(2*output_size);
155
156 word* z_data = &ws[0];
157 word* ws_data = &ws[output_size];
158
159 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
160
161 bigint_mul(z_data, output_size,
162 x.data(), x.size(), std::min(m_p_words, x.size()),
163 y.data(), y.size(), std::min(m_p_words, y.size()),
164 ws_data, output_size);
165
166 bigint_monty_redc(z_data,
167 m_p.data(), m_p_words, m_p_dash,
168 ws_data, output_size);
169
170 if(x.size() < output_size)
171 x.grow_to(output_size);
172 copy_mem(x.mutable_data(), z_data, output_size);
173 }
BOTAN_DEBUG_ASSERT
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
Botan::BigInt::data
const word * data() const
Definition: bigint.h:618
Botan::copy_mem
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:132
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::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

const BigInt& Botan::Montgomery_Params::p | ( |  | ) | const
| inline

Definition at line 144 of file monty.h.

References m_p.

Referenced by inv_mod_p(), and Montgomery_Params().

144 { return m_p; }

word Botan::Montgomery_Params::p_dash | ( |  | ) | const
| inline

Definition at line 149 of file monty.h.

References m_p_dash.

149 { return m_p_dash; }

size_t Botan::Montgomery_Params::p_words | ( |  | ) | const
| inline

Definition at line 151 of file monty.h.

References m_p_words.

151 { return m_p_words; }

const BigInt& Botan::Montgomery_Params::R1 | ( |  | ) | const
| inline

Definition at line 145 of file monty.h.

145 { return m_r1; }

const BigInt& Botan::Montgomery_Params::R2 | ( |  | ) | const
| inline

Definition at line 146 of file monty.h.

References m_r2.

146 { return m_r2; }

const BigInt& Botan::Montgomery_Params::R3 | ( |  | ) | const
| inline

Definition at line 147 of file monty.h.

References m_r3.

147 { return m_r3; }

BigInt Botan::Montgomery_Params::redc | ( | const BigInt & | x,
|  | secure_vector< word > & | ws
| ) |  | const

Definition at line 55 of file monty.cpp.

References Botan::bigint_monty_redc(), Botan::BigInt::data(), Botan::BigInt::grow_to(), and Botan::BigInt::mutable_data().

56 {
57 const size_t output_size = 2*m_p_words + 2;
58
59 if(ws.size() < output_size)
60 ws.resize(output_size);
61
62 BigInt z = x;
63 z.grow_to(output_size);
64
65 bigint_monty_redc(z.mutable_data(),
66 m_p.data(), m_p_words, m_p_dash,
67 ws.data(), ws.size());
68
69 return z;
70 }
Botan::BigInt::data
const word * data() const
Definition: bigint.h:618
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

BigInt Botan::Montgomery_Params::sqr | ( | const BigInt & | x,
|  | secure_vector< word > & | ws
| ) |  | const

Definition at line 175 of file monty.cpp.

References Botan::bigint_monty_redc(), Botan::bigint_sqr(), BOTAN_DEBUG_ASSERT, Botan::BigInt::data(), Botan::BigInt::mutable_data(), Botan::BigInt::Positive, Botan::BigInt::sig_words(), and Botan::BigInt::size().

176 {
177 const size_t output_size = 2*m_p_words + 2;
178
179 if(ws.size() < output_size)
180 ws.resize(output_size);
181
182 BigInt z(BigInt::Positive, output_size);
183
184 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
185
186 bigint_sqr(z.mutable_data(), z.size(),
187 x.data(), x.size(), std::min(m_p_words, x.size()),
188 ws.data(), ws.size());
189
190 bigint_monty_redc(z.mutable_data(),
191 m_p.data(), m_p_words, m_p_dash,
192 ws.data(), ws.size());
193
194 return z;
195 }
Botan::BigInt::Positive
Definition: bigint.h:35
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_DEBUG_ASSERT
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
Botan::BigInt::data
const word * data() const
Definition: bigint.h:618
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

void Botan::Montgomery_Params::square_this | ( | BigInt & | x,
|  | secure_vector< word > & | ws
| ) |  | const

Definition at line 197 of file monty.cpp.

References Botan::bigint_monty_redc(), Botan::bigint_sqr(), BOTAN_DEBUG_ASSERT, Botan::copy_mem(), Botan::BigInt::data(), Botan::BigInt::grow_to(), Botan::BigInt::mutable_data(), Botan::BigInt::sig_words(), and Botan::BigInt::size().

199 {
200 const size_t output_size = 2*m_p_words + 2;
201
202 if(ws.size() < 2*output_size)
203 ws.resize(2*output_size);
204
205 word* z_data = &ws[0];
206 word* ws_data = &ws[output_size];
207
208 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
209
210 bigint_sqr(z_data, output_size,
211 x.data(), x.size(), std::min(m_p_words, x.size()),
212 ws_data, output_size);
213
214 bigint_monty_redc(z_data,
215 m_p.data(), m_p_words, m_p_dash,
216 ws_data, output_size);
217
218 if(x.size() < output_size)
219 x.grow_to(output_size);
220 copy_mem(x.mutable_data(), z_data, output_size);
221 }
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_DEBUG_ASSERT
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
Botan::BigInt::data
const word * data() const
Definition: bigint.h:618
Botan::copy_mem
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:132
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

The documentation for this class was generated from the following files:

- src/lib/math/numbertheory/monty.h
- src/lib/math/numbertheory/monty.cpp