Botan 3.7.1
Crypto and TLS for C&
Botan::Montgomery_Params Class Referencefinal

#include <monty.h>

Public Member Functions

 Montgomery_Params (const BigInt &p)
 
 Montgomery_Params (const BigInt &p, const Modular_Reducer &mod_p)
 
void mul (BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
 
void mul (BigInt &z, const BigInt &x, std::span< const word > y, secure_vector< word > &ws) const
 
BigInt mul (const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
 
BigInt mul (const BigInt &x, std::span< const word > y, secure_vector< word > &ws) const
 
void mul_by (BigInt &x, const BigInt &y, secure_vector< word > &ws) const
 
void mul_by (BigInt &x, std::span< const word > y, secure_vector< word > &ws) const
 
const BigIntp () const
 
word p_dash () const
 
size_t p_words () const
 
const BigIntR1 () const
 
const BigIntR2 () const
 
const BigIntR3 () const
 
BigInt redc (const BigInt &x, secure_vector< word > &ws) const
 
void redc_in_place (BigInt &x, secure_vector< word > &ws) const
 
void sqr (BigInt &z, const BigInt &x, secure_vector< word > &ws) const
 
void sqr (BigInt &z, std::span< const word > x, secure_vector< word > &ws) const
 
BigInt sqr (const BigInt &x, secure_vector< word > &ws) const
 
BigInt sqr (std::span< const word > 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 136 of file monty.h.

Constructor & Destructor Documentation

◆ Montgomery_Params() [1/2]

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 17 of file monty.cpp.

17 {
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}
size_t sig_words() const
Definition bigint.h:616
word word_at(size_t n) const
Definition bigint.h:548
bool is_even() const
Definition bigint.h:440
static BigInt power_of_2(size_t n)
Definition bigint.h:830
BigInt & square(secure_vector< word > &ws)
Definition big_ops2.cpp:177
const BigInt & p() const
Definition monty.h:150
#define BOTAN_MP_WORD_BITS
Definition build.h:71
constexpr auto monty_inverse(W a) -> W
Definition mp_core.h:788

References BOTAN_MP_WORD_BITS, 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().

◆ Montgomery_Params() [2/2]

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 33 of file monty.cpp.

33 {
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}
static Modular_Reducer for_secret_modulus(const BigInt &m)
Definition reducer.cpp:32

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

Member Function Documentation

◆ mul() [1/4]

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

Definition at line 84 of file monty.cpp.

84 {
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
98 bigint_mul(z.mutable_data(),
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}
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:98
const word * _data() const
Definition bigint.h:936
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_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

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

Referenced by mul(), and mul().

◆ mul() [2/4]

void Botan::Montgomery_Params::mul ( BigInt & z,
const BigInt & x,
std::span< const word > y,
secure_vector< word > & ws ) const

Definition at line 118 of file monty.cpp.

118 {
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
129 bigint_mul(z.mutable_data(),
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}

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

◆ mul() [3/4]

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

Definition at line 78 of file monty.cpp.

78 {
79 BigInt z = BigInt::with_capacity(2 * m_p_words);
80 this->mul(z, x, y, ws);
81 return z;
82}
static BigInt with_capacity(size_t n)
Definition bigint.cpp:58
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition monty.cpp:84

References mul(), and Botan::BigInt::with_capacity().

◆ mul() [4/4]

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

Definition at line 112 of file monty.cpp.

112 {
113 BigInt z = BigInt::with_capacity(2 * m_p_words);
114 this->mul(z, x, y, ws);
115 return z;
116}

References mul(), and Botan::BigInt::with_capacity().

◆ mul_by() [1/2]

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

Definition at line 174 of file monty.cpp.

174 {
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}
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:147

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

◆ mul_by() [2/2]

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

Definition at line 143 of file monty.cpp.

143 {
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}

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

◆ p()

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

Definition at line 150 of file monty.h.

150{ return m_p; }

Referenced by Montgomery_Params(), and Montgomery_Params().

◆ p_dash()

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

Definition at line 158 of file monty.h.

158{ return m_p_dash; }

◆ p_words()

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

Definition at line 160 of file monty.h.

160{ return m_p_words; }

◆ R1()

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

Definition at line 152 of file monty.h.

152{ return m_r1; }

◆ R2()

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

Definition at line 154 of file monty.h.

154{ return m_r2; }

◆ R3()

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

Definition at line 156 of file monty.h.

156{ return m_r3; }

◆ redc()

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

Definition at line 51 of file monty.cpp.

51 {
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}

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

◆ redc_in_place()

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

Definition at line 66 of file monty.cpp.

66 {
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}

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

◆ sqr() [1/4]

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

Definition at line 216 of file monty.cpp.

216 {
217 this->sqr(z, std::span{x._data(), x.size()}, ws);
218}
BigInt sqr(const BigInt &x, secure_vector< word > &ws) const
Definition monty.cpp:205

References Botan::BigInt::_data(), Botan::BigInt::size(), and sqr().

◆ sqr() [2/4]

void Botan::Montgomery_Params::sqr ( BigInt & z,
std::span< const word > x,
secure_vector< word > & ws ) const

Definition at line 220 of file monty.cpp.

220 {
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}
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

References Botan::BigInt::_data(), Botan::bigint_monty_redc(), Botan::bigint_sqr(), Botan::BigInt::grow_to(), Botan::BigInt::mutable_data(), and Botan::BigInt::size().

◆ sqr() [3/4]

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

Definition at line 205 of file monty.cpp.

205 {
206 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
207 return this->sqr(std::span{x._data(), x.size()}, ws);
208}

References Botan::BigInt::_data(), BOTAN_DEBUG_ASSERT, Botan::BigInt::sig_words(), Botan::BigInt::size(), and sqr().

Referenced by sqr(), sqr(), and sqr().

◆ sqr() [4/4]

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

Definition at line 210 of file monty.cpp.

210 {
211 BigInt z = BigInt::with_capacity(2 * m_p_words);
212 this->sqr(z, x, ws);
213 return z;
214}

References sqr(), and Botan::BigInt::with_capacity().

◆ square_this()

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

Definition at line 236 of file monty.cpp.

236 {
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}

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


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